17.7. Expectation Maximization

Expectation-Maximization (EM) [26] method is a maximum likelihood based estimation paradigm. It requires an explicit probabilistic model of the mixed data-set. The algorithm estimates model parameters and the segmentation of data in Maximum-Likelihood (ML) sense.

We assume that ${\mathbf{y}}_s$ are samples drawn from multiple “component” distributions and each component distribution is centered around a mean. Let there be $K$ such component distributions. We introduce a latent (hidden) discrete random variable $z\in \{1,\dots ,K\}$ associated with the random variable $\mathbf{y}$ such that $z_s=k$ if ${\mathbf{y}}_s$ is drawn from $k$-th component distribution. The random vector $(\mathbf{y},z)\in {\mathbb{R}}^M\times \{1,\dots ,K\}$ completely describes the event that a point $\mathbf{y}$ is drawn from a component indexed by the value of $z$.

We assume that $z$ is subject to a multinomial (marginal) distribution. i.e.:

$$p(z=k)={\pi }_k\ge 0,{\pi }_1+\cdots +{\pi }_K=1.$$

Each component distribution can then be modeled as a conditional (continuous) distribution $f(\mathbf{y}|z)$. If each of the components is a multivariate normal distribution, then we have $f(\mathbf{y}|z=k)\sim \mathcal{N}({\mu }_k,{\mathrm{\Sigma }}_k)$ where ${\mu }_k$ is the mean and ${\mathrm{\Sigma }}_k$ is the covariance matrix of the $k$-th component distribution. The parameter set for this model is then $\theta =\{{\pi }_k,{\mu }_k,{\mathrm{\Sigma }}_K{\}}_{k=1}^K$ which is unknown in general and needs to be estimated from the dataset $\mathbf{Y}$.

With $(\mathbf{y},z)$ being the complete random vector, the marginal PDF of $\mathbf{y}$ given $\theta$ is given by

$$f(\mathbf{y}|\theta )=\sum _{z=1}^{K}f(\mathbf{y}|z,\theta )p(z|\theta )=\sum _{z=1}^K{\pi }_{k}f(\mathbf{y}|z=k,\theta ).$$

The log-likelihood function for the dataset

$$\mathbf{Y}=\{{\mathbf{y}}_s{\}}_{s=1}^N$$

is given by

$$l(\mathbf{Y};\theta )=\sum _{s=1}^S\ln f({\mathbf{y}}_s|\theta ).$$

An ML estimate of the parameters, namely ${\hat{\theta }}_{\mathbf{ML}}$ is obtained by maximizing $l(\mathbf{Y};\theta )$ over the parameter space. The statistic $l(Y;\theta )$ is called incomplete log-likelihood function since it is marginalized over $z$. It is very difficult to compute and maximize directly. The EM method provides an alternate means of maximizing $l(\mathbf{Y};\theta )$ by utilizing the latent r.v. $z$.

We start with noting that

$$f(\mathbf{y}|\theta )p(z|\mathbf{y},\theta )=f(\mathbf{y},z|\theta ),$$

$$\sum _{k=1}^{K}p(z=k|\mathbf{y},\theta )=1.$$

Thus, $l(\mathbf{Y};\theta )$ can be rewritten as

$$\begin{array}{rl}l(\mathbf{Y};\theta )& =\sum _{s=1}^S\sum _{k=1}^{K}p(z_s=k|{\mathbf{y}}_s,\theta )\ln \frac{f({\mathbf{y}}_s,z_s=k|\theta )}{p(z_s=k|{\mathbf{y}}_s,\theta )}\\ & =\sum _{s,k}p(z_s=k|{\mathbf{y}}_s,\theta )\ln f({\mathbf{y}}_s,z_s=k|\theta )\\ & -\sum _{s,k}p(z_s=k|{\mathbf{y}}_s,\theta )\ln p(z_s=k|{\mathbf{y}}_s,\theta ).\end{array}$$

The first term is expected complete log-likelihood function and the second term is the conditional entropy of $z_s$ given ${\mathbf{y}}_s$ and $\theta$.

Let us introduce auxiliary variables $w_{sk}(\theta )=p(z_s=k|{\mathbf{y}}_s,\theta )$. $w_{sk}$ represents the expected membership of ${\mathbf{y}}_s$ in the $k$-th cluster. Put $w_{sk}$ in a matrix $\mathbf{W}(\theta )$ and write:

$$l^{\prime }(\mathbf{Y};\theta ,\mathbf{W})=\sum _{s=1}^S\sum _{k=1}^K{w}_{sk}\ln f({\mathbf{y}}_s,z_s=k|\theta ).$$

$$h(z|\mathbf{y};\mathbf{W})=-\sum _{s=1}^S\sum _{k=1}^K{w}_{sk}\ln w_{sk}.$$

Then, we have

$$l(\mathbf{Y};\theta ,\mathbf{W})=l^{\prime }(\mathbf{Y};\theta ,\mathbf{W})+h(z|\mathbf{y};W)$$

where, we have written $l$ as a function of both $\theta$ and $W$.

An iterative maximization approach can be introduced as follows:

1. Maximize $l(\mathbf{Y};\theta ,\mathbf{W})$ w.r.t. $\mathbf{W}$ keeping $\theta$ as constant.

2. Maximize $l(\mathbf{Y};\theta ,\mathbf{W})$ w.r.t. $\theta$ keeping $\mathbf{W}$ as constant.

3. Repeat the previous two steps till convergence.

This is essentially the EM algorithm. Step 1 is known as E-step and step 2 is known as the M-step. In the E-step, we are estimating the expected membership of each sample being drawn from each component distribution. In the M-step, we are maximizing the expected complete log-likelihood function as the conditional entropy term doesn’t depend on $\theta$.

Using Lagrange multiplier, we can show that the optimal ${\hat{w}}_{sk}$ in the E-step is given by

$${\hat{w}}_{sk}=\frac{{\pi }_{k}f({\mathbf{y}}_s|z_s=k,\theta )}{\sum _{l=1}^K{\pi }_{l}f({\mathbf{y}}_s|z_s=l,\theta )}.$$

A closed form solution for the $M$-step depends on the particular choice of the component distributions. We provide a closed form solution for the special case when each of the components is an isotropic normal distribution ($\mathcal{N}({\mu }_k,{\sigma }_k^{2}I)$).

$$\begin{array}{rl}& \widehat{{\mu }_k}=\frac{\sum _{s=1}^S{w}_{sk}{y}_s}{\sum _{s=1}^S{w}_{sk}},\\ & {\hat{\sigma }}_k^2=\frac{\sum _{s=1}^S{w}_{sk}\Vert y_s-{\mu }_k{\Vert }_2^2}{M\sum _{s=1}^S{w}_{sk}},\\ & \widehat{{\pi }_k}=\frac{\sum _{k=1}^K{w}_{sk}}{K}.\end{array}$$

In $K$-means, each ${\mathbf{y}}_s$ gets hard assigned to a specific cluster. In EM, we have a soft assignment given by $w_{sk}$.

EM-method is a good method for a hybrid dataset consisting of mixture of component distributions. Yet, its applicability is limited. We need to have a good idea of the number of components beforehand. Further, for a Gaussian Mixture Model (GMM), it fails to work if the variance in some of the directions is arbitrarily small [82]. For example, a subspace like distribution is one where the data has large variance within a subspace but almost zero variance orthogonal to the subspace. The EM method tends to fail with subspace like distributions.