forked from ArquintL/eth-cil-exam-summary
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Mixture.tex
53 lines (53 loc) · 5.48 KB
/
Mixture.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
\section*{Data Clustering \& Mixture Models}
\subsection*{K-Means}
$\mathbf{Z} \in \{0,1\}^{N\times K}$ (if point $i$ assigned to cluster $j$) \\
\textbf{Target:} $\min_{\mathbf{U}, \mathbf{Z}} J(\mathbf{U}, \mathbf{Z}) = \|\mathbf{X} - \mathbf{U} \mathbf{Z}\|_F^2$\\
$= \sum_{n=1}^N \sum_{k=1}^K \mathbf{z}_{k,n} \|\mathbf{x}_n - \mathbf{u}_k\|_2^2$\\
1. \textbf{Initiate:} choose $K$ centroids $\mathbf{U} = [\mathbf{u}_1, \ldots, \mathbf{u}_K]$\\
2. \textbf{Cluster Assign:} assign data points to closest cluster $z_{ij}^* = 1 \text{ if } j=\argmin_k||\mathbf{x}_i - \mathbf{u}_k||^2 \text{ else } 0$\\
3. \textbf{Update centroids}: $\mathbf{u}_k = \frac{\sum_{n=1}^N z_{k,n} \mathbf{x}_n}{\sum_{n=1}^N z_{k,n}}$. Repeat 2\\
Stop if $||\mathbf{Z} - \mathbf{Z_{new}}||_F^2 = 0$.
Guaranteed to converge to local optimum.
Computational cost: $O(k\cdot n \cdot d)$
\subsection*{Gaussian Mixture Models (GMM)}
$p(x;\mu;\Sigma)=\frac{1}{|\Sigma|^{\frac{1}{2}}(2\pi)^{\frac{D}{2}}}\mathit{exp}[-\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu)]$ \\
$\int \mathcal{N}(z;\mu, \Sigma) \log(\mathcal{N}(z;0,I)) dz = E_z[\mathcal{N}(z;0, I)]$\\
$=-D/2 \log(2\pi)-1/2 \sum_{i=1}^D(\mu_i^2 + \sigma_i^2)$ \\
For GMM let $\boldsymbol{\theta}_k = (\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$; $p_{\theta_k}(\mathbf{x}) = \mathcal{N}(\mathbf{x} | \boldsymbol{\mu}_k, \Sigma_k)$\\
\textbf{Mixture Models:} $p_\theta(\mathbf{x}) = \sum_{k=1}^K \pi_k p_{\theta_k}(\mathbf{x})$\\
\textbf{Generate:}
sample cluster $j \sim Categorical(\pi)$, \\
sample data from $j$-th cluster: $x \sim \mathcal{N}(\mu_j, \Sigma_j)$\\
\textbf{Assignment variable (generative model):} \\
$z_{ij} \in \{0, 1\}$, $\sum_{j=1}^k z_{ij} = 1$\\
$\operatorname{Pr}(z_k = 1) = \pi_k \Leftrightarrow p(\mathbf{z}) = \prod_{k=1}^K \pi_k^{z_k}$\\
\textbf{Complete data distribution:}\\
$p_\theta(\mathbf{x}, \mathbf{z}) = \prod_{k=1}^K \left( \boldsymbol{\pi}_k p_{\theta_k}(\mathbf{x})\right)^{z_k}$\\
\textbf{Posterior Probabilities:} $\\\operatorname{Pr}(z_k = 1 | \mathbf{x}) = \frac{\operatorname{Pr}(z_k = 1) p(\mathbf{x} | z_k = 1)}{\sum_{l=1}^K \operatorname{Pr}(z_l = 1) p(\mathbf{x} | z_l = 1)} = \frac{\boldsymbol{\pi}_k p_{\theta_k}(\mathbf{x})}{\sum_{l=1}^K \boldsymbol{\pi}_l p_{\theta_l}(\mathbf{x})}$\\
$\text{posterior } p(A|B)=\frac{\text{prior } p(A)\ \times \ \text{likelihood } p(B|A)}{\text{evidence } p(B)}$\\
\textbf{Likelihood of observed data $\mathbf{X}$:}\\
$p_\theta(\mathbf{X}) = \prod_{n=1}^N p_\theta(\mathbf{x}_n) = \prod_{n=1}^N \left(\sum_{k=1}^K \pi_k p_{\theta_k}(\mathbf{x}_n)\right)$
\textbf{Max. Likelihood Estimation (MLE):}\\
$\argmax_\theta\sum_{n=1}^N \log \left( \sum_{k=1}^K \pi_k p_{\theta_k}(\mathbf{x}_n)\right)$ (mult. 1)\\
$\ge \sum_{n=1}^N \sum_{k=1}^K{q_{nk}[\log p_{\theta_k}(\mathbf{x}_n) + \log \pi_k - \log q_{nk}]}$\\
with $\sum_{k=1}^K{q_{nk}} = 1$ by Jensen Inequality.
\subsection*{Expectation-Maximization (EM) for GMM}
\textbf{E-Step:}
$Pr[z_{j}=1|\mathbf{x}_i] = q_{ij}=\frac{\pi_j p(\mathbf{x}_i;\theta_j)}{\sum_{l=1}^K \pi_l p(\mathbf{x}_i;\theta_l)}$ \\
\textit{Derivation:} Can maximize independent of $i$. Take derivative of lower bound w.r.t. $q_{ij}$ with Lagrangian: $\lambda(\sum_j q_{ij} -1)$ to get: $\log \pi_j +\log p(x_i|\mu_j, \Sigma_j)-\log q_{ij} - 1 + \lambda = 0 \to q_{ij}=\pi_j p(x_i|\mu_j, \Sigma_j) e^{\lambda-1}$. Now use $\sum_j q_{ij}=\sum_j \pi_j p(x_i|\mu_j, \Sigma_j)e^{\lambda-1}=1 \to e^{\lambda -1}= 1/(\sum_j pi_j p(x_i|\mu_j, \Sigma_j))$ and plug in.
\\
\textbf{M-Step:}
$\boldsymbol{\mu}_j^{*} := \frac{\sum_{i=1}^N q_{ij} \mathbf{x}_i}{\sum_{i=1}^N q_{ij}}$
$, \pi_j^* := \frac{1}{N} \sum_{i=1}^N q_{ij}$\\
$\Sigma_k^{*} = \frac{\sum_{i=1}^N q_{ij} (\mathbf{x}_i - \boldsymbol{\mu}_j)(\mathbf{x}_i - \boldsymbol{\mu}_j)^\top}{\sum_{i=1}^N q_{ij}}$\\
\textit{Derivations:} Take derivative of lower bound w.r.t. $\pi_k$ with Lagrangian: $\lambda (\sum_k \pi_k - 1)$ to get $\sum_i q_{ik} (1 / \pi_k) + \lambda = 0 \to \pi_k = (\sum_i q_{ik}) / \lambda$. Then use $\sum_k \pi_k=1 \to (\sum_k \sum_i q_{ik})/\lambda = N / \lambda = 1 \to \lambda = 1 / N$ and plug in. For $\mathbf{\mu}_k$: $-\sum_i q_{ik} \Sigma_k^{-1}(\mathbf{x}_i - \mathbf{\mu}_i)=\Sigma_k^{-1}\sum_i q_{ik}(\mathbf{x}_i - \mathbf{\mu}_k)$ (note: $\Sigma$ is symmetric \& invertible so $Ax=0$ iff $x=0$), so $\sum_i q_{ik}(\mathbf{x}_i - \mathbf{\mu}_k) = 0 \to \mathbf{\mu}_k = (\sum_i q_{ik}\mathbf{x_i}) / (\sum_i q_{ik})$
\\
Guaranteed to converge to local optimum. \\
\textbf{Comparison to K-Means}\\
Soft assignments (not hard), learn cov. matrix (not spherical clusters), slow (not fast), more (not less) iterations, use K-means as initialization (use sample coveriance as matrix, use fraction of datapoints as mixing weights). K-means as a special case of GMM with covariances $\Sigma_j = \sigma^2 I$. in the limit of $\sigma \rightarrow 0$, recover K-means (hard assignments). \\
\textbf{Model Order Selection (AIC / BIC for GMM)}\\
Trade-off between data fit (i.e. likelihood $p(\mathbf{X} | \theta)$) and complexity (i.e. \# of free parameters $\kappa(\cdot)$). Compare for different parameters and take smallest:\\
$\operatorname{AIC}(\theta | \mathbf{X}) = -\log p_\theta(\mathbf{X}) + \kappa(\theta)$\\
$\operatorname{BIC}(\theta | \mathbf{X}) = -\log p_\theta(\mathbf{X}) + \frac{1}{2} \kappa(\theta) \log N$ \\
(penalizes complexity more)\\
\textbf{Example:} \#free params, fixed cov. matrix: $\kappa(\theta) = K \cdot D + (K - 1)$ ($K$: \# clusters, $D$: $\mathsf{dim}\text{(data)}=\mathsf{dim}(\mu_i)$), full cov. matrix: $\kappa(\theta) = K(D + \frac{D(D+1)}{2}) + (K - 1)$.