Tag Info

102

This is a recipe to learn EM with a practical and (in my opinion) very intuitive 'Coin-Toss' example: Read this short EM tutorial paper by Do and Batzoglou. This is the schema where the coin toss example is explained: You may have question marks in your head, especially regarding where the probabilities in the Expectation step come from. Please have ...

64

It sounds like your question has two parts: the underlying idea and a concrete example. I'll start with the underlying idea, then link to an example at the bottom. EM is useful in Catch-22 situations where it seems like you need to know $A$ before you can calculate $B$ and you need to know $B$ before you can calculate $A$. The most common case people deal ...

63

There is no "k-means algorithm". There is MacQueens algorithm for k-means, the Lloyd/Forgy algorithm for k-means, the Hartigan-Wong method, ... There also isn't "the" EM-algorithm. It is a general scheme of repeatedly expecting the likelihoods and then maximizing the model. The most popular variant of EM is also known as "Gaussian Mixture Modeling" (GMM), ...

43

K means Hard assign a data point to one particular cluster on convergence. It makes use of the L2 norm when optimizing (Min {Theta} L2 norm point and its centroid coordinates). EM Soft assigns a point to clusters (so it give a probability of any point belonging to any centroid). It doesn't depend on the L2 norm, but is based on the Expectation, i.e., the ...

28

EM is not guaranteed to converge to a local minimum. It is only guaranteed to converge to a point with zero gradient with respect to the parameters. So it can indeed get stuck at saddle points.

22

From: Xu L and Jordan MI (1996). On Convergence Properties of the EM Algorithm for Gaussian Mixtures. Neural Computation 2: 129-151. Abstract: We show that the EM step in parameter space is obtained from the gradient via a projection matrix P, and we provide an explicit expression for the matrix. Page 2 In particular we show that the EM step ...

22

Your approach is correct. EM is equivalent to VB under the constraint that the approximate posterior for $\Theta$ is constrained to be a point mass. (This is mentioned without proof on page 337 of Bayesian Data Analysis.) Let $\Theta^*$ be the unknown location of this point mass: $$Q_\Theta(\Theta) = \delta(\Theta - \Theta^*)$$ VB will minimize the ...

20

The question is legit and I had the same confusion when I first learnt the EM algorithm. In general terms, the EM algorithm defines an iterative process that allows to maximize the likelihood function of a parametric model in the case in which some variables of the model are (or are treated as) "latent" or unknown. In theory, for the same purpose, you can ...

17

You have several problems in the source code: As @Pat pointed out, you should not use log(dnorm()) as this value can easily go to infinity. You should use logmvdnorm When you use sum, be aware to remove infinite or missing values You looping variable k is wrong, you should update loglik[k+1] but you update loglik[k] The initial values for your method and ...

16

I think there's some crossed wires here. The MLE, as referred to in the statistical literature, is the Maximum Likelihood Estimate. This is an estimator. The EM algorithm is, as the name implies, an algorithm which is often used to compute the MLE. These are apples and oranges. When the MLE is not in closed form, a commonly used algorithm for finding this ...

15

In principle, both EM and standard optimization approaches can work for fitting mixture distributions. Like EM, convex optimization solvers will converge to a local optimum. But, a variety of optimization algorithms exist for seeking better solutions in the presence of multiple local optima. As far as I'm aware, the algorithm with best convergence speed will ...

14

Here's an example of Expectation Maximisation (EM) used to estimate the mean and standard deviation. The code is in Python, but it should be easy to follow even if you're not familiar with the language. The motivation for EM The red and blue points shown below are drawn from two different normal distributions, each with a particular mean and standard ...

14

First of all, it is possible that EM converges to a local min, a local max, or a saddle point of the likelihood function. More precisely, as Tom Minka pointed out, EM is guaranteed to converge to a point with zero gradient. I can think of two ways to see this; the first view is pure intuition, and the second view is the sketch of a formal proof. First, I ...

14

First, GMM is a particular algorithm for clustering, where you try to find the optimal labelling of your $n$ observations. Having $k$ possible classes, it means that there are $k^n$ possible labellings of your training data. This becomes already huge for moderate values of $k$ and $n$. Second, the functional you are trying to minimize is not convex, and ...

14

Imagine that you have some data $X$ and probabilistic model parametrized by $\theta$, you are interested in learning about $\theta$ given your data. The relation between data, parameter and model is described using likelihood function $$\mathcal{L}(\theta \mid X) = p(X \mid \theta)$$ To find the best fitting $\theta$ you have to look for such value that ...

13

