Source-linked AI summary
Online EM Algorithm for Latent Data Models
Olivier Cappé, Eric Moulines
TL;DR
The paper addresses how to perform EM estimation for latent-variable models when data arrive sequentially and cannot be repeatedly stored or accessed. It introduces an online EM algorithm that stochastically updates the E-step while retaining the M-step, achieving convergence at the maximum-likelihood estimator’s rate and extending to regression models. The approach is also analysed when the model is misspecified.
Problem
Batch EM is impractical for large data sets or streams because each iteration requires the whole data, while existing online approaches rely on complete-data information and well-specified models.
Method
The algorithm uses stochastic approximation for the E-step and retains the standard EM maximisation step, without requiring complete-data information-matrix inversion.
Results
The algorithm converges to stationary points of the Kullback-Leibler divergence at the optimal maximum-likelihood-estimator rate and can achieve comparable performance without explicit matrix approximation or inversion.
Takeaways & Limitations
The approach provides a simpler online EM procedure for independent latent-data models and extends naturally to conditional or regression models.
Takeaways & Limitations
The method requires the function ¯θ(s) to be explicit and does not directly cover non-independent models such as hidden Markov models or Markov random fields.
Abstract
from arXiv · showhide
In this contribution, we propose a generic online (also sometimes called adaptive or recursive) version of the Expectation-Maximisation (EM) algorithm applicable to latent variable models of independent observations. Compared to the algorithm of Titterington (1984), this approach is more directly connected to the usual EM algorithm and does not rely on integration with respect to the complete data distribution. The resulting algorithm is usually simpler and is shown to achieve convergence to the stationary points of the Kullback-Leibler divergence between the marginal distribution of the observation and the model distribution at the optimal rate, i.e., that of the maximum likelihood estimator. In addition, the proposed approach is also suitable for conditional (or regression) models, as illustrated in the case of the mixture of linear regressions model.
1 Introduction
The paper develops an online EM algorithm for latent-data models because batch EM requires repeated access to all observations. It stays close to standard EM while addressing practical and theoretical limitations of earlier online approaches.
- Batch EM becomes impractical for large data sets and streams because each iteration requires the whole data set.
- Online EM variants estimate latent-data model parameters without storing the data.
- The proposed algorithm replaces the conventional complete-data-information approach with a stochastic approximation E-step followed by the usual M-step maximisation.
- It avoids evaluating and inverting the complete-data information matrix and does not require the fitted model to be correctly specified.
- The paper states convergence results for consistency and convergence rate, and illustrates performance in mixtures of linear regressions.
2 Algorithm Derivation
The proposed online EM method recursively updates sufficient-statistic information from each observation and then maximises an updated surrogate objective. Its design preserves EM-like parameter updates, avoids explicit matrix inversion, supports conditional models, and can maintain parameter constraints.
- EM basics: The latent-data model treats observations as deterministic functions of unobserved variables distributed under a parameterised complete-data model.
- EM basics: Standard EM alternates a conditional-expectation E-step with an M-step that maximises the resulting expected complete-data log-likelihood.
- Connections and assumptions: For canonical exponential families, the complete-data Fisher information and the limiting matrix used by the gradient recursion coincide; otherwise their convergence behaviour can differ.
- Online setting: The online setting processes each new observation once, using decreasing positive step sizes to update parameter estimates at fixed computational cost.
- Proposed online EM: The proposed method replaces the expectation step by stochastic approximation while retaining the maximisation step, automatically enforcing parameter constraints without explicit matrix inversion.
- Poisson mixture: In the Poisson mixture example, the proposed update preserves intensity constraints, whereas the alternative gradient update can produce negative intensities.
- Conditional models: For conditional regression models, covariate-dependent conditional expectations extend the method when the covariate distribution is unspecified and complete-data expectations are unavailable.
3 Convergence Issues
The proposed online EM algorithm converges almost surely to stationary points of the Kullback–Leibler divergence under stated regularity and stability assumptions. Its convergence-rate analysis links the method to online gradient algorithms and shows how averaging can recover asymptotic efficiency in well-specified models.
- Consistency: Roots of the stochastic-approximation mean field correspond exactly to stationary points of the Kullback–Leibler divergence.Proposition 3 establishes both directions: each root maps to a stationary point, and each stationary point yields a mean-field root.
- Consistency: A Lyapunov function decreases along the unperturbed mean-field iterations, paralleling the monotonicity property of batch EM.This supports global asymptotic stability when the step size is sufficiently small.
- Consistency: The algorithm converges almost surely to the stationary-point set of the Kullback–Leibler divergence between the observation density and model likelihood.The result follows under Assumptions 1–2 and additional boundedness, stability, and step-size conditions.
- Rate of Convergence: Near convergence, online EM is equivalent to an online gradient algorithm while avoiding explicit matrix approximation and inversion.The equivalence uses Iπ(θ) in place of the matrix appearing in Titterington’s recursion; canonical exponential families yield a further coincidence.
- Rate of Convergence: Polyak–Ruppert averaging yields an asymptotically efficient sequence in well-specified models, with covariance equal to the inverse observed-data Fisher information matrix.For γn = γ0n^-α with α ∈ (1/2, 1), averaging avoids the scale constraint required for the optimal 1/√n rate of the unaveraged recursion.
4 Application to Mixtures of Gaussian Regressions
The paper applies online EM to finite mixtures of Gaussian linear regressions, including a conditional-likelihood setting where the complete-data Fisher information is unavailable. Simulations compare batch EM, online step sizes, and Polyak-Ruppert averaging, with averaging providing the most favorable large-sample behavior.
- Model: The model is a finite mixture of Gaussian linear regressions with latent class indicators, regression vectors, mixture weights, and variances.The observed data are responses and regressors, while the mixture indicator is latent.
- Algorithm: The E-step uses conditional expectations of the latent indicator, and the M-step updates sufficient statistics and regression parameters.The sufficient-statistic vector includes four statistic blocks per mixture component; parameter re-estimation requires states in the set S.
- Model: Online EM maximizes the conditional likelihood of responses given regressors without explicitly modeling the regressors’ marginal distribution.This conditional formulation is not fully specified as a joint observation model, but the preceding theory applies.
- Results: The regression coefficients are highly correlated, making an unweighted parameter-space stochastic approximation inefficient.The simulated asymptotic standard deviations for each βj coordinate are reported as (47.8, 22.1, 21.1).
- Simulation design: The simulations compare five batch-EM iterations with online step sizes γn = 1/n, γn = n^-0.6, and n^-0.6 plus averaging from n/2.Each method starts from the same point and is evaluated over 500 independent simulated replicas for n = 100 and n = 10,000.
- Results: OL06a is the only approach reported as having variance compatible with the asymptotic benchmark, while its systematic bias vanishes as n increases.Averaging substantially reduces OL06 variability; longer runs confirmed the observed n^-1/2 inconsistency of batch EM suggested by Figure 3.
5 Conclusion
The proposed online EM algorithm combines close correspondence with batch EM and provably optimal convergence behavior. Its robustness is supported by slow parameter decrease with Polyak–Ruppert averaging, while explicit maximization limits some extensions.
- The algorithm mirrors standard batch EM, making it easier to implement while retaining provably optimal convergence behavior.
- A typical step-size choice is γn = n−0.5+ǫ, combined with Polyak–Ruppert averaging.
- The combination of slow parameter decrease and Polyak–Ruppert averaging appears to be very robust.
- The function ¯θ(s) must be explicit, excluding mixture-of-regressions models with generalised link functions from this formulation.
A Proofs
The proofs establish convergence properties by analyzing the EM maximization map, its mean field, martingale errors, and local linearization. Under the stated assumptions, sufficient statistics and parameter estimates converge toward stationary or limiting sets, with positive local stability properties.
- The latent-model score satisfies ∇θ log g(y; θ) = −∇θψ(θ) + ∇θφT(θ)¯s(y; θ), linking observed-data gradients to sufficient statistics.
- Roots of the mean field correspond to stationary points of the Kullback–Leibler divergence through the relation ∇θK(π ∥ gθ) = −∇θψ(θ) + ∇θφT(θ)Eπ[¯s(Y; θ)].
- Under the assumptions, the sufficient-statistics sequence approaches the limiting set Γ almost surely, and parameter estimates follow by continuity of ¯θ.
- The stochastic-approximation remainder satisfies rn = oP(1), because the step-size-weighted fluctuation term converges to zero in probability.
- At a possibly local KL minimum, the mean-field Jacobian is related to the KL Hessian through the complete-data information matrix.
- The relevant eigenvalues are all real and strictly positive, establishing the theorem’s first stability assertion under the stated assumptions.