Paper Info
Title
Picking up the pieces: Causal states in noisy data, and how to recover them
Abstract
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.
Year
DOI
Venue
2013
10.1016/j.patrec.2012.11.013
Pattern Recognition Letters
Keywords
Field
DocType
markov model application,predictively optimal markov representation,hidden markov model,robust causal state,causal state representation,so-called causal state,noisy data,causal state,underlying causal structure,established pattern discovery algorithm,endowing cssr,computer and information science,computational mechanics,hmm
Causal structure,Pattern recognition,Computer science,Markov model,A priori and a posteriori,Ergodic theory,Markov chain,Cardinality,Error detection and correction,Artificial intelligence,Hidden Markov model
Journal
Volume
Issue
ISSN
34
5
0167-8655
Citations 
PageRank 
References 
1
0.36
17
Authors
2
Name
Order
Citations
PageRank
Gustav Eje Henter13711.40
W. Bastiaan Kleijn21110106.92