Gaussian Mixtures and EM · Tutorial 634 of 975

Deriving EM from the Variational Lower Bound

Learn how Jensen’s inequality turns a Gaussian-mixture likelihood into a lower bound and how alternating its optimization yields EM.

Advanced 12 min read

What You'll Learn

Write the Gaussian-mixture likelihood using latent component allocations.
Derive the evidence lower bound from Jensen’s inequality.
Relate the bound’s gap to a Kullback–Leibler divergence.
Obtain posterior responsibilities by maximizing over allocation distributions.
Explain why maximizing the bound gives the EM maximization step.
Verify likelihood monotonicity for exact EM updates.

From the Mixture Likelihood to a Lower Bound

A finite Gaussian mixture describes each observation through an unobserved component allocation. The observed-data likelihood sums over those possible allocations, and the logarithm of that sum is difficult to optimize directly. The expectation-maximization (EM) algorithm makes this structure manageable by introducing a distribution over allocations and optimizing a lower bound on the log-likelihood.

This derivation uses the Gaussian-mixture model and latent allocations directly. Write $x_1,\ldots,x_n\in\mathbb{R}^d$ for independent observations and $Z_i\in\{1,\ldots,K\}$ for the component generating $x_i$. Let $\theta=(\pi_1,\ldots,\pi_K,\mu_1,\ldots,\mu_K,\Sigma_1,\ldots,\Sigma_K)$, where $\pi_k>0$, $\sum_{k=1}^K\pi_k=1$, and each covariance matrix $\Sigma_k$ is positive definite. The component density is the $d$-variate Gaussian density $\phi_d(x;\mu_k,\Sigma_k)$.

Definition: For a probability distribution $q$ on the possible allocation vectors $Z=(Z_1,\ldots,Z_n)$, define the evidence lower bound (ELBO) $$ \mathcal{L}(q,\theta) = E_q\!\left[\log p(x,Z\mid\theta)\right]+H(q), \qquad H(q)=-E_q[\log q(Z)]. $$ Here $p(x,Z\mid\theta)$ is the joint density or mass of observations and allocations, and $H(q)$ is the entropy of $q$. The ELBO depends on both the model parameter $\theta$ and the chosen allocation distribution $q$.

For any $q$ assigning positive probability only to allocations with positive joint probability, Jensen’s inequality gives a lower bound. In the Gaussian mixture with strictly positive weights and nonsingular covariances, every allocation has positive posterior probability for finite observations, so this condition causes no restriction.

Theorem: For fixed $\theta$, the observed-data log-likelihood satisfies $$ \ell(\theta)=\log p(x\mid\theta) = \mathcal{L}(q,\theta) + \operatorname{KL}\!\left(q(Z)\,\|\,p(Z\mid x,\theta)\right), $$ where $\operatorname{KL}(q\|r)=E_q[\log\{q(Z)/r(Z)\}]$. Consequently, $\mathcal{L}(q,\theta)\leq \ell(\theta)$, with equality if and only if $q(Z)=p(Z\mid x,\theta)$ with probability one.

To prove the identity, use Bayes’ rule to write $p(x,Z\mid\theta)=p(Z\mid x,\theta)p(x\mid\theta)$. Taking logarithms and expectation under $q$ gives $$ E_q[\log p(x,Z\mid\theta)] = E_q[\log p(Z\mid x,\theta)]+\log p(x\mid\theta). $$ Subtracting $E_q[\log q(Z)]$ from both sides yields $\mathcal{L}(q,\theta)=\ell(\theta)-\operatorname{KL}(q\|p(Z\mid x,\theta))$. The divergence is nonnegative: applying $\log t\leq t-1$ to $t=p(Z\mid x,\theta)/q(Z)$ on the support of $q$ shows $$ -\operatorname{KL}(q\|p) = E_q\!\left[\log\frac{p}{q}\right] \leq E_q\!\left[\frac{p}{q}-1\right] \leq 0. $$ Equality in the divergence holds precisely when the distributions agree (up to probability-zero sets). This proves the result. $\square$

Responsibilities and the E-Step

