Home / Formulas / MLF

MLF formula sheet

Collected automatically from the lessons. Print it, or read it the night before.

Week 1 - What is machine learning, and which maths do we need?

• Norm: $\|v\|=\sqrt{v_1^2+\dots+v_n^2}$
• Distance: $\|a-b\|$
• Dot product: $a\cdot b=\sum_i a_ib_i=\|a\|\|b\|\cos\theta$; perpendicular $\iff a\cdot b=0$
• Cauchy-Schwarz: $|a\cdot b|\le\|a\|\|b\|$
• Unit vector: $\hat v=v/\|v\|$
• Squared loss: $(y-\hat y)^2$; MSE $=\frac1n\sum(y_i-\hat y_i)^2$
• 0-1 loss: $1$ if $y\ne\hat y$, else $0$; average = fraction of mistakes

Week 2 - Slopes, change and the steepest way up

• Derivative: $f'(a)=\lim_{h\to0}\frac{f(a+h)-f(a)}{h}$
• Power: $(x^n)'=nx^{n-1}$; chain: $(f(g))'=f'(g)g'$; product: $(fg)'=f'g+fg'$
• Linear approximation: $L(x)=f(a)+f'(a)(x-a)$
• Two variables: $L(x,y)=f(a,b)+f_x(a,b)(x-a)+f_y(a,b)(y-b)$
• Gradient: $\nabla f=(f_x,f_y)$; directional derivative $D_{\mathbf u}f=\nabla f\cdot\mathbf u$, $\|\mathbf u\|=1$
• Steepest rate: $\|\nabla f\|$ along $\nabla f$

Week 3 - Vectors, matrices and the best-fit line

• $A\mathbf x=x_1\,\text{col}_1+\dots+x_n\,\text{col}_n$
• rank + nullity $=n$; left-null dimension $=m-r$
• Projection onto line: $\frac{\mathbf a\cdot\mathbf x}{\mathbf a\cdot\mathbf a}\mathbf a$; matrix $\frac{\mathbf a\mathbf a^T}{\mathbf a^T\mathbf a}$
• Projection onto $\text{col}(A)$: $P=A(A^TA)^{-1}A^T$; $P^2=P=P^T$; $\text{rank}P=\text{trace}P$
• Normal equations: $A^TA\mathbf w=A^T\mathbf y$; $\mathbf w=(A^TA)^{-1}A^T\mathbf y$
• $\text{rank}(AB)\le\min(\text{rank}A,\text{rank}B)$

Week 4 - The special directions of a matrix

• $A\mathbf v=\lambda\mathbf v$, $\det(A-\lambda I)=0$
• $2\times2$: $\lambda^2-(\operatorname{tr}A)\lambda+\det A=0$
• $\sum\lambda_i=\operatorname{tr}A$, $\prod\lambda_i=\det A$
• $A^{-1}:1/\lambda$; $A^k:\lambda^k$; $A+cI:\lambda+c$; $A^T:\lambda$
• $A=PDP^{-1}$, $A^k=PD^kP^{-1}$

Week 5 - Symmetric matrices: the well-behaved ones

• Spectral theorem: $A=A^T\Rightarrow A=Q\Lambda Q^T$, $Q^TQ=I$, $\lambda_i\in\mathbb R$
• Quadratic form $q(\mathbf x)=\mathbf x^TA\mathbf x=\sum\lambda_iy_i^2$
• PD $\iff$ all $\lambda>0$ $\iff$ all leading minors $>0$; PSD $\iff$ all $\lambda\ge0$
• Orthogonal: $Q^TQ=I$, $\|Q\mathbf x\|=\|\mathbf x\|$, $\det Q=\pm1$
• Hermitian: $A^*=A$; unitary: $U^*U=I$; Schur: $A=UTU^*$

Week 6 - SVD and PCA: squeezing data

• $A=U\Sigma V^T=\sum_i\sigma_i\mathbf u_i\mathbf v_i^T$; $\sigma_i=\sqrt{\lambda_i(A^TA)}$; $\text{rank}A=\#\{\sigma_i\ne0\}$
• Rank-$k$ storage: $k(m+n+1)$; error $\|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2$
• Covariance (centred): $C=\frac1nXX^T$; variance along unit $\mathbf u$: $\mathbf u^TC\mathbf u$
• Variance explained: $\frac{\sum_{i\le k}\lambda_i}{\sum_i\lambda_i}$; reconstruction error: $\sum_{i>k}\lambda_i$
• $\lambda_i(C)=\sigma_i^2/n$

Week 7 - Finding the lowest point: gradient descent

