Chapter 2 · Part I: Foundations
The Math You Need, Seen Through ML
You already know calculus, linear algebra, and probability. This chapter shows which parts machine learning uses constantly, in this book's notation, and adds a few tools standard courses skip: gradients with respect to vectors, maximum likelihood, and cross-entropy.
After this chapter you will be able to
- Represent a data set as a design matrix and predictions as a matrix–vector product.
- Compute projections and use eigendecompositions of symmetric matrices.
- Take gradients of scalar functions of vectors and apply the chain rule with Jacobians.
- Use Bayes' rule and explain the base-rate effect.
- Derive maximum likelihood estimates and connect them to loss functions.
- Define entropy, cross-entropy, and KL divergence.
2.1Data as Vectors and Matrices
One example is a column vector $\vx\in\R^d$. A data set stacks examples as the rows of the design matrix $\mX\in\R^{n\times d}$; labels form $\vy\in\R^n$. A linear model predicts every example at once:
$$\hat\vy = \mX\vw. \tag{2.1}$$Entry $i$ of $\mX\vw$ is the dot product of row $i$ with $\vw$. This batched form is also how code runs fast: one matrix multiply is hundreds of times faster than a Python loop.
- Bias trick. Append a constant feature 1 to each example so $\vw\T\vx + b$ becomes $\tilde\vw\T\tilde\vx$ with $\tilde\vx = (\vx, 1)$, $\tilde\vw = (\vw, b)$.
- Cosine similarity. $\vu\T\vv = \norm{\vu}\norm{\vv}\cos\phi$, so $\vu\T\vv/(\norm{\vu}\norm{\vv})$ compares directions only. It is the basic similarity for embeddings and retrieval (Chapter 19, Chapter 24).
- Norms. $\norm{\vx}_2 = \sqrt{\sum_j x_j^2}$ and $\norm{\vx}_1 = \sum_j|x_j|$ both reappear as regularization penalties, with very different effects (Chapter 5).
2.2Projections and Eigendecompositions
The closest point to $\vy$ on the line through $\va$ is $c^\star\va$ with
$$c^\star = \frac{\va\T\vy}{\va\T\va}, \qquad \mathrm{proj}_{\va}(\vy) = \frac{\va\T\vy}{\va\T\va}\,\va. \tag{2.2}$$The residual $\vy - c^\star\va$ is orthogonal to $\va$. "The error is orthogonal to everything you could have used" is the geometric heart of least squares (Chapter 4).
Spectral theorem. A real symmetric matrix factors as
$$\mA = \mU\mathbf\Lambda\mU\T = \sum_{j=1}^d\lambda_j\vu_j\vu_j\T, \tag{2.3}$$with orthonormal eigenvectors $\vu_j$ and real eigenvalues $\lambda_j$: $\mA$ stretches space by $\lambda_j$ along $\vu_j$. It is positive semidefinite (PSD) if $\vv\T\mA\vv\ge 0$ for all $\vv$, equivalently all $\lambda_j\ge0$. Every $\mB\T\mB$ is PSD because $\vv\T\mB\T\mB\vv = \norm{\mB\vv}^2$; so are $\mX\T\mX$ and every covariance matrix.
2.3Gradients, Jacobians, and the Chain Rule
For $f:\R^d\to\R$, the gradient is the unique vector with $f(\vx + \vv) = f(\vx) + \nabla f(\vx)\T\vv + o(\norm{\vv})$. That gives a fast recipe: expand $f(\vx+\vv)$, keep the terms linear in $\vv$, and read off the vector multiplying $\vv$.
Example: three identities used everywhere
- $f(\vx) = \va\T\vx$ gives $\nabla f = \va$.
- $f(\vx) = \vx\T\mA\vx$: the linear terms of $f(\vx+\vv)$ are $\vv\T\mA\vx + \vx\T\mA\vv$, so $\nabla f = (\mA + \mA\T)\vx$, which is $2\mA\vx$ for symmetric $\mA$.
- $f(\vw) = \norm{\mX\vw-\vy}^2$: with $\vr = \mX\vw-\vy$, $f(\vw+\vv) = \norm{\vr}^2 + 2\vr\T\mX\vv + \norm{\mX\vv}^2$, so $$\nabla_{\vw}\norm{\mX\vw - \vy}_2^2 = 2\mX\T(\mX\vw-\vy). \tag{2.4}$$
Read (2.4) as "residuals mapped back to feature space by $\mX\T$": each example pushes the weights along its own feature vector, scaled by how wrong it is. The Hessians of the three examples are $\mathbf 0$, $\mA + \mA\T$, and $2\mX\T\mX$.
Jacobians and the chain rule. For $\vg:\R^m\to\R^k$, the Jacobian $\mathbf J_{\vg}\in\R^{k\times m}$ holds $\partial g_i/\partial x_j$. For a scalar loss $L = f(\vg(\vx))$:
$$\nabla_{\vx}L = \mathbf J_{\vg}(\vx)\T\,\nabla f(\vg(\vx)). \tag{2.5}$$The gradient flows backward: first how $L$ depends on the intermediate $\vg$, then multiplied by the transposed Jacobian. Repeating this through many layers is backpropagation (Chapter 15).
Example: chain rule for a linear model
For $L = \tfrac12(\vw\T\vx - y)^2$, set $z = \vw\T\vx$. Then $\partial L/\partial z = z - y$ and $\nabla_{\vw}z = \vx$, so $\nabla_{\vw}L = (z-y)\,\vx$.
2.4Probability Refresher
- Expectation is always linear: $\E[aX + bY] = a\E X + b\E Y$. Variance $\Var(X) = \E[X^2] - (\E X)^2$ adds for independent variables.
- A random vector has mean $\vmu = \E\vx$ and covariance $\mSigma = \E[(\vx-\vmu)(\vx-\vmu)\T]$; for fixed $\mA$, $\Cov(\mA\vx) = \mA\mSigma\mA\T$.
- Bernoulli$(\pi)$: $p(x) = \pi^x(1-\pi)^{1-x}$ for binary labels. Categorical$(\boldsymbol\pi)$: $p(k) = \pi_k$ for multi-class labels and next tokens.
- Gaussian: $p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\!\big(-\frac{(x-\mu)^2}{2\sigma^2}\big)$. Multivariate: $p(\vx) \propto \exp\!\big(-\tfrac12(\vx-\vmu)\T\mSigma^{-1}(\vx-\vmu)\big)$, with elliptical contours along the eigenvectors of $\mSigma$.
- For independent examples the joint probability factorizes: $p(\vx^{(1)},\dots,\vx^{(n)}) = \prod_i p(\vx^{(i)})$.
2.5Bayes' Rule
The prior $p(h)$ is the belief before the evidence, the likelihood $p(e\mid h)$ says how probable the evidence is under $h$, and the posterior $p(h\mid e)$ is the updated belief.
Example: the base-rate effect
A disease affects 1% of people. A test catches 95% of cases and false-alarms on 5% of healthy people. Given a positive test,
$$p(\text{sick}\mid +) = \frac{0.95\times0.01}{0.95\times0.01 + 0.05\times0.99} \approx 0.16.$$Among 10,000 people, 95 sick people test positive, but so do 495 healthy ones.
The same effect appears whenever a classifier hunts for something rare, like fraud: high accuracy does not make a positive prediction trustworthy. Chapter 6 formalizes this with precision and recall.
2.6Maximum Likelihood Estimation
For i.i.d. data from $p(x\mid\vtheta)$, the likelihood $\prod_i p(x^{(i)}\mid\vtheta)$ is the probability of the observed data as a function of $\vtheta$. The maximum likelihood estimate maximizes it, or equivalently minimizes the average negative log-likelihood:
$$\hat\vtheta_{\mathrm{MLE}} = \argmin_{\vtheta}\; -\frac1n\sum_{i=1}^n\log p(x^{(i)}\mid\vtheta). \tag{2.7}$$Key idea: losses are negative log-likelihoods
Minimizing the average negative log-likelihood is empirical risk minimization with $\ell = -\log p$. Squared error comes from Gaussian noise (Chapter 4), cross-entropy from Bernoulli and categorical labels (Chapter 6), and the training loss of language models from a categorical distribution over the next token (Chapter 24).
Show derivation: MLE for a Gaussian and for a coin
Gaussian: $\ell(\mu,\sigma^2) = -\frac n2\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\sum_i(x^{(i)}-\mu)^2$. Setting $\partial\ell/\partial\mu = 0$ gives $\hat\mu = \bar x$; setting $\partial\ell/\partial\sigma^2 = -\frac{n}{2\sigma^2} + \frac{1}{2\sigma^4}\sum_i(x^{(i)}-\mu)^2 = 0$ gives $\hat\sigma^2 = \frac1n\sum_i(x^{(i)}-\bar x)^2$.
Coin with $k$ heads in $n$ flips: $\ell(\pi) = k\log\pi + (n-k)\log(1-\pi)$, and $\ell'(\pi) = 0$ gives $\hat\pi = k/n$.
Priors and MAP. With a prior $p(\vtheta)$, the posterior is $p(\vtheta\mid\Data)\propto p(\Data\mid\vtheta)p(\vtheta)$. Its maximizer (MAP) minimizes the negative log-likelihood plus $-\log p(\vtheta)$. A Gaussian prior on the weights adds a squared-norm penalty: ridge regression (Chapter 5).
2.7Information Theory in One Page
- Entropy $H(p) = -\sum_x p(x)\log p(x)$ measures uncertainty: $\log 2$ for a fair coin, 0 for a certain outcome.
- Cross-entropy $H(p,q) = -\sum_x p(x)\log q(x)$ is the average negative log-probability model $q$ gives to outcomes from $p$.
- KL divergence $D_{\mathrm{KL}}(p\Vert q) = \sum_x p(x)\log\frac{p(x)}{q(x)} = H(p,q) - H(p) \ge 0$, with equality only when $q = p$. It is not symmetric.
Show derivation: why KL is nonnegative
$\log$ is concave, so by Jensen's inequality $-D_{\mathrm{KL}}(p\Vert q) = \sum_x p(x)\log\frac{q(x)}{p(x)} \le \log\sum_x p(x)\frac{q(x)}{p(x)} = \log 1 = 0.$
Key idea: why cross-entropy is the right classification loss
If $p$ is the empirical distribution of training labels, a model's average negative log-likelihood is exactly $H(p,q)$. Since $H(p)$ is fixed, minimizing cross-entropy minimizes $D_{\mathrm{KL}}(p\Vert q)$: it pulls the model's distribution toward the data's.
2.8Summary
- A data set is a design matrix $\mX$; a linear model predicts all examples as $\mX\vw$.
- Projection residuals are orthogonal to what was projected onto; symmetric matrices factor as $\mU\mathbf\Lambda\mU\T$.
- Gradients: expand and read off the linear term. $\nabla(\va\T\vx) = \va$, $\nabla(\vx\T\mA\vx) = (\mA+\mA\T)\vx$, $\nabla\norm{\mX\vw-\vy}^2 = 2\mX\T(\mX\vw-\vy)$.
- The chain rule multiplies transposed Jacobians, propagating gradients backward.
- Bayes' rule combines prior and likelihood; rare events make positives less conclusive than they look.
- Maximum likelihood minimizes average negative log-likelihood; minimizing cross-entropy minimizes KL divergence to the data.
2.9Exercises
- MathShow that $\nabla\norm{\vx}_2 = \vx/\norm{\vx}_2$ for $\vx\neq\mathbf 0$. What happens at $\mathbf 0$?
- MathFor $\vs = \softmax(\vz)$, show $\partial s_k/\partial z_j = s_k(\mathbb 1[k=j] - s_j)$, i.e. the Jacobian is $\diag(\vs) - \vs\vs\T$.
- MathFor PSD $\mA$, show $\max_{\norm{\vv}=1}\vv\T\mA\vv = \lambda_{\max}$, attained at the top eigenvector.
- MathA spam filter flags 98% of spam and 1% of legitimate mail. If 20% of mail is spam, what fraction of flagged mail is legitimate? What if 2% is spam?
- MathFind the MLE of $\lambda$ for i.i.d. samples from $p(x) = \lambda e^{-\lambda x}$, $x\ge0$.
- MathCompute $D_{\mathrm{KL}}(p\Vert q)$ and $D_{\mathrm{KL}}(q\Vert p)$ for $p = (0.9, 0.1)$, $q = (0.5, 0.5)$.
- CodingVerify Equation (2.4) numerically with central finite differences, $h = 10^{-5}$. Keep this gradient check habit for every gradient you derive by hand.