For independent observations, the posterior distribution of the allocation vector factorizes across observations. Its one-observation probabilities are the posterior responsibilities. At a current parameter value $\theta^{(t)}$, define $$ \tau_{ik}^{(t)} = P(Z_i=k\mid x_i,\theta^{(t)}) = \frac{\pi_k^{(t)}\phi_d(x_i;\mu_k^{(t)},\Sigma_k^{(t)})} {\sum_{j=1}^K\pi_j^{(t)}\phi_d(x_i;\mu_j^{(t)},\Sigma_j^{(t)})}. $$

The E-step chooses $q^{(t)}(Z)=p(Z\mid x,\theta^{(t)})$. Equivalently, it sets the categorical probabilities for $Z_i$ to $\tau_{ik}^{(t)}$, for every observation $i$. The theorem shows why this is the right choice: for the current parameter, it makes the ELBO equal to the observed-data log-likelihood, and no other $q$ can give a larger bound.

Worked Example: Computing Responsibilities in a Two-Component Mixture

Consider a univariate mixture with equal weights, unit variances, and component means $1$ and $-1$. For the observation $x=0.4$, the weighted component densities are $$ a_1=0.5\,\phi(0.4;1,1) =\frac{1}{2\sqrt{2\pi}}e^{-0.18} \approx 0.1666123, \qquad a_2=0.5\,\phi(0.4;-1,1) =\frac{1}{2\sqrt{2\pi}}e^{-0.98} \approx 0.0748638. $$ The observed density at this value is $a_1+a_2\approx0.2414761$, so its log-likelihood contribution is approximately $-1.4210$. The responsibilities are $$ \tau_1=\frac{0.1666123}{0.2414761}\approx0.6900, \qquad \tau_2=\frac{0.0748638}{0.2414761}\approx0.3100. $$ They are positive and sum to one, as required.

If instead we use $q=(0.5,0.5)$, the ELBO contribution for this one observation is $$ 0.5\log\!\left(\frac{a_1}{0.5}\right) + 0.5\log\!\left(\frac{a_2}{0.5}\right) \approx 0.5(-1.0989)+0.5(-1.8989) =-1.4989. $$ This is below the log-likelihood contribution $-1.4210$. Choosing $q=(0.6900,0.3100)$, the posterior allocation probabilities, makes the ELBO equal to the log-likelihood, as the theorem predicts.

The M-Step: Maximizing the Bound

Once $q^{(t)}$ is fixed, its entropy does not depend on the candidate parameter $\theta$. Therefore maximizing $\mathcal{L}(q^{(t)},\theta)$ over $\theta$ is equivalent to maximizing $$ Q(\theta\mid\theta^{(t)}) = E_{q^{(t)}}[\log p(x,Z\mid\theta)]. $$ This is the M-step objective. It is the expected complete-data log-likelihood, where the expectation uses the allocation distribution from the E-step. In a Gaussian mixture, the complete-data log-likelihood is $$ \log p(x,Z\mid\theta) = \sum_{i=1}^n\sum_{k=1}^K \mathbf{1}\{Z_i=k\} \left[ \log\pi_k+\log\phi_d(x_i;\mu_k,\Sigma_k) \right]. $$ Taking its expectation replaces each allocation indicator by its posterior probability: $$ Q(\theta\mid\theta^{(t)}) = \sum_{i=1}^n\sum_{k=1}^K \tau_{ik}^{(t)} \left[ \log\pi_k+\log\phi_d(x_i;\mu_k,\Sigma_k) \right]. $$

Theorem: Suppose the current parameter $\theta^{(t)}$ is admissible, its observed log-likelihood is finite, and the M-step selects an admissible $\theta^{(t+1)}$ satisfying $$ Q(\theta^{(t+1)}\mid\theta^{(t)}) \geq Q(\theta^{(t)}\mid\theta^{(t)}). $$ Then the observed-data log-likelihood does not decrease: $$ \ell(\theta^{(t+1)})\geq\ell(\theta^{(t)}). $$

