← Reference · Nestor G Pestelos Jr · Print this page

Machine Learning

Supervised Learning

A citable reference on Supervised Learning: mathematical problem formulation, empirical risk minimization, regression and classification loss functions, the bias-variance decomposition, algorithm taxonomy, and generalization bounds.

1. Formal Mathematical Formulation

Supervised Learning is a machine learning paradigm in which an algorithm learns a mapping function from input features to output targets based on training examples composed of labeled pairs.[1, 2] The objective is to produce a model that generalizes accurately to previously unseen inputs sampled from the underlying joint data distribution.

1.1 Data Spaces and Training Experience

Let $\mathcal{X} \subseteq \mathbb{R}^d$ denote the input feature space and $\mathcal{Y}$ denote the target output space. In the supervised setting, the training experience $E$ consists of a dataset $\mathcal{D}$ of $N$ independent and identically distributed (i.i.d.) pairs drawn from a fixed but unknown probability distribution $P(X, Y)$:

$$\mathcal{D} = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\} \sim P(X, Y)^N$$

The nature of $\mathcal{Y}$ determines the fundamental task category:

Regression: The target space is continuous, $\mathcal{Y} \subseteq \mathbb{R}^k$ (typically $k=1$).
Binary Classification: The target space contains discrete binary labels, $\mathcal{Y} = \{-1, +1\}$ or $\mathcal{Y} = \{0, 1\}$.
Multiclass Classification: The target space contains $C$ categorical labels, $\mathcal{Y} = \{1, 2, \dots, C\}$.
Multilabel / Structured Output: The target space consists of binary vectors $\mathcal{Y} = \{0, 1\}^C$ or complex combinatorial objects such as parse trees, bounding boxes, or sequences.

1.2 True Risk vs. Empirical Risk Minimization (ERM)

Given a hypothesis class $\mathcal{H}$ of parameterized candidate functions $f_\theta: \mathcal{X} \to \mathcal{Y}$ and a loss function $\mathcal{L}: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$, the ideal goal is finding parameters $\theta^*$ that minimize the True Risk (or generalization error) $R(f_\theta)$:[3]

$$R(f_\theta) = \mathbb{E}_{(x, y) \sim P(X, Y)} \left[ \mathcal{L}(f_\theta(x), y) \right] = \int_{\mathcal{X} \times \mathcal{Y}} \mathcal{L}(f_\theta(x), y) \, dP(x, y)$$

Because $P(X, Y)$ is unknown, the true risk cannot be computed directly. Under the Empirical Risk Minimization (ERM) principle (Vapnik, 1998), the algorithm optimizes the sample average loss across the training set:[3]

$$\hat{R}_{\text{emp}}(f_\theta, \mathcal{D}) = \frac{1}{N} \sum_{i=1}^N \mathcal{L}\big(f_\theta(x_i), y_i\big)$$

1.3 Regularization Framework

Unconstrained minimization of empirical risk over complex hypothesis spaces leads to overfitting, where the model memorizes sample noise rather than generalizable functional relationships. Structural Risk Minimization (SRM) augments empirical risk with a complexity penalty $\Omega(\theta)$ weighted by a hyperparameter $\lambda > 0$:[2, 3]

$$\hat{\theta} = \arg\min_{\theta} \left( \frac{1}{N} \sum_{i=1}^N \mathcal{L}\big(f_\theta(x_i), y_i\big) + \lambda \Omega(\theta) \right)$$

$L_2$ Regularization (Ridge / Weight Decay): $\Omega(\theta) = \|\theta\|_2^2 = \sum_j \theta_j^2$. Imposes a Gaussian prior on parameters, penalizing large weights and stabilizing ill-conditioned inversions.
$L_1$ Regularization (Lasso): $\Omega(\theta) = \|\theta\|_1 = \sum_j |\theta_j|$. Imposes a Laplacian prior on parameters, driving uninformative feature weights to zero to perform embedded feature selection.
Elastic Net: $\Omega(\theta) = \alpha \|\theta\|_1 + (1 - \alpha) \|\theta\|_2^2$, combining sparsity induction with group selection for correlated predictors.

2. Canonical Loss Functions

The loss function specifies the penalty assigned to discrepancies between model predictions $\hat{y} = f_\theta(x)$ and ground-truth targets $y$. The selection of loss function dictates the probabilistic interpretation and robustness of the resulting estimator.

2.1 Regression Losses

