Picking up the pieces: Causal states in noisy data, and how to recover them
2013 (English)In: Pattern Recognition Letters, ISSN 0167-8655, Vol. 34, no 5, 587-594 p.Article in journal (Refereed) Published
Automatic structure discovery is desirable in many Markov model applications where a good topology (states and transitions) is not known a priori. CSSR is an established pattern discovery algorithm for stationary and ergodic stochastic symbol sequences that learns a predictively optimal Markov representation consisting of so-called causal states. By means of a novel algebraic criterion, we prove that the causal states of a simple process disturbed by random errors frequently are too complex to be learned fully, making CSSR diverge. In fact, the causal state representation of many hidden Markov models, representing simple but noise-disturbed data, has infinite cardinality. We also report that these problems can be solved by endowing CSSR with the ability to make approximations. The resulting algorithm, robust causal states (RCS), is able to recover the underlying causal structure from data corrupted by random substitutions, as is demonstrated both theoretically and in an experiment. The algorithm has potential applications in areas such as error correction and learning stochastic grammars.
Place, publisher, year, edition, pages
2013. Vol. 34, no 5, 587-594 p.
Computational mechanics, Causal states, CSSR, Hidden Markov model, HMM, Learnability
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-121467DOI: 10.1016/j.parrec.2012.11.013ISI: 000316425800020ScopusID: 2-s2.0-84873870023OAI: oai:DiVA.org:kth-121467DiVA: diva2:619085
FunderEU, European Research Council, FP6-034362
QC 201305022013-05-022013-04-292013-12-03Bibliographically approved