Formula & theorem reference
Concept clusters →Every named result in this course, grouped by chapter. Each one links back to where it's derived.
Readiness review
Theorem
Bayes' Theorem
For events A and B with P(B) \neq 0, P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}.
Show proof
The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.
Formula
The Gradient Descent Update Rule
To search for a local minimum of a differentiable function f, starting from a point \mathbf{x}_0, repeat \mathbf{x}_{n+1} = \mathbf{x}_n - \alpha\,\nabla f(\mathbf{x}_n), where \alpha>0 is a fixed (or shrinking) learning rate. Each step moves from \mathbf{x}_n a small distance in the direction of steepest descent, -\nabla f(\mathbf{x}_n), and stops improving (to first order) once \nabla f(\mathbf{x}_n)\approx\mathbf{0}.
Linear regression and regularization
Theorem
The Normal Equations
For a matrix A and vector \mathbf b, every least-squares solution \hat{\mathbf x} of A\mathbf x = \mathbf b satisfies
A^{\mathsf T} A \hat{\mathbf x} = A^{\mathsf T} \mathbf bShow proof
A least-squares solution \hat{\mathbf x} is, by definition, a minimizer of \lVert A\mathbf x - \mathbf b \rVert over all \mathbf x — equivalently, a vector for which A\hat{\mathbf x} is the point of \operatorname{Col}(A) closest to \mathbf b. The closest-point characterization of a projection says exactly that the residual \mathbf b - A\hat{\mathbf x} must be orthogonal to \operatorname{Col}(A): no vector in that column space can be nearer to \mathbf b than its orthogonal projection, so if the residual had any component lying in \operatorname{Col}(A), subtracting that component would move A\hat{\mathbf x} closer to \mathbf b still, contradicting minimality.
Orthogonality to every vector in \operatorname{Col}(A) means orthogonality to every column of A in particular, since those columns span \operatorname{Col}(A). Writing \mathbf a_1, \dots, \mathbf a_n for the columns of A, this is the system of dot-product conditions
\mathbf a_j \cdot \left(\mathbf b - A\hat{\mathbf x}\right) = 0, \qquad j = 1, \dots, n.Stacking these n scalar equations into one vector equation is precisely what A^{\mathsf T} does: the j-th row of A^{\mathsf T} is \mathbf a_j^{\mathsf T}, so left-multiplying by A^{\mathsf T} produces a vector whose j-th entry is \mathbf a_j \cdot (\mathbf b - A\hat{\mathbf x}). Since every one of those entries is 0,
A^{\mathsf T}\left(\mathbf b - A\hat{\mathbf x}\right) = \mathbf 0.Distributing A^{\mathsf T} across the difference and moving the A^{\mathsf T} A \hat{\mathbf x} term to the other side gives
A^{\mathsf T} A \hat{\mathbf x} = A^{\mathsf T} \mathbf b.Sanity check: if \mathbf b already lies in \operatorname{Col}(A), the system A\mathbf x = \mathbf b is consistent and any exact solution \mathbf x^* leaves residual \mathbf b - A\mathbf x^* = \mathbf 0, which is trivially orthogonal to every column of A — so \mathbf x^* satisfies the normal equations too, and least squares reduces to ordinary solving exactly when there's no error left to minimize.
Theorem
The Bias-Variance Decomposition
also known as: the bias-variance tradeoff, formally
Fit a model \hat{f} to random training data. Use it to predict at a fixed point x, where the true value is y = f(x) + \varepsilon -- irreducible noise, with mean 0 and variance \sigma^2. The expected squared prediction error then decomposes exactly as \mathbb{E}\big[(y - \hat{f}(x))^2\big] \;=\; \underbrace{\sigma^2}_{\text{irreducible error}} \;+\; \underbrace{\big(\mathbb{E}[\hat{f}(x)] - f(x)\big)^2}_{\text{bias}^2} \;+\; \underbrace{\operatorname{Var}\big[\hat{f}(x)\big]}_{\text{variance}}. The expectation is taken over different random draws of the training data. It asks: if this exact model-fitting procedure ran on many different training sets, how would its predictions at x behave?
Show proof
Write \hat{f} = \hat{f}(x) and f = f(x) for brevity, and let \bar f = \mathbb{E}[\hat f]. Since y = f + \varepsilon, with \varepsilon independent of \hat f and \mathbb{E}[\varepsilon] = 0: \mathbb{E}[(y-\hat f)^2] = \mathbb{E}[(f + \varepsilon - \hat f)^2] = \mathbb{E}[\varepsilon^2] + \mathbb{E}[(f-\hat f)^2] + 2\,\mathbb{E}[\varepsilon(f-\hat f)]. The last term vanishes, since \varepsilon is independent of \hat f and mean-zero. For the middle term, insert and subtract \bar f: \mathbb{E}[(f-\hat f)^2] = \mathbb{E}[((f-\bar f) - (\hat f - \bar f))^2] = (f-\bar f)^2 - 2(f-\bar f)\,\mathbb{E}[\hat f - \bar f] + \mathbb{E}[(\hat f - \bar f)^2]. The middle cross term vanishes too. That's because \mathbb{E}[\hat f - \bar f] = 0 by definition of \bar f. What's left is (f - \bar f)^2 + \operatorname{Var}[\hat f] -- the squared bias plus the variance. Combine this with \mathbb{E}[\varepsilon^2] = \sigma^2 to get the stated identity.
Classification foundations: logistic regression, generative classifiers, and KNN
Theorem
Bayes' Theorem
For events A and B with P(B) \neq 0, P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)}.
Show proof
The Conditional Probability formula, applied to P(A\mid B) and to P(B\mid A) separately, gives two ways to write the same joint probability: P(A\text{ and }B) = P(A\mid B)\,P(B), \qquad P(A\text{ and }B) = P(B\mid A)\,P(A). Both right-hand sides equal the same quantity, so they equal each other: P(A\mid B)\,P(B) = P(B\mid A)\,P(A). Dividing both sides by P(B) (nonzero by hypothesis) isolates P(A\mid B): P(A\mid B) = \frac{P(B\mid A)\,P(A)}{P(B)}.
Unsupervised learning: clustering and dimensionality reduction
Theorem
The EM Algorithm's Monotonic Likelihood Guarantee
also known as: EM never decreases the likelihood
Let \theta^{(t)} denote the parameters after t iterations of the Expectation-Maximization (EM) algorithm applied to a latent-variable model with observed data X and latent variables Z. Then the observed-data log-likelihood is non-decreasing across iterations: \ell(\theta^{(t+1)}) \;\geq\; \ell(\theta^{(t)}), \qquad \ell(\theta) = \log p(X \mid \theta).
Show proof
For any distribution q(Z) over the latent variables, Jensen's inequality applied to the concave \log function gives a lower bound (the "evidence lower bound," ELBO) on the log-likelihood: \ell(\theta) = \log \sum_Z p(X, Z \mid \theta) = \log \sum_Z q(Z) \frac{p(X,Z\mid\theta)}{q(Z)} \;\geq\; \sum_Z q(Z) \log \frac{p(X,Z\mid\theta)}{q(Z)} =: \mathcal{L}(q,\theta). Equality holds exactly when q(Z) = p(Z \mid X, \theta), the true posterior over the latent variables given the current parameters. The E-step sets q^{(t)}(Z) = p(Z \mid X, \theta^{(t)}) — the posterior/responsibilities under \theta^{(t)} — which makes the bound tight at \theta^{(t)}: \mathcal{L}(q^{(t)}, \theta^{(t)}) = \ell(\theta^{(t)}). The M-step then chooses \theta^{(t+1)} = \arg\max_\theta \mathcal{L}(q^{(t)}, \theta), so in particular \mathcal{L}(q^{(t)}, \theta^{(t+1)}) \geq \mathcal{L}(q^{(t)}, \theta^{(t)}). Chaining these three facts: \ell(\theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t)}, \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t)}, \theta^{(t)}) \;=\; \ell(\theta^{(t)}), where the first inequality is the Jensen bound applied at \theta^{(t+1)} (the bound holds for any q, not just the tight one) and the second is the M-step's own optimality. The likelihood therefore never decreases across an EM iteration.