Machine Learning Techniques (BSCS2007) formula sheet

$\text{MSE} = \frac{1}{n} \sum_{i=1}^{n} \left( f(x^{(i)}) - y^{(i)} \right)^2$

$\text{Avg. Misclassification Error} = \frac{\text{number of wrongly classified points}}{\text{total points}}$

$\text{Classification: } y \in \{c_1, c_2, \ldots, c_k\}, \quad k < \infty$

$\text{Regression: } y \in \mathbb{R} \text{ (or } \mathbb{R}^d\text{)}$

$c^* = \frac{x_1 w_1 + x_2 w_2}{w_1^2 + w_2^2} = \frac{\mathbf{x}^T \mathbf{w}}{\|\mathbf{w}\|^2}$

$\text{If } \|\mathbf{w}\| = 1, \quad c^* = \mathbf{x}^T \mathbf{w}, \quad \text{proxy} = (\mathbf{x}^T \mathbf{w})\,\mathbf{w}$

$\max_{\mathbf{w}: \|\mathbf{w}\|^2 = 1} \; \mathbf{w}^T C \mathbf{w}, \quad \text{where } C = \frac{1}{n}\sum_{i=1}^{n} x_i x_i^T$

$\mathbf{w}^* = \text{eigenvector of } C \text{ corresponding to its largest eigenvalue}$

$w_1 = \arg\max_{\|w\|^2 = 1}\; w^T C w, \quad C = \frac{1}{n}\sum_{i=1}^n x_i x_i^T$

$x_i' = x_i - (x_i^T w_1)\,w_1$

$C w_k = \lambda_k w_k$

$\lambda_k = w_k^T C w_k = \frac{1}{n}\sum_{i=1}^n (x_i^T w_k)^2$

$\frac{\sum_{i=1}^{l} \lambda_i(C)}{\sum_{i=1}^{d} \lambda_i(C)} \geq 0.95$

$\frac{\lambda_1}{\lambda_1 + \lambda_2} = \frac{3}{4} = 0.75$

$\mathbf{x}_i \in \mathbb{R}^{mn}, \quad \text{dataset } X \in \mathbb{R}^{N \times mn}$

$\hat{\mathbf{x}} = \bar{\mathbf{x}} + \sum_{k=1}^{r} (\mathbf{x} - \bar{\mathbf{x}})^\top \mathbf{u}_k \cdot \mathbf{u}_k$

$\text{Compression ratio} = \frac{d}{r} = \frac{32{,}000}{300} \approx 107$

$\underbrace{\mathbf{x} \in \mathbb{R}^{32000}}_{\text{raw image}} \xrightarrow{\text{project onto top }r\text{ eigenfaces}} \underbrace{\mathbf{z} \in \mathbb{R}^{r}}_{\text{compressed code}} \xrightarrow{\text{classifier}} \underbrace{\hat{y}}_{\text{identity}}$

$\text{Time for PCA} \sim \mathcal{O}(d^3)$

$C = \frac{1}{n} \sum_{i=1}^{n} x_i x_i^T = \frac{1}{n} X X^T$

$w_k = X \alpha_k, \quad \alpha_k \in \mathbb{R}^n$

$K = X^T X, \quad K \in \mathbb{R}^{n \times n}, \quad K_{ij} = x_i^T x_j$

$K \alpha_k = n \lambda_k \alpha_k$

$\|w_k\|^2 = \|X \alpha_k\|^2 = \alpha_k^T X^T X \alpha_k = \alpha_k^T K \alpha_k$

$\alpha_k = \frac{\beta_k}{\sqrt{n \lambda_k}}$

$\textbf{Step 1: } K = X^T X \in \mathbb{R}^{n \times n}, \quad K_{ij} = x_i^T x_j$

$\textbf{Step 2: } K \beta_k = n\lambda_k \beta_k, \quad k = 1, \ldots, l$

$\textbf{Step 3: } \alpha_k = \frac{\beta_k}{\sqrt{n \lambda_k}}, \quad w_k = X \alpha_k$

$(f_1 - a)^2 + (f_2 - b)^2 = r^2$

$f_1^2 + f_2^2 - 2a f_1 - 2b f_2 + (a^2 + b^2 - r^2) = 0$

$\phi(f_1, f_2) = \begin{bmatrix} 1 \\ f_1 \\ f_2 \\ f_1^2 \\ f_1 f_2 \\ f_2^2 \end{bmatrix} \in \mathbb{R}^6$

$u = \begin{bmatrix} a^2+b^2-r^2 \\ -2a \\ -2b \\ 1 \\ 0 \\ 1 \end{bmatrix}$

$u^T \phi(x) = f_1^2 + f_2^2 - 2af_1 - 2bf_2 + (a^2+b^2-r^2) = 0$

$D = \sum_{i=0}^{p} \binom{d}{i}$

$u = \begin{bmatrix} a^2+b^2-r^2 \\ -2a \\ -2b \\ 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1+4-5 \\ -2 \\ -4 \\ 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -2 \\ -4 \\ 1 \\ 0 \\ 1 \end{bmatrix}$

