Jonathan Huggins: May 1st

Jonathan Huggins will present his joint work with Frank Wood. Here is an abstract:

We develop a class of non-parametric Bayesian models we call infinite structured explicit duration hidden Markov models (ISEDHMMs). ISEDHMMs are HMMs that possess an unbounded number of states, encode state dwell-time distributions explicitly, and have constraints on what state transitions are allowed. The ISEDHMM framework generalizes explicit duration finite HMMs, infinite HMMs, left-to-right HMMs, and more (all are recoverable by specific choices of ISEDHMM parameters).  This suggests that ISEDHMMs should be applicable to data-analysis problems in a variety of settings.

David Pfau: April 24th

David be presenting "A Spectral Algorithm for Learning Hidden Markov Models" by Hsu, Kakade and Zhang.  The article can be found here.  And the abstract:

Hidden Markov Models (HMMs) are one of the most fundamental and widely used statistical tools for modeling discrete time series. In general, learning HMMs from data is computationally hard (under cryptographic assumptions), and practitioners typically resort to search heuristics which suffer from the usual local optima issues. We prove that under a natural separation condition (bounds on the smallest singular value of the HMM parameters), there is an efficient and provably correct algorithm for learning HMMs. The sample complexity of the algorithm does not explicitly depend on the number of distinct (discrete) observations—it implicitly depends on this quantity through spectral properties of the underlying HMM. This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language processing where the space of observation is sometimes the words in a language. The algorithm is also simple: it employs only a singular value decomposition and matrix multiplications.

Yashar Ahmadian: April 10th & 17th

Learning unbelievable marginal probabilities

Xaq Pitkow, Yashar Ahmadian, Ken D. Miller

Loopy belief propagation performs approximate inference on graphical models with loops. One might hope to compensate for the approximation by adjusting model parameters. Learning algorithms for this purpose have been explored previously, and the claim has been made that every set of locally consistent marginals can arise from belief propagation run on a graphical model. On the contrary, here we show that many probability distributions have marginals that cannot be reached by belief propagation using any set of model parameters or any learning algorithm. We call such marginals `unbelievable.' This problem occurs whenever the Hessian of the Bethe free energy is not positive-definite at the target marginals. All learning algorithms for belief propagation necessarily fail in these cases, producing beliefs or sets of beliefs that may even be worse than the pre-learning approximation. We then show that averaging inaccurate beliefs, each obtained from belief propagation using model parameters perturbed about some learned mean values, can achieve the unbelievable marginals.