Timezone: »

Small-Variance Asymptotics for Hidden Markov Models
Anirban Roychowdhury · Ke Jiang · Brian Kulis

Sat Dec 07 05:44 PM -- 05:48 PM (PST) @ Harvey's Convention Center Floor, CC

Small-variance asymptotics provide an emerging technique for obtaining scalable combinatorial algorithms from rich probabilistic models. We present a small-variance asymptotic analysis of the Hidden Markov Model and its infinite-state Bayesian nonparametric extension. Starting with the standard HMM, we first derive a “hard” inference algorithm analogous to k-means that arises when particular variances in the model tend to zero. This analysis is then extended to the Bayesian nonparametric case, yielding a simple, scalable, and flexible algorithm for discrete-state sequence data with a non-fixed number of states. We also derive the corresponding combinatorial objective functions arising from our analysis, which involve a k-means-like term along with penalties based on state transitions and the number of states. A key property of such algorithms is that — particularly in the nonparametric setting — standard probabilistic inference algorithms lack scalability and are heavily dependent on good initialization. A number of results on synthetic and real data sets demonstrate the advantages of the proposed framework.

Author Information

Anirban Roychowdhury (Facebook)
Ke Jiang (Ohio State University)
Brian Kulis (Boston University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors