Generalized EM and Constrained M-Steps

Why an Exact M-Step Is Not Always Necessary

In the expectation-maximization algorithm, the E-step forms an auxiliary function using the current parameter estimate, and the M-step maximizes that function. Exact maximization is convenient when it has a closed form, as in the usual Gaussian mixture update. In more complicated models, however, a constrained optimization may be costly, or the available calculation may produce only an improving candidate. The key fact is that an exact maximum is not required for likelihood monotonicity: it is enough that the update does not decrease the auxiliary function.

This observation gives generalized EM, often abbreviated GEM. A related strategy, expectation-conditional-maximization (ECM), replaces one joint M-step by a sequence of maximizations over parameter blocks. Both methods rely on the same inequality connecting the auxiliary function to the observed-data log-likelihood.

Auxiliary Function and Generalized EM

Let \(x\) denote the observed data and \(z\) the latent allocation. Write \(p_\theta(x,z)\) for the joint density or mass function under parameter \(\theta\), and \(p_\theta(x)=\sum_z p_\theta(x,z)\) for the observed-data likelihood in a finite latent-allocation model. Let \(\Theta\) be the feasible parameter space. At a current feasible value \(\theta^{(t)}\), the posterior distribution of the latent allocation is \(q_t(z)=p_{\theta^{(t)}}(z\mid x)\).

Definition: The EM auxiliary function at \(\theta^{(t)}\) is \(Q(\theta\mid\theta^{(t)})=E_{\theta^{(t)}}[\log p_\theta(x,Z)\mid x]\), where the expectation is over the conditional distribution of \(Z\) given \(x\) at \(\theta^{(t)}\). An exact M-step chooses a feasible maximizer of \(Q(\theta\mid\theta^{(t)})\) over \(\Theta\). A generalized EM step chooses any feasible \(\theta^{(t+1)}\) satisfying \(Q(\theta^{(t+1)}\mid\theta^{(t)})\ge Q(\theta^{(t)}\mid\theta^{(t)})\).

The distinction is about what the update is required to do, not how it is computed. A constrained optimizer that finds a maximum is still an exact M-step, even if that maximum differs from the unconstrained one. A numerical or approximate update is a GEM step if it is feasible and its auxiliary-function value is verified not to decrease.

Why Auxiliary-Function Ascent Preserves Likelihood

For any candidate parameter, the auxiliary function alone does not equal the observed log-likelihood. The difference is accounted for by a Kullback–Leibler divergence between the current latent posterior and the candidate latent posterior. This gives a precise monotonicity guarantee.

Theorem: Suppose \(p_{\theta^{(t)}}(x)>0\) and \(p_{\theta^{(t+1)}}(x)>0\), and the relevant log-likelihoods and auxiliary-function expectations are finite. Suppose also that \(q_t\) is absolutely continuous with respect to \(p_{\theta^{(t+1)}}(z\mid x)\), so the divergence below is defined and finite. Then \(\ell(\theta^{(t+1)})-\ell(\theta^{(t)}) = Q(\theta^{(t+1)}\mid\theta^{(t)})-Q(\theta^{(t)}\mid\theta^{(t)}) +\operatorname{KL}\{q_t\,\|\,p_{\theta^{(t+1)}}(Z\mid x)\}\). Consequently, every GEM update has nondecreasing observed-data log-likelihood.

Proof. For any feasible \(\theta\), expand the divergence using the posterior identity \(p_\theta(z\mid x)=p_\theta(x,z)/p_\theta(x)\):

\begin{aligned} \operatorname{KL}\{q_t\,\|\,p_\theta(Z\mid x)\} &= E_{q_t}\left[\log\frac{q_t(Z)}{p_\theta(Z\mid x)}\right]\\ &= E_{q_t}[\log q_t(Z)] -E_{q_t}[\log p_\theta(x,Z)] +\ell(\theta). \end{aligned}

Apply this identity first at \(\theta=\theta^{(t+1)}\), then at \(\theta=\theta^{(t)}\). At the current parameter, \(q_t\) is its own posterior, so \(\operatorname{KL}\{q_t\,\|\,p_{\theta^{(t)}}(Z\mid x)\}=0\). Subtracting the two identities cancels \(E_{q_t}[\log q_t(Z)]\) and gives the displayed equality. A Kullback–Leibler divergence is nonnegative. Thus if the GEM condition makes the difference in \(Q\) nonnegative, the difference in \(\ell\) is nonnegative as well. \(\square\)