The MLE method can be applied in cases where someone knows the basic functional form of the pdf (e.g., it's Gaussian, or log-normal, or exponential, or whatever), but not the underlying parameters; e.g., they don't know the values of $\mu$ and $\sigma$ in the pdf: $$f(x|\mu, \sigma) = \frac{1}{\sqrt{2\pi\sigma^{2}}} \exp\left[\frac{-(x-\mu)^{2}}{2 \sigma^{2}}... 13 EM is an optimisation technique: given a likelihood with useful latent variables, it returns a local maximum, which may be a global maximum depending on the starting value. MCMC is a simulation method: given a likelihood with or without latent variables, and a prior, it produces a sample that is approximately distributed from the posterior distribution. The ... 12 EM is not needed instead of using some numerical technique because EM is a numerical method as well. So it's not a substitute for Newton-Raphson. EM is for the specific case when you have missing values in your data matrix. Consider a sample X = (X_{1},...,X_{n}) which has conditional density f_{X|\Theta}(x|\theta). Then the log-likelihood of this is$$l(...

11

The root of the difficulty you are having lies in the sentence: Then using the EM algorithm, we can maximize the second log-likelihood. As you have observed, you can't. Instead, what you maximize is the expected value of the second log likelihood (known as the "complete data log likelihood"), where the expected value is taken over the $z_i$. This ...

11

Expectations are central to the EM algorithm. To start with, the likelihood associated with the data $(x_1,\ldots,x_n)$ is represented as an expectation \begin{align*} p(x_1,\ldots,x_n;\theta) &= \int_\mathfrak{{Z}^n} p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\int_\mathfrak{{Z}^n} p(x_1,\ldots,...

10

No, they are not equivalent. In particular, EM convergence is much slower. If you are interested in an optimization point-of-view on EM, in this paper you will see that EM algorithm is a special case of wider class of algorithms (proximal point algorithms).

10

The EM algorithm has different interpretations and can arise in different forms in different applications. It all starts with the likelihood function $p(x \vert \theta)$, or equivalently, the log-likelihood function $\log p(x \vert \theta)$ we would like to maximize. (We generally use logarithm as it simplifies the calculation: It is strictly monotone, ...

10

Likelihood vs. log-likelihood As has already been said, the $\log$ is introduced in maximum likelihood simply because it is generally easier to optimize sums than products. The reason we don't consider other monotonic functions is that the logarithm is the unique function with the property of turning products into sums. Another way to motivate the ...

10

Following Zhubarb's answer, I implemented the Do and Batzoglou "coin tossing" E-M example in GNU R. Note that I use the mle function of the stats4 package - this helped me to understand more clearly how E-M and MLE are related. require("stats4"); ## sample data from Do and Batzoglou ds<-data.frame(heads=c(5,9,8,4,7),n=c(10,10,10,10,10), coin=c("B","...

10

Indeed, indeed, there is a typo in (9.16) and it should be $$0=\sum_{n=1}^N \gamma(z_{nk}) {\mathbf \Sigma}_k^{-1} ({\mathbf x}_n-{\mathbf \mu}_k)$$Fortunately, this does not impact the next equation (9.17). As for deriving the conditional MLE of the covariance matrix ${\mathbf \Sigma}_k$, the result and the method are correct. The determinant is accounted ...

9

All of the above look like great resources, but I must link to this great example. It presents a very simple explanation for finding the parameters for two lines of a set of points. The tutorial is by Yair Weiss while at MIT. http://www.cs.huji.ac.il/~yweiss/emTutorial.pdf http://www.cs.huji.ac.il/~yweiss/tutorials.html

9

[Note: This is my answer to the Dec. 19, 2014, version of the question.] If you operate the change of variable $y=x^2$ in your density $$f_X(x|\alpha,\beta,\sigma)=\frac{1}{\Gamma \left( \alpha \right)\beta^{\alpha}}\exp\left\{{-\frac{x^2}{2\sigma^{2}}\frac{1}{\beta}}\right\}\frac{x^{2\alpha-1}}{2^{\alpha-1}\sigma^{2\alpha}}\mathbb{I}_{{\mathbb{R}}^{+}}(x) ... 8 The Weibull MLE is only numerically solvable: Let$$ f_{\lambda,\beta}(x) = \begin{cases} \frac{\beta}{\lambda}\left(\frac{x}{\lambda}\right)^{\beta-1}e^{-\left(\frac{x}{\lambda}\right)^{\beta}} & ,\,x\geq0 \\ 0 &,\, x<0 \end{cases} $$with \beta,\,\lambda>0. 1) Likelihoodfunction:$$ \mathcal{L}_{\hat{x}}(\lambda, \beta) =\prod_{i=1}^N f_{...

8

As the OP mentions, it's possible to solve k-means using gradient descent, and this may be useful in the case of large scale problems. There are certainly historical reasons for the prevalence of EM style algorithms for solving k-means (i.e. Lloyd's algorithm). Lloyd's algorithm is so popular that people sometimes call it "the k-means algorithm", and may ...

8

It sounds like you are taking too narrow a view of incomplete data in the context of the EM algorithm. Latent variables may indeed be unobservable due to issues with the measurement process but they can also correspond to more abstract concepts. The $t$-distribution admits the following hierarchical decomposition:  y_i \sim t(\mu,\sigma^2,\nu)\\ y_i|\...

Only top voted, non community-wiki answers of a minimum length are eligible