Loss Function	Mathematical Definition	Optimal Point Prediction	Properties & Robustness
Squared Error (MSE / $L_2$)	$\mathcal{L}(f(x), y) = \frac{1}{2}(y - f(x))^2$	Conditional Mean $\mathbb{E}[Y \mid X=x]$	Differentiable everywhere; highly sensitive to outliers. Corresponds to Gaussian likelihood.
Absolute Error (MAE / $L_1$)	$\mathcal{L}(f(x), y) = \|y - f(x)\|$	Conditional Median $\text{Med}(Y \mid X=x)$	Robust to extreme outliers; non-differentiable at $y - f(x) = 0$. Corresponds to Laplace likelihood.
Huber Loss	$\begin{cases} \frac{1}{2}(y - f(x))^2 & \|y - f(x)\| \le \delta \\ \delta \|y - f(x)\| - \frac{1}{2}\delta^2 & \|y - f(x)\| > \delta \end{cases}$	Hybrid conditional statistic	Smoothly transitions from quadratic for small residuals to linear for large residuals; robust and differentiable.

2.2 Classification Losses

Loss Function	Mathematical Definition	Target Setting	Properties & Optimization
Cross-Entropy Loss (Log Loss)	$\mathcal{L}(f(x), y) = -\sum_{c=1}^C y_c \log \hat{p}_c(x)$	Probabilistic multiclass $y \in \{0,1\}^C$	Maximizes likelihood under multinomial distribution; strictly convex when combined with linear parameterizations.
Hinge Loss	$\mathcal{L}(f(x), y) = \max(0, 1 - y f(x))$	Margin classification $y \in \{-1, +1\}$	Convex surrogate for 0-1 loss; yields sparse support vectors by penalizing margin violations.
Exponential Loss	$\mathcal{L}(f(x), y) = e^{-y f(x)}$	Margin classification $y \in \{-1, +1\}$	Underlying loss function of AdaBoost; places high penalty on misclassified samples.
0-1 Loss	$\mathcal{L}(f(x), y) = \mathbb{I}(y \ne \text{sign}(f(x)))$	Binary classification	True classification error rate; NP-hard and non-convex to optimize directly.

3. The Bias-Variance Tradeoff

The generalization performance of a supervised model is governed by the structural tension between model simplicity and model expressiveness.[2, 4]

3.1 Analytical Error Decomposition

Assume a true data-generating process $y = g(x) + \epsilon$, where $\mathbb{E}[\epsilon] = 0$ and $\text{Var}(\epsilon) = \sigma^2$. For a fixed query point $x$ and an estimator $\hat{f}_{\mathcal{D}}(x)$ fit on random training dataset $\mathcal{D}$, the expected mean squared test error decomposes analytically into three mutually orthogonal terms:

$$\mathbb{E}_{\mathcal{D}, \epsilon} \left[ \big(y - \hat{f}_{\mathcal{D}}(x)\big)^2 \right] = \underbrace{\Big(\mathbb{E}_{\mathcal{D}}[\hat{f}_{\mathcal{D}}(x)] - g(x)\Big)^2}_{\text{Bias}^2} + \underbrace{\mathbb{E}_{\mathcal{D}}\left[ \Big(\hat{f}_{\mathcal{D}}(x) - \mathbb{E}_{\mathcal{D}}[\hat{f}_{\mathcal{D}}(x)]\Big)^2 \right]}_{\text{Variance}} + \underbrace{\sigma^2}_{\text{Irreducible Noise}}$$

$\text{Bias}^2$: Systematic error arising from faulty inductive assumptions or insufficient model capacity (underfitting). High-bias models fail to capture underlying functional complexities.
$\text{Variance}$: Error stemming from estimation sensitivity to idiosyncratic variations across training datasets (overfitting). High-variance models fit sample-specific noise.
$\sigma^2$: Inherent statistical noise in the data distribution that cannot be eliminated by any learning algorithm regardless of capacity.

3.2 Overfitting, Underfitting, and Double Descent

Classical statistical learning posits a U-shaped generalization curve where increasing model capacity initially reduces bias, reaches an optimal trade-off point, and then causes test error to escalate due to explosive variance.

Modern empirical research demonstrates the Double Descent phenomenon (Belkin et al., 2019): as model parameters exceed the number of training samples (the interpolation threshold where training error reaches zero), test risk peaks and subsequently decreases as capacity grows further.[5] Overparameterized deep networks and kernel machines find minimum-norm interpolating solutions that generalize effectively despite having zero empirical training loss.

4. Taxonomy of Supervised Algorithms

Family	Primary Algorithms	Inductive Bias	Typical Applications
Linear & Logistic Models	Ordinary Least Squares (OLS), Ridge, Lasso, Logistic Regression, Elastic Net	Linear relationship between input features (or basis expansions) and response	Econometrics, baseline tabular modeling, risk scoring, fast inference
Maximum Margin	Support Vector Machines (SVM), Support Vector Regression (SVR)	Maximal geometric margin between decision boundary and nearest support samples	High-dimensional bioinformatics, text categorization, image classification
Tree Ensembles	CART Decision Trees, Random Forests, Gradient Boosted Decision Trees (XGBoost, LightGBM, CatBoost)	Hierarchical axis-aligned orthogonal partitions of feature space	Tabular data competitions, fraud detection, credit scoring, ranking
Instance-Based	$k$-Nearest Neighbors ($k$-NN), Locally Weighted Regression	Local smoothness; similar instances in feature space share similar target values	Low-dimensional spatial interpolation, recommendation baselines
Deep Neural Architectures	Multilayer Perceptrons (MLP), Convolutional Networks (CNN), Supervised Transformers	Hierarchical compositional representations across layers	Computer vision, speech recognition, machine translation, protein folding

4.1 Generalized Linear and Logistic Models

Linear models assume an expectation function $g(\mathbb{E}[Y \mid X]) = w^T x + b$, where $g$ is a link function.

Ordinary Least Squares: $\hat{w} = (X^T X)^{-1} X^T y$. Closed-form analytical solution minimizing sum of squared residuals.
Logistic Regression: Utilizes the logit link function $\log \frac{p}{1-p} = w^T x + b$, yielding posterior class probabilities modeled through the logistic sigmoid $\sigma(z) = \frac{1}{1 + e^{-z}}$:
$$P(Y=1 \mid X=x) = \frac{1}{1 + e^{-(w^T x + b)}}$$

4.2 Support Vector Machines and Kernel Methods

Support Vector Machines (Cortes & Vapnik, 1995) find a hyperplane $w^T x + b = 0$ that maximizes the geometric margin $\frac{2}{\|w\|_2}$ between two separable classes.[6] The primal optimization problem with soft margin slack variables $\xi_i$ is:

$$\min_{w, b, \xi} \left( \frac{1}{2} \|w\|_2^2 + C \sum_{i=1}^N \xi_i \right) \quad \text{subject to} \quad y_i (w^T x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0$$

The dual formulation depends only on pairwise inner products $\langle x_i, x_j \rangle$. The Kernel Trick implicitly projects input vectors into a high-dimensional reproducing kernel Hilbert space (RKHS) $\Phi(x)$ by replacing inner products with a Mercer kernel function $K(x_i, x_j) = \langle \Phi(x_i), \Phi(x_j) \rangle$, such as the Radial Basis Function (RBF) kernel:

$$K_{\text{RBF}}(x_i, x_j) = \exp\left( -\gamma \|x_i - x_j\|_2^2 \right)$$

4.3 Decision Trees and Ensemble Methods

Decision trees recursively partition the input space into hyperrectangles by choosing greedy splits that maximize impurity reduction (measured via Gini impurity $I_G(p) = 1 - \sum p_k^2$ or Entropy $H(p) = -\sum p_k \log_2 p_k$).

Random Forests (Breiman, 2001): Bagging (Bootstrap Aggregation) ensemble of unpruned deep trees trained on bootstrap resamples of $\mathcal{D}$ with random feature sub-sampling at each split.[7] Reduces variance without increasing bias.
Gradient Boosted Decision Trees (Friedman, 2001): Sequential ensemble where each base learner $h_m(x)$ fits the negative gradient (pseudo-residuals) of the loss function with respect to current ensemble predictions $F_{m-1}(x)$:[8]
$$r_{im} = -\left[ \frac{\partial \mathcal{L}(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x) = F_{m-1}(x)}, \quad F_m(x) = F_{m-1}(x) + \eta \, h_m(x)$$

4.4 Supervised Neural Networks

In deep supervised learning, multilayer architectures perform end-to-end feature learning and target mapping. Parameters are optimized via mini-batch stochastic gradient descent (SGD) using backpropagation to compute analytical gradients of empirical loss with respect to all layer weights.[9]

5. Generalization Bounds and Statistical Learning Theory

Statistical learning theory provides rigorous mathematical bounds establishing conditions under which empirical risk on training data guarantees bounded true risk on unseen test distributions.

5.1 PAC Learning Framework

In Leslie Valiant's Probably Approximately Correct (PAC) framework (Valiant, 1984), a concept class $\mathcal{C}$ is PAC-learnable if an algorithm can select a hypothesis $h \in \mathcal{H}$ such that with probability at least $1 - \delta$, the generalization error is bounded by $\epsilon$, using a sample size polynomial in $\frac{1}{\epsilon}$, $\frac{1}{\delta}$, and instance size $d$:[10]

$$\mathbb{P}_{\mathcal{D} \sim P^N}\Big( R(h) \le \hat{R}_{\text{emp}}(h) + \epsilon \Big) \ge 1 - \delta$$

5.2 VC Dimension and Rademacher Complexity

For an infinite hypothesis space $\mathcal{H}$, generalization error is bounded by its Vapnik-Chervonenkis (VC) Dimension $d_{\text{VC}}$, defined as the cardinality of the largest set of points that $\mathcal{H}$ can shatter (assign all $2^N$ possible binary label configurations):[3]

$$R(h) \le \hat{R}_{\text{emp}}(h) + \sqrt{\frac{8 d_{\text{VC}} \ln(2N/d_{\text{VC}}) + 8 \ln(4/\delta)}{N}}$$

Rademacher Complexity $\mathcal{R}_N(\mathcal{H})$ refines this bound by measuring the empirical capacity of hypothesis space $\mathcal{H}$ to fit random Rademacher noise $\sigma_i \in \{-1, +1\}$ on the actual dataset distribution, providing data-dependent generalization guarantees.

6. References

^ Tom M. Mitchell, Machine Learning (McGraw-Hill, 1997).
^ Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Springer, 2009). DOI: 10.1007/978-0-387-84858-7.
^ Vladimir N. Vapnik, Statistical Learning Theory (John Wiley & Sons, 1998).
^ Christopher M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006).
^ Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal, "Reconciling modern machine-learning practice and the classical bias–variance trade-off," Proceedings of the National Academy of Sciences 116(32), 15849–15854 (2019). DOI: 10.1073/pnas.1903070116.
^ Corinna Cortes and Vladimir Vapnik, "Support-vector networks," Machine Learning 20(3), 273–297 (1995). DOI: 10.1007/BF00994018.
^ Leo Breiman, "Random Forests," Machine Learning 45(1), 5–32 (2001). DOI: 10.1023/A:1010933404324.
^ Jerome H. Friedman, "Greedy function approximation: A gradient boosting machine," The Annals of Statistics 29(5), 1189–1232 (2001). DOI: 10.1214/aos/1013203451.
^ Yann LeCun, Yoshua Bengio, and Geoffrey Hinton, "Deep learning," Nature 521(7553), 436–444 (2015). DOI: 10.1038/nature14539.
^ Leslie G. Valiant, "A theory of the learnable," Communications of the ACM 27(11), 1134–1142 (1984). DOI: 10.1145/1968.1972.

