Machine Learning Algorithms
from First Principles

Despite its name, Logistic Regression is a classification algorithm. It models the probability that an input belongs to a particular class by passing a linear combination of features through the sigmoid function σ(z) = 1/(1+e⁻ᶻ).

The model learns weights w and bias b by maximizing the log-likelihood of the training data, which is equivalent to minimizing the binary cross-entropy loss. The decision boundary is a hyperplane where P(y=1|x) = 0.5.

Because the sigmoid squashes outputs to [0,1], the model naturally produces probabilistic predictions. The gradient of the loss is proportional to the prediction error, making optimization via gradient descent straightforward.

KNN is the simplest non-parametric classifier: it stores the entire training set and classifies new points by majority vote of their k nearest neighbors, typically measured by Euclidean distance.

No training occurs — the model IS the data. At prediction time, it computes distances to all training points, sorts them, and takes the top-k. The decision boundary is entirely determined by the local geometry of the data.

The choice of k controls the bias-variance tradeoff: small k gives complex, noisy boundaries (high variance); large k smooths boundaries (high bias). Distance weighting can mitigate the effect of imbalanced class densities.

Decision Trees recursively partition the feature space using axis-aligned splits. At each node, the algorithm selects the feature and threshold that maximizes information gain (or minimizes Gini impurity).

The process is greedy: at each step, it picks the locally best split without backtracking. This continues until a stopping criterion is met — maximum depth, minimum samples per leaf, or pure leaves.

The resulting model is a set of if-then rules that can be traversed in O(depth) time. Each leaf outputs the majority class of its training examples. The piecewise-constant boundaries are axis-aligned, creating a stair-step pattern.

The RBF (Radial Basis Function) kernel maps inputs into an infinite-dimensional feature space where data that is not linearly separable becomes separable. The kernel computes K(x,x') = exp(−γ‖x−x'‖²) without explicitly performing the mapping.

In this implicit high-dimensional space, SVM finds the maximum-margin hyperplane. Points near the decision boundary become support vectors. The γ parameter controls the width of the RBF: large γ creates tight, complex boundaries; small γ creates smooth, broad ones.

Combined with the C parameter (regularization), the RBF SVM can model highly non-linear decision boundaries while still optimizing a convex objective, guaranteeing a global optimum.

Linear SVM finds the hyperplane that separates classes with maximum margin — the largest possible distance between the hyperplane and the nearest training points from each class.

Only the support vectors (points on or within the margin) affect the decision boundary. All other points can be moved freely without changing the model. This makes SVM robust to outliers far from the boundary.

The primal formulation minimizes ‖w‖² + C·Σξᵢ subject to yᵢ(w·xᵢ+b) ≥ 1−ξᵢ. The dual formulation introduces Lagrange multipliers αᵢ, leading to the kernelizable form.

The polynomial kernel K(x,x') = (γ·x·x' + r)^d maps features into a d-dimensional polynomial space. This allows SVM to learn polynomial decision boundaries of degree d.

For d=2, the kernel captures all pairwise feature interactions. Higher degrees model more complex interactions but risk overfitting. The parameter r (coef0) controls the influence of high-order terms.

Like the RBF kernel, the polynomial kernel computes inner products in the transformed space without explicitly mapping, making computation tractable even for high-degree polynomials.

Random Forest builds many decision trees on bootstrapped samples (bagging) and random subsets of features at each split. This decorrelates the trees, reducing variance without increasing bias.

Each tree votes on the class; the majority vote wins. Because each tree sees different data and features, individual errors average out. The out-of-bag (OOB) samples provide a built-in validation estimate.

Feature importance is measured by how much each feature decreases impurity across all trees, or by permutation importance on OOB data.

AdaBoost trains weak learners sequentially. After each round, it increases the weights of misclassified samples and decreases weights of correctly classified ones, forcing the next learner to focus on hard examples.

Each learner's contribution is weighted by its accuracy. The final prediction is a weighted vote. The algorithm can be shown to minimize an exponential loss function.

