We consider the problem of estimating the number of hidden states (the order) of a nonparametric hidden Markov model (HMM). We propose two different methods and prove their almost sure consistency without any prior assumption, be it on the order or on the emission distributions. This is the first time a consistency result is proved in such a general setting without using restrictive assumptions such as a priori upper bounds on the order or parametric restrictions on the emission distributions. Our main method relies on the minimization of a penalized least squares criterion. In addition to the consistency of the order estimation, we also prove that this method yields rate minimax adaptive estimators of the parameters of the HMM - up to a logarithmic factor. Our second method relies on estimating the rank of a matrix obtained from the distribution of two consecutive observations. Finally, numerical experiments are used to compare both methods and study their ability to select the right order in several situations.
From a theoretical point of view, the order estimation problem remains widely open in the HMM framework. One can distinguish two kinds of results. The first kind does not need an upper bound on the order, but is only applicable to restrictive cases. For instance, using tools from coding theory, @cite_20 introduced a penalized maximum likelihood order estimator for which they prove strong consistency without upper bound on the order of the HMM. Nevertheless, their result is restricted to a finite observation space and they have to use heavy penalties that grow as a power of the order. For the special case of Gaussian or Poisson emission distributions, @cite_17 showed that the penalized maximum likelihood estimator is strongly consistent without any upper bound on the order. The second kind of results is more general but requires an upper bound of the order just to get weak consistency of order estimators, for penalized likelihood criterion ( @cite_6 ) as well as Bayesian approaches ( @cite_0 @cite_3 ).
@cite_3 @cite_6 @cite_0 @cite_20 @cite_17
2043862650 2119525808 2155805386 1996769950
Abstract We give two simple inequalities on likelihood ratios. A first application is the consistency of the maximum-penalized marginal-likelihood estimator of the number of populations in a mixture with Markov regime. The second application is the derivation of the asymptotic power of the likelihood ratio test under loss of identifiability for contiguous alternatives. Finally, we propose self-normalized score tests that have exponentially decreasing level and asymptotic power 1. We consider finite state space stationary hidden Markov models (HMMs) in the situation where the number of hidden states is unknown. We provide a frequentist asymptotic evaluation of Bayesian analysis methods. Our main result gives posterior concentration rates for the marginal densities, that is for the density of a fixed number of consecutive observations. Using conditions on the prior, we are then able to define a consistent Bayesian estimator of the number of hidden states. It is known that the likelihood ratio test statistic for overfitted HMMs has a nonstandard behaviour and is unbounded. Our conditions on the prior may be seen as a way to penalize parameters to avoid this phenomenon. Inference of parameters is a much more difficult task than inference of marginal densities, we still provide a precise description of the situation when the observations are i.i.d. and we allow for 2 possible hidden states. We consider the estimation of the number of hidden states (the order) of a discrete-time finite-alphabet hidden Markov model (HMM). The estimators we investigate are related to code-based order estimators: penalized maximum-likelihood (ML) estimators and penalized versions of the mixture estimator introduced by Liu and Narayan (1994). We prove strong consistency of those estimators without assuming any a priori upper bound on the order and smaller penalties than previous works. We prove a version of Stein's lemma for HMM order estimation and derive an upper bound on underestimation exponents. Then we prove that this upper bound can be achieved by the penalized ML estimator and by the penalized mixture estimator. The proof of the latter result gets around the elusive nature of the ML in HMM by resorting to large-deviation techniques for empirical processes. Finally, we prove that for any consistent HMM order estimator, for most HMM, the overestimation exponent is null. Abstract We address the issue of order identification for hidden Markov models with Poisson and Gaussian emissions. We prove information-theoretic BIC-like mixture inequalities in the spirit of Finesso [1991. Consistent estimation of the order for Markov and hidden Markov chains. Ph.D. Thesis, University of Maryland]; Liu and Narayan [1994. Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures. Canad. J. Statist. 30(4), 573–589]; Gassiat and Boucheron [2003. Optimal error exponents in hidden Markov models order estimation. IEEE Trans. Inform. Theory 49(4), 964–980]. These inequalities lead to consistent penalized estimators that need no prior bound on the order. A simulation study and an application to postural analysis in humans are provided.