For the proof, let $q^{(t)}=p(Z\mid x,\theta^{(t)})$. At the current parameter, the KL divergence in the ELBO identity is zero, so $$ \ell(\theta^{(t)})=\mathcal{L}(q^{(t)},\theta^{(t)}). $$ At the updated parameter, nonnegativity of KL gives $$ \ell(\theta^{(t+1)}) \geq \mathcal{L}(q^{(t)},\theta^{(t+1)}). $$ The entropy $H(q^{(t)})$ is fixed while $\theta$ changes, so the assumed increase in $Q$ implies $$ \mathcal{L}(q^{(t)},\theta^{(t+1)}) \geq \mathcal{L}(q^{(t)},\theta^{(t)}). $$ Combining these inequalities proves the stated monotonicity. $\square$

An exact M-step maximizes $Q$ over the admissible parameter space, and so satisfies the theorem’s inequality because the current parameter is an available comparison point. This explains EM’s two alternating tasks: the E-step tightens the bound at the current parameter, and the M-step raises that bound while holding the allocation distribution fixed. The bound is not generally equal to the new likelihood after the M-step; it is the next E-step that makes it tight again.

Worked Example: Maximizing the Mixing-Weight Part

Suppose three observations have fixed E-step responsibilities for two components: $(0.8,0.2)$, $(0.4,0.6)$, and $(0.1,0.9)$. The part of $Q$ involving the mixing weights is $$ Q_{\pi}=\sum_{i=1}^3\sum_{k=1}^2\tau_{ik}\log\pi_k, \qquad \pi_1+\pi_2=1,\quad \pi_1,\pi_2>0. $$ The total responsibility for component 1 is $0.8+0.4+0.1=1.3$; for component 2 it is $0.2+0.6+0.9=1.7$. Thus $$ Q_{\pi}=1.3\log\pi_1+1.7\log\pi_2. $$

Set $\pi_2=1-\pi_1$. Differentiating on $0<\pi_1<1$ gives $$ \frac{dQ_{\pi}}{d\pi_1}=\frac{1.3}{\pi_1}-\frac{1.7}{1-\pi_1}. $$ The derivative is zero when $1.3(1-\pi_1)=1.7\pi_1$, hence $\pi_1=1.3/3\approx0.4333$ and $\pi_2=1.7/3\approx0.5667$. The second derivative is $$ -\frac{1.3}{\pi_1^2}-\frac{1.7}{(1-\pi_1)^2}<0, $$ so this stationary point is the unique maximum. The update uses fractional component counts because the allocations are uncertain rather than observed.

Why the Variational View Matters

The ELBO separates two sources of difficulty: uncertainty about the latent allocations, represented by $q$, and estimation of the model parameters, represented by $\theta$. Its KL-gap identity is more informative than the Jensen inequality alone: it identifies exactly when the bound is tight and quantifies the gap for any other allocation distribution. The same argument also explains why EM can increase likelihood without directly maximizing the observed-data log-likelihood in each step.

In practice, the required M-step maximizer may not be available or convenient. The monotonicity proof only requires a candidate that does not decrease $Q$, provided the current parameter remains an admissible comparison. If the update decreases $Q$, however, the proof no longer guarantees that the observed likelihood increases. Exact responsibility calculations and a valid M-step objective are therefore essential to the argument.

Common Pitfall

Wrong reasoning: “The ELBO is a lower bound, so increasing it automatically increases the observed-data likelihood.” The inequality $\mathcal{L}(q,\theta)\leq\ell(\theta)$ alone does not establish that: the bound could rise while the likelihood falls.
Correction: In EM, the E-step makes the bound tight at the current parameter. The M-step then increases the bound while holding $q$ fixed, and the new likelihood is at least that new bound. Both facts are needed for the monotonicity chain.
Another common error: Treating the responsibilities as fixed in the E-step and recomputing them during the M-step. The M-step maximizes $Q$ using the responsibilities calculated at the current parameter; they are updated in the next E-step.

Check Your Understanding

Use the ELBO identity and the EM derivation to answer the following.

What distribution $q(Z)$ makes the ELBO equal the observed-data log-likelihood at a fixed parameter?
Why does the entropy term disappear when maximizing the ELBO over $\theta$ with $q$ held fixed?
For an exact M-step, which parameter value provides the comparison that guarantees $Q$ does not decrease?
Why does an increase in the ELBO alone, without the E-step tightness condition, not prove likelihood monotonicity?
In the three-observation example, verify that the two updated mixing weights sum to one and that the total effective count is three.

Back to Tutorials