Classical ML

Information gain = H(parent) - Σ(|child|/|parent|)·H(child). Choose split maximizing information gain.

• Entropy: H = -Σ p_i log₂ p_i. Theoretically motivated (information theory). Slightly more expensive to compute.
• Gini impurity: G = Σ p_i(1-p_i) = 1 - Σ p_i². Faster to compute, similar results in practice. Default in sklearn.

In practice, the choice rarely matters. Use Gini for speed, Entropy for interpretability or when you want to match information-theoretic intuitions.

Stopping criteria: max depth, min samples per leaf, min information gain threshold.

Random Forest:

• Trees built in parallel, independently (bagging)
• Each tree sees a random subset of features + data (variance reduction)
• Final: majority vote / average
• Hard to overfit, great baseline, fast to train

Gradient Boosting (XGBoost/LightGBM):

• Trees built sequentially, each correcting previous residuals
• Optimizes arbitrary differentiable loss
• Usually better accuracy with tuning
• Slower, more sensitive to hyperparameters

Choose RF when: need fast training, good baseline, interpretability, parallel compute available, limited time to tune.

Choose GB when: need max tabular accuracy, have time to tune, gradient-based optimization needed (custom loss).

SVM decision boundary only requires dot products between samples: f(x) = Σ α_i y_i K(x_i, x). The kernel function K(x,z) = φ(x)·φ(z) computes a dot product in a higher-dimensional feature space φ without explicitly computing φ.

• RBF kernel: K(x,z) = exp(-||x-z||²/2σ²) - equivalent to infinite-dimensional feature space. Handles any continuous decision boundary.
• Polynomial: K(x,z) = (x·z + c)^d - polynomial features.
• Why it works: Mercer's theorem - any symmetric PSD function is a valid kernel, implicitly computing a dot product in some Hilbert space.

The trick: never explicitly compute high-dimensional φ(x). Map non-linearly separable data to separable space implicitly. O(n²) training (n = samples), not O(d²) where d could be infinite.

Convergence proof: each iteration (assign + update) either decreases or maintains within-cluster sum of squares (WCSS). WCSS is bounded below by 0. With finite cluster assignments (k^n possible partitions), must converge - but potentially to local minimum.

Initialization problem: random initialization often leads to poor local minima. Example: two clusters initialized inside one true cluster - convergence to wrong partition.

K-Means++:

• Choose first center uniformly at random
• Each subsequent center: sample with probability ∝ d(x, nearest center)²
• Centers start spread out → better initial partition
• Provably O(log k)-competitive with optimal solution

Also run multiple random restarts and take best WCSS.

LASSO (L1): minimize L + λ||w||₁. Gives sparse solutions (many weights → exactly 0).

Ridge (L2): minimize L + λ||w||₂². Shrinks weights smoothly, rarely zeros them out.

Geometric intuition: think of the unconstrained solution as a ball. L1 constraint set is a diamond (corners on axes). L2 constraint set is a sphere (no corners). The optimal point is where the loss surface first touches the constraint. Diamond corners are on axes → solution often lands on corner where some coordinates = 0. Sphere has no corners → rarely zeros out any coordinate.

When to use: LASSO for feature selection (sparse model); Ridge when all features matter; Elastic Net for both.

EM finds maximum likelihood parameters for models with latent (unobserved) variables.

Two steps:

• E-step: compute expected log-likelihood Q(θ|θ_old) = E_{Z|X,θ_old}[log P(X,Z|θ)]. Compute the "soft assignments" of data to components.
• M-step: θ_new = argmax Q(θ|θ_old). Maximize with these soft assignments fixed.

GMM example: Gaussian Mixture Models with K components.

• E-step: for each point, compute r_ik = P(component k | x_i, params) using Bayes' theorem
• M-step: update μ_k = Σ r_ikx_i/Σ r_ik, update Σ_k similarly

Guaranteed to increase (or maintain) likelihood at each step. Converges to local maximum. K-means is a hard-assignment special case of EM on GMMs.

As dimensions d increase, data becomes increasingly sparse. Volume of a unit ball vanishes relative to the unit cube. Most points cluster near the surface of the hypersphere rather than the interior.

• KNN breaks: in high dimensions, all points are approximately equidistant. "Nearest neighbor" loses meaning. Distances concentrate around the mean distance.
• More data needed: to maintain constant sample density, data requirements grow exponentially with d.
• Gaussian kernels vanish: K(x,z) = exp(-||x-z||²) → 0 for all pairs when d is large and data is sparse.

Mitigations: PCA / dimensionality reduction, feature selection, embeddings (neural nets learn low-dimensional representations), algorithms that exploit structure (trees).

• Precision = TP/(TP+FP) - "of what I flagged, how many were correct?" Prioritize when false positives are costly. e.g., spam filter - don't want to block legitimate email.
• Recall = TP/(TP+FN) - "of all positives, how many did I catch?" Prioritize when false negatives are costly. e.g., cancer detection - missing a positive is dangerous.
• F1 = 2·P·R/(P+R) - harmonic mean. Use when you need balance. Better than accuracy for imbalanced datasets (F1 ignores true negatives).
• F-beta: F_β = (1+β²)·P·R/(β²·P+R). β>1 weights recall more (β=2 for medical). β<1 weights precision more.

ROC-AUC: plots TPR (recall) vs FPR at each threshold. AUC = probability that a random positive is ranked higher than a random negative.

PR-AUC: plots Precision vs Recall. AUC = average precision across recall levels.

For imbalanced datasets: use PR-AUC.

Reason: ROC curve uses FPR = FP/(FP+TN). With many true negatives (imbalanced case), FPR stays small even with many false positives → ROC-AUC looks great even for poor models. PR-AUC doesn't include TN, so it's more sensitive to performance on the minority class.

Example: 1% positive rate. A classifier predicting all negative gets ROC-AUC ≈ 0.5 but PR-AUC ≈ 0.01.

• Paired t-test: test if mean difference in per-example correct predictions is significantly different from 0.
• McNemar's test: for classification - tests if you model makes systematically different errors on same test set.
• Bootstrap confidence intervals: resample test set 10,000 times with replacement, compute metric each time. 95% CI. Robust, assumption-free.
• 5x2 cross-validation test: 5 rounds of 2-fold CV, test statistic from fold differences. Recommended by Dietterich 1998.

Practical tip: always report CI alongside point estimates. A 0.5% accuracy gain with overlapping CIs is not meaningful.

k-fold CV: split data into k folds. Train on k-1 folds, evaluate on held-out fold. Repeat k times. Average k evaluation scores. Typical: k=5 or k=10.

Stratified k-fold: maintain class distribution in each fold. If dataset is 10% positive, each fold has ~10% positive.

Use stratified when:

• Imbalanced classes (without stratification, a fold might have 0% of the minority class)
• Small dataset where random splitting could create unrepresentative folds
• Classification tasks in general - stratified is almost always the correct default

LOOCV: k=n. Max training data per fold, but high variance and slow. Use only for very small datasets (<50 examples).

• MAE (Mean Absolute Error): average of |y - ŷ|. Robust to outliers. Interpretable (same units as target). Gradient undefined at 0 → slower convergence.
• MSE (Mean Squared Error): average of (y - ŷ)². Penalizes large errors heavily. Differentiable everywhere → smooth optimization. Sensitive to outliers.
• RMSE: √MSE. Same units as target. Easier to interpret than MSE but still sensitive to outliers.

When to use:

• Large errors are genuinely costly (stock prediction, delivery time with massive outlier) → MSE/RMSE (penalizes them heavily)
• Outliers are data quality noise → MAE (robust)
• Reporting to stakeholders → RMSE or MAE (interpretable units)
• Huber loss: MAE for large errors, MSE for small. Best of both worlds.

• Silhouette score: s = (b - a) / max(a, b) where a = mean intra-cluster distance, b = mean distance to nearest other cluster. Range [-1, 1], higher = better. Works for any distance metric.
• Davies-Bouldin index: ratio of within-cluster scatter to between-cluster separation. Lower = better.
• Calinski-Harabasz: between-cluster variance / within-cluster variance. Higher = denser, well-separated clusters.
• Elbow method: plot WCSS vs. k. Choose k where marginal improvement decreases (the "elbow"). Heuristic, not rigorous.

Most important: domain evaluation. Do clusters make business sense? Present cluster centers to domain experts. Quantitative metrics are necessary but not sufficient.

κ = (Po - Pe) / (1 - Pe) where Po = observed agreement, Pe = expected agreement by chance.

Range: κ=1 (perfect), κ=0 (no better than chance), κ<0 (worse than chance).

When better than accuracy:

• Class imbalance: 95% of labels are class A. A model always predicting class A gets 95% accuracy but κ ≈ 0. Accuracy is misleading; κ reveals the model does nothing useful.
• Inter-rater reliability: measuring how well two annotators (or human vs. model) agree, accounting for chance agreement
• Multi-class with imbalance: weighted kappa accounts for degree of disagreement (partially vs. completely wrong)

Interpretation: κ <0.2 = poor, 0.2-0.4 = fair, 0.4-0.6 = moderate, 0.6-0.8 = substantial, >0.8 = near-perfect.