What is a general form of the EM Algorithm?

Not really. You can have hard assignments and maximize over the variances as well, and have soft assignments and maximize over the means.

For example, assume we have one dimension, three points, at (1, 2, and 3), and two means (currently at 1.5 and 2.4). Using hard assignments, after updating, we get the two means at 1.5 and 3. Using soft assignments (assuming variance 1) the means should both move towards 2. I didn't do the math out of laziness, but you're welcome to verify this for yourself.

Well, let's dissect your example from two different perspectives

• On one hand, as the variance in your "soft assignments" algorithm assumed increases, then the new means will approach the values of the hard assignment 1.5 and 3 correct? So you can see the hard assignments problem as a special case of the soft assignments problem.

• On the other hand, in the assumptions of the "hard assignments" problem, we can maximize over the means, the individual variances and assume that the covariances are exactly 1. Doing that (I believe) will "draw" the new means closer together as we are imposing a squared penalty if they are too far apart. So the hard assignments problem is a special case of the soft assignments problem.

Since they are both special cases of each other, then they are equivalent.

Erm, what?

Leaving the variances aside, the maximize-maximize EM algorithm is:

E step: assign each point to the closest gaussian M step: replace the mean of each gaussian by the mean of its points

So, if we have points at 1, 2, and 3, and means at 1.5 and 2.4, the E step produces the assignments 1 2 2, and the M step produces the means 1, 2.5

The soft algorith is:

E step: for each point, assign to it a distribution over the gaussians, weighted by their likelihood M step: for each gaussian, compute its mean as (sum_i W_i x_i )/(sum_i W_i), where W_i are the distributions obtained from the E step.

So, if we have points at 1, 2, and 3, and means at 1.5 and 2.4, the E step assigns the distributions: [ 0.84683628, 0.15316372], [ 0.47751518, 0.52248482], and [ 0.13124447, 0.86875553], and the new means are 1.508 and 2.463.

So they are different, yes.

Also, for the specific case of gaussian likelihood, the hard and soft algorithms become more similar when the variance decreases (if they do, the probabilities converge to a single one and a lot of zeros). But his point is moot if you reestimate the variance, which you can do both in the maximization-maximization (hard assignments) and expecation-maximization (soft assignments) algorithms.

Sorry if that didn't make sense.

Leaving the variances aside, the maximize-maximize EM algorithm is:

E step: assign each point to the closest gaussian M step: replace the mean of each gaussian by the mean of its points

Aha! This is where you and I differ. My version of the E-step is this

E step: maximize the log-likelihood over the means and variances of the joint (multivariate-gaussian) distribution over all means.

In other words, in your example, with three data-points and 2 means, we are finding the maximum value of a distribution from the sample (this is also E[X] - hence the equivalence)

X ~ MultivariateNormal([1.5,3], Sigma)

Where

Sigma is a 2x2 matrix which looks like this. The variances are either actively re-estimated or assumed to be constant.

[[v1, 1] [1, v2]]

In other words, once you do this, the maximum of that distribution does not occur at

(1 + 2)/2 and (3)/1

But somewhere in the middle. They would, however, if

Sigma = [[v1, 0] [0, v2]]

Usually the E step adjusts the latent variables and the M step the parameters. Your M step seems to jumble everything together. Also, you don't need a covariance matrix in one-dimensional data, only a variance/precision parameter. I don't understand which distribution are you maximizing. The likelihood in this model is not a multivariate gaussian, it's a mixture of gaussians, something like P(x) = alpha P_gaussian(x; mean_1, sigma_1) + (1-alpha)P_gaussian(x; mean_2, sigma_2).

What are you maximizing, exactly, and how? In what I described, you maximize over the latent variables (ie, the variable determining from which gaussian came a specific point), and this is clearly done by assigning them to the closes point. Computing their expectation is what you get in the soft EM.

Hey Alex, I am maximizing over the likelihood, or the log likelihood of the k-dimensional Gaussian with the means [1.5,3] and the covariances defined above (note I edited a typo) Specifically, the minimum of the function (this is the "energy")

http://mathurl.com/28lg7z2.png

note that without the third term, the maximum occurs exactly at k1, k2. Not so with the third term.

@dogy, this sounds like a completely different hierarchical model, almost like a gaussian process prior (ie, each mean is one dimension of a multivariate gaussian) for the mixture of gaussians model; but it still doesn't explain how you can maximize over it without marginalizing over all values of the latent variables, which is intractable.

Also, how do you get to this equation, from the traditional graphical model formulation of the mixture of gaussians density estimation problem?

Yes, you're right, it's like a Gaussian process prior. You see Gaussians are magic in that way, as doing marginalization = finding the mode of the distribution = doing a maximization on a quadratic function. This is still slightly unbelievable to me :)

It's a bit complex to type out. It's pretty standard stuff in a stats class, you take the log of the distribution, normalization constants fall out, you're only doing an expectation over the thing which is in the exponent of the numerator.

Because the mixture of gaussians likelihood is not at all hard to type out; L(x, m1, s1, m2, s2) = 1/2 Pr(x;m1,s1) + 1/2 Pr(x;m2,s2); since this is a sum, you can't just take the log to get rid of the exponent, and it involves no priors on the means m1 m2 or the variances s1 s2. By making the variances constant and equal to one, I mean the likelihood as L(x, m1, m2) = 1/2 Pr(x;m1,1) + 1/2 Pr(x;m2,1). To the get the complete-data likelihood you just multiply this function for all x. Gaussian conjugacy can enter if you have gaussian priors on the means (not gaussian process priors!), which would make the complete data likelihood L(x, m1, m2) = prod_i (1/2 Pr(x_i, m1, 1) + 1/2 Pr(x_i, m2, 1)) prod_j Pr(m_j, hyper mean, hyper variance). Then, the posterior mean is a function of the sample mean and the hyper mean (and the number of samples), due to conjugacy. It has nothing to do with the means being the dimensions of a gaussian process, the means are independent samples from it.

You are making a classic mistake here. The log likelihood is a sum, but the likelihood (with a big L) is a product. The log likelihood is a sum.

Pr(x;m1,s1)Pr(x;m2,s2) = Pr(x;[m1,m2],S)

Maybe I should type this out in latex

The log likelihood is a sum if and only if the likelihood is a product. In a mixture model, however, the likelihood is a sum.

you're right, i see the mistake. I'm not thinking of a mixture model at all. This also confirms the original point, which was that the maximum is not the same as the expectation.

for what it's worth, this has been an excellent discussion (for me, perhaps more an exercise in patience for you) thank you for correcting a deep seated misunderstanding on my part.

You're welcome. I'd read up on one of the referenced texts, btw, they are very interesting and show nice aspects of the EM algorithm.