8
$\begingroup$

I understand where the E step happens in the algorithm (as explicated in the math section below). In my mind, the key ingenuity of the algorithm is the use of the Jensen's inequality to create a lower bound to the log likelihood. In that sense, taking the Expectation is simply done to reformulate the log likelihood to fit into Jensen's inequality (i.e. $E(f(x)) < f(E(x))$ for concave function.)

Is there a reason why the E-step is so-called? Is there any significance to the thing that we're taking expectation of (i.e. $p(x_i, z_i| \theta)$? I feel like I'm missing some intuition behind why the Expectation is so central, rather than simply being incidental to the use of Jensen's inequality.

EDIT: A tutorial says:

The name 'E-step' comes from the fact that one does not usually need to form the probability distribution over completions explicitly, but rather need only compute 'expected' sufficient statistics over these completions.

What does it mean "one does not usually need to form the probability distribution over completions explicitly"? What would that probability distribution look like?


Appendix: E-step in the EM algorithm $$\begin{align} ll &= \sum_i{\log p(x_i; \theta)} && \text{definition of log likelihood} \\ &= \sum_i \log \sum_{z_i}{p(x_i, z_i; \theta)} && \text{augment with latent variables $z$} \\ &= \sum_i \log \sum_{z_i} Q_i(z_i) \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{$Q_i$ is a distribution for $z_i$} \\ &= \sum_i \log E_{z_i}[\frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{taking expectations - hence the E in EM} \\ &\geq \sum E_{z_i}[\log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{Using Jensen's rule for $\log$ which is concave} \\ &\geq \sum_i \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{Q function to maximize} \end{align} $$

$\endgroup$
  • 2
    $\begingroup$ It's not clear to me what you are asking, but I've always assumed that the relevance behind naming the E-step is that, in some sense, you are "filling in" or "imputing" the missing $z$ by taking the expectation. Granted, this isn't exactly what is going on because you are taking $E_\theta [\log p(x, Z; \theta') \mid X = x]$ which isn't the same thing as plugging in something for the missing $Z$ values, but operationally one often ends up doing something like that. If we were doing data augmentation - which is similar to EM in many respects. $\endgroup$ – guy Feb 28 '15 at 7:53
  • $\begingroup$ Yes this is the kind of discussion I want to have. So when you say impute z by taking expectation". The expectation of what? Also, do you mean $E_z$ instead of $E_\theta$? $\endgroup$ – Heisenberg Feb 28 '15 at 8:01
  • $\begingroup$ My upbringing had always been to index the $E$ with the parameter indexing the probability measure that the expectation is being taken with respect to. In CS they do it as you are suggesting. I'm integrating out $Z$, conditioning on $X$ against a measure indexed by $\theta$. $\endgroup$ – guy Feb 28 '15 at 17:43
  • $\begingroup$ As an example, when fitting Gaussian mixtures, the E-step imputed the missing class indicators. But it does so in a fuzzy way by calculating responsibilities for each observation. $\endgroup$ – guy Feb 28 '15 at 17:45
11
$\begingroup$

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,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)p(\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right] \end{align*} where the expectation is in terms of the marginal distribution of the latent vector $(\mathfrak{z}_1,\ldots,\mathfrak{z}_n)$.

The intuition behind EM is also based on an expectation. Since $\log p(x_1,\ldots,x_n;\theta)$ cannot be directly optimised, while $\log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)$ can but depends on the unobserved $\mathfrak{z}_i$'s, the idea is to maximise instead the expected complete log-likelihood $$\mathbb{E}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$$ except that this expectation also depends on a value of $\theta$, chosen as $\theta_0$, say, hence the function to maximise (in $\theta$) in the M step: $$Q(\theta_0,\theta)=\mathbb{E}_{\theta_0}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$$ Jensen's inequality only comes as a justification for the increase in the observed likelihood at each M step.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the explanation. Since our posterior distribution for the latent vectors changes at every step, does $E_\theta[p(x_1,\dots,x_n, \mathfrak{z}, \dots, \mathfrak{z}, \theta)]$ change at every step as well? If so, this picture is a bit confusing because there is a fixed red curve representing $p(x;\theta)$, whereas it $p(x;\theta)$ "changes" at every step since we're averaging over our current belief about the latent vectors $z$ at that step. $\endgroup$ – Heisenberg Feb 28 '15 at 18:38
  • $\begingroup$ sorry I do not understand the question: at each EM step, the value of $\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$ changes and increases. This does not mean the likelihood function itself changes. $\endgroup$ – Xi'an Feb 28 '15 at 20:07
  • $\begingroup$ Isn't $p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$? If the RHS changes according to our posterior belief about the latent vector, does the LHS change as well? $\endgroup$ – Heisenberg Feb 28 '15 at 20:09
  • $\begingroup$ This identity is in my answer. Both sides take different values when $\theta$ varies. However, in this equation there is no notion of posterior belief as (a) $\theta$ is fixed and (b) the $\mathfrak{z}_i$'s are considered marginally. $\endgroup$ – Xi'an Feb 28 '15 at 20:13
  • 1
    $\begingroup$ At each iteration $t$, the E step uses $p(\mathfrak{z}|x, \theta_t)$ to compute the integral$$Q(\theta_t,\theta)=\mathbb{E}_{\theta_t}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right].$$ Hence the target function to maximise changes at each iteration $t$. This says nothing about the original target likelihood $p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$ which only depends on a single $\theta$. $\endgroup$ – Xi'an Feb 28 '15 at 20:37
0
$\begingroup$

Xi'an's answer is very good, just some extension regarding the edit.

The name 'E-step' comes from the fact that one does not usually need to form the probability distribution over completions explicitly, but rather need only compute 'expected' sufficient statistics over these completions.

Since the value of $z$ is not observed, we estimate a distribution $q_x(z)$ for each data point $x$ as completions of the unobserved data. The Q function is the sum of expected log likelihoods over $q_x(z)$ $$Q(\theta)=\sum_x E_{q_x}[\log p(x,z|\theta)]$$

The mentioned probability distribution over completions should refer to $p(x,z|\theta)$. For some distributions (especially the exponential family, since the likelihood is in its log form), we only have to know the expected sufficient statistics (instead of the expected likelihood) in order to compute and maximize $Q(\theta)$.


There's a very good introduction in Chapter 19.2 of Probabilistic Graphical Models.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.