AdaBoost is theoretically elegant — it performs a stage-wise additive modeling approach that greedily minimizes the loss, and has strong generalization bounds from VC theory.

Gradient Boosting generalizes boosting by fitting each new learner to the negative gradient of the loss function with respect to the current ensemble's predictions. This is equivalent to functional gradient descent.

At each step, the algorithm computes pseudo-residuals rᵢ = −∂L(yᵢ,F(xᵢ))/∂F(xᵢ), then fits a regression tree to these residuals. The learning rate η scales each tree's contribution.

This framework supports any differentiable loss function — log-loss for classification, squared error for regression, and many more — making it extremely versatile.

Naive Bayes applies Bayes' theorem with the 'naive' assumption that features are conditionally independent given the class. For Gaussian NB, each feature's class-conditional distribution is modeled as a Gaussian.

At prediction time, it computes P(y|x) ∝ P(y)·Π P(xⱼ|y) for each class and picks the maximum. Despite the independence assumption rarely holding exactly, the classifier often performs well because the ranking of posteriors is preserved.

Training is O(n·d): just compute the mean and variance of each feature per class. The model is essentially a lookup table of Gaussian parameters.

A Multi-Layer Perceptron is a shallow neural network with one or more hidden layers. Each layer applies a linear transformation Wx+b followed by a nonlinear activation (typically ReLU).

The network learns hierarchical feature representations: early layers capture simple patterns, later layers combine them into complex decision boundaries. Training uses backpropagation to compute gradients through the chain rule.

With sufficient hidden units, an MLP with one hidden layer can approximate any continuous function (universal approximation theorem). In practice, 1-2 hidden layers with ReLU activation work well for most tabular data.

Linear Regression fits a hyperplane y = w·x + b that minimizes the mean squared error (MSE) between predictions and actual values. The closed-form solution is w = (XᵀX)⁻¹Xᵀy.

This is the foundation of statistical modeling. The OLS estimator is unbiased and, under Gaussian noise assumptions, is the best linear unbiased estimator (BLUE) by the Gauss-Markov theorem.

The model assumes a linear relationship between features and target. Residual analysis reveals violations — non-linearity, heteroscedasticity, or autocorrelation.

Ridge adds an L2 penalty λ‖w‖² to the MSE loss, shrinking coefficients toward zero but never setting them exactly to zero. This reduces variance at the cost of introducing small bias.

Geometrically, the L2 constraint is a circle in coefficient space. The MSE loss forms elliptical contours. The solution is where the smallest ellipse touches the circle — typically a point where all coefficients are reduced but nonzero.

Ridge is especially useful when features are correlated (multicollinearity) — it distributes weight across correlated features rather than picking one arbitrarily.

Lasso adds an L1 penalty λ‖w‖₁ to the loss, which shrinks some coefficients exactly to zero, performing automatic feature selection. The L1 penalty's diamond-shaped constraint has corners on the axes.

Geometrically, the elliptical loss contours are more likely to touch a diamond corner (where one coefficient is zero) than a smooth circle's edge. This is why Lasso produces sparse solutions.

The number of non-zero coefficients is bounded by min(n, p). Lasso is ideal for high-dimensional data where only a few features are truly relevant.

Elastic Net combines L1 and L2 penalties: λ₁‖w‖₁ + λ₂‖w‖². The mixing ratio l1_ratio controls the blend. This gets Lasso's sparsity while keeping Ridge's stability with correlated features.

When features are correlated, Lasso picks one arbitrarily and sets others to zero. Elastic Net tends to select groups of correlated features together, which is more realistic.

The penalty shape is between a diamond (pure L1) and circle (pure L2), creating a rounded diamond that touches axes less aggressively.

Decision Tree Regressor partitions the feature space and assigns the mean target value of training samples in each leaf. The splitting criterion minimizes MSE (or MAE) within each partition.

Like the classification tree, splits are axis-aligned and chosen greedily. The prediction for any input is the average of all training targets that fall into the same leaf region.

The resulting function is piecewise constant — a step function over the feature space. Pruning controls the complexity to prevent overfitting.

Random Forest Regressor averages the predictions of many bootstrapped, feature-randomized decision trees. Each tree predicts a constant in each leaf; the forest averages these to produce a smoother prediction.

The ensemble variance reduction comes from averaging uncorrelated trees. While individual trees overfit, the average is robust. Feature randomization ensures diversity.

OOB error provides a free validation estimate. Feature importance can be computed by permutation or impurity decrease.

GBR fits a sequence of regression trees, each correcting the residual errors of the previous ensemble. At each step, it computes the negative gradient of the squared error loss (which equals the residual) and fits a tree to it.

The learning rate η shrinks each tree's contribution, trading training speed for generalization. Subsampling (stochastic gradient boosting) adds randomness to reduce overfitting.

GBR is one of the most powerful algorithms for structured/tabular data. It consistently wins Kaggle competitions and is the default choice for regression tasks on tabular datasets.

Support Vector Regression fits a function within an ε-tube around the data. Points inside the tube have zero loss; only points outside contribute to the loss. This makes SVR robust to small noise.

Linear SVR finds a linear function f(x) = w·x + b that minimizes ‖w‖² + C·Σξᵢ, where ξᵢ are slack variables for points outside the ε-tube.

The ε-insensitive loss makes SVR sparse — only support vectors (points on or outside the tube boundary) define the model.

RBF SVR uses the kernel trick to fit a non-linear function within an ε-tube. The RBF kernel maps data to infinite dimensions where the ε-tube constraint becomes linear.

The γ parameter controls the smoothness of the fitted function: large γ creates wiggly fits; small γ creates smooth fits. Combined with C and ε, three parameters control the bias-variance tradeoff.

Like classification SVM, only support vectors define the function, making prediction sparse in terms of training data usage.

KNN Regressor predicts the target as the average of the k nearest training samples. No training occurs — the model stores the data and computes distances at prediction time.

The prediction surface is piecewise constant in each Voronoi cell. Increasing k smooths the surface. Distance weighting (giving closer neighbors more influence) improves performance.

KNN regression is a non-parametric method that adapts to any function shape, given enough data. Its performance depends critically on the distance metric and the choice of k.

A Gaussian Process defines a distribution over functions. Given training data, it produces a posterior distribution over functions consistent with the data, providing both predictions and uncertainty estimates.