• Critical point: $\nabla f(\mathbf x^*)=0$; Hessian $H_{ij}=\partial^2f/\partial x_i\partial x_j$
• Gradient descent: $\mathbf x_{t+1}=\mathbf x_t-\eta\nabla f(\mathbf x_t)$
• Quadratic bowl $\frac a2x^2$: $x_{t+1}=(1-\eta a)x_t$; stable iff $0<\eta<2/a$
• Descent direction: $\nabla f\cdot\mathbf d<0$
• Newton: $\mathbf x_{t+1}=\mathbf x_t-H^{-1}\nabla f$
• Least squares gradient: $\nabla\|X\mathbf w-\mathbf y\|^2=2X^T(X\mathbf w-\mathbf y)$

Week 8 - Bowls, not bumpy hills: convexity

• Convex set: $\theta\mathbf x+(1-\theta)\mathbf y\in S$ for $\theta\in[0,1]$
• Convex function: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$
• 1-D: $f''\ge0$; many variables: $H\succeq0$ (PSD); strictly convex: $H\succ0$
• First-order: $f(\mathbf y)\ge f(\mathbf x)+\nabla f(\mathbf x)\cdot(\mathbf y-\mathbf x)$
• Jensen: $f(E[X])\le E[f(X)]$
• Epigraph: $\{(\mathbf x,t):t\ge f(\mathbf x)\}$ convex $\iff f$ convex

Week 9 - Optimising with rules: Lagrange and KKT

• Lagrange: $\nabla f=\lambda\nabla g$, $g=c$; Lagrangian $L=f-\lambda(g-c)$
• KKT ($g\le0$): $\nabla f+\mu\nabla g=0$; $g\le0$; $\mu\ge0$; $\mu g=0$
• Distance$^2$ from origin to $\mathbf a^T\mathbf x=b$: $b^2/\|\mathbf a\|^2$; closest point $=\frac{b}{\|\mathbf a\|^2}\mathbf a$
• LP: optimum at a vertex of the feasible region
• Sigmoid: $\sigma(z)=\frac1{1+e^{-z}}$; log-loss $-\frac1n\sum[y\log p+(1-y)\log(1-p)]$; gradient $\frac1n\sum(p_i-y_i)\mathbf x_i$

Week 10 - Probability for machine learning

• $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$; Bayes $P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}$
• $\operatorname{Var}X=E[X^2]-(E[X])^2$; $\operatorname{Cov}(X,Y)=E[XY]-E[X]E[Y]$
• Binomial: $np$, $np(1-p)$; Uniform: $\frac{a+b}2$, $\frac{(b-a)^2}{12}$; Exponential: $\frac1\lambda$, $\frac1{\lambda^2}$, $P(X>t)=e^{-\lambda t}$
• $aX+b\sim N(a\mu+b,a^2\sigma^2)$; independent sum: means and variances add
• Markov: $P(X\ge a)\le E[X]/a$; Chebyshev: $P(|X-\mu|\ge k\sigma)\le1/k^2$
• Sample mean: $E=\mu$, $\operatorname{Var}=\sigma^2/n$; WLLN: $P(|\bar X_n-\mu|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2}$

Week 11 - The exponential family

• $p(x\mid\eta)=h(x)\exp(\eta T(x)-A(\eta))$
• $E[T]=A'(\eta)$, $\operatorname{Var}[T]=A''(\eta)$
• MLE: $A'(\hat\eta)=\frac1n\sum_iT(x_i)$
• Bernoulli $\hat p=\bar x$; Poisson $\hat\lambda=\bar x$; Exponential $\hat\lambda=1/\bar x$
• Logit: $\eta=\ln\frac p{1-p}$; inverse: $p=\frac1{1+e^{-\eta}}$

Week 12 - Estimating parameters, and EM

• $L(\theta)=\prod p(x_i\mid\theta)$, $\ell=\sum\ln p(x_i\mid\theta)$, $\ell'(\hat\theta)=0$
• Normal: $\hat\mu=\bar x$, $\hat\sigma^2_{MLE}=\frac1n\sum(x_i-\bar x)^2$; unbiased $\frac1{n-1}\sum$
• Uniform$(0,\theta)$: $\hat\theta=\max x_i$; Exponential: $\hat\lambda=1/\bar x$
• MAP: $\arg\max p(\text{data}\mid\theta)p(\theta)$
• EM: $r_{ik}=\frac{\pi_kp_k(x_i)}{\sum_j\pi_jp_j(x_i)}$; $\pi_k=\frac{\sum_ir_{ik}}n$; $\mu_k=\frac{\sum r_{ik}x_i}{\sum r_{ik}}$