3 Model definition : statetopologiesfr om cell packings
By thinking of each state in a hidden Markov model as corresponding to some spatial region of a fictitious topology spaceit is possible to naturally define neighbouring states as those which are connected in that space. The transition matrix can then be constrained to allow transitions only between neighbours; this means that all valid state sequences correspond to connected paths in the topology space. I show how such constrained HMMs can learn to discover underlying structure in complex sequences of high dimensional data, and apply them to the problem of recovering mouth movements from acoustics in continuous speech. 1 Latent variable models for sequence data Hidden Markov models (HMMs) can be thought of as dynamic generalizations o f di crete state models for static data such as vector quantization or Gaussian mixtur e models. They can also be though of as discrete state versions of linear dynamical systems ( Kal an filter models) which are themselves dynamic generalizations of continuous latent v riable models for static data such as factor analysis or principal component analysis (PC A). While both HMMs and linear dynamical systems provide probabilistic latent var iable models for dynamic data, both have important limitations in time-series modelin g. Traditional HMMs have a very powerful model of the relationship between the underlying s tate and the associated observations because each state stores a private distribution over the output variables. This means that small changes in the hidden state can cause arbitrarily complex changes in the output distribution. However, it is extremely difficult to capture reasonable dynamics on the latent discrete variable because in principle any state is reachable f rom any other state at any time step and the next state depends only on the current state. L inear dynamical systems, on the other hand, have an extremely impoverished representatio n of the outputs as a function of the latent variables since this transformation is restri cted to be global and linear. But it is somewhat easier to capture state dynamics since the state i s a multidimensional vector of continuous variables on which a matrix “flow” is acting; th is enforces some continuity of the latent variables across time. Constrained hidden Markov models address the modeling of state dynamics by building some topology into the hidden state representation. The essential idea is to constrain the transition parameters of a co nventional HMM so that the discrete-valued hidden state evolves in a structured way. 1 In particular, below I consider parameter restrictions which constrain the state to evolve as a di scretized version of a continuous multivariate variable, i.e. so that it inscribes only con nected paths in some space. This lends a physical interpretation to the discrete state trajectori es in an HMM. A standard trick in traditional speech applications of HMMs is to use “left-to-right” transition matrices which are a special case of the type of constraints i nvestigated in this paper. However, leftto-right (Bakis) HMMs force state trajectories that are inh erently one-dimensional and uni-directional whereas here I consider higher dimensional topology and fre e motion. 2 An illustrative game Consider playing the following game: divide a sheet of paper into sever al contiguous, non-overlapping regions which between them cover it entirely. In each regio n inscribe an integer, allowing integers to be r peatedin different regions. Place a pencil on the sheet and move it around, reading out (in order) the numbers in the regions th rough which it passes. Add somenoise to the observation process so that some fraction of the time incorrect numbers are reported in the list instead of the correct ones. The game is to reconstruct the configuration of regions on the sheet from only such an ordered list(s) of noisy numbers. Of course, the absolute scale, rotation and reflection of the sheet can never be r ecov red, but learning the essential topologymay be possible. Figure 1 illustrates this setup. 1 11 24 10 25 17 7 5 9 20 8 6 21 15 22 18 2 16 14 12 19 10 3 23 1 True Generative Map 19 10 3 23 1 18 2 16 14 12 8 6 21 15 22 17 7 5 9 20 1 11 24 1