Aram Galstyan (University of Southern California)
Abstract. A Hidden Markov Model (HMM) is a Markov process observed through a noisy channel. HMMs are used extensively for modeling sequential data and have various applications in natural language processing, bioinformatics, mathematical economics, and so on. One of the main problems underlying HMMs is inferring the hidden state sequence based on noise-corrupted observations, which is usually solved via the maximum a posteriori (MAP) method. Here I present a statistical physics analysis of MAP estimation for a simple binary HMM, by reducing it to an appropriately defined Ising model. It is shown that for sufficiently low noise levels, the MAP solution is uniquely related to the observed sequence. Above a critical noise level, however, there are exponentially many solutions to the estimation problem, which means that one cannot uniquely reconstruct the hidden state sequence based on observations. I will also discuss how one can mitigate this undesirable feature by active inference, i.e., by adaptively acquiring information about the (true) hidden states.