The theorem states a guarantee, not a claim that every improving auxiliary-function update gives a strict likelihood increase. The divergence term can be positive even when \(Q\) is unchanged, and both terms can be zero. Conversely, the argument requires a valid, finite auxiliary-function comparison. If a proposed update makes a complete-data log density equal to \(-\infty\) on allocations that have positive current posterior probability, the finite-\(Q\) condition fails; one cannot claim monotonicity by applying the finite identity without checking its assumptions.

Worked Example: A Partial Update of a Mixture Weight

Consider one observed binary value \(x=1\) from a two-component Bernoulli mixture. The component success probabilities are fixed at \(p_1=0.8\) and \(p_2=0.2\). At the current parameter, \(\pi_1=0.5\), so the observed likelihood is \(0.5(0.8)+0.5(0.2)=0.5\), and the current posterior responsibility for component 1 is \(q_t(1)=0.8\).

Make a partial update to \(\pi_1=0.6\), leaving the component probabilities unchanged. The auxiliary-function change comes only from the allocation probabilities: \(Q_{\mathrm{new}}-Q_{\mathrm{old}}=0.8\log(0.6/0.5)+0.2\log(0.4/0.5)\). Numerically, this is approximately \(0.1012>0\), so this is a GEM update, even though it need not be the maximizing update.

The new observed likelihood is \(0.6(0.8)+0.4(0.2)=0.56\), which exceeds \(0.5\). Its log-likelihood increase is \(\log(0.56/0.5)=\log(1.12)\approx0.1133\). The new posterior probabilities are \(6/7\) and \(1/7\); the divergence from the old posterior \((0.8,0.2)\) is approximately \(0.0121\). Thus the identity gives \(0.1012+0.0121\approx0.1133\), matching the observed increase.

Constrained M-Steps

A constrained M-step maximizes \(Q\) over the actual feasible parameter set, not over a larger unconstrained space. If a constrained maximizer exists and its \(Q\)-value is at least that at the current feasible parameter, the theorem guarantees likelihood monotonicity. The maximizing value may lie on the boundary of the constraint set; that does not weaken the argument.

Worked Example: A Mixture-Weight Constraint

Suppose the current E-step gives expected component counts 4 and 6. Ignoring terms that do not depend on the mixture weight, the auxiliary function for \(\pi_1\) is \(Q(\pi_1)=4\log\pi_1+6\log(1-\pi_1)\). Now impose the constraint \(0.6\le\pi_1<1\).

Without the constraint, the derivative is \(4/\pi_1-6/(1-\pi_1)\), which is zero at \(\pi_1=4/10=0.4\). For every \(\pi_1\ge0.6\), the derivative is negative: indeed, \(4/\pi_1\le 4/0.6\) while \(6/(1-\pi_1)\ge15\). Therefore the constrained maximum is at the boundary \(\pi_1=0.6\).

If the current feasible value is \(\pi_1=0.7\), the constrained update increases \(Q\) by \(Q(0.6)-Q(0.7)=4\log(6/7)+6\log(4/3)\approx1.1095\). It is therefore a valid GEM update, and the observed log-likelihood cannot decrease. Maximizing over the unconstrained space and reporting \(0.4\) would not be a valid update for this constrained model because \(0.4\) is infeasible.

Expectation-Conditional-Maximization

In ECM, the E-step is followed by several conditional maximization steps (CM-steps). Each CM-step maximizes the same fixed function \(Q(\cdot\mid\theta^{(t)})\), holding the other parameter blocks at their current values, and respects the feasible parameter space. The latent posterior is not recomputed between CM-steps: it remains the one formed at the start of the iteration.

Theorem: Let \(\theta^{(t,0)}=\theta^{(t)}\), and suppose an ECM iteration produces feasible intermediate parameters \(\theta^{(t,1)},\ldots,\theta^{(t,m)}\) such that \(Q(\theta^{(t,j)}\mid\theta^{(t)})\ge Q(\theta^{(t,j-1)}\mid\theta^{(t)})\) for every \(j=1,\ldots,m\). Setting \(\theta^{(t+1)}=\theta^{(t,m)}\) gives a GEM update and hence a nondecreasing observed-data log-likelihood.

