Clustering Markov States into Equivalence Classes using SVD and Heuristic Search Algorithms

Xianping Ge, Sridevi Parise, Padhraic Smyth
Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, PMLR R4:109-116, 2003.

Abstract

This paper investigates the problem of finding a $K$-state first-order Markov chain that approximates an $M$-state first-order Markov chain, where $K$ is typically much smaller than $M$. A variety of greedy heuristic search algorithms that maximize the data likelihood are investigated and found to work well empirically. The proposed algorithms are demonstrated on two applications: learning user models from traces of Unix commands, and word segmentation in language modeling.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR4-ge03a, title = {Clustering Markov States into Equivalence Classes using {SVD} and Heuristic Search Algorithms}, author = {Ge, Xianping and Parise, Sridevi and Smyth, Padhraic}, booktitle = {Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics}, pages = {109--116}, year = {2003}, editor = {Bishop, Christopher M. and Frey, Brendan J.}, volume = {R4}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r4/ge03a/ge03a.pdf}, url = {https://proceedings.mlr.press/r4/ge03a.html}, abstract = {This paper investigates the problem of finding a $K$-state first-order Markov chain that approximates an $M$-state first-order Markov chain, where $K$ is typically much smaller than $M$. A variety of greedy heuristic search algorithms that maximize the data likelihood are investigated and found to work well empirically. The proposed algorithms are demonstrated on two applications: learning user models from traces of Unix commands, and word segmentation in language modeling.}, note = {Reissued by PMLR on 01 April 2021.} }
Endnote
%0 Conference Paper %T Clustering Markov States into Equivalence Classes using SVD and Heuristic Search Algorithms %A Xianping Ge %A Sridevi Parise %A Padhraic Smyth %B Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2003 %E Christopher M. Bishop %E Brendan J. Frey %F pmlr-vR4-ge03a %I PMLR %P 109--116 %U https://proceedings.mlr.press/r4/ge03a.html %V R4 %X This paper investigates the problem of finding a $K$-state first-order Markov chain that approximates an $M$-state first-order Markov chain, where $K$ is typically much smaller than $M$. A variety of greedy heuristic search algorithms that maximize the data likelihood are investigated and found to work well empirically. The proposed algorithms are demonstrated on two applications: learning user models from traces of Unix commands, and word segmentation in language modeling. %Z Reissued by PMLR on 01 April 2021.
APA
Ge, X., Parise, S. & Smyth, P.. (2003). Clustering Markov States into Equivalence Classes using SVD and Heuristic Search Algorithms. Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R4:109-116 Available from https://proceedings.mlr.press/r4/ge03a.html. Reissued by PMLR on 01 April 2021.

Related Material