Unit 8: Supervised Learning

I. Orientation — Learning from Labelled Data

Supervised learning is a branch of machine learning in which an algorithm learns a mapping from input features to known target values. In classification, the target is a discrete class—such as spam/not spam—and the trained model predicts the class of previously unseen observations.

• Training data: Each observation is represented by a feature vector (\mathbf{x}) and a label (y); a dataset is written as (D={(\mathbf{x}_i,yi)}{i=1}^{n}).
• Features: Inputs may be numerical, such as age, or categorical, such as product type; preprocessing can include scaling, encoding, and missing-value treatment.
• Target classes: Binary classification uses two labels, while multiclass classification uses three or more labels, such as low, medium, and high risk.
• Learning objective: The algorithm estimates a function (f) so that (\hat{y}=f(\mathbf{x})), where (\hat{y}) is the predicted label.
• Generalization: A useful model performs well on unseen data, not merely on the observations used for training.
• Core assumptions:
  • Training and future observations come from sufficiently similar distributions.
  • Labels are meaningful and reasonably accurate.
  • Features contain information relevant to the target.
• Evaluation convention: Training data fits the model, validation data supports model selection, and test data estimates final performance.

II. Classification Algorithms — Assigning Observations to Categories

A. Introduction to classification algorithms

Classification algorithms learn decision rules or class probabilities from labelled examples and use them to assign discrete labels.

• Classification output: A hard prediction returns a class label, whereas a probabilistic classifier may return (P(Y=c\mid\mathbf{x})) for each class (c).
• Decision rule: A common rule selects the class with the largest estimated conditional probability:

ŷ = argmax P(Y = c | x)
        c

• (\mathbf{x}): feature vector for an observation.
• (c): a possible class.
• (Y): target-class variable.
• (\hat{y}): predicted class.
  • Binary classification: Two possible outcomes are modelled, such as (Y\in{0,1}), where 1 might indicate fraud and 0 legitimate activity.
  • Multiclass classification: One label is selected from several mutually exclusive classes, such as three flower species.
  • Decision boundary: The boundary divides feature space into predicted classes; it may be linear, curved, probabilistic, or locally determined.
  • Major algorithm families:
• Instance-based: KNN predicts from nearby stored observations.
• Probabilistic: Naïve Bayes applies Bayes’ theorem to class probabilities.
• Other common families: Logistic regression, decision trees, support-vector machines, and neural networks learn different forms of decision boundaries.
  • Training pipeline: Clean the data, separate predictors from labels, split the observations, fit candidate models, tune hyperparameters, and evaluate on held-out data.
  • Generalization errors:
    1. Underfitting: A model is too simple to capture the class structure, producing high error even on training data.
    2. Overfitting: A model captures noise in training data, producing low training error but high unseen-data error.
  • Class imbalance: If 99% of transactions are legitimate, always predicting “legitimate” gives 99% accuracy but detects no fraud; class-sensitive metrics are therefore necessary.

B. Applications and limitations

Classification supports automated decisions, but performance depends on data quality, representativeness, and the cost of mistakes.

• Applications: Typical tasks include disease screening, document categorization, customer-churn prediction, image recognition, and credit-risk grouping.
• Data leakage: A feature containing information unavailable at prediction time—such as final treatment outcome in a diagnosis model—creates unrealistically high evaluation scores.
• Ethical limitation: Biased historical labels or unrepresentative samples can produce systematically unequal predictions across groups.
• Interpretability: Accuracy alone does not explain why a prediction occurred; high-stakes systems may require transparent features, probability calibration, and human review.

III. K-Nearest Neighbors — Classification by Local Similarity

A. KNN (k-nearest neighbors) algorithm

KNN is a non-parametric, instance-based algorithm that classifies an observation according to the labels of its (k) closest training examples.

• Core procedure:
  1. Choose (k), a positive integer.
  2. Compute the distance from the new observation to every training observation.
  3. Select the (k) observations with the smallest distances.
  4. Predict the majority class, optionally weighting nearer neighbors more heavily.
• Euclidean distance: For two observations (\mathbf{x}) and (\mathbf{z}) with (p) numerical features:

d(x, z) = √[Σ(xj − zj)²],  j = 1, 2, ..., p

• (d(\mathbf{x},\mathbf{z})): distance between the observations.
• (x_j,z_j): values of feature (j).
• (p): number of features.
  • Worked example: Suppose the three nearest labels to a new point are ({A,A,B}). With (k=3), majority voting predicts class (A).
  • Choice of (k):
    1. Small (k): Produces flexible, irregular boundaries and is sensitive to noise; (k=1) assigns the nearest observation’s label.
    2. Large (k): Produces smoother boundaries but may ignore small, meaningful local patterns.
  • Hyperparameter tuning: Cross-validation compares candidate values such as (k\in{1,3,5,7,9}); (k) must be selected without using the final test set.
  • Feature scaling: Standardization is important because a feature measured in thousands can dominate one measured between 0 and 1:

z = (x − μ) / σ

• (x): original value.
• (\mu): training-set mean.
• (\sigma): training-set standard deviation.
• (z): standardized value.
  • Tie handling: Odd (k) reduces binary-class ties; alternatives include distance-weighted voting or a fixed deterministic rule.

B. Applications and limitations

KNN is useful when nearby observations genuinely tend to share labels and the dataset is not prohibitively large.

