2019

Learning higher-order sequential structure with cloned HMMs

Dedieu, Antoine, Gothoskar, Nishad, Swingle, Scott et al.

Understand

Variable order sequence modeling is an important problem in artificial and natural intelligence.

While overcomplete Hidden Markov Models (HMMs), in theory, have the capacity to represent long-term temporal structure, they often fail to learn and converge to local minima.
We show that by constraining HMMs with a simple sparsity structure inspired by biology, we can make it learn variable order sequences efficiently.
We call this model cloned HMM (CHMM) because the sparsity structure enforces that many hidden states map deterministically to the same emission state.

Built on

On the convergence properties of the em algorithm
CF Jeff Wu · 1983
Earlier work this paper cites.
Data compression using dynamic markov modelling
Gordon V. Cormack and R Nigel S Horspool · 1987
Earlier work this paper cites.
A tutorial on hidden markov models and selected applications in speech recognition
Lawrence R Rabiner · 1989
Earlier work this paper cites.
Equivalence of regularization and truncated iteration in the solution of iii-posed image reconstruction problems
Henry E Fleming · 1990
Earlier work this paper cites.
Smooth on-line learning algorithms for hidden markov models
Pierre Baldi and Yves Chauvin · 1994
Earlier work this paper cites.
Diffusion of context and credit information in markovian models
Yoshua Bengio and Paolo Frasconi · 1995
Earlier work this paper cites.
Improved backing-off for m-gram language modeling
Reinhard Kneser and Hermann Ney · 1995
Earlier work this paper cites.
Hmm topology design using maximum likelihood successive state splitting
Mari Ostendorf and Harald Singer · 1997
Earlier work this paper cites.
An empirical study of smoothing techniques for language modeling
Stanley F Chen and Joshua Goodman · 1999
Earlier work this paper cites.
Kylm - the kyoto language modeling toolkit, 1999
Graham Neubig · 1999
Earlier work this paper cites.

Similar

Constrained hidden markov models
Sam T Roweis · 2000
Cited alongside, same era.
Inducing hidden markov models to model long-term dependencies
Jérôme Callut and Pierre Dupont · 2005
Cited alongside, same era.
On early stopping in gradient descent learning
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto · 2007
Cited alongside, same era.
Maps of random walks on complex networks reveal community structure
Martin Rosvall and Carl T Bergstrom · 2008
Cited alongside, same era.
Natural language processing with Python: analyzing text with the natural language toolkit
Steven Bird, Ewan Klein, and Edward Loper · 2009
Cited alongside, same era.
Towards a mathematical theory of cortical micro-circuits
Dileep George and Jeff Hawkins · 2009
Cited alongside, same era.
Sequence memory for prediction, inference and behaviour
Jeff Hawkins, Dileep George, and Jamie Niemasik · 2009
Cited alongside, same era.
Complex sequencing rules of birdsong can be explained by simple hidden markov processes
Kentaro Katahira, Kenta Suzuki, Kazuo Okanoya, and Masato Okada · 2011
Cited alongside, same era.
Scikit-learn: Machine learning in Python
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay · 2011
Cited alongside, same era.
The sequence memoizer
Frank Wood, Jan Gasthaus, Cédric Archambeau, Lancelot James, and Yee Whye Teh · 2011
Cited alongside, same era.

Then

A method of moments for mixture models and hidden markov models
Animashree Anandkumar, Daniel Hsu, and Sham M Kakade · 2012
Later among the works it cites.
Visualizing and understanding recurrent networks
Original
Andrej Karpathy, Justin Johnson, and Li Fei-Fei · 2015
Later among the works it cites.
Growth and splitting of neural sequences in songbird vocal development
Tatsuo S Okubo, Emily L Mackevicius, Hannah L Payne, Galen F Lynch, and Michale S Fee · 2015
Later among the works it cites.
Continuous online sequence learning with an unsupervised neural network model
Yuwei Cui, Subutai Ahmad, and Jeff Hawkins · 2016
Later among the works it cites.
Maps of sparse markov chains efficiently reveal community structure in network flows with memory
Original
Christian Persson, Ludvig Bohlin, Daniel Edler, and Martin Rosvall · 2016
Later among the works it cites.
Representing higher-order dependencies in networks
Jian Xu, Thanuka L Wickramarathne, and Nitesh V Chawla · 2016
Later among the works it cites.
Feature discovery for sequential prediction of monophonic music
Jonas Langhabel, Robert Lieck, Marc Toussaint, and Martin Rohrmeier · 2017
Later among the works it cites.
Learning overcomplete HMMs
Vatsal Sharan, Sham M Kakade, Percy S Liang, and Gregory Valiant · 2017
Later among the works it cites.
Statistical and computational guarantees for the baum-welch algorithm
Fanny Yang, Sivaraman Balakrishnan, and Martin J Wainwright · 2017
Later among the works it cites.
Cna uoy raed thsi nwo? contextual and stimulus effects on decoding scrambled words
Sarah J Starling and Kelsey A Snyder · 2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…