Reference Document

Machine Learning

A citable reference on Machine Learning (ML): empirical risk minimization, supervised, unsupervised, and reinforcement paradigms, optimization, and generalization theorems.

Jump to Section

Formal Definition · Learning Paradigms · Empirical Risk Minimization · Bias-Variance Tradeoff · Generalization & Core Theorems · Sources

1. Formal Definition: The (T, P, E) Formulation

Machine Learning (ML) is a subfield of artificial intelligence focused on mathematical algorithms that build statistical models from sample data in order to make predictions or decisions without being explicitly programmed with deterministic rules.

Under Tom Mitchell's canonical definition (Mitchell, 1997):

"A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."

2. The Three Primary Learning Paradigms

Paradigm	Training Data Signal (Experience $E$)	Objective / Task $T$	Representative Algorithms
Supervised Learning	Labeled pairs $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$.	Learn mapping function $f: X \to Y$ predicting labels for unseen $x$.	Linear/Logistic Regression, Support Vector Machines (SVM), Random Forests, DNNs.
Unsupervised & Self-Supervised	Unlabeled data $\mathcal{D} = \{x_i\}_{i=1}^N$ (or self-derived token masks).	Discover latent structure, density $P(X)$, or predict masked tokens from context.	k-Means Clustering, PCA, t-SNE, Autoencoders, Autoregressive Pre-Training.
Reinforcement Learning (RL)	Scalar reward signal $R_t$ from environment transitions in an MDP $(S, A, P, R, \gamma)$.	Learn optimal policy $\pi^*(a \mid s)$ maximizing expected cumulative discounted return.	Q-Learning, PPO, Deep Q-Networks (DQN), RLHF/DPO for LLM Alignment.

3. Empirical Risk Minimization (ERM)

In supervised learning, the ideal objective is minimizing the true risk $R(f) = \mathbb{E}_{(x,y)\sim P}[\mathcal{L}(f(x), y)]$ over the unknown data distribution $P(X,Y)$. Because $P$ is unknown, algorithms minimize the Empirical Risk over the training set, augmented by a regularization penalty $\Omega(\theta)$ to prevent overfitting:

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

Loss Function $\mathcal{L}$: Measures point-wise error (e.g. Mean Squared Error $(y - \hat{y})^2$ for regression; Cross-Entropy $-\sum y_k \log \hat{y}_k$ for classification).
Regularization $\Omega(\theta)$: Penalizes model complexity (e.g. $L_1$ Lasso $\|\theta\|_1$ for sparsity; $L_2$ Ridge $\|\theta\|_2^2$ / Weight Decay for smoothness).

4. The Bias-Variance Tradeoff

For any supervised regression model, the expected generalization error on unseen test data decomposes analytically into three orthogonal components:

$$\mathbb{E}\big[(y - \hat{f}(x))^2\big] = \text{Bias}\big[\hat{f}(x)\big]^2 + \text{Var}\big[\hat{f}(x)\big] + \sigma^2$$

Bias: Error from erroneous assumptions in the learning algorithm (underfitting; e.g. fitting a straight line to quadratic data).
Variance: Error from extreme sensitivity to small fluctuations in the training set (overfitting; model memorizes noise).
Irreducible Error ($\sigma^2$): Inherent noise in the data-generating distribution that no model can eliminate.

5. Foundational Theorems & Principles

No Free Lunch Theorem (Wolpert & Macready, 1997): Averaged over all possible data distributions, no single machine learning algorithm outperforms random guessing. An algorithm succeeds only by exploiting inductive biases matched to the target problem domain.
Curse of Dimensionality: As feature dimension $d$ increases, the volume of the space grows exponentially, causing sample data to become exponentially sparse. Distance metrics (e.g. Euclidean distance) lose contrast unless constrained by manifold learning or dense embeddings.
Double Descent Phenomenon (Belkin et al., 2019): In modern overparameterized models (such as deep networks and LLMs), increasing parameters past the interpolation threshold causes test error to decrease again, defying classical bias-variance tradeoffs.

Paradigm	Training Data Signal (Experience \(E\))	Objective / Task \(T\)	Representative Algorithms
Supervised Learning	Labeled pairs \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N\).	Learn mapping function \(f: X \to Y\) predicting labels for unseen \(x\).	Linear/Logistic Regression, Support Vector Machines (SVM), Random Forests, DNNs.
Unsupervised & Self-Supervised	Unlabeled data \(\mathcal{D} = \{x_i\}_{i=1}^N\) (or self-derived token masks).	Discover latent structure, density \(P(X)\), or predict masked tokens from context.	k-Means Clustering, PCA, t-SNE, Autoencoders, Autoregressive Pre-Training.
Reinforcement Learning (RL)	Scalar reward signal \(R_t\) from environment transitions in an MDP \((S, A, P, R, \gamma)\).	Learn optimal policy \(\pi^*(a \mid s)\) maximizing expected cumulative discounted return.	Q-Learning, PPO, Deep Q-Networks (DQN), RLHF/DPO for LLM Alignment.