Clustering Markov States into Equivalence Classes using SVD and Heuristic Search Algorithms.
Xianping Ge, Sridevi Parise, Padhraic Smyth · 2003
This paper investigates the problem of finding a K-state first-order Markov chain that approximates an 2/-state first-order Markov chain, where K is typically nmch smaller than M. A variety of greedy heuristic search algorithms that nmxinfize the data likelihood are investigated and found to work well empirically. The proposed algorithms are demonstrated on txvo applications: learning user models from traces of Unix commands, and word segmentation in language modeling.