Proof. Chaining the conditional inequalities gives \(Q(\theta^{(t,m)}\mid\theta^{(t)})\ge Q(\theta^{(t,0)}\mid\theta^{(t)})\). Since \(\theta^{(t,0)}=\theta^{(t)}\), this is exactly the GEM condition. The likelihood-monotonicity theorem then gives \(\ell(\theta^{(t+1)})\ge\ell(\theta^{(t)})\). Feasibility of every intermediate value ensures that the final candidate belongs to the model’s parameter space. \(\square\)

Worked Example: A Blockwise Gaussian Mixture Update

Take two observations, \(x_1=0\) and \(x_2=2\), from a two-component univariate Gaussian mixture. Initially, let both weights be \(0.5\), the component means be \(0.5\) and \(1.5\), and both variances be \(v=1/\log 4\). The likelihood ratio of component 1 to component 2 at \(x=0\) is \(\exp\{[(1.5)^2-(0.5)^2]/(2v)\}=\exp(1/v)=4\). At \(x=2\) the ratio is \(1/4\). Thus the E-step responsibilities for component 1 are \(0.8\) and \(0.2\); those for component 2 are \(0.2\) and \(0.8\).

The expected counts are \(N_1=N_2=1\). In a CM-step for the weights, the update is \(\pi_k=N_k/2\), so both remain \(0.5\). In the next CM-step, the weighted means are \(\mu_1=(0.8(0)+0.2(2))/1=0.4\) and \(\mu_2=(0.2(0)+0.8(2))/1=1.6\).

For the variance block, using these new means gives weighted residual sums \(0.8(0-0.4)^2+0.2(2-0.4)^2=0.64\) for component 1 and \(0.2(0-1.6)^2+0.8(2-1.6)^2=0.64\) for component 2. Since each expected count is 1, the conditional variance updates are \(0.64\) for both components. Each block update maximizes \(Q\) over that block with the other blocks held fixed. Therefore each step does not decrease \(Q\), and the completed sweep cannot decrease the observed log-likelihood. The calculation illustrates the ECM guarantee; it does not require a joint maximization to be performed in one operation.

When These Methods Matter—and a Common Pitfall

GEM and ECM are useful when an exact joint maximization is impractical but a feasible improving step is available, or when parameter blocks admit simpler conditional optimizations. Their guarantee is local to each iteration: it concerns the observed-data likelihood at the current and next parameter values. It does not establish that an iteration reaches a global maximum, that every step is strictly improving, or that a particular stopping point is statistically desirable.

Pitfall: checking the wrong objective. A parameter update that improves a surrogate, penalty, or numerical score is not automatically a GEM update. The condition concerns \(Q(\theta\mid\theta^{(t)})\) for the fixed current E-step.
Pitfall: recomputing responsibilities mid-sweep. ECM CM-steps use the same \(q_t\) throughout one iteration. Recomputing it changes the objective being compared; that is a different algorithm and requires its own justification.
Pitfall: ignoring feasibility. A block update must leave the full parameter vector feasible. Maximizing one coordinate without respecting coupled constraints may produce an invalid candidate.
Pitfall: assuming approximate means improving. An approximate optimizer qualifies only after its candidate is feasible and its \(Q\)-value is shown to be no smaller than the current value. Otherwise, the monotonicity theorem does not apply.

A practical implementation can evaluate the fixed auxiliary function before accepting a proposed update, or use a backtracking procedure that retains only feasible candidates with nondecreasing \(Q\). The essential safeguard is not the name of the optimizer; it is the verified ascent condition.

Check Your Understanding

Use the definitions and monotonicity argument to answer these questions.

What condition distinguishes a generalized EM update from an exact M-step?
In the likelihood-difference identity, what role does the Kullback–Leibler divergence play?
Why must a constrained M-step optimize over the feasible parameter set rather than the unconstrained space?
During an ECM iteration, why is the E-step posterior held fixed across the conditional maximization steps?
An approximate update is feasible but decreases \(Q(\theta\mid\theta^{(t)})\). What can the GEM monotonicity result conclude about its likelihood change?