PAC-learning of Markov models with hidden state
par/by Doina Precup
School of Computer Science
McGill University
The standard approach for learning Markov Models with Hidden
State uses the Expectation-Maximization framework. While this approach had
a significant impact on several practical applications (e.g. speech
recognition, biological sequence alignment) it has two major limitations:
it requires a known model topology, and learning is only locally optimal.
We propose a new PAC framework for learning both the topology and the
parameters in partially observable Markov models. Our algorithm learns a
Probabilistic Deterministic Finite Automata (PDFA) which approximates a
Hidden Markov Model (HMM) up to some desired degree of accuracy. We
discuss theoretical conditions under which the algorithm produces an
optimal solution (in the PAC-sense) and demonstrate promising performance
on simple dynamical systems. We also outline the relationship of this
approach to current work in learning predictive state representations.
This is joint work with Ricard Gavalda, Joelle Pineau and Philipp Keller.