2
$\begingroup$

I am trying to learn EM Algorithm for Gaussian Mixture. But not able to understand few stuffs. This is what I have understood.

Consider GMM with k components. $$ p( \mathbf{x}| \mathbf{\alpha_{k}},\mathbf{\mu},\mathbf{\Sigma}) = \sum_{k=1}^K \alpha_{k}\mathcal{N}(\mathbf{x}|\mu_{k},\mathbf{\Sigma}_{k})$$

We have $N$ data points which constitute $\mathbf{x}$ and we have to find $\mathbf{\alpha_{k}},\mathbf{\mu},\mathbf{\Sigma}$ using EM algo.

So we assume some value for $\mathbf{\alpha_{k}},\mathbf{\mu},\mathbf{\Sigma}$ and calculate classification probability $w_{ik}$ for each data point to each Gaussian $$w_{ik} = \dfrac{ \alpha_{k}\mathcal{N}(\mathbf{x}|\mu_{k},\mathbf{\Sigma}_{k})}{ \sum_{k=1}^K \alpha_{k}\mathcal{N}(\mathbf{x}|\mu_{k},\mathbf{\Sigma}_{k})}$$ So you get a $\mathbf{W}$ of size $N \times K$ This is considered as the E step.

Now new parameter values are found. $$\mathbf{\alpha}_{k}^{new} = \dfrac{ \sum_{n=1}^Nw_{ik}}{ \mathbf{N}}$$ $$\mathbf{\mu}_{k}^{new} = \dfrac{ \sum_{n=1}^Nw_{ik}x_{i}}{ \sum_{n=1}^Nw_{ik}}$$ $$\mathbf{\Sigma}_{k}^{new} = \dfrac{ \sum_{n=1}^Nw_{ik}(x_{i}-\mathbf{\mu}_{k}^{new})(x_{i}-\mathbf{\mu}_{k}^{new})^{T}}{ \sum_{n=1}^Nw_{ik}}$$ which is the M step.

  1. How does equations in M step help in finding the maxima of the objective function? Is $\prod_{i=1}^{N}\prod_{k=1}^{K}w_{ik}$ the objective function?
  2. I read the explanation for EM algo in http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html. The article says "During the E-step, expectation maximization chooses a function $g_{t}$ that lower bounds $log P(x;\theta)$ everywhere, and for which $g_{t}(\hat{\theta} (1))=logP(x;\hat{\theta} (t))$. " I don't understand this.

There is a graphical explanation in http://www.nature.com/nbt/journal/v26/n8/extref/nbt1406-S1.pdf. What are the axes of the graph.

  1. What makes this problem to have multiple local maxima rather than than 1 global maxima? that is, when will a problem has a single maxima and when will a problem has multiple local maxima?

I am not able to understand these things. Could some one please explain them?

$\endgroup$
  • 2
    $\begingroup$ What you need is a tutorial on EM algorithms... $\endgroup$ – Memming Aug 9 '15 at 11:00
  • $\begingroup$ @Memming Thanks for your comment. I read many tutorials. All the tutorials explain the above equations and explain about maximizing the objective function. But none of them actually link them. How implementing these equations actually result in maximization of objective function. May be, I am not able to link them. Could you please suggest me a tutorial which explains the link? $\endgroup$ – user3852441 Aug 9 '15 at 11:49
  • $\begingroup$ I second @Memming. If you only read the computer science side literature, it will be only marginally helpful to you, as they may not explain e.g. identification issues. There is a classic book devoted solely to the EM algorithm, and there are good explanations in books on missing data. As far as (3) goes, numeric optimizers can only find the local maxima, and the EM algorithm can find a saddle point instead of a maximum. $\endgroup$ – StasK Aug 9 '15 at 14:11
  • $\begingroup$ @StasK Thanks for the links. I will try reading them. Regarding (3), my question was, what is the reason behind a problem to have local maxima?that is, in which scenario does a problem cannot have proper convex/concave shape(it has many maxima/minima)? $\endgroup$ – user3852441 Aug 9 '15 at 14:31
  • $\begingroup$ Many reasons. First, the problem has identification issues. If your data are in fact Gaussian, and you try fitting two or more components, then the algorithm has several options: declare $\alpha_1=1$ and $\alpha_2=0$, in which case $\mu_2$ and $\Sigma_2$ are not estimable; switch the labels and declare $\alpha_1=0$ and $\alpha_2=1$; or declare $\mu_1=\mu_2$ and $\Sigma_1=\Sigma_2$, in which case any $\alpha_1\in[0,1]$ and $\alpha_2=1-\alpha_1$ will work. Second, for whatever reasons, small samples are more prone to local maxima compared to larger samples, although that observation is informal. $\endgroup$ – StasK Aug 9 '15 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.