$\phi(x) = [x_1^2,\; x_2^2,\; 1,\; \sqrt{2}\,x_1 x_2,\; \sqrt{2}\,x_1,\; \sqrt{2}\,x_2]$

$k(x, x') = (x^T x' + 1)^p, \quad p \geq 1$

$k(x, x') = e^{-\gamma \|x - x'\|^2}, \quad \gamma > 0$

$k \text{ is a valid kernel} \iff \begin{cases} \text{(A)} & k(x, x') = k(x', x) \text{ for all } x, x' \quad (\text{symmetry}) \\ \text{(B)} & \text{For any dataset } \{x_1, \ldots, x_n\}, \text{ the matrix } K \text{ with } K_{ij} = k(x_i, x_j) \text{ is positive semi-definite} \end{cases}$

$K_{ij} = k(x_i, x_j), \quad K \text{ is PSD } \iff \text{all eigenvalues of } K \geq 0$

$\phi([x_1, x_2]^T) = [1,\; x_1,\; x_2,\; x_1^2 x_2,\; x_1 x_2^2]$

$K_{ij} = K(x_i, x_j) \quad \text{for all } i, j \in \{1, \ldots, n\}$

$y_i^{(k)} = w_k^T \phi(x_i) = \sum_{j=1}^{n} \alpha_{kj}\, K_c(x_i, x_j)$

$\text{Eigenvalue of covariance matrix} = \frac{\lambda_k^{(K_c)}}{n}$

$\lambda_k^{\text{cov}} = \frac{\lambda_k^{K_c}}{n}$

$z_i \in \{1, 2, \ldots, K\}, \quad i = 1, \ldots, n$

$\mu_k = \frac{\sum_{i=1}^{n} \mathbf{1}(z_i = k)\, x_i}{\sum_{i=1}^{n} \mathbf{1}(z_i = k)}$

$J(z_1,\ldots,z_n) = \sum_{i=1}^{n} \|x_i - \mu_{z_i}\|^2$

$\mu_k^t = \frac{\sum_{i=1}^{n} x_i \, \mathbf{1}(z_i^t = k)}{\sum_{i=1}^{n} \mathbf{1}(z_i^t = k)}$

$z_i^{t+1} = \arg\min_{k} \| x_i - \mu_k^t \|^2$

$v^* = \arg\min_{v \in \mathbb{R}^d} \sum_{i=1}^{l} \|x_i - v\|^2 = \frac{1}{l}\sum_{i=1}^{l} x_i$

$F(Z^t) = \sum_{i=1}^{n} \|x_i - \mu_{Z_i^t}^t\|^2$

$I^t = \sum_{i=1}^{n} \|x_i - \mu_{Z_i^{t+1}}^t\|^2 < \sum_{i=1}^{n} \|x_i - \mu_{Z_i^t}^t\|^2 = F(Z^t)$

$\sum_{i \in C_k^{t+1}} \|x_i - \mu_k^{t+1}\|^2 \leq \sum_{i \in C_k^{t+1}} \|x_i - \mu_k^t\|^2$

$F(Z^{t+1}) \leq I^t < F(Z^t)$

$\|x - \mu_1\|^2 \leq \|x - \mu_2\|^2 \quad \text{for all } x \in \text{cluster 1}$

$x^T(\mu_2 - \mu_1) \leq \frac{\|\mu_2\|^2 - \|\mu_1\|^2}{2}$

$\text{Cluster 1} = \{x : \|x-\mu_1\|^2 \leq \|x-\mu_j\|^2 \text{ for all } j \neq 1\}$

$\text{Each cluster region} = \bigcap_{j \neq i} \{x : x^T(\mu_j - \mu_i) \leq \tfrac{\|\mu_j\|^2 - \|\mu_i\|^2}{2}\}$

$\text{score}(x) = \min_{j \in \{1,\ldots,l-1\}} \|x - \mu_j^0\|^2$

$P(x_i \text{ chosen}) = \frac{\text{score}(x_i)}{\sum_{j=1}^{n} \text{score}(x_j)}$

$F(Z_1,\ldots,Z_n) = \sum_{i=1}^{n} \|x_i - \mu_{x_i}\|^2$

$\text{AIC} = 2K - 2\log L(\theta^*)$

$\text{BIC} = K\log(n) - 2\log L(\theta^*)$

$P(X = 1) = p, \quad P(X = 0) = 1 - p, \quad p \in [0, 1]$

$P(X_i = 1 \mid X_j = v) = P(X_i = 1) \quad \forall\, i \neq j,\; \forall\, v$

$P(X_i = 1) = P(X_j = 1) = p \quad \forall\, i, j$

$L(P; x_1,\ldots,x_n) = \prod_{i=1}^{n} P^{x_i}(1-P)^{1-x_i}$

$\ell(P) = \log L(P) = \sum_{i=1}^{n} \left[ x_i \log P + (1-x_i)\log(1-P) \right]$

$\hat{P}_{\text{ML}} = \frac{1}{n}\sum_{i=1}^{n} x_i = \frac{\text{number of ones}}{n}$

