Beam sampling for the infinite hidden Markov model
Published 1 January 2008
Jurgen Van Gael, Yunus Saatçi, Yee Whye Teh, Zoubin Ghahramani
Citations224
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper introduces a new inference algorithm for the infinite Hidden Markov model called beam sampling, which typically outperforms the Gibbs sampler and is more robust.
Abstract
The infinite hidden Markov model is a non-parametric extension of the widely used hidden Markov model. Our paper introduces a new inference algorithm for the infinite Hidden Markov model called beam sampling. Beam sampling combines slice sampling, which limits the number of states considered at each time step to a finite number, with dynamic programming, which samples whole state trajectories efficiently. Our algorithm typically outperforms the Gibbs sampler and is more robust. We present applications of iHMM inference using the beam sampler on changepoint detection and text prediction problems.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Proceedings of the IEEEA tutorial on hidden Markov models and selected applications in speech recognition
22,785 Citations1989L. R. Rabiner
Bayesian Data Analysis
13,688 Citations2003Andrew Gelman, John B. Carlin +2 more
The MIT Press eBooksGaussian Processes for Machine Learning
10,409 Citations2005Carl Edward Rasmussen, Christopher K. I. Williams
The book provides a long-needed, systematic and unified treatment of theoretical and practical aspects of GPs in machine learning, targeted at researchers and students in machine learning and applied statistics.
Journal of the American Statistical AssociationHierarchical Dirichlet Processes
3,567 Citations2006Yee Whye Teh, Michael I. Jordan +2 more
This work considers problems involving groups of data where each observation within a group is a draw from a mixture model and where it is desirable to share mixture components between groups, and considers a hierarchical model, specifically one in which the base measure for the childDirichlet processes is itself distributed according to a Dirichlet process.
Journal of the American Statistical AssociationBayesian Density Estimation and Inference Using Mixtures
2,241 Citations1995Michael Escobar, Mike West
These models provide natural settings for density estimation and are exemplified by special cases where data are modeled as a sample from mixtures of normal distributions, allowing for direct inference on a variety of practical issues.
Journal of Computational and Graphical StatisticsMarkov Chain Sampling Methods for Dirichlet Process Mixture Models
2,212 Citations2000Radford M. Neal
The Annals of StatisticsMixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems
2,030 Citations1974C. Antoniak
This paper gives a formal definition for Dirichlet process mixtures and develops several theorems about their properties, the most important of which is a closure property for such mixtures.
A Constructive Definition of Dirichlet Priors
1,611 Citations1991Jayaram Sethuraman
Journal of the American Statistical AssociationGibbs Sampling Methods for Stick-Breaking Priors
1,556 Citations2001Hemant Ishwaran, Lancelot F. James
Two general types of Gibbs samplers that can be used to fit posteriors of Bayesian hierarchical models based on stick-breaking priors are presented and the blocked Gibbs sampler, based on an entirely different approach that works by directly sampling values from the posterior of the random measure.
The Infinite Gaussian Mixture Model
987 Citations1999Carl Edward Rasmussen
This paper presents an infinite Gaussian mixture model which neatly sidesteps the difficult problem of finding the "right" number of mixture components and uses an efficient parameter-free Markov Chain that relies entirely on Gibbs sampling.
Infinite latent feature models and the Indian buffet process
552 Citations2005Zoubin Ghahramani, Thomas L. Griffiths
A probability distribution over equivalence classes of binary matrices with a finite number of rows and an unbounded number of columns is defined, suitable for use as a prior in probabilistic models that represent objects using a potentially infinite array of features.
Journal of the American Statistical AssociationBayesian Methods for Hidden Markov Models
535 Citations2002Steven L. Scott
It is shown how recursive computing allows the statistically efficient use of MCMC output when estimating the hidden states, and the use of log-likelihood for assessing MCMC convergence is illustrated.
The MIT Press eBooksThe Infinite Hidden Markov Model
481 Citations2002Matthew J. Beal, Zoubin Ghahramani +1 more
Communications in Statistics - Simulation and ComputationSampling the Dirichlet Mixture Model with Slices
442 Citations2007Stephen G. Walker
The key to the algorithm detailed in this article, which also keeps the random distribution functions, is the introduction of a latent variable which allows a finite number of objects to be sampled within each iteration of a Gibbs sampler.
TechnometricsNumerical Bayesian Methods Applied to Signal Processing
350 Citations1997Kurt S. Riedel, Joseph J. K. Ó Ruanaidh +1 more
An Input Output HMM Architecture
260 Citations1994Yoshua Bengio, Paolo Frasconi
A recurrent architecture having a modular structure that has similarities to hidden Markov models, but supports recurrent networks processing style and allows to exploit the supervised learning paradigm while using maximum likelihood estimation is introduced.
arXiv (Cornell University)Bayesian Agglomerative Clustering with Coalescents
73 Citations2009Yee Whye Teh, Daniel Hsu +1 more
A new Bayesian model for hierarchical clustering based on a prior over trees called Kingman's coalescent is introduced, and novel greedy and sequential Monte Carlo inferences which operate in a bottom-up agglomerative fashion are developed.
Neural Information Processing SystemsInferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models
42 Citations2003Radford M. Neal, Matthew J. Beal +1 more
A Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations, and compares the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers.