Unit 5: Machine learning-2

Machine learning-2 extends the supervised/unsupervised toolkit beyond linear regression into margin-based classifiers, rule-based trees, grouping algorithms, and the metrics that decide whether any of them is trustworthy. The unifying question is generalisation: fitting patterns in training data that survive on unseen data.

• Supervised learning: learns a mapping f: X → y from labelled pairs; SVM and decision trees fall here.
• Unsupervised learning: finds structure in X with no labels; clustering falls here.
• Feature space: each sample is a vector x ∈ ℝ^d; algorithms carve or group this space.
• Bias–variance trade-off: high bias underfits (too simple), high variance overfits (too flexible); every method below is tuned against this axis.
• Generalisation: performance measured on held-out data, not training loss — the concern of model evaluation.

II. Support Vector Machine

A maximum-margin classifier that separates classes with the widest possible gap.

A. Principle and formulation

SVM finds the hyperplane that maximises the distance to the nearest points of each class.

• Decision boundary: the hyperplane wᵀx + b = 0, where w is the normal vector and b the bias/offset.
• Classification rule: predict sign(wᵀx + b); label +1 if positive, −1 if negative.
• Margin: the perpendicular distance between the two class boundaries, equal to 2/‖w‖; maximising it means minimising ‖w‖.
• Support vectors: the training points lying exactly on the margin (|wᵀx + b| = 1); only these determine w, so the model is sparse.

minimise   (1/2)‖w‖²
subject to yᵢ(wᵀxᵢ + b) ≥ 1   for all i

Here yᵢ ∈ {−1, +1} is the true label and the constraint forces every point onto the correct side of its margin.

B. Soft margin and the kernel trick

Real data overlaps and is rarely linearly separable, so SVM relaxes the hard margin and lifts data into higher dimensions.

• Slack variables ξᵢ: allow violations; the objective becomes (1/2)‖w‖² + C·Σξᵢ.
• Regularisation C: large C penalises misclassification heavily (low bias, high variance); small C tolerates errors for a wider margin.
• Kernel trick: replaces dot products xᵢᵀxⱼ with K(xᵢ, xⱼ), computing similarity in a higher-dimensional space without explicit mapping.
  • Linear kernel: K = xᵢᵀxⱼ — for linearly separable data.
  • RBF (Gaussian) kernel: K = exp(−γ‖xᵢ − xⱼ‖²); γ controls influence radius of a single point.
  • Polynomial kernel: K = (xᵢᵀxⱼ + c)^d.

C. Strengths and limitations

• Effective in high dimensions: works well when d exceeds the number of samples, e.g. text or gene data.
• Memory-efficient: stores only support vectors, not the full training set.
• Limitation — scaling: training is roughly O(n²)–O(n³), poor for very large n.
• Limitation — interpretability: kernelised boundaries are opaque, and probabilities require extra calibration.

III. Decision Trees

A recursive partitioning of feature space into axis-aligned regions labelled by class or value.

A. Structure and splitting

A tree asks a sequence of feature tests, routing a sample from root to leaf.

• Node types: the root holds all data; internal nodes test one feature (x_j ≤ t); leaves assign the prediction.
• Greedy induction: at each node choose the split that best reduces impurity, then recurse — no backtracking.
• Gini impurity: Gini = 1 − Σ pₖ², where pₖ is the fraction of class k at the node; 0 means pure.
• Entropy and information gain: Entropy = −Σ pₖ log₂ pₖ; gain = parent entropy minus weighted child entropy, and the split maximising gain is chosen.

Worked example: a node with 10 samples split 6 positive / 4 negative has Gini = 1 − (0.6² + 0.4²) = 1 − 0.52 = 0.48. A split producing two pure leaves drops Gini to 0, a gain of 0.48.

B. Overfitting and pruning

Unrestricted trees memorise training noise, so growth must be controlled.

• Overfitting symptom: a fully grown tree reaches near-zero training error but high test error (high variance).
• Pre-pruning: stop early via max_depth, min_samples_split, or a minimum impurity decrease.
• Post-pruning: grow fully, then collapse nodes that fail to improve validation accuracy (cost-complexity pruning trades size against error via parameter α).
• Ensembles as remedy:
  • Random Forest: averages many trees on bootstrapped samples and random feature subsets to cut variance.
  • Boosting: grows trees sequentially, each correcting the previous residuals.

C. Interpretability and limitations

• White-box model: the decision path is a readable set of if–then rules, valued in regulated domains.
• Handles mixed data: numeric and categorical features, no scaling required.
• Limitation — instability: small data changes can restructure the whole tree.
• Limitation — axis-aligned bias: diagonal boundaries need many splits to approximate.

IV. Clustering

Unsupervised grouping of samples so intra-group similarity is high and inter-group similarity low.

A. Purpose and distance

Clustering discovers structure without labels, using a distance measure to define similarity.

• Objective: partition or group X into clusters that are internally cohesive and mutually separated.
• Euclidean distance: d(x, y) = √(Σ (xⱼ − yⱼ)²) — the default metric; sensitive to feature scale, so standardisation matters.
• Manhattan / cosine: alternatives for grid-like or direction-based similarity respectively.

B. K-means clustering

Partitions data into a preset number K of clusters by minimising within-cluster variance.

• Objective function: minimise Σₖ Σ_{x∈Cₖ} ‖x − μₖ‖², where μₖ is the centroid of cluster Cₖ.
• Algorithm (Lloyd's):
  
  TEXT

  1. Initialise K centroids (e.g. k-means++)
  2. Assign each point to nearest centroid
  3. Recompute each centroid as the mean of its points
  4. Repeat 2–3 until assignments stop changing

• Choosing K — elbow method: plot within-cluster sum of squares against K; the "elbow" bend suggests a good K.
• Limitations: assumes spherical, equally sized clusters; sensitive to initialisation and outliers.

C. Hierarchical and density-based clustering

When K is unknown or clusters are irregular, other paradigms apply.

1. Hierarchical (agglomerative): starts with each point as its own cluster and merges the closest pair repeatedly, producing a dendrogram cut at a chosen height. Linkage — single (nearest points), complete (farthest), average — controls cluster shape. No K needed in advance.
2. DBSCAN (density-based): grows clusters from dense regions using radius ε and minPts; points in sparse zones are labelled noise. Finds arbitrary shapes and outliers but struggles with varying density.

V. Model Evaluation

Quantifying how well a model generalises, and comparing candidates fairly.

A. Data splitting and cross-validation

Evaluation must use data the model never trained on.

• Train/validation/test split: train fits parameters, validation tunes hyperparameters, test gives the final unbiased estimate.
• k-fold cross-validation: partition data into k folds, train on k−1 and test on the remainder, rotating; average the k scores for a stable estimate.
• Overfitting vs underfitting signal: large train–validation gap indicates overfitting; poor scores on both indicate underfitting.

B. Classification metrics

Accuracy alone misleads on imbalanced data, so a confusion matrix underpins richer metrics.

• Confusion matrix: counts of TP, TN, FP, FN (true/false positives/negatives).
• Accuracy: (TP + TN) / total — fraction correct; unreliable when classes are skewed.
• Precision: TP / (TP + FP) — of predicted positives, how many are correct.
• Recall (sensitivity): TP / (TP + FN) — of actual positives, how many were caught.
• F1-score: 2·(precision·recall)/(precision + recall) — harmonic mean balancing the two.
• ROC–AUC: the curve of true-positive rate against false-positive rate across thresholds; AUC near 1.0 is strong, 0.5 is random.

C. Regression metrics

Continuous targets are scored by the size of residuals.

• MAE: (1/n) Σ |yᵢ − ŷᵢ| — mean absolute error, in the target's own units, robust to outliers.
• RMSE: √((1/n) Σ (yᵢ − ŷᵢ)²) — penalises large errors more heavily via squaring.
• R² (coefficient of determination): 1 − (SS_res / SS_tot) — fraction of variance explained; 1 is perfect, 0 matches predicting the mean.
• Interpretation: report RMSE with a baseline; a low RMSE is only meaningful relative to the target's scale and a naive predictor.