Home / Formulas / MLT

MLT formula sheet

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

Week 1 - PCA: finding the best view of your data

• Centre: $\mathbf x_i\leftarrow\mathbf x_i-\bar{\mathbf x}$; $C=\frac1nXX^T$
• Variance along unit $\mathbf w$: $\mathbf w^TC\mathbf w$; best $\mathbf w$: $C\mathbf w=\lambda\mathbf w$, top $\lambda$
• Coordinates $\mathbf z=W^T\mathbf x$; reconstruction $\hat{\mathbf x}=WW^T\mathbf x$
• Variance explained $=\frac{\lambda_1+\dots+\lambda_k}{\lambda_1+\dots+\lambda_d}$; error $=\lambda_{k+1}+\dots+\lambda_d$
• SVD link: $\lambda_j=\sigma_j^2/n$

Week 2 - Kernel PCA: curved views of data

• $k(\mathbf x,\mathbf y)=\phi(\mathbf x)^T\phi(\mathbf y)$; $(\mathbf x^T\mathbf y)^2\leftrightarrow\phi=(x_1^2,\sqrt2x_1x_2,x_2^2)$
• RBF: $\exp(-\|\mathbf x-\mathbf y\|^2/2\sigma^2)$; polynomial $(\mathbf x^T\mathbf y+c)^d$
• Valid $\iff$ $K=K^T$, $K\succeq0$
• Centring: $\tilde K=K-\mathbf 1_nK-K\mathbf 1_n+\mathbf 1_nK\mathbf 1_n$
• Coordinates on component $j$: $\sqrt{\mu_j}\,v_{j,i}$; variance along it $\mu_j/n$

Week 3 - K-means: grouping without labels

• $F=\sum_i\|\mathbf x_i-\boldsymbol\mu_{z_i}\|^2$; assign $z_i=\arg\min_k\|\mathbf x_i-\boldsymbol\mu_k\|^2$; update $\boldsymbol\mu_k=\text{mean}(C_k)$
• k-means++: $P(\mathbf x)=D(\mathbf x)^2/\sum D^2$; $E[F]\le8(\ln k+2)F_{opt}$
• Kernel distance: $k(\mathbf x,\mathbf x)-\frac2{|C|}\sum_jk(\mathbf x,\mathbf x_j)+\frac1{|C|^2}\sum_{j,l}k(\mathbf x_j,\mathbf x_l)$

Week 4 - MLE, Bayes, Gaussian mixtures and EM

• Beta posterior: $\text{Beta}(\alpha+h,\beta+t)$; mean $\frac{\alpha+h}{\alpha+\beta+n}$; MAP $\frac{\alpha+h-1}{\alpha+\beta+n-2}$; MLE $\frac hn$
• Beta mean $\frac\alpha{\alpha+\beta}$; variance $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$
• GMM: $p(\mathbf x)=\sum_k\pi_k\mathcal N(\mathbf x\mid\boldsymbol\mu_k,\Sigma_k)$
• $r_{ik}=\frac{\pi_k\mathcal N_k(\mathbf x_i)}{\sum_j\pi_j\mathcal N_j(\mathbf x_i)}$; $n_k=\sum_ir_{ik}$; $\pi_k=\frac{n_k}n$; $\boldsymbol\mu_k=\frac{\sum r_{ik}\mathbf x_i}{n_k}$; $\Sigma_k=\frac{\sum r_{ik}(\mathbf x_i-\boldsymbol\mu_k)(\cdot)^T}{n_k}$
• Parameters: full $K(d+\frac{d(d+1)}2)+K-1$; diagonal $2Kd+K-1$; spherical $K(d+1)+K-1$

Week 5 - Regression: least squares and its Bayesian view

• $\hat{\mathbf y}=X\mathbf w$; $\mathcal L=\|\mathbf y-X\mathbf w\|^2$; $\nabla\mathcal L=-2X^T(\mathbf y-X\mathbf w)$
• $\mathbf w^*=(X^TX)^{-1}X^T\mathbf y$; gradient step $\mathbf w\leftarrow\mathbf w+2\eta X^T(\mathbf y-X\mathbf w)$
• MSE $=\frac1n\sum(y_i-\hat y_i)^2$; $R^2=1-\frac{SS_{res}}{SS_{tot}}$
• LOOCV $=\frac1n\sum_i(y_i-\hat y^{(-i)}_i)^2$

