Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime

Antoine Chambaz; Catherine Matias

ESAIM: Probability and Statistics (2009)

  • Volume: 13, page 38-50
  • ISSN: 1292-8100

Abstract

top
This paper deals with order identification for Markov chains with Markov regime (MCMR) in the context of finite alphabets. We define the joint order of a MCMR process in terms of the number k of states of the hidden Markov chain and the memory m of the conditional Markov chain. We study the properties of penalized maximum likelihood estimators for the unknown order (k, m) of an observed MCMR process, relying on information theoretic arguments. The novelty of our work relies in the joint estimation of two structural parameters. Furthermore, the different models in competition are not nested. In an asymptotic framework, we prove that a penalized maximum likelihood estimator is strongly consistent without prior bounds on k and m. We complement our theoretical work with a simulation study of its behaviour. We also study numerically the behaviour of the BIC criterion. A theoretical proof of its consistency seems to us presently out of reach for MCMR, as such a result does not yet exist in the simpler case where m = 0 (that is for hidden Markov models).

How to cite

top

Chambaz, Antoine, and Matias, Catherine. "Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime." ESAIM: Probability and Statistics 13 (2009): 38-50. <http://eudml.org/doc/250627>.

@article{Chambaz2009,
abstract = { This paper deals with order identification for Markov chains with Markov regime (MCMR) in the context of finite alphabets. We define the joint order of a MCMR process in terms of the number k of states of the hidden Markov chain and the memory m of the conditional Markov chain. We study the properties of penalized maximum likelihood estimators for the unknown order (k, m) of an observed MCMR process, relying on information theoretic arguments. The novelty of our work relies in the joint estimation of two structural parameters. Furthermore, the different models in competition are not nested. In an asymptotic framework, we prove that a penalized maximum likelihood estimator is strongly consistent without prior bounds on k and m. We complement our theoretical work with a simulation study of its behaviour. We also study numerically the behaviour of the BIC criterion. A theoretical proof of its consistency seems to us presently out of reach for MCMR, as such a result does not yet exist in the simpler case where m = 0 (that is for hidden Markov models). },
author = {Chambaz, Antoine, Matias, Catherine},
journal = {ESAIM: Probability and Statistics},
keywords = {Markov regime; order estimation; hidden states; conditional memory; hidden Markov model},
language = {eng},
month = {2},
pages = {38-50},
publisher = {EDP Sciences},
title = {Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime},
url = {http://eudml.org/doc/250627},
volume = {13},
year = {2009},
}

TY - JOUR
AU - Chambaz, Antoine
AU - Matias, Catherine
TI - Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime
JO - ESAIM: Probability and Statistics
DA - 2009/2//
PB - EDP Sciences
VL - 13
SP - 38
EP - 50
AB - This paper deals with order identification for Markov chains with Markov regime (MCMR) in the context of finite alphabets. We define the joint order of a MCMR process in terms of the number k of states of the hidden Markov chain and the memory m of the conditional Markov chain. We study the properties of penalized maximum likelihood estimators for the unknown order (k, m) of an observed MCMR process, relying on information theoretic arguments. The novelty of our work relies in the joint estimation of two structural parameters. Furthermore, the different models in competition are not nested. In an asymptotic framework, we prove that a penalized maximum likelihood estimator is strongly consistent without prior bounds on k and m. We complement our theoretical work with a simulation study of its behaviour. We also study numerically the behaviour of the BIC criterion. A theoretical proof of its consistency seems to us presently out of reach for MCMR, as such a result does not yet exist in the simpler case where m = 0 (that is for hidden Markov models).
LA - eng
KW - Markov regime; order estimation; hidden states; conditional memory; hidden Markov model
UR - http://eudml.org/doc/250627
ER -

References

top
  1. D. Blackwell and L. Koopmans, On the identifiability problem for functions of finite Markov chains. Ann. Math. Stat.28 (1957) 1011–1015.  
  2. S. Boucheron and E. Gassiat, Order estimation and model selection, in Inference in hidden Markov models, Olivier Cappé, Eric Moulines, and Tobias Rydén (Eds.), Springer Series in Statistics. New York, NY: Springer (2005).  
  3. R.J. Boys and D.A. Henderson, A Bayesian approach to DNA sequence segmentation. Biometrics60 (2004) 573–588.  
  4. O. Cappé, E. Moulines and T. Rydén (Eds.), Inference in hidden Markov models. Springer Series in Statistics (2005).  
  5. I. Csiszár and Z. Talata, Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Info. Theory52 (2006) 1007–1016.  
  6. L.D. Davisson, R.J. McEliece, M.B. Pursley and M.S. Wallace, Efficient universal noiseless source codes. IEEE Trans. Inf. Theory27 (1981) 269–279.  
  7. A.P. Dempster, N.M. Laird and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. Ser. B39 (1977) 1–38. With discussion.  
  8. Y. Ephraim and N. Merhav, Hidden Markov processes. IEEE Trans. Inform. Theory, special issue in memory of Aaron D. Wyner48 (2002) 1518–1569.  
  9. L. Finesso, Consistent estimation of the order for Markov and hidden Markov chains. Ph.D. Thesis, University of Maryland, ISR, USA (1991).  
  10. C-D. Fuh, Efficient likelihood estimation in state space models. Ann. Stat.34 (2006) 2026–2068.  
  11. E. Gassiat and S. Boucheron, Optimal error exponents in hidden Markov model order estimation. IEEE Trans. Info. Theory48 (2003) 964–980.  
  12. E.J. Hannan, The estimation of the order of an ARMA process. Ann. Stat.8 (1980) 1071–1081.  
  13. H. Ito, S.I. Amari and K. Kobayashi, Identifiability of hidden Markov information sources and their minimum degrees of freedom. IEEE Trans. Inf. Theory38 (1992) 324–333.  
  14. J.C. Kieffer, Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Trans. Inf. Theory39 (1993) 893–902.  
  15. B.G. Leroux, Maximum-likelihood estimation for hidden Markov models. Stochastic Process. Appl.40 (1992) 127–143.  
  16. C.C. Liu and P. Narayan, Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures. IEEE Trans. Inf. Theory40 (1994) 1167–1180.  
  17. R.J. MacKay, Estimating the order of a hidden markov model. Canadian J. Stat.30 (2002) 573–589.  
  18. P. Nicolas, L. Bize, F. Muri, M. Hoebeke, F. Rodolphe, S.D. Ehrlich, B. Prum and P. Bessières, Mining bacillus subtilis chromosome heterogeneities using hidden Markov models. Nucleic Acids Res.30 (2002) 1418–1426.  
  19. P. Nicolas, A.S. Tocquet and F. Muri-Majoube, SHOW User Manual. URL: (2004). Software available at URL: .  URIhttp://www-mig.jouy.inra.fr/ssb/SHOW/show_doc.pdf
  20. B.M. Pötscher, Estimation of autoregressive moving-average order given an infinite number of models and approximation of spectral densities. J. Time Ser. Anal.11 (1990) 165–179.  
  21. C.P. Robert, T. Rydén and D.M. Titterington, Bayesian inference in hidden Markov models through the reversible jump Markov chain Monte Carlo method. J. R. Stat. Soc., Ser. B, Stat. Methodol.62 (2000) 57–75.  
  22. T. Rydén, Estimating the order of hidden Markov models. Statistics26 (1995) 345–354.  
  23. Y.M. Shtar'kov, Universal sequential coding of single messages. Probl. Inf. Trans.23 (1988) 175–186.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.