Loss Function	Mathematical Definition	Optimal Point Prediction	Properties & Robustness
Squared Error (MSE / \(L_2\))	\(\mathcal{L}(f(x), y) = \frac{1}{2}(y - f(x))^2\)	Conditional Mean \(\mathbb{E}[Y \mid X=x]\)	Differentiable everywhere; highly sensitive to outliers. Corresponds to Gaussian likelihood.
Absolute Error (MAE / \(L_1\))	\(\mathcal{L}(f(x), y) = \|y - f(x)\|\)	Conditional Median \(\text{Med}(Y \mid X=x)\)	Robust to extreme outliers; non-differentiable at \(y - f(x) = 0\). Corresponds to Laplace likelihood.
Huber Loss	\(\begin{cases} \frac{1}{2}(y - f(x))^2 & \|y - f(x)\| \le \delta \\ \delta \|y - f(x)\| - \frac{1}{2}\delta^2 & \|y - f(x)\| > \delta \end{cases}\)	Hybrid conditional statistic	Smoothly transitions from quadratic for small residuals to linear for large residuals; robust and differentiable.

Loss Function	Mathematical Definition	Target Setting	Properties & Optimization
Cross-Entropy Loss (Log Loss)	\(\mathcal{L}(f(x), y) = -\sum_{c=1}^C y_c \log \hat{p}_c(x)\)	Probabilistic multiclass \(y \in \{0,1\}^C\)	Maximizes likelihood under multinomial distribution; strictly convex when combined with linear parameterizations.
Hinge Loss	\(\mathcal{L}(f(x), y) = \max(0, 1 - y f(x))\)	Margin classification \(y \in \{-1, +1\}\)	Convex surrogate for 0-1 loss; yields sparse support vectors by penalizing margin violations.
Exponential Loss	\(\mathcal{L}(f(x), y) = e^{-y f(x)}\)	Margin classification \(y \in \{-1, +1\}\)	Underlying loss function of AdaBoost; places high penalty on misclassified samples.
0-1 Loss	\(\mathcal{L}(f(x), y) = \mathbb{I}(y \ne \text{sign}(f(x)))\)	Binary classification	True classification error rate; NP-hard and non-convex to optimize directly.