Classical ML algorithms

XGBoost approximates the loss at each boosting round using both the gradient (first derivative) and the Hessian (second derivative) of the loss w.r.t. the current predictions. The optimal leaf weight becomes -G/(H+lambda) and the split gain uses both G and H, giving a Newton-like step that converges faster and supports arbitrary twice-differentiable losses. This is why XGBoost is often called a Newton boosting method rather than pure gradient boosting.

Bagging averages many high-variance, low-bias base learners (e.g., deep trees) trained on bootstrap samples, which shrinks variance without materially changing bias. Boosting sequentially fits weak, high-bias learners to the residuals/gradient of the ensemble, progressively reducing bias (and can also reduce variance via shrinkage). Thus bagging targets variance and boosting primarily targets bias.

L1 produces sparse solutions, driving some coefficients exactly to zero, which performs implicit feature selection; its constraint region has corners that the loss contour tends to touch. L2 shrinks coefficients smoothly toward zero but rarely exactly to zero, distributing weight among correlated features. Hence Lasso is preferred for sparsity/selection and Ridge for stability under multicollinearity.

The kernel trick lets the SVM compute inner products in a high- (possibly infinite-) dimensional feature space via a kernel function K(x,x') without ever materializing the mapped feature vectors phi(x). This makes nonlinear decision boundaries tractable, since the dual formulation depends only on dot products. The RBF kernel, for example, corresponds to an infinite-dimensional feature space.

kNN and SVMs rely on distance or dot-product computations, so features with larger numeric ranges dominate unless standardized. Decision trees split on thresholds per individual feature and are invariant to monotonic rescaling of any single feature, so scaling has no effect on their splits. Therefore scaling is essential for distance/margin-based methods but irrelevant for trees.

The naive assumption is conditional independence of features given the class label, which is usually violated in practice. It still performs well because classification only needs the correct argmax of the posterior, not accurate probability estimates; biased probabilities often preserve the correct ranking of classes. It is also extremely data-efficient and fast, which helps in high-dimensional settings like text.

Inertia monotonically decreases as K increases (reaching zero when K equals N), so it cannot be minimized to choose K. The elbow method looks for the K where the marginal decrease in inertia sharply diminishes, indicating diminishing returns from adding clusters. Because the elbow is often ambiguous, silhouette score or gap statistic are commonly used as complements.

A one-unit increase in feature x_j, holding others fixed, multiplies the odds of the positive class by exp(beta_j); equivalently beta_j is the change in log-odds. A positive coefficient increases the odds, a negative one decreases them, and exp(beta_j) is the odds ratio. This interpretability is a key reason logistic regression remains a strong baseline.

PCA is unsupervised and finds orthogonal directions maximizing total variance, ignoring labels. LDA is supervised and finds directions maximizing between-class variance relative to within-class variance (Fisher's criterion), so it is optimized for class separability. LDA can produce at most C-1 components for C classes, while PCA can yield up to min(n_features, n_samples-1) nonzero components (mean-centering removes one degree of freedom).

Each tree is trained on a bootstrap sample, leaving roughly 37% (1/e) of observations out-of-bag (OOB). Predicting each sample using only the trees that did not see it yields the OOB error, a roughly unbiased estimate of test error. It can be slightly conservative (pessimistic) because each sample is scored by only about a third of the forest, and it degrades when observations are highly correlated.

Gamma sets the inverse radius of influence of each support vector: large gamma means each point influences only its immediate neighborhood, producing a wiggly boundary prone to overfitting. Small gamma gives broad influence, yielding a smoother, potentially underfit boundary. It is tuned jointly with C, which controls the margin-violation penalty.

Shrinkage scales each tree's contribution by a factor eta < 1, so smaller steps reduce overfitting and improve generalization by preventing any single tree from dominating. To compensate for slower learning you need more boosting rounds, trading compute for accuracy. The eta-vs-n_estimators tradeoff is a central regularization knob, often paired with early stopping.

Both measure node impurity and usually yield very similar trees; Gini = 1 - sum p_k^2 and entropy = -sum p_k log p_k. Entropy is slightly more expensive due to the logarithm and tends to penalize impurity a bit more aggressively, but in practice the choice rarely changes performance materially. Gini is the sklearn default largely for speed.

Elastic net minimizes loss plus alpha*(rho*||w||_1 + (1-rho)/2*||w||_2^2), blending sparsity from L1 with the grouping/stability of L2. It is preferred when features are highly correlated, because Lasso tends to arbitrarily pick one of a correlated group while elastic net can select the group together. It also handles the p >> n case better than Lasso alone, which saturates at n selected features.

As dimensionality grows, distances between points concentrate so that nearest and farthest neighbors become nearly equidistant, eroding the meaning of 'nearest'. Data also becomes sparse, requiring exponentially more samples to maintain density. This makes kNN's local averaging unreliable in high dimensions unless dimensionality is reduced or distances are reweighted.

After each weak learner, misclassified examples have their weights increased and correctly classified examples decreased, so subsequent learners focus on the hard cases. Each learner gets a weight alpha = 0.5*ln((1-err)/err) reflecting its accuracy, and the final prediction is a weighted vote. This adaptive reweighting is what gives AdaBoost its name.

Generative models learn the joint distribution P(x,y) (or P(x|y) and P(y)) and use Bayes' rule to classify; examples include Naive Bayes and Gaussian Discriminant Analysis. Discriminative models learn P(y|x) or the decision boundary directly; examples include logistic regression and SVMs. Discriminative models often have lower asymptotic error, while generative ones can converge faster with little data (the Ng-Jordan result).

K-Means minimizes a non-convex objective via alternating assignment and update steps (Lloyd's algorithm), which only guarantees convergence to a local minimum dependent on initialization. k-means++ seeds initial centroids spread out proportionally to squared distance from existing centers, reducing the chance of poor local optima and improving both speed and final quality. Multiple restarts (n_init) further mitigate the issue.

Multicollinearity inflates the variance of coefficient estimates, making them unstable and hard to interpret (signs may flip) even though predictions can remain accurate. It is commonly detected via the Variance Inflation Factor (VIF > 5-10 is a warning) or a high condition number of the design matrix. Ridge regression or dropping/combining correlated features mitigates it.

DBSCAN groups points by density using two parameters (eps radius and min_samples), so it can find arbitrarily shaped clusters and explicitly labels low-density points as noise/outliers. K-Means assumes roughly spherical, similarly sized clusters and forces every point into a cluster. DBSCAN also does not require specifying the number of clusters, but struggles with varying densities.

C controls the trade-off between maximizing the margin and minimizing classification errors (slack). Large C heavily penalizes misclassifications, producing a narrower margin that fits training data tightly (risk of overfitting), while small C allows more violations for a wider, more generalizable margin. It is effectively the inverse of regularization strength.

With heavy class imbalance, a trivial model predicting the majority class achieves high accuracy while completely failing the minority class. Better metrics include precision, recall, F1, the precision-recall AUC, balanced accuracy, and Matthews correlation coefficient, chosen based on the relative cost of false positives vs false negatives. ROC-AUC can also be overly optimistic under extreme imbalance, so PR-AUC is often preferred.

Precision = TP/(TP+FP) measures correctness of positive predictions; recall = TP/(TP+FN) measures coverage of actual positives. Lowering the decision threshold typically raises recall but lowers precision (and vice versa), tracing the precision-recall curve. The right operating point depends on whether false positives or false negatives are costlier.

Under the Gauss-Markov assumptions (linearity in parameters, zero-mean errors, homoscedasticity / constant error variance, no autocorrelation of errors, and no perfect multicollinearity) OLS is the Best Linear Unbiased Estimator. Normality of errors is NOT required for BLUE; it is only needed for exact small-sample inference (t/F tests). Violations like heteroscedasticity keep OLS unbiased but make it inefficient (no longer minimum variance).

The E-step computes the posterior responsibility of each Gaussian component for each point given current parameters; the M-step updates each component's mean, covariance, and mixing weight using those responsibilities. Iterating monotonically increases the data log-likelihood until convergence to a local optimum. GMM thus generalizes K-Means to soft assignments with full covariance shapes.

A single unpruned tree can change drastically with small perturbations to the training data, producing very different splits, which is high variance. Bagging and random forests average many decorrelated trees to reduce that variance, while feature subsampling at each split further decorrelates them. Boosting instead grows shallow trees sequentially to reduce bias.

Stratified k-fold preserves the class proportions in each fold, which is important for classification, especially with imbalanced data, so each fold is representative and the variance of the performance estimate is reduced. Plain k-fold can produce folds with skewed or even missing classes by chance. For regression, plain or grouped k-fold is typical instead.

Bagging trains base learners independently and in parallel on bootstrap samples, then aggregates by voting/averaging. Boosting trains learners sequentially, each correcting the errors of the prior ensemble by reweighting examples or fitting residuals. Consequently bagging is parallelizable and variance-reducing, while boosting is sequential and bias-reducing but more prone to overfitting noise.

Without smoothing, a feature value unseen for a class in training yields P=0, which zeroes the entire product of conditional probabilities. Laplace smoothing adds a pseudocount alpha (often 1) to every count and adjusts the denominator by alpha*K (K = number of feature values), guaranteeing nonzero probabilities. This is equivalent to a Dirichlet prior on the categorical likelihoods.

Lambda penalizes the squared leaf weights, shrinking predictions and reducing overfitting, and it appears in the denominator of the optimal leaf-weight formula -G/(H+lambda). Gamma is the minimum loss reduction required to make a split, acting as a complexity penalty that prunes splits with insufficient gain. Together they regularize tree structure and leaf magnitudes.

The first principal component is the unit-norm direction along which the projected (mean-centered) data has maximum variance, equivalently the direction minimizing the sum of squared orthogonal (perpendicular) distances from the points to the line. It is the eigenvector of the covariance matrix with the largest eigenvalue, and that eigenvalue equals the variance captured. Subsequent components are orthogonal directions of next-largest variance.

LightGBM grows the leaf with the maximum delta loss rather than level-wise, which reaches lower loss with fewer splits and is faster on large data. The risk is overfitting, especially on small datasets, because deep asymmetric trees can form; this is controlled with num_leaves, max_depth, and min_data_in_leaf. Histogram-based binning further speeds up split finding.

Target leakage occurs when features incorporate information unavailable at prediction time or derived from the target, inflating offline metrics but failing in production. Classic examples are scaling/imputing using statistics computed over the entire dataset before the train/test split, or including a post-outcome field like 'days_until_payment' to predict default. The fix is to fit all preprocessing inside cross-validation folds (e.g., an sklearn Pipeline) and audit feature provenance.

Hinge loss max(0, 1 - y*f(x)) is zero once a point is correctly classified beyond the margin, focusing the model on margin violators and yielding sparse support vectors; it is not differentiable at the kink. Log loss is smooth, never exactly zero, penalizes all points and produces calibrated probabilities. Thus SVMs emphasize the margin while logistic regression yields probabilistic outputs.

Impurity-based importance is biased toward high-cardinality and continuous features because they offer more split points to reduce impurity, and it is computed on training data so it can reward overfit splits. Permutation importance (measuring performance drop when a feature is shuffled on held-out data) or SHAP values give more reliable, model-agnostic attributions. Permutation importance can still be misleading under correlated features.

PCA maximizes variance, so without standardization features measured in large units (e.g., income in dollars) dominate the principal components purely due to scale, not informativeness. Standardizing to zero mean and unit variance makes PCA operate on the correlation matrix, giving each feature comparable influence. Mean-centering is always required; unit-variance scaling is recommended when feature scales differ.

Hard voting takes the majority predicted class label across base models. Soft voting averages the predicted class probabilities and picks the argmax, which weights confident models more and usually performs better when the base estimators are well-calibrated. Soft voting requires that all base models expose probability estimates.

Ridge shrinks the OLS solution by filtering each direction's contribution by sigma^2/(sigma^2 + lambda), where sigma are the singular values from the SVD of the design matrix. Directions with small singular values (low-variance, often noisy) are shrunk the most, stabilizing estimates against multicollinearity. As lambda goes to 0 it recovers OLS; as lambda grows, all coefficients shrink toward zero.

Calibration means predicted probabilities match observed frequencies (e.g., among samples scored 0.8, about 80% are positive). AUC measures only ranking/discrimination, so a model can perfectly rank positives above negatives yet output systematically over- or under-confident probabilities. Calibration is fixed post-hoc with Platt scaling (sigmoid) or isotonic regression and assessed with reliability diagrams or the Brier score.

It reweights the loss inversely proportional to class frequencies, so errors on the minority class incur proportionally larger penalties, effectively rebalancing the gradient without resampling. This shifts the decision boundary to better capture the minority class, trading some majority-class precision for minority recall. It is an alternative to oversampling (e.g., SMOTE) or undersampling.