Unit 8: Supervised Learning - Subjective Questions

Supervised learning is a machine learning approach in which a model learns a relationship between input features and known output labels from a labeled training dataset.

A training dataset can be represented as:

where is the feature vector and is its known label.

In classification, the target variable belongs to a finite set of categories. Labeled data enables the algorithm to:

• Identify patterns associated with each class.
• Learn a decision rule that predicts a class label.
• Compare predictions with correct labels during training.
• Estimate performance on unseen labeled examples.

For example, an email classifier may learn from messages labeled spam or not spam and then classify new messages.

A supervised classification workflow generally includes the following steps:

1. Define the problem: Identify the input features and target classes.
2. Collect labeled data: Obtain representative observations with known class labels.
3. Preprocess the data: Handle missing values, encode categorical variables, remove errors, and scale features when required.
4. Split the dataset: Create training, validation, and test sets, or use cross-validation.
5. Select an algorithm: Examples include KNN and Naive Bayes.
6. Train the model: Learn patterns from the training data.
7. Tune hyperparameters: Select settings such as the value of in KNN.
8. Evaluate performance: Use a confusion matrix and metrics such as accuracy, precision, recall, and -score.
9. Test the final model: Evaluate once on unseen test data.
10. Deploy and monitor: Track performance and retrain when the data distribution changes.

Data preprocessing and parameter selection must be learned from training data only to avoid data leakage.

Classification and regression are both supervised learning tasks, but they predict different types of outputs.

• Classification: Predicts a discrete category or class label. Examples include predicting whether a transaction is fraudulent or assigning an image to the classes cat, dog, or bird.
• Regression: Predicts a continuous numerical value. Examples include predicting house prices, temperature, or monthly sales.

If represents the input features, classification learns a mapping such as:

whereas regression learns:

Classification is commonly evaluated using accuracy, precision, recall, and -score. Regression typically uses metrics such as mean absolute error and mean squared error.

K-nearest neighbors (KNN) is a non-parametric, instance-based classification algorithm. It does not construct an explicit model during training; instead, it stores the labeled training observations.

To classify a new observation :

1. Select a value for .
2. Calculate the distance between and every training observation.
3. Identify the observations with the smallest distances.
4. Count the class labels of these neighbors.
5. Assign the class with the majority vote.

The prediction can be expressed as:

where is the set of the nearest neighbors of .

KNN is simple and can model nonlinear class boundaries, but prediction can be slow for large datasets because distances must be computed at prediction time.

For two observations with numerical features,

Euclidean distance follows from the Pythagorean theorem:

For and :

Thus, the Euclidean distance is 5 units. In KNN, the same calculation is performed between a query observation and every training observation, after which the smallest distances are selected.

The hyperparameter controls how many neighboring observations participate in a KNN prediction.

• Small : The model has a flexible and irregular decision boundary. For example, can fit noise and outliers, resulting in low bias, high variance, and possible overfitting.
• Large : The model averages over a wider region. This produces a smoother boundary but may hide local patterns, resulting in high bias, low variance, and possible underfitting.
• Even values: In binary classification, an even may produce tied votes, so an odd value is often convenient.

A suitable value should be selected using a validation set or, preferably, cross-validation:

1. Define several candidate values of .
2. evaluate each candidate across the same folds.
3. Calculate the mean validation score.
4. Choose the value with the strongest suitable metric.
5. Refit the model using the selected .

The test set must not be used to select , because doing so would produce an optimistically biased performance estimate.

KNN bases its predictions on distance. If features use very different numerical scales, a large-scale feature can dominate the distance even when it is not more informative.

For example, suppose a dataset contains:

• Age measured from approximately to .
• Annual income measured from approximately to .

Without scaling, income differences contribute much more to Euclidean distance than age differences. Consequently, the selected neighbors may be determined almost entirely by income.

Two common methods are:

• Min-max normalization:

• Standardization:

Scaling parameters must be estimated from the training data and then applied unchanged to validation and test data. This prevents data leakage.

For observations and with features, Euclidean distance is:

Manhattan distance is:

Key differences include:

• Euclidean distance measures straight-line distance and squares feature differences, making large differences more influential.
• Manhattan distance measures distance along coordinate axes and grows linearly with each difference.
• Euclidean distance is often suitable for continuous, scaled features when geometric closeness is meaningful.
• Manhattan distance can be preferable for grid-like movement, sparse data, or situations where reduced sensitivity to large individual differences is desirable.

The best metric depends on the data distribution and should normally be selected through domain knowledge and cross-validation. Feature scaling remains important for both metrics.

Advantages of KNN:

• It is simple to understand and implement.
• It makes few assumptions about the underlying data distribution.
• It can represent nonlinear and irregular decision boundaries.
• Training is inexpensive because observations are mainly stored.
• It naturally supports multiclass classification.

Limitations of KNN:

• Prediction can be computationally expensive for large training sets.
• It requires memory to store the training data.
• Results are sensitive to feature scale and the selected distance metric.
• Noise, outliers, irrelevant features, and class imbalance can distort voting.
• Performance often deteriorates in high-dimensional spaces because distances become less informative; this is part of the curse of dimensionality.
• Selecting and other settings requires validation.

Weighted voting, feature selection, dimensionality reduction, scaling, and efficient neighbor-search structures can reduce some of these limitations.

Ordinary KNN gives every selected neighbor an equal vote. Weighted KNN gives greater influence to neighbors that are closer to the query observation.

A common inverse-distance weight is:

where is the distance between the query and neighbor , while prevents division by zero.

For a class , the weighted vote is:

The predicted class is the class with the largest score .

Weighted KNN may perform better because a very close observation is often more relevant than a neighbor near the edge of the selected neighborhood. It can also reduce the effect of distant observations belonging to another class. However, it remains sensitive to scaling, noisy nearby points, and the choice of weighting function.

Bayes' theorem relates a posterior probability to a prior probability and a likelihood:

where:

• is the posterior probability of class after observing features .
• is the likelihood of observing in class .
• is the prior probability of class .
• is the evidence.

Naive Bayes calculates the posterior score for each possible class and predicts the class with the largest value. Since is the same for all candidate classes, classification uses:

The algorithm becomes computationally practical by assuming that features are conditionally independent given the class.

Bayes' theorem gives the posterior probability of class as:

The Naive Bayes assumption states that features are conditionally independent after the class is known. Therefore:

Substituting this result into Bayes' theorem gives:

Because is identical for all candidate classes, it does not affect which class maximizes the score. The decision rule is therefore:

To avoid numerical underflow caused by multiplying many small probabilities, implementations commonly use logarithms:

Naive Bayes assumes that all input features are conditionally independent given the class. For two features and , this means:

For features, the joint likelihood becomes:

The assumption is called naive because real-world features are frequently correlated. For example, the words good and excellent may be related in a sentiment-analysis dataset.

Naive Bayes may nevertheless classify well because:

• Exact probability estimates are not always necessary to rank classes correctly.
• The independence assumption greatly reduces the number of parameters that must be estimated.
• Reliable estimates can be obtained even from relatively small datasets.
• Irrelevant dependencies may affect multiple classes similarly without changing the final maximum score.

However, strongly correlated or duplicated features can effectively be counted multiple times and may reduce performance.

The three variants use different models for feature likelihoods:

• Gaussian Naive Bayes: Suitable for continuous numerical features. It assumes each feature within a class follows a Gaussian distribution:

• Multinomial Naive Bayes: Suitable for nonnegative counts or frequencies, such as word counts in documents. It is widely used for text categorization.
• Bernoulli Naive Bayes: Suitable for binary features, such as whether a word is present or absent in a document.

Thus, Gaussian Naive Bayes models continuous measurements, Multinomial Naive Bayes models occurrence counts, and Bernoulli Naive Bayes models binary events. Selecting a variant whose likelihood assumptions match the feature representation is important for good performance.

The zero-frequency problem occurs when a feature value never appears with a particular class in the training data. Its estimated conditional probability is then zero. Because Naive Bayes multiplies feature probabilities, one zero makes the entire class score zero:

For a categorical feature with possible values, Laplace smoothing estimates the probability as:

where:

• is the count of value in class .
• is the relevant total count for class .
• is the number of possible feature values.
• is the smoothing parameter, commonly .

Adding ensures that unseen values receive a small nonzero probability. This prevents a single unseen event from eliminating an otherwise plausible class.

KNN and Naive Bayes differ in several important ways:

• Learning approach: KNN is instance-based and stores training examples. Naive Bayes estimates class priors and feature likelihoods.
• Training cost: KNN has minimal training cost, whereas Naive Bayes must calculate probability parameters.
• Prediction cost: KNN can be slow because it computes distances to training observations. Naive Bayes prediction is generally fast.
• Assumptions: KNN makes few distributional assumptions but relies on a meaningful distance measure. Naive Bayes assumes conditional feature independence and a likelihood model suited to the features.
• Preprocessing: KNN usually requires feature scaling. Naive Bayes does not use geometric distances, although its features must match the selected variant.
• Storage: KNN normally retains the full training set. Naive Bayes stores a comparatively small set of parameters.
• Applications: KNN is useful for local pattern recognition, while Naive Bayes is especially common in document, spam, and sentiment classification.

Neither algorithm is universally superior; cross-validation can compare them on the target dataset.

In -fold cross-validation, the available training data is divided into approximately equal subsets called folds.

The procedure is:

1. Use one fold as validation data.
2. Train the model on the remaining folds.
3. Evaluate the model on the held-out fold.
4. Repeat until every fold has served as validation data once.
5. Average the fold scores.

If the score from fold is , the cross-validation estimate is:

Cross-validation uses the available data more efficiently than a single validation split and reveals how performance varies across subsets. Stratified -fold cross-validation is usually preferred for classification because it approximately preserves class proportions in every fold. All preprocessing steps must be fitted separately inside each training fold to prevent data leakage.

• Holdout validation: Divides data once into training and validation subsets. It is simple and fast, but the estimated performance can depend heavily on one random split.
• -fold cross-validation: Divides data into folds and validates on each fold once. It provides a more stable estimate than a single split but requires fitting the model times.
• Leave-one-out cross-validation (LOOCV): Uses one observation for validation and all remaining observations for training, repeating this process for every observation. For observations, LOOCV is equivalent to .

Trade-offs:

• Holdout is computationally cheapest but usually has greater split-related uncertainty.
• Moderate -fold cross-validation, commonly using or folds, balances computation and reliable evaluation.
• LOOCV uses nearly all data for every training run but can be computationally expensive and may have high variance across its highly similar training sets.

A separate untouched test set is still recommended for the final assessment after model selection.

A binary confusion matrix contains:

• True positive (): Positive observations correctly predicted as positive.
• True negative (): Negative observations correctly predicted as negative.
• False positive (): Negative observations incorrectly predicted as positive.
• False negative (): Positive observations incorrectly predicted as negative.

The main metrics are:

The -score is the harmonic mean of precision and recall:

Accuracy measures overall correctness, precision measures the reliability of positive predictions, recall measures the proportion of actual positives detected, specificity measures the proportion of actual negatives detected, and balances precision with recall.

Accuracy can be misleading when one class is much more common than another. For example, if only of transactions are fraudulent, a classifier that always predicts non-fraud achieves accuracy but detects no fraud.

More informative measures include:

• Precision: Of all predicted positives, how many are actually positive? It is important when false positives are costly.
• Recall: Of all actual positives, how many are detected? It is important when false negatives are costly.
• -score: Uses the harmonic mean to balance precision and recall.
• ROC curve: Plots true-positive rate against false-positive rate across classification thresholds.
• ROC-AUC: Measures how well the model ranks a randomly selected positive observation above a randomly selected negative observation. A value near indicates strong ranking, while corresponds to random ranking.

For highly imbalanced problems, the precision-recall curve and its area can be more revealing than ROC-AUC. Metric selection should reflect the real cost of each type of error.