Week 6 - Ridge and LASSO: taming overfitting

• Ridge: $\mathbf w=(X^TX+\lambda I)^{-1}X^T\mathbf y$; 1-D: $\frac{\sum xy}{\sum x^2+\lambda}$; per-feature shrink $\frac z{1+\lambda}$
• LASSO soft-threshold: $\operatorname{sign}(z)\max(|z|-\lambda/2,0)$
• MAP: Gaussian prior $\to\lambda=\sigma^2/\tau^2$ (ridge); Laplace prior $\to$ LASSO

Week 7 - k-NN and decision trees

• Euclidean distance $\|\mathbf x-\mathbf q\|$; k-NN regression: mean of $k$ neighbours
• Entropy $H=-\sum_cp_c\log_2p_c$ (50/50 gives 1; 75/25 gives 0.811)
• Gini $=1-\sum p_c^2$ (50/50 gives 0.5; 75/25 gives 0.375)
• $IG=H(\text{parent})-\sum_j\frac{n_j}{n}H(\text{child}_j)$

Week 8 - Generative models: Naive Bayes

• $P(y\mid\mathbf x)\propto P(y)\prod_jP(x_j\mid y)$
• Laplace: $\frac{\text{count}+1}{\text{total}+V}$ (words) or $\frac{\text{count}+1}{n_c+2}$ (yes/no)
• Parameters (binary): naive $Cd+C-1$; full $C(2^d-1)+C-1$
• Gaussian NB: $\mathcal N(x_j\mid\mu_{jc},\sigma^2_{jc})$ with class-wise MLE

Week 9 - Perceptron and logistic regression

• Perceptron: mistake if $y\mathbf w^T\mathbf x\le0$; update $\mathbf w\leftarrow\mathbf w+y\mathbf x$; mistakes $\le(R/\gamma)^2$
• Logistic: $p=\sigma(\mathbf w^T\mathbf x)=\frac1{1+e^{-\mathbf w^T\mathbf x}}$; $\ln\frac p{1-p}=\mathbf w^T\mathbf x$
• Loss $-\sum[y\ln p+(1-y)\ln(1-p)]$; gradient $\sum(p_i-y_i)\mathbf x_i$; step $\mathbf w\leftarrow\mathbf w-\eta\nabla\mathcal L$

Week 10 - Support vector machines

• Primal: $\min\frac12\|\mathbf w\|^2+C\sum\xi_i$ s.t. $y_i(\mathbf w^T\mathbf x_i+b)\ge1-\xi_i$, $\xi_i\ge0$
• Margin $=\frac{2}{\|\mathbf w\|}$
• Dual: $\max\sum\alpha_i-\frac12\sum_{ij}\alpha_i\alpha_jy_iy_jk(\mathbf x_i,\mathbf x_j)$; $0\le\alpha_i\le C$; $\sum\alpha_iy_i=0$
• $\mathbf w=\sum\alpha_iy_i\mathbf x_i$; $f(\mathbf x)=\sum\alpha_iy_ik(\mathbf x_i,\mathbf x)+b$
• Hinge loss: $\max(0,1-y f(\mathbf x))$

Week 11 - Bagging, boosting and AdaBoost

• Average of $n$ independent: $\sigma^2/n$; correlated: $\rho\sigma^2+\frac{1-\rho}n\sigma^2$
• OOB probability $(1-\frac1n)^n\to e^{-1}\approx0.368$
• AdaBoost: $\varepsilon_t=\sum_{\text{wrong}}w_i$; $\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}$; $w_i\leftarrow w_ie^{-\alpha_ty_ih_t(\mathbf x_i)}$; $H=\operatorname{sign}\sum\alpha_th_t$

Week 12 - Neural networks

• $\mathbf h=g(W\mathbf x+\mathbf b)$; ReLU $\max(0,z)$; sigmoid $\frac1{1+e^{-z}}$ with derivative $\sigma(1-\sigma)$
• Softmax $p_k=e^{z_k}/\sum_je^{z_j}$; loss $-\ln p_{y}$
• Parameters per layer: $mn+n$
• Chain rule: $\frac{\partial L}{\partial w_1}=\frac{\partial L}{\partial\hat y}\frac{\partial\hat y}{\partial h}\frac{\partial h}{\partial w_1}$