$L(\mu,\sigma^2; x_1,\ldots,x_n) = \prod_{i=1}^{n} f(x_i;\mu,\sigma^2) = \prod_{i=1}^{n} \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x_i-\mu)^2}{2\sigma^2}}$

$\hat{\mu}_{\text{ML}} = \frac{1}{n}\sum_{i=1}^{n} x_i$

$P(p \mid \alpha, \beta) = \frac{p^{\alpha-1}(1-p)^{\beta-1}}{Z}$

$P(\theta \mid \text{data}) = \frac{P(\text{data} \mid \theta) \cdot P(\theta)}{P(\text{data})}$

$P(\theta \mid \text{data}) \propto P(\text{data} \mid \theta) \cdot P(\theta)$

$P(p \mid \text{data}) \propto p^{n_h}(1-p)^{n_t} \cdot p^{\alpha-1}(1-p)^{\beta-1} = p^{(\alpha + n_h)-1}(1-p)^{(\beta + n_t)-1}$

$\text{Posterior} = \text{Beta}(\alpha + n_h,\; \beta + n_t)$

$E[p \mid \text{data}] = \frac{\alpha_{\text{post}}}{\alpha_{\text{post}} + \beta_{\text{post}}}$

$\hat{p}_{\text{MAP}} = \arg\max_p\; P(p \mid \text{data})$

$\hat{p}_{\text{mean}} = E[p \mid \text{data}] = \frac{\alpha + n_h}{\alpha + n_h + \beta + n_t}$

$P(z_i = k) = \pi_k, \quad \sum_{k=1}^{K} \pi_k = 1, \quad 0 < \pi_k \leq 1$

$x_i \mid z_i = k \;\sim\; \mathcal{N}(\mu_{z_i},\, \sigma^2_{z_i})$

$\theta = \underbrace{(\mu_1,\ldots,\mu_K)}_{K \text{ means}},\; \underbrace{(\sigma^2_1,\ldots,\sigma^2_K)}_{K \text{ variances}},\; \underbrace{(\pi_1,\ldots,\pi_K)}_{K{-}1 \text{ free weights}}$

$p(x_i \mid \theta) = \sum_{k=1}^{K} \pi_k \cdot \mathcal{N}(x_i;\, \mu_k,\, \sigma^2_k)$

$L(\theta) = \prod_{i=1}^{n} \sum_{k=1}^{K} \pi_k \cdot \frac{1}{\sqrt{2\pi}\,\sigma_k} \exp\!\left(-\frac{(x_i - \mu_k)^2}{2\sigma_k^2}\right)$

$\hat{\pi}_k = \frac{1}{n} \sum_{i=1}^{n} \lambda_k^i$

$f\!\left(\frac{a+b}{2}\right) \leq \frac{f(a)+f(b)}{2} \quad \text{(convex)}$

$f\!\left(\frac{a+b}{2}\right) \geq \frac{f(a)+f(b)}{2} \quad \text{(concave)}$

$f(\lambda a + (1-\lambda)b) \leq \lambda f(a) + (1-\lambda)f(b), \quad 0 \leq \lambda \leq 1 \quad \text{(convex)}$

$f\!\left(\sum_{k=1}^{K} \lambda_k \, a_k\right) \geq \sum_{k=1}^{K} \lambda_k \, f(a_k), \quad \sum_{k=1}^{K} \lambda_k = 1,\ 0 \leq \lambda_k \leq 1 \quad \text{(concave } f\text{)}$

$\log\!\left(\sum_{k=1}^{K} \pi_k \, p_k(x)\right) \geq \sum_{k=1}^{K} \pi_k \log p_k(x)$

$\underbrace{f\!\left(\textstyle\sum_k \lambda_k a_k\right)}_{\text{function of blend}} \geq \underbrace{\sum_k \lambda_k f(a_k)}_{\text{blend of functions}} \quad \text{when } f \text{ is concave}$

$\log L(\theta) = \sum_{i=1}^{n} \log \left( \sum_{k=1}^{K} \pi_k \cdot \frac{1}{\sqrt{2\pi}\sigma_k} e^{-\frac{(x_i - \mu_k)^2}{2\sigma_k^2}} \right)$

$\sum_{k=1}^{K} \lambda_i^k = 1, \quad 0 \leq \lambda_i^k \leq 1 \quad \text{for all } i, k$

$\hat{\lambda}_i^k = \frac{\pi_k \cdot \frac{1}{\sqrt{2\pi}\sigma_k} e^{-\frac{(x_i - \mu_k)^2}{2\sigma_k^2}}}{\sum_{l=1}^{K} \pi_l \cdot \frac{1}{\sqrt{2\pi}\sigma_l} e^{-\frac{(x_i - \mu_l)^2}{2\sigma_l^2}}}$

$\hat{\mu}_k = \frac{\sum_{i=1}^{n} \lambda_i^k \, x_i}{\sum_{i=1}^{n} \lambda_i^k}$

$\hat{\sigma}_k^2 = \frac{\sum_{i=1}^{n} \lambda_i^k (x_i - \hat{\mu}_k)^2}{\sum_{i=1}^{n} \lambda_i^k}$

$\hat{\pi}_k = \frac{\sum_{i=1}^{n} \lambda_i^k}{n}$