The kernel function k(x,x') defines the prior covariance between any two points. Smooth kernels (like RBF) assume nearby points have similar values. The posterior mean is the best prediction; the posterior variance quantifies uncertainty.

GP regression is exact for small datasets (n < 1000) but scales as O(n³) due to matrix inversion, limiting its use to small problems or requiring sparse approximations.

MLP Regressor uses the same architecture as the classifier but with a linear output layer and squared error loss. It learns a continuous mapping from features to target values.

The hidden layers learn hierarchical representations. With enough units and data, it can approximate any continuous function. ReLU activations in hidden layers enable learning non-linear patterns.

Training uses backpropagation with MSE loss. Regularization through dropout, early stopping, or weight decay prevents overfitting.

K-Means partitions n data points into k clusters by iteratively assigning points to the nearest centroid and recomputing centroids as the mean of assigned points. This alternation monotonically decreases the total within-cluster sum of squares.

The algorithm converges to a local optimum (not guaranteed global). K-Means++ initialization places initial centroids far apart, significantly improving convergence quality.

The resulting clusters form a Voronoi tessellation — each point belongs to the cluster whose centroid is closest. This means boundaries are always linear (axis-aligned if features are scaled).

DBSCAN groups points that are closely packed (high-density regions) and marks points in low-density regions as noise. It needs no specification of k — clusters emerge from the density structure.

Two parameters define density: ε (neighborhood radius) and min_samples (minimum points to form a dense region). A point is a core point if it has ≥ min_samples within its ε-neighborhood. Border points are within ε of a core point but don't have enough neighbors.

DBSCAN can find arbitrarily shaped clusters and automatically identifies noise. However, it struggles with varying densities — a single ε cannot capture clusters of different densities simultaneously.

Agglomerative clustering starts with each point as its own cluster and repeatedly merges the closest pair. The linkage criterion defines 'closest': single (min distance), complete (max distance), average, or Ward (min variance increase).

The merge history forms a dendrogram — a tree that can be cut at different levels to yield different numbers of clusters. This hierarchical structure reveals the data's natural grouping at multiple scales.

Ward's method (default in scikit-learn) merges clusters that minimize the total within-cluster variance increase, producing compact, equally-sized clusters.

GMM models the data as a mixture of k Gaussian distributions, each with its own mean and covariance. Unlike K-Means (which hard-assigns), GMM gives soft probabilistic cluster assignments.

Training uses the Expectation-Maximization (EM) algorithm: E-step computes posterior probabilities of each point belonging to each Gaussian; M-step updates means, covariances, and mixing weights.

GMM can model elliptical clusters of different sizes and orientations. The number of components k can be selected via BIC or AIC, which penalize model complexity.

Spectral clustering builds a similarity graph from the data, then clusters based on the graph structure. It computes eigenvectors of the graph Laplacian L = D − A and uses the bottom eigenvectors as a low-dimensional embedding.

In this embedding, clusters that were not linearly separable in the original space become separable by K-Means. The key insight: the Fiedler vector (second-smallest eigenvector) of the Laplacian encodes the optimal graph cut.

Spectral clustering excels on non-convex shapes (moons, rings) where K-Means fails. The similarity graph (typically k-NN or ε-neighborhood) defines what 'nearby' means.

PCA finds orthogonal directions (principal components) that maximize variance in the data. The first component captures the most variance, the second captures the most remaining variance orthogonal to the first, and so on.

Computationally, PCA computes the eigendecomposition of the covariance matrix or the SVD of the data matrix. The eigenvectors are the principal components; the eigenvalues indicate the variance explained.

By projecting onto the top-k components, PCA reduces dimensionality while preserving maximum variance. The fraction of variance retained is Σλᵢ / Σλⱼ for the selected components.

t-SNE (t-distributed Stochastic Neighbor Embedding) models pairwise similarities between points as probability distributions. In high dimensions, it uses Gaussians; in low dimensions, it uses Student-t distributions (heavier tails).

It minimizes the KL divergence between the high-dimensional and low-dimensional similarity distributions using gradient descent. The heavier tails of the t-distribution in low-D prevent crowding.

t-SNE excels at revealing local cluster structure in 2D. However, distances between clusters are not meaningful — only local neighborhoods are preserved. Perplexity controls the effective number of neighbors.

UMAP (Uniform Manifold Approximation and Projection) is based on Riemannian geometry and algebraic topology. It constructs a fuzzy simplicial set (topological representation) of the high-dimensional data.

It optimizes a low-dimensional embedding to have a similar topological structure. The loss function is cross-entropy between high-D and low-D fuzzy set memberships, similar to t-SNE but with different mathematical foundations.

UMAP is faster than t-SNE and better preserves global structure. It scales linearly with n using approximate nearest neighbors. The n_neighbors parameter controls the balance between local and global structure.

Isomap preserves geodesic distances (distances along the manifold surface) rather than Euclidean distances. It constructs a k-NN graph, computes shortest paths (approximating geodesics), then applies multidimensional scaling.

The key insight: Euclidean distances are wrong for curved manifolds. Two points on a Swiss roll may be close in Euclidean space but far apart along the surface. Isomap measures the true along-the-surface distance.

For the Swiss roll and similar manifolds, Isomap produces a faithful 2D unfolding. However, it is sensitive to noise, short-circuit edges (k too large), and holes in the manifold.