PaperlayerView exact revision on arXiv

Source-linked AI summary

Online EM Algorithm for Hidden Markov Models

Olivier Cappé

arXiv:0908.2359v2stat.COstat.ML

TL;DR

Online parameter estimation for HMMs must operate on dependent observations that are scanned once and never stored. The paper combines sufficient-statistics reparameterization with recursive smoothing to construct an online EM algorithm, identifies limiting behavior without a complete convergence proof, and reports performance comparable to maximum likelihood for large samples in a noisily observed Markov-chain setting.

  • Problem

    Online HMM parameter estimation must handle dependent observations in one-pass, unstored data streams, while existing EM-inspired approaches rely on finite-memory approximations or do not directly follow EM principles.

  • Method

    The algorithm reparameterizes the model using complete-data sufficient statistics and computes required HMM smoothing functionals through an auxiliary recursive smoothing update.

  • Results

    The analysis identifies possible limiting points of the recursion through a limiting EM mapping and establishes deterministic large-sample behavior for key quantities, including under parameter freeze.

  • Takeaways & Limitations

    The proposed online EM method extends earlier finite-valued-observation ideas to general HMMs, including continuous observations, with encouraging large-sample estimation performance in the evaluated setting.

  • Takeaways & Limitations

    Complete convergence analysis is missing, and computational attractiveness may decline for models with many distinct or non-finite hidden states.

Abstract

from arXiv · show

Online (also called "recursive" or "adaptive") estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modelling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maximization (EM) methodology consists in reparameterizing the problem using complete-data sufficient statistics. The second ingredient consists in exploiting a purely recursive form of smoothing in HMMs based on an auxiliary recursion. Although the proposed online EM algorithm resembles a classical stochastic approximation (or Robbins-Monro) algorithm, it is sufficiently different to resist conventional analysis of convergence. We thus provide limited results which identify the potential limiting points of the recursion as well as the large-sample behavior of the quantities involved in the algorithm. The performance of the proposed algorithm is numerically evaluated through simulations in the case of a noisily observed Markov chain. In this case, the algorithm reaches estimation results that are comparable to that of the maximum likelihood estimator for large sample sizes.

1 Introduction

The paper targets online HMM parameter estimation from one-pass, unstored observation streams, extending EM-inspired ideas beyond finite-memory or gradient-based approaches. It proposes a general-HMM algorithm built on recursive smoothing and sufficient-statistics reparameterization, while providing preliminary rather than complete convergence analysis.

  • Online HMM estimation processes observations once without storing them, enabling continuous parameter adaptation along potentially infinite data streams.
  • Existing EM-inspired online methods use finite-memory approximations, while gradient-based methods do not directly follow EM principles.
  • The proposed algorithm extends Mongillo and Denève’s online EM approach to general HMMs, including models with continuous observations.Its recursive smoothing recursion is identified as an instance of an established recursive smoothing scheme for sum functionals.
  • The analysis identifies possible limiting points as stationary points of a limiting EM mapping, but a complete convergence analysis remains unavailable.The limiting mapping can be interpreted as the infinite-observation limit of the EM recursion.

2 Online EM Algorithm for HMMs

The online EM algorithm combines exponential-family sufficient statistics with recursive smoothing quantities, updating model parameters as observations arrive. An auxiliary recursion makes the batch E-step’s smoothing computation recursive, while decreasing step sizes and initialization safeguards support online updates.

  • 2.1 Model and Notations: The model assumes a stationary HMM with unknown parameter θ⋆ and a finite-valued hidden state sequence, while the initial distribution is not estimated.
  • 2.2 Exponential-Family Model: The exponential-family formulation represents complete-data structure through sufficient statistics, a natural-parameter map, and a log-partition function.
  • 2.2 Exponential-Family Model: An explicit M-step is required: the function θ̄ maps feasible sufficient-statistics values to the corresponding complete-data maximum-likelihood estimator.
  • 2.3 Online EM Algorithm: The E-step’s normalized smoothing sum is computed recursively using the usual filter and an auxiliary quantity updated through a recursive smoothing proposition.The auxiliary recursion uses backward retrospective probabilities that do not depend on the newly arriving observation.
  • 2.3 Online EM Algorithm: Algorithm 1 uses decreasing step sizes, an initialized parameter, and a minimum observation count before the first update.The minimum count is intended to avoid numerically degenerate early maximum-likelihood equations; the simulations use nmin = 20.

3 Discussion

The discussion distinguishes the proposed HMM recursion from independent-observation stochastic approximation and relates it to earlier online EM methods. It also examines implementation complexity and shows why the finite-observation special case can be optimized without changing the practical update.

  • 3.1 Connections with Previous Works: For independent observations, the update reduces to a standard stochastic-approximation recursion, whereas HMMs require maintaining both an approximate filter and an auxiliary smoothing recursion.
  • 3.1 Connections with Previous Works: The HMM algorithm cannot be analyzed with off-the-shelf stochastic-approximation arguments because its auxiliary update includes a backward retrospective probability.
  • 3.1 Connections with Previous Works: For finite-valued observations, the proposed update coincides with Mongillo and Denève’s equations under the corresponding indicator sufficient statistics.
  • 3.2 Discussion of the Finite-Valued Case: The auxiliary recursion is expected to converge to a deterministic limit, unlike the approximate filtering recursion, supporting decreasing step sizes for the auxiliary quantity but not naturally for the combined update.
  • 3.2 Implementation and Numerical Complexity: The finite-observation special case has per-observation complexity of order |X|^4 × |Y|, reducible to order |X|^4 + |X|^3 × |Y| by separate statistic updates.

4 Some Results on Convergence

The paper establishes large-sample limits for the HMM online EM update and its auxiliary recursion under stated regularity assumptions. Complete convergence analysis remains unavailable, but the results identify deterministic limits and indicate where stable behavior may occur.

  • The normalized HMM log-likelihood converges almost surely and in L1 to a limiting contrast under suitable assumptions.
  • The normalized score converges almost surely to the gradient of the limiting contrast.Fisher identity connects the score to conditional expectations of complete-data quantities.
  • Theorem 1 characterizes the limiting EM update through smoothed sufficient statistics conditioned on the infinite past and future.This limiting form is more complicated for HMMs than for independent observations and motivates recursive smoothing.
  • The convergence results require a finite state space, compact parameter space, an interior true parameter, uniformly positive transitions, and integrability conditions on emissions.
  • The fixed points of the limiting EM algorithm correspond to stationary points of the limiting contrast under the theorem’s assumptions.The paper presents this stability implication heuristically because the auxiliary-recursion result assumes the parameter is frozen.
  • Under parameter freeze, the auxiliary quantity converges to a deterministic constant independent of the state index.Its limit equals the limiting smoothed sufficient-statistics expression used by the EM mapping.

5 Application to Gaussian HMMs

The application evaluates online EM for a noisily observed Markov chain, comparing its estimation behavior with batch EM under challenging state identification. Online EM appears consistent and becomes preferable at larger sample sizes, while averaging can improve asymptotic behavior but introduces tuning concerns.

  • Online EM implementation: The online iteration recursively updates the approximate filter and sufficient statistics before applying the M-step to update the parameters.The M-step separately updates transition parameters and state-dependent Gaussian means and covariance parameters.
  • Experimental model: The scalar experiment models a Markov chain observed with additive Gaussian noise of variance υ, with chain states represented by means µ(1), …, µ(m).State identification is difficult because the means are separated by only 1.4 noise standard deviations, and the optimal filter misclassifies about 10.3% of states.
  • Batch EM comparison: Fixed-iteration batch EM reduces estimate variability as n grows but does not improve accuracy, because its limiting value depends on initialization.Statistical consistency therefore requires increasing the number of batch EM iterations with the sample size.
  • Online EM results: Online EM with γn = n^-0.6 suggests consistent estimation and is preferable to 50 batch EM iterations for n = 8000 and larger, despite somewhat higher variance.At n = 500 and n = 2000, online estimates are less accurate than those from 50 batch iterations.
  • Step-size choice: Hand-tuned step sizes do not significantly improve results over γn = n^-0.6, while larger exponents and γn = n^-1 can produce poor robustness or slow bias reduction.The hand-tuning phase would hardly be feasible in real-life applications, and temporal dependence contributes to slow forgetting of initial filtering and smoothing states.
  • Scope of evaluation: Repeatedly running online EM on the same fixed batch was not considered because this use is less straightforward for HMMs than for independent data.This limits the evaluated comparison to the presented online and batch procedures.
  • Computational cost: The recursive batch-EM implementation and online EM have similar running times, but using the full transition matrix makes their complexity scale as m^4 rather than m^2.The comparison between 50 batch iterations and online estimates is not fair in computing time: batch EM takes about 10 to 40 times longer.
  • Asymptotic behavior: Polyak-Ruppert averaging suggests asymptotic efficiency for µ(1) and υ, whereas q(1,1) retains a slowly disappearing negative bias when averaging begins at n = 8000.Choosing the averaging start optimally is generally infeasible in practice; starting too early slows forgetting of the initial parameter guess.

6 Conclusions

The paper combines sufficient-statistics reparameterization with recursive smoothing to develop online EM for HMMs. Its analysis remains limited, especially regarding convergence and computational scalability for large or non-finite state spaces.

  • The algorithm reparameterizes the model using sufficient statistics and approximates the limiting EM recursion through a stochastic-approximation-like procedure.This is paired with recursive smoothing of hidden-state sum functionals through an auxiliary recursion.
  • Recursive smoothing supplies the HMM-specific component needed because complete-data sufficient statistics cannot be computed directly online.
  • Convergence of Algorithm 1 remains theoretically unresolved because the backward kernel operator complicates application of existing stochastic-approximation results.
  • The method may become computationally less attractive when models contain many distinct state values or have non-finite hidden state spaces.Monte Carlo approximations are suggested for broader state spaces.

A Proofs

The proofs use forgetting bounds to control forward-backward quantities and establish limiting behavior for the online EM recursion. Under the stated finite-state and mixing-related assumptions, the relevant conditional expectations and gradients converge almost surely.

  • Two-sided forgetting bounds control dependence on both past and future observations, enabling asymptotic analysis of smoothing quantities.This extends one-sided forgetting arguments by conditioning in both temporal directions.
  • For finite hidden state spaces, the backward function can be normalized to a pseudo-probability, supporting the proof’s forward-backward decomposition.This normalization property is not generally available outside the finite-state setting.
  • The conditional expectation of complete-data sufficient statistics given increasingly long observation windows converges almost surely and has finite expectation under the true model.Finite first and second moments follow from the stated exponential-family and interior-parameter conditions.
  • The limiting empirical quantities converge to an expectation involving two-sided smoothing, by combining the martingale-style bound with the ergodic theorem.
  • The limiting contrast gradient converges almost surely, and its stationary points correspond to parameter values satisfying the associated limiting EM equation.
  • The auxiliary recursion has the same limiting behavior as the corresponding smoothed sufficient-statistics average under parameter freezing.The argument uses Proposition 1, Corollary 2, and step-size reductions to the case γ_k = k^-1.
Loading 0908.2359v2…