• Advantages: Training is minimal, nonlinear boundaries arise naturally, and multiclass prediction requires no structural change.
• Computational limitation: Basic prediction compares each query with all (n) training observations, requiring roughly (O(np)) distance work per query.
• Curse of dimensionality: In high-dimensional spaces, distances become less informative and observations appear similarly far apart.
• Data sensitivity: Irrelevant features, outliers, imbalanced classes, and inconsistent scaling can distort neighborhood composition.

IV. Naïve Bayes — Probabilistic Classification with Conditional Independence

A. Naïve Bayes algorithm

Naïve Bayes applies Bayes’ theorem while assuming that features are conditionally independent once the class is known.

• Bayes’ theorem:

P(C | x) = P(x | C)P(C) / P(x)

• (C): candidate class.
• (\mathbf{x}): observed feature vector.
• (P(C)): prior probability of the class.
• (P(\mathbf{x}\mid C)): likelihood of the observed features.
• (P(C\mid\mathbf{x})): posterior class probability.
  • Naïve factorization: For features (x_1,\ldots,x_p), conditional independence gives:

P(C | x) ∝ P(C) Π P(xj | C),  j = 1, 2, ..., p

The denominator (P(\mathbf{x})) is identical for all candidate classes, so classification compares only the prior-likelihood products.

• Training estimates: The class prior is commonly estimated as (P(C=c)=n_c/n), where (n_c) is the number of training observations in class (c).
• Main variants:
  • Gaussian Naïve Bayes: Models each continuous feature within a class using a normal distribution.
  • Multinomial Naïve Bayes: Uses feature counts, making it suitable for word-frequency document representations.
  • Bernoulli Naïve Bayes: Uses binary features, such as whether a word is present.
• Worked example: If (P(\text{spam})=0.4), (P(\text{“offer”}\mid\text{spam})=0.6), and (P(\text{“win”}\mid\text{spam})=0.5), the unnormalized spam score is (0.4\times0.6\times0.5=0.12).
• Zero-frequency problem: An unseen feature-class combination can make the entire product zero; Laplace smoothing adds a small count, commonly 1, before estimating probabilities.
• Numerical stability: Implementations add logarithms rather than multiplying many small probabilities:

score(C) = log P(C) + Σ log P(xj | C)

B. Applications and limitations

Naïve Bayes is especially effective for sparse, high-dimensional data despite its simplifying independence assumption.

• Advantages: Training and prediction are fast, memory requirements are modest, and probability estimates can be produced directly.
• Applications: Common uses include spam filtering, sentiment analysis, topic classification, and basic medical classification.
• Independence limitation: Correlated features may effectively count the same evidence repeatedly; document words, for example, are rarely truly independent.
• Probability limitation: Class rankings may be effective even when posterior probabilities are poorly calibrated.

V. Model Assessment — Reliable Estimation of Predictive Performance

A. Cross-validation and metrics

Cross-validation estimates performance across repeated held-out subsets, while metrics quantify particular kinds of classification success or error.

• Holdout method: Data is split once into training and test sets; the test set must remain untouched during fitting and hyperparameter selection.
• (k)-fold cross-validation: Divide training data into (k) folds, train on (k-1) folds, validate on the remaining fold, and repeat until every fold has served as validation data.
• Mean cross-validation score:

CV = (1/k) Σ mj,  j = 1, 2, ..., k

• (k): number of folds.
• (m_j): metric obtained on fold (j).
• (CV): average estimated performance.
  • Stratified folds: Each fold approximately preserves class proportions, which is particularly important for imbalanced targets.
  • Confusion matrix components:
• TP: Positive cases predicted positive.
• TN: Negative cases predicted negative.
• FP: Negative cases incorrectly predicted positive.
• FN: Positive cases incorrectly predicted negative.
  • Accuracy: The overall proportion of correct predictions:

Accuracy = (TP + TN) / (TP + TN + FP + FN)

• Precision: The proportion of predicted positives that are truly positive:

Precision = TP / (TP + FP)

• Recall: The proportion of actual positives detected:

Recall = TP / (TP + FN)

• F1-score: The harmonic mean of precision and recall:

F1 = 2 × (Precision × Recall) / (Precision + Recall)

• Metric trade-off:
  1. Precision priority: Important when false positives are costly, such as incorrectly blocking legitimate transactions.
  2. Recall priority: Important when false negatives are costly, such as missing a dangerous condition during screening.
• ROC-AUC: The ROC curve plots true-positive rate against false-positive rate across thresholds; AUC summarizes the model’s ranking ability.
• Worked example: If (TP=40), (FP=10), and (FN=20), precision is (40/50=0.80), while recall is (40/60\approx0.67).
• Pipeline discipline: Scaling, feature selection, and imputation must be fitted separately inside each training fold to prevent validation-data leakage.

B. Applications and limitations

Evaluation procedures provide estimates rather than guarantees and must reflect the model’s real deployment conditions.

• Fold choice: Five-fold and ten-fold cross-validation are common compromises between computation and estimate stability.
• Temporal data: Random folds can leak future information into training; time-ordered validation trains on earlier observations and validates on later ones.
• Metric selection: The chosen metric should represent operational costs, class imbalance, and whether labels, rankings, or calibrated probabilities matter.
• Final evaluation: After model and hyperparameter selection, retrain on available training data and evaluate once on the untouched test set.