Chapter 1: Introduction to ML

Traditional programming maps $f: \text{Rules} \times \text{Data} \to \text{Output}$, while ML inverts this to learn $f: \text{Data} \times \text{Output} \to \text{Rules}$. The learned function $\hat{f}$ minimizes empirical risk $\frac{1}{n}\sum_{i=1}^n L(\hat{f}(x_i), y_i)$ over the training set. The key insight is that $\hat{f}$ is parameterized (e.g., by weights $\theta$), and learning means adjusting $\theta$ to minimize this loss — converting the "find the rules" problem into a continuous optimization problem that calculus can solve.

ML is appropriate when the mapping $f: X \to Y$ exists but is too complex to specify manually. The formal criterion: the problem has a pattern ($f$ exists), it cannot be pinned down mathematically (no closed-form), and data is available ($\{(x_i, y_i)\}$). The learning bound $|R(\hat{f}) - \hat{R}(\hat{f})| \leq O(\sqrt{\text{complexity}/n})$ shows that the gap between true and empirical risk shrinks as data $n$ grows — more data makes ML more reliable, while rule-based systems do not improve with more data.

ML adds unnecessary complexity when the problem has a known exact solution. For deterministic rules like tax calculation, $f(\text{income}) = \text{tax}$ can be coded directly with zero error. ML would introduce approximation error $\epsilon > 0$ by construction, since it learns from finite samples. The bias-variance decomposition $E[(\hat{f}(x) - f(x))^2] = \text{Bias}^2 + \text{Variance} + \text{Noise}$ shows that ML always has non-zero error — only justified when the alternative (manual rules) has even higher error.

The ML setup: given dataset $\mathcal{D} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ with features $\mathbf{x}_i \in \mathbb{R}^d$ and labels $y_i$, learn model $\hat{f}_\theta: \mathbb{R}^d \to \mathcal{Y}$ parameterized by $\theta$. Training minimizes $\hat{R}(\theta) = \frac{1}{n}\sum L(\hat{f}_\theta(x_i), y_i)$. Inference computes $\hat{y} = \hat{f}_\theta(x_{\text{new}})$ for unseen data. The number of parameters $|\theta|$ relative to training samples $n$ controls model capacity — when $|\theta| \gg n$, the model can memorize rather than generalize.

We observe a sample $\mathcal{D} = \{(x_i, y_i)\}$ drawn i.i.d. from an unknown population distribution $P(X, Y)$. ML approximates the true conditional $P(Y|X)$ using only the sample. The generalization error $R(\hat{f}) = E_{(x,y) \sim P}[L(\hat{f}(x), y)]$ depends on $P$, not just $\mathcal{D}$. Distribution shift occurs when the training distribution $P_{\text{train}}$ differs from deployment $P_{\text{deploy}}$, violating the core assumption. Domain adaptation techniques attempt to learn representations that are invariant to the shift.

Parametric models have a fixed number of parameters $|\theta|$ regardless of data size: linear regression has $d+1$ parameters whether trained on 100 or 1M samples. Non-parametric models grow with data: k-NN stores all $n$ training points, costing $O(nd)$ per prediction. The bias-variance tradeoff manifests differently: parametric models may underfit if the fixed form is wrong (high bias), while non-parametric models may overfit with small $n$ (high variance). Kernel methods and Gaussian processes are non-parametric models with elegant theoretical guarantees.