Unit 3: SUPERVISED LEARNING: CLASSIFICATION

I. Orientation — Learning from labelled examples

Classification is a supervised learning task in which a model learns a mapping from input features to a categorical target. Training data contain labelled examples, while the trained model predicts the class of previously unseen observations, such as “spam” or “not spam.”

A. Defining principles and assumptions

• Input and target: Each observation is represented as (\mathbf{x}=(x_1,x_2,\ldots,x_p)), where (x_j) is a feature, and (y) is the class label.
• Decision function: A classifier estimates (f(\mathbf{x})=\hat{y}), or estimates class probabilities (P(y=k\mid\mathbf{x})).
• Training and testing: Data are divided into training data for fitting and test data for evaluating generalisation.
• Class boundaries: Classification methods construct boundaries separating classes in feature space; these may be linear, nonlinear, rule-based, or probability-based.
• Important assumptions: Results depend on representative data, relevant features, consistent labels, and a test set that reflects future cases.
• Evaluation convention: A prediction is not judged only by the number of correct answers; false positives, false negatives, probability quality, and class imbalance may also matter.

II. Lazy learning: Nearest neighbors — Instance-based classification

Lazy learning postpones generalisation until a prediction is requested. Instead of building an explicit model during training, the method stores training examples and compares a new observation with nearby labelled observations.

A. Lazy learning: Nearest neighbors

The nearest-neighbor method classifies an observation using the labels of its (k) most similar stored examples.

• Distance calculation: For numeric features, Euclidean distance is commonly used:

d(x, z) = sqrt(Σj (xj - zj)^2)

Here, (x) and (z) are observations and (j) indexes the features.

• Majority voting: For (k=5), a new point may be assigned class A when three of its five nearest neighbours are A and two are B.
• Choice of (k): Small (k), such as (k=1), follows local detail but can overfit; larger (k) smooths noise but can overlook minority patterns.
• Feature scaling: A feature measured from 0 to 10,000 can dominate one measured from 0 to 1. Standardisation, (z=(x-\mu)/\sigma), prevents this distortion.
• Weighted neighbours: A closer point can receive greater influence, for example (w_i=1/(d_i+\epsilon)), where (d_i) is distance and (\epsilon>0) avoids division by zero.
• Strength and limitation: Training is fast because storage is the main operation, but prediction can be slow for large datasets and sensitive to irrelevant features, missing values, and the distance metric.

III. Naïve Bayes — Probabilistic classification

Naïve Bayes applies Bayes’ theorem while assuming that features are conditionally independent given the class. Despite this simplifying assumption, it is effective for text classification and other high-dimensional problems.

A. Naïve Bayes

The classifier selects the class with the largest posterior probability:

P(Ck | x) = P(x | Ck) P(Ck) / P(x)

Here, (C_k) is class (k), (\mathbf{x}) is the feature vector, (P(C_k)) is the prior, and (P(\mathbf{x}\mid C_k)) is the likelihood.

• Conditional independence: The model approximates

P(x | Ck) = Πj P(xj | Ck)

Thus, word “free” and word “offer” are treated as independent once the class “spam” is known.

• Prediction rule: Since (P(\mathbf{x})) is the same for all classes, prediction uses (\arg\max_k P(C_k)\prod_jP(x_j\mid C_k)).
• Gaussian form: For continuous feature (x_j), Gaussian Naïve Bayes models each class-conditional feature using its class mean and variance.
• Multinomial form: In document classification, word counts are used. The probability of a word may be estimated with Laplace smoothing:

P(word | class) = (count(word, class) + α) /
                  (total words in class + αV)

Here, (\alpha>0) is the smoothing parameter and (V) is vocabulary size.

• Zero-frequency problem: Without smoothing, an unseen word gives probability zero and makes the entire product zero.
• Strength and limitation: Training and prediction are computationally efficient, but correlated features can violate independence and make probability estimates poorly calibrated.

IV. Divide and Conquer: Decision Trees and Rules — Hierarchical classification

Divide-and-conquer methods recursively split a dataset into smaller, more homogeneous groups. Decision trees express this process as a sequence of tests; rules express paths through the tree as IF–THEN statements.

A. Divide and Conquer: Decision Trees and Rules

A decision tree predicts by following feature tests from a root node to a leaf containing a class or class distribution.

• Recursive splitting: A node might test income > 50,000, dividing observations into two child nodes. Each child is split again until a stopping condition is reached.
• Information gain: For entropy (H(S)=-\sum_k p_k\log_2p_k), a split (A) has:

Gain(S, A) = H(S) - Σv (|Sv| / |S|) H(Sv)

Here, (S_v) is the subset produced by value (v), and (p_k) is the proportion of class (k).

• Gini impurity: Another criterion is (G(S)=1-\sum_kp_k^2). A pure node containing one class has Gini impurity 0.
• Rules: A path such as income > 50,000 AND debt < 10,000 becomes an interpretable rule predicting “approved.”
• Pruning: A deep tree may memorise training noise. Pre-pruning limits depth or minimum leaf size; post-pruning removes weak branches after growth.
• Categorical and numeric data: Trees can split categories directly or choose thresholds such as age ≤ thirty.
• Strength and limitation: Trees require little scaling and are interpretable, but unstable small data changes can produce a different tree and unpruned trees overfit.

V. Support vector machine — Maximum-margin classification

