Lecture 5: Expectation maximization and variational maximum likelihood
We first go back to traditional MLE approach instead of Bayesian approaches. Preparatory material for autoencoders.
Starting point: $p(x,z|\theta)$, where $z$ is unobserved. We don't necessarily care about $z$, i.e. it is some confounder that affects the distribution
Today we that a frequentist approach, i.e. we don't define a prior $p(\theta)$. $\theta$ is just some fixed parameter.
I.e. we apply the MLE procedure. The obvious complication is that we don't know $z$, so we need to marginalize $z$ out. This happens all the time in practice, because in practice you often have missing variables.
Example of Gaussian Mixture Model
We discuss the problem of density estimation with a Gaussian mixture model. Usually, we have a closed-form solution where the ML estimate is the empirical mean of the data etc.
We then of course assume the data is Gaussian e.g. unimodal. In real life these assumptions do not hold. E.g. the distribution of height will at least be bi-modal because the average between men and women differ. I.e. there are at least two groups underlying the height distribution.
But the distribution will also be skewed due to the presence of children, which dominate the lower end. So non-Gaussianity often comes from the presence of multiple subpopulations.
In this case, we can define a Gaussian mixture model with k subpopulations. See eq. 5. If you know the labels of the dataset, you can fit a dataset per group and then weigh the resulting distribution with $\rho$ i.e. the number of labels for a given group. That is, the MLE solution for the mixture problem can be decomposed in several very easy MLE problems, one for each class $k$.
In the complex scenario, we do not know the data labels. This means that we need a latent variable z for the unknown class membership. This is where the expectation-maximization algorithm comes in.
We have the conditional $p(x|\theta, z)$, but we want $p(x,z|theta)$. So to do that we need to multiply with the probability $p(z)$ and then we want to marginalize out $z$ (because we don't have labeled data)
Assuming you would have access to labels, a good probability for class membership of $z$ would be found by just taking the partial counts and expressing the probability of counting this many using a multinomial distribution. See eq. 10.
So we can write $p(x,z|theta)$ now. In this simple case, it is often feasible to marginalize out $z$ if we know the amount of groups to be low.
We are not using a prior over $\theta$ so the confusion here is a bit sneaky! $p(z)$ (multinomial) really looks like a prior! But it's really not. It's a contribution to the joint likelihood, so is conceptually really different. We are sort of Bayesianish in z, but $\theta$ is the value we care to do MLE about here!
Expectation maximization
Soft-k means is a special case of expectation maximization.
So gain, goal is MLE over $\theta$ but we need to get rid of z. As we know, the required marginalization is the difficult part of Bayesian inference.
Frequentists will not even try to do this, because they rely so much on closed form solutions.
We could do gradient descent over all parameters. But more efficient is to do expectation-maximization
If the labels would be given, you just maximimize the log likelihood given the labels. p(x|z,theta)
But again, we don't know z.
E-step:
Now we instead average over the possible distribution over labels z. For this we pick a distribution to find what plausible values of z are. We pick the conditional $p(z|x,theta^{m})$, i.e. we can guess z based on the data. This is, in fact, what Bayesians would call a posterior.
This is a problem actually, because this posterior depends on the parameter for $\theta$! I.e. we cannot compute the posterior in general because we don't know $\theta$. But we can compute the best approx now given our current estimate for $\theta$.
$$Q(\theta; \hat{\theta}^{(m)}) = E_{z ~ p(z , x , \hat{\theta^m})}[ logp(x,z|\theta)]$$
Example: if I see someone is 2 meter tall, I'm pretty sure the label is not "6-year child".
M-step:
We have computed the expectation over the likelihood. Now we take the argmax, i.e. the MLE procedure with the current expectation of the likelihood function $p(x|z,\theta)$ under the current guess of z.
$$\hat{\theta^{(m+1)}} = argmax Q(\theta; \hat{\theta^{(m)}})$$
So output is... new guess for z right?
EM converges to a local optimum of the marginal likelihood function.
EM for Gaussian Mixture Models
Define the parameters of interest $\theta$. In this case, for each class $k$ we need to know the mixing coefficient $\rho$, the mean $\mu$ and the variance $\sigma^2$.
TODO Review
Now the conditional likelihood $p(x|\theta, z)$ is a product of Gaussians. (But we work with the conditional log likelihood)
From eq. 16 to eq. 17, notice that only a few depend on k so drop out in the gradient.
eq. should sum of m not j.
We assume datapoints to be interchangeable, so the mixing coefficients are not conditioned upon data.
Mistake, no minus in eq. 14.
In eq. 20 you want them to sum to 1, so you need Lagrange.
Expectation maximization from a variational perspective
How to generalize to situations where you cannot compute posterior in closed form. So we can define a variational posterior.
Again, basic problem was to maximize the marginal likelihood. Starting point is marginal likelihood of x:
$$log p(x|\theta) = log \int p(x,z|\theta) dz$$
(It is confusing that it's called marginal when conditioned on $\theta$ But again, parameters $\theta$ just describe the latent $z$ that we do not care about and marginalize out.
Define variational distribution using the ELBO formula; as an exercise, derive using Jensen's inequality.
Notice that variational posterior depends on the current guess at iteration $m$!
Also notice that ratio of probabilities is very unstable, so that's why Jensen equality is so important here. The log is way more well-behaved, since log cancels out exponential behavior.
Notice that variational posterior q doesn't depend on $\theta$ in this variational framework, because in $q^{(m)}$ we have assumed to have fixed the parameters (our current estimate)!
Main insight: This is why taking the gradient is exactly equivalent to the gradient of the average conditional likelihood, which is equivalent to the gradient of the objective function for EM!
Again, if variational gets closer to posterior, ELBO will converge on the true marginal likelihood. This is exactly what we assume in EM! There we assume that the variational inference is the true posterior, so the ELBO will be equal to the marginal likelihood.
We know see why EM works! Assuming true posterior we derive the objective function of EM, because then essentially we are using the MLE approach (right?). That is, EM is a special case of VI!
"The expectation step of EM coincides with the computation of the ELBO while the maximization step corresponds to the maximization of the ELBO with respect to the parameters."
But now we have a more general recipe that does not assume the true posterior to be available!
AND we now see that ELBO has a dual use. We can use ELBO for two things now:
- Train variational distribution because ELBO is the objective function for parameters $\theta$ and
- train the variational parameters of the approximate posterior
See p.6 for possible shortcomings.
- If q is not parameterized enough, we will not find the true posterior distribution
- Even if q is highly parameterized, we still have a non-convex problem and we can easily get stuck in local optimimum; as a result, also result in local optimum for likelihood.
Main advantage of the variational approach is that it works for any differentaible model, not just ones with close form posteriors.
Extra: derivation
Derive MLE solutions for mixture component for EM, using Lagrange multiplier.
We start with mixture model after E-step.
$Q(\theta; \theta^{(m)}) = \sum_{k=1}^{K} \sum_{n=1}^{N} \rho_{k_{n}} ...$
See recording.
Gaussian part is not function of $\rho$, so for gradient only last term $p_{k|n} log \rho_k$ is relevant.
- Trick. Sum both sides over j.
- Sum over posterior is ofc. also 1
-
Get solution.
-
My comment: I wouldn't have figured out the summing over j.
- Luca: always first estimate the solution
- Know what to work towards
- Fact check whether you made a mistake somewhere; helps spotting mistakes