10
$\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} $$

Improve this question
$\endgroup$
4
  • 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, 2015 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, 2015 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, 2015 at 17:43
  • 1
    $\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, 2015 at 17:45

2 Answers 2

Reset to default
13
$\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)$, which depends on $\theta$.

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}_\vartheta\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 $\vartheta$, 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.

Improve this answer
$\endgroup$
7
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 20:37
1
$\begingroup$

Just some extension regarding the edited part.

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ One thing I don't understand is, why need to introduce $q(z)$? Since the derivation I saw so far that it wants to introduce Jensen's inequality, hence it introduce $q(z)$. But I think without introducing $q(z)$, we can still have Jensen's inequality by using $p(z)$ directly in the derivation, i.e. $p(x,z;\theta) = p(z) * p(x|z;\theta)$, we can still have the Jensen's inequality, right? Then I'm confused why need to have a separate $q(z)$. $\endgroup$
    – avocado
    Mar 21, 2021 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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