A support vector machine (SVM) constructs a separating boundary that maximises the margin between classes. The observations closest to the boundary, called support vectors, determine its position.

A. Support vector machine

For a linearly separable binary problem with labels (y_i\in{-1,+1}), the hard-margin SVM seeks:

minimise       1/2 ||w||^2
subject to     yi (w · xi + b) ≥ 1

Here, (w) defines the boundary, (b) is the intercept, and the margin width is (2/|w|).

• Maximum margin: A wider margin generally improves generalisation because the boundary is less sensitive to small feature perturbations.
• Soft margin: Real data overlap, so slack variables (\xi_i\ge0) allow violations:

minimise  1/2 ||w||^2 + C Σi ξi

The parameter (C) controls the trade-off between a wide margin and training errors.

• Support vectors: Points on or inside the margin affect the fitted boundary; distant points usually do not.
• Kernel trick: A kernel computes similarity in an implicit higher-dimensional space. The radial basis function kernel is

K(x, z) = exp(-γ ||x-z||^2)

where (\gamma) controls the influence range of each observation.

• Scaling requirement: Because distances and dot products determine the boundary, features should commonly be standardised.
• Strength and limitation: SVMs work well in high-dimensional spaces, but kernel and parameter selection can be expensive and the resulting model is less interpretable than a small tree.

VI. Classification evaluation — Measuring predictive quality

Evaluation compares predicted labels or probabilities with known outcomes. The appropriate metric depends on class balance, error costs, and whether probability ranking or calibrated probability values are important.

A. Confusion Matrix

A confusion matrix counts actual classes against predicted classes and forms the basis of most binary classification metrics.

• True positive (TP): A positive case correctly predicted positive, such as a disease case detected.
• True negative (TN): A negative case correctly predicted negative.
• False positive (FP): A negative case incorrectly predicted positive, such as a healthy patient flagged.
• False negative (FN): A positive case incorrectly predicted negative.
• Matrix structure: Rows commonly represent actual classes and columns predicted classes; the convention must be stated because some software reverses these axes.
• Concrete counts: If (TP=80), (TN=900), (FP=20), and (FN=10), all derived measures use these four counts.

B. Accuracy

Accuracy is the proportion of all predictions that are correct.

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

• Interpretation: With the counts above, accuracy is ((80+900)/1010\approx0.970), or 97.0%.
• Main limitation: In a dataset with 990 negatives and 10 positives, predicting every case as negative gives 99% accuracy but detects no positive cases.
• Use: Accuracy is suitable when classes are reasonably balanced and false positive and false negative errors have similar costs.

C. Logarithmic Loss

Logarithmic loss evaluates predicted probabilities and penalises confident incorrect predictions.

LogLoss = -(1/N) Σi [yi log(pi) + (1-yi) log(1-pi)]

Here, (N) is the number of cases, (y_i\in{0,1}) is the actual label, and (p_i) is the predicted probability of class 1.

• Probability sensitivity: For an actual positive, assigning (p=0.9) contributes approximately (-\log(0.9)=0.105); assigning (p=0.1) contributes approximately 2.303.
• Interpretation: Lower log loss is better because it rewards accurate, well-calibrated probabilities.
• Numerical convention: Probabilities are clipped away from exactly 0 and 1 in software to avoid undefined (\log(0)).

D. Area Under Curve

Area Under Curve (AUC) usually means the area under the receiver operating characteristic (ROC) curve, which plots true positive rate against false positive rate over all classification thresholds.

TPR = TP / (TP + FN)
FPR = FP / (FP + TN)

• Threshold independence: A classifier producing scores can be evaluated at thresholds from 0 to 1; each threshold supplies one ROC point.
• Ranking meaning: AUC is the probability that a randomly chosen positive receives a higher score than a randomly chosen negative.
• Scale: AUC (=0.5) represents random ranking; AUC (=1.0) represents perfect ranking. A value below 0.5 may indicate reversed scores.
• Limitation: ROC AUC can appear strong when negatives greatly outnumber positives; precision-recall analysis may better represent rare-positive performance.

E. Precision

Precision measures how many predicted positive cases are actually positive.

Precision = TP / (TP + FP)

• Example: With (TP=80) and (FP=20), precision is (80/100=0.80), or 80%.
• Operational meaning: Precision matters when false alarms are costly, such as unnecessary fraud investigations.
• Relationship: Precision is calculated among predicted positives, unlike recall, which is calculated among actual positives.

F. Recall

Recall, also called sensitivity or true positive rate, measures how many actual positive cases are detected.

Recall = TP / (TP + FN)

• Example: With (TP=80) and (FN=10), recall is (80/90\approx0.889), or 88.9%.
• Operational meaning: High recall is important when missing a positive case is dangerous, such as failing to identify a serious disease.
• Trade-off: Lowering the decision threshold usually increases recall but may also increase false positives and reduce precision.

G. F1 Score

The F1 score is the harmonic mean of precision and recall, giving a balanced measure when both are important.

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

• Example: Precision (=0.80) and recall (=0.889) produce (F1\approx0.842).
• Harmonic effect: A very low precision or recall strongly reduces F1; the score is not high merely because one component is high.
• Limitation: F1 ignores true negatives and does not incorporate the quality of predicted probabilities, so it should accompany the confusion matrix and, where relevant, log loss or AUC.