AI Glossary / Probabilistic machine learning / Advanced

Online expectation maximization

Definition

Online expectation maximization (online EM) updates a latent-variable model as observations arrive, rather than repeatedly processing the entire dataset in batch EM iterations. A common formulation maintains running expected sufficient statistics, incorporates each new observation using a learning rate, and maps the updated statistics into new parameter estimates.

What it means

In a mixture model, an observation's generating component is unknown. An E-step assigns conditional probabilities to the possible components. Batch EM recomputes such quantities across the dataset; online EM incorporates new information into a compact running summary.
This makes the method useful for large datasets or streams, but changes its behavior. Earlier observations were processed using earlier parameter estimates. Their contributions are not necessarily the same as recomputing every latent expectation under the latest parameters. Online EM is therefore not simply batch EM executed faster with identical intermediate results.

How it works

For suitable latent-variable models, compute the new observation's expected complete-data sufficient statistic under the current parameter estimate. Update the running statistic as s_new = (1 - gamma) s_old + gamma s_expected. Then apply the model's M-step mapping to s_new.
The learning rate gamma determines how much the new information changes the summary. Decreasing schedules can support convergence under appropriate stability and regularity conditions. A fixed learning rate gives continuing influence to recent observations and can support tracking, but does not carry the same convergence interpretation as a diminishing schedule.
The averaging occurs in sufficient-statistic space. In general, averaging independently fitted parameter estimates is not equivalent because the M-step can be nonlinear. Initialization must also keep the running statistics in a region where the M-step is defined. Models with dependent latent sequences can require additional machinery beyond the independent-observation formulation.

Three practical examples

• Streaming mixtures: analysts update mixture weights and component summaries as records arrive, retaining soft responsibilities rather than assigning each record to one component with certainty.
• Large-data estimation: a team makes sequential passes through data that would be expensive to repeatedly process in full batch E-steps. It records order, initialization and learning-rate choices.
• Changing environments: researchers investigate a fixed-rate variant for tracking changing patterns, evaluating responsiveness and variability rather than claiming convergence to one fixed population optimum.

Think of it this way

Imagine maintaining a weighted ledger of uncertain memberships. Each new record contributes fractional credits to several categories. The ledger changes gradually, and the model is reconstructed from its totals. Rebuilding the ledger from all old records using today's model would be a different calculation from simply carrying the old totals forward.

Worked example

Consider an original mixture with two known Bernoulli components. Component A produces a success with probability 0.8, and component B produces a success with probability 0.2. Only the mixing weight pi for A is estimated. The component success probabilities remain fixed throughout this example.
Initialize the running expected membership of A at 0.5, so pi = 0.5. The first observed outcome is a success. Its responsibility for A is [0.5 times 0.8] divided by [0.5 times 0.8 + 0.5 times 0.2] = 0.8.
Choose a stipulated learning rate of 1/4. The running membership becomes (3/4) times 0.5 + (1/4) times 0.8 = 0.575, or 23/40. For this restricted model, the M-step sets the mixing weight equal to that running membership.
The next observation is a failure. Recompute its responsibility using the updated pi. The numerator is (23/40) times 0.2, and the denominator adds (17/40) times 0.8. The responsibility is 23/91, approximately 0.252747. With a new stipulated rate of 1/5, the next mixing weight is (4/5) times (23/40) + (1/5) times (23/91) = 2323/4550, approximately 0.510549.
The complementary weight for B is approximately 0.489451, so the weights still sum to one. The observed success rate over these two records is exactly one half, but that is not the same quantity as a component mixing weight. The update also retains its initialization and rate history. These two steps illustrate the recursion; they do not show convergence or establish the best learning-rate schedule. Estimating unknown component probabilities as well would require additional sufficient statistics and introduce a different estimation problem.

Illustrative case study

Fictional company Cedar Records models incoming operational measurements with a mixture distribution. Its researchers first verify responsibility calculations and statistic updates on a small example. They then compare sequential fits under several data orders and initializations, checking predictive behavior on later records.
The team distinguishes estimating a stable population from tracking a changing one. For the latter, it evaluates how quickly a fixed-rate method responds and how much its estimates fluctuate. It avoids interpreting a smooth parameter trace as proof of global optimality. This is a fictional research workflow, not a measured deployment outcome.

Common misconceptions and mistakes

Online EM does not require hard assignments to latent classes. It does not guarantee that each incoming-record update increases the likelihood of every previously observed record. Batch EM's ascent property should not be transferred automatically to the online recursion.
A fixed learning rate and a decreasing rate serve different statistical purposes. Neither removes the need for valid sufficient statistics or an appropriate model. Convergence results generally concern stationary points under assumptions, not guaranteed discovery of a global optimum. Finally, processing a stream does not make the method Bayesian inference over its unknown parameters; ordinary online EM produces parameter estimates.

Business use

Online EM can reduce storage and repeated computation when a latent-variable model has manageable sufficient statistics. It can be attractive for continuously updated models, provided teams distinguish adaptation from stable estimation. Operational monitoring should cover numerical stability, sensitivity to initialization and changes in data quality, alongside the usefulness of the resulting predictions.

People also ask

Does it need to store every past observation?

In suitable sufficient-statistic formulations, no; compact running summaries can support updates.

Is the learning rate always one divided by the observation count?

No. Different schedules are possible and affect behavior.

Does it work unchanged for hidden Markov models?

No. Temporal dependence requires an appropriate extension rather than blindly applying independent-data updates.

Check your understanding

Why was the second responsibility computed with 0.575?

Answer: Responsibilities use the current parameter estimate.

Why is parameter averaging not generally equivalent?

Answer: The M-step mapping from statistics to parameters can be nonlinear.

What do two successful arithmetic updates prove?

Answer: That the illustrated recursion was evaluated correctly, not that the algorithm converged.

Related terms

• Expectation-maximization
• Sufficient statistic
• Learning rate
• Concept drift
• Stochastic approximation
• Mixture model
• Responsibility

Learn next

Derive sufficient statistics for a small mixture, compare online updates with a full batch E-step, and study how decreasing and fixed rates weight historical information.

More in Probabilistic machine learning

• Nonstationary kernel - A nonstationary kernel is a covariance function whose value can change when both inputs are translated by the same amount.
• Normalizing-flow Kalman filter - A normalizing-flow Kalman filter combines a linear Gaussian state-space model with an invertible transformation of its noisy observations.
• One-standard-error rule - The one-standard-error rule selects a simpler model whose estimated validation error is no more than one estimated standard error above the smallest...
• Open-universe probability model - An open-universe probability model represents uncertainty about which objects exist, how many there are, and how observations refer to them.
• Open world classification - Open world classification recognizes examples from known categories, allows unfamiliar examples to remain unknown, and supports adding newly established...
• Ordinal probit regression - Ordinal probit regression models an ordered categorical outcome using a latent linear score with normally distributed noise.

Sources

Cappe and Moulines, Online EM Algorithm for Latent Data Models, Section 2.3, especially Equation 15: https://arxiv.org/abs/0712.4273 . The fixed-component Bernoulli example and fictional company case are original illustrations. Section 2.3 statistic recursion independently consulted; both responsibilities and updates verified.

Previous: Online complex processing Next: Online gradient descent