Clustering Markov States into Equivalence Classes Using SVD and Heuristic Search Algorithms
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
Text
Ge et al. "Clustering Markov States into Equivalence Classes Using SVD and Heuristic Search Algorithms." Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, 2003.Markdown
[Ge et al. "Clustering Markov States into Equivalence Classes Using SVD and Heuristic Search Algorithms." Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, 2003.](https://mlanthology.org/aistats/2003/ge2003aistats-clustering/)BibTeX
@inproceedings{ge2003aistats-clustering,
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},
year = {2003},
pages = {109-116},
volume = {R4},
url = {https://mlanthology.org/aistats/2003/ge2003aistats-clustering/}
}