work with

We show that it is possible to extend hidden Markov models to have a countably infinite number of hidden states. By using the theory of Dirichlet processes we can implicitly integrate out the infinitely many transition parameters, leaving only three hyperparameters which can be learned from data. These three hyperparameters define a hierarchical Dirichlet process capable of capturing a rich set of transition dynamics. The three hyperparameters control the time scale of the dynamics, the sparsity of the underlying state-transition matrix, and the expected number of distinct hidden states in a finite sequence. In this framework it is also natural to allow the alphabet of emitted symbols to be infinite—consider, for example, symbols being possible words appearing in English text. Overview • Introduce the idea of an HMM with an infinite number of states and symbols. • Make use of the infinite Dirichlet process, and generalise this to a two-level hierarchical Dirichlet process over transitions and states. • Explore the properties of the prior over trajectories. • Present inference and learning procedures for the infinite HMM. eg. Infinite Gaussian Mixtures Following Neal (1991), Rasmussen (2000) showed that it is possible to do inference in countably infinite mixtures of Gaussians. P (x1,..., xN |pi,µ,Σ) = N∏ i=