Gaussian Mixture Modelling | Expectation Maximization Algorithm | Matrix Calculus | Classification смотреть онлайн

#MachineLearning #AI #Statistics #Math

Let $X' = [X_1, X_2,..., X_{n}]$ be observed sample, iid with pdf $f(x|\theta)$. Let $Z'=[Z_1, Z_2,..., Z_{n}]$ be hidden/unobserved. We further assume that $\{ X_i \}$ and $\{ Z_j \}$ are mutually independent.

Let $g(\bold{x}|\theta)$ be the joint pdf of $\bold{X}$.

Let $h(\bold{x},\bold{z}|\theta)$ be the complete pdf of $\bold{X}, \bold{Z}$.

Let $k(\bold{z}|\theta,\bold{x})$ be the conditional pdf of the hidden data given the observed data.

$$
k(\bold{z}|\theta,\bold{x}) = \frac{h(\bold{x},\bold{z}|\theta)}{g(\bold{x}|\theta)}
$$

We want to find an estimate of the unknown parameter $\theta$.

We'll conduct MLE to maximize the probability of observing $X$ by maximizing $g(\bold{x}|\theta)$.

McLachlan and Krishman (1997) gives a in-depth knowledge of an algorithm call EM Algo. Let's see the inspiration of EM algo. We want to maximize **incomplete likelyhood function** $L(\theta; \bold{x})=g(\bold{x}|\theta)$ wrt $\theta$:

$$
\begin{aligned}
\log{L(\theta; \bold{x})} = \log{g(\bold{x}|\theta)} &= \int{\log{g(\bold{x}|\theta)} k(\bold{z}|\theta_0,\bold{x}) d\bold{z} } \\
&= E_{\bold{Z}}[\log{h(\bold{x},\bold{Z}|\theta)|\theta_0,\bold{x}}] - E_{\bold{Z}}[\log{k(\bold{Z}|\theta, \bold{x})}|\theta_0,\bold{x}]
\end{aligned}
$$

Here we are assuming $\theta_0$ is known. The $L(\theta; \bold{x}, \bold{z}) = h(\bold{x},\bold{Z}|\theta)|\theta_0,\bold{x}$ is the **complete likelyhood function**.

Let

$$
Q(\theta|\theta_0,\bold{x})=E_{\bold{Z}}[\log{h(\bold{x},\bold{Z}|\theta)|\theta_0,\bold{x}}]
$$

And let

$$
R(\theta|\theta_0,\bold{x})=E_{\bold{Z}}[\log{k(\bold{Z}|\theta, \bold{x})}|\theta_0,\bold{x}]
$$

## Algorithm

**[Step E] Expectation Step**

Suppose $\hat{\theta}_m$ is known. Compute $Q(\theta|\hat{\theta}_m,\bold{x})=E_{\bold{Z}}[\log{h(\bold{x},\bold{z}|\theta)|\hat{\theta}_m,\bold{x}}]$

**[Step M] Maximization Step**

Find next $\hat{\theta}_{m+1}=\underset{\theta}{\argmax}{Q(\theta|\hat{\theta}_m,\bold{x})}$

**[Step S] Stop Step**

Stop the iteration when $\|Q(\theta_{m+1}|\hat{\theta}_m,\bold{x}) - Q(\theta_m|\hat{\theta}_m,\bold{x}) \| \le \epsilon$


### Why Only Maximizing $Q(\theta|\hat{\theta}_m,\bold{x})$?

### __Theorem__

Let $\{\theta_m\}$ be the sequence of estimations by conducting the EM Algorithm.

$$
R(\theta_{m+1}|\theta_m,\bold{x}) \le R(\theta_m|\theta_m,\bold{x})
$$

## Gaussian mixture

Let $\mathbf{x} = (\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_n)$ be a sample of $n$ independent observations from a mixture of two multivariate normal distributions of dimension $d$.

$X_{i}\mid (Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})$ and $X_{i}\mid (Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2})$

where $\operatorname{P} (Z_i = 1 ) = \tau_1$ and $\operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}$

The aim is to estimate the unknown parameters representing the mixing value between the Gaussians and the means and covariances of each:

$$
\theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )}
$$

Deriving the pdf of X:

$$
\begin{aligned}
P(X \le x)' &= P(X \le x | Z = 1)' P(Z = 1) + P(X \le x | Z = 2)' P(Z = 2) \\
&= \tau _{1}\ f(\mathbf {x};{\boldsymbol {\mu }}_{1},\Sigma _{1}) + \tau _{2}\ f(\mathbf {x};{\boldsymbol {\mu }}_{2},\Sigma _{2})
\end{aligned}
$$


where the incomplete-data likelihood function is:

$$
L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})
$$

and the complete-data likelihood function is:

$$
L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \mid \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)}
$$

The conditional pdf of $k(\bold{Z}|\theta, \bold{x})$ is:

**E Step**

We could derive $Q(\theta \mid \theta ^{(t)})$ as follows:

**M Step**

The linear form of $\tau_{i}$ and $\mu_{i}/\Sigma_i$ means we could maiximize $Q$ independently by maximizing $\tau_{i}$ and $\mu_{i}/\Sigma_{i}$ terms separately.

$\tau$ terms, with constrain $\tau_2 = 1 - \tau_1$:

By taking derivative of each $\tau$, we get:

For the next estimates of $(\mu_1, \Sigma_1)$:

We'll gonna make use of this formula: $\mathbf{ \frac{\partial w^T A w}{\partial w} = 2Aw}$, where A is symmetric.


To derive the formula for $\Sigma_{i}^{(t+1)}$, we'll gonna make use of the following equations:

- Invariant under cyclic permutation $tr[ABC] = tr[CAB] = tr[BCA]$

- Derivative of a trace: $\frac{\partial}{\partial{A}} tr[BA] = B^T$

- Derivative of a log determinant: $\frac{\partial}{\partial{A}}\log{|A|} = A^{-T}$.

- Determinant of an inverse is the inverse of the determinant: $|A|^{-1} = |A^{-1}|$