×

zbMATH — the first resource for mathematics

Online expectation maximization based algorithms for inference in hidden Markov models. (English) Zbl 1336.62090
Summary: The Expectation Maximization (EM) algorithm is a versatile tool for model parameter estimation in latent data models. When processing large data sets or data stream however, EM becomes intractable since it requires the whole data set to be available at each iteration of the algorithm. In this contribution, a new generic online EM algorithm for model parameter inference in general Hidden Markov Model is proposed. This new algorithm updates the parameter estimate after a block of observations is processed (online). The convergence of this new algorithm is established, and the rate of convergence is studied showing the impact of the block-size sequence. An averaging procedure is also proposed to improve the rate of convergence. Finally, practical illustrations are presented to highlight the performance of these algorithms in comparison to other online maximum likelihood procedures.

MSC:
62F12 Asymptotic properties of parametric estimators
62L20 Stochastic approximation
62L12 Sequential estimation
60J22 Computational methods in Markov chains
65C60 Computational problems in statistics (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Billingsley, P. Probability and Measure . Wiley, New York, 3rd edition, 1995.
[2] Cappé, O. Online sequential Monte Carlo EM algorithm. In IEEE Workshop on Statistical Signal Processing (SSP) , 2009.
[3] Cappé, O. Online EM algorithm for Hidden Markov Models. J. Comput. Graph. Statist. , 20(3):728-749, 2011.
[4] Cappé, O. and Moulines, E. Online Expectation Maximization algorithm for latent data models. J. Roy. Statist. Soc. B , 71(3):593-613, 2009. 10.1111/j.1467-9868.2009.00698.x Cappé, O., Moulines, E. and Rydén, T. Inference in Hidden Markov Models . Springer, 2005. · Zbl 1250.62015
[5] Carlin, B. P., Polson, N. G. and Stoffer, D. S. A Monte Carlo approach to nonnormal and nonlinear state space modeling. Journal of the American Statistical Association , 87:493-500, 1992.
[6] Churchill, G. Hidden Markov chains and the analysis of genome structure. Computers & Chemistry , 16(2):107-115, 1992. · Zbl 0752.92015
[7] Davidson, J. Stochastic Limit Theory: An Introduction for Econometricians . Oxford University Press, 1994. · Zbl 0904.60002
[8] Del Moral, P. and Guionnet, A. Large deviations for interacting particle systems: applications to non-linear filtering. Stoch. Proc. App. , 78:69-95, 1998. · Zbl 0934.60026
[9] Del Moral, P., Ledoux, M. and Miclo, L. On contraction properties of Markov kernels. Probab. Theory Related Fields , 126(3):395-420, 2003. · Zbl 1030.60060
[10] Del Moral, P., Doucet, A. and Singh, S. S. Forward smoothing using sequential Monte Carlo.
[11] Dempster, A. P., Laird, N. M. and Rubin, D. B. Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc. B , 39(1):1-38 (with discussion), 1977. · Zbl 0364.62022
[12] Douc, R., Moulines, E. and Rydén, T. Asymptotic properties of the maximum likelihood estimator in autoregressive models with Markov regime. Ann. Statist. , 32(5):2254-2304, 2004. · Zbl 1056.62028
[13] Doucet, A., De Freitas, N. and Gordon, N., editors. Sequential Monte Carlo Methods in Practice . Springer, New York, 2001. · Zbl 0967.00022
[14] Dubarry, C. and Le Corff, S. Nonasymptotic deviation inequalities for smoothed additive functionals in non-linear state-space models. Accepted for publication in Bernoulli , · Zbl 1411.60116
[15] Fort, G. and Moulines, E. Convergence of the Monte Carlo Expectation Maximization for curved exponential families. Ann. Statist. , 31(4):1220-1259, 2003. · Zbl 1043.62015
[16] Hall, P. and Heyde, C. C. Martingale Limit Theory and its Application . Academic Press, New York, London, 1980. · Zbl 0462.60045
[17] Juang, B. and Rabiner, L. Hidden Markov models for speech recognition. Technometrics , 33:251-272, 1991. · Zbl 0762.62036
[18] Kushner, H. J. and Yin, G. G. Stochastic Approximation Algorithms and Applications . Springer, 1997. · Zbl 0914.60006
[19] Le Corff, S. and Fort, G. Supplement paper to “Online Expectation Maximization based algorithms for inference in Hidden Markov Models”. Technical report, · Zbl 1336.62090
[20] Le Corff, S. and Fort, G. Convergence of a Particle-Based Approximation of the Block Online Expectation Maximization Algorithm. ACM Trans. Model. Comput. Simul. , 23(1):2:1-2:22, 2013. · Zbl 1384.62066
[21] Le Corff, S., Fort, G. and Moulines, E. Online EM algorithm to solve the SLAM problem. In IEEE Workshop on Statistical Signal Processing (SSP) , 2011.
[22] Le Gland, F. and Mevel, L. Recursive estimation in HMMs. In Proc. IEEE Conf. Decis. Control , pages 3468-3473, 1997.
[23] Mamon, R. S. and Elliott, R. J. Hidden Markov Models in Finance , volume 104 of International Series in Operations Research & Management Science . Springer, Berlin, 2007.
[24] Meyn, S. P. and Tweedie, R. L. Markov Chains and Stochastic Stability . Springer, London, 1993. · Zbl 0925.60001
[25] Mongillo, G. and Denève, S. Online learning with hidden Markov models. Neural Computation , 20(7):1706-1716, 2008. 10.1162/neco.2008.10-06-351. · Zbl 1147.68646
[26] Pólya, G. and Szegő, G. Problems and Theorems in Analysis. Vol. II . Springer, 1976.
[27] Polyak, B. T. and Juditsky, A. B. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. , 30(4):838-855, 1992. · Zbl 0762.62022
[28] Rio, E. Théorie asymptotique des processus aléatoires faiblement dépendants . Springer, 1990.
[29] Tadić, V. B. Analyticity, convergence, and convergence rate of recursive maximum-likelihood estimation in hidden Markov models. IEEE Trans. Inf. Theor. , 56:6406-6432, December 2010. ISSN 0018-9448. · Zbl 1366.62166
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.