<title>CSSR: An Algorithm for Building Markov Models from Time Series</title> <h1>CSSR</h1> <h2>An Algorithm for Building Markov Models from Time Series</h2> <P>This is the homepage for CSSR (Causal State Splitting Reconstruction), analgorithm for building recursive hidden Markov models from discrete-valued timeseries, and other discrete sequential data. Unlike conventional hidden-Markovalgorithms, which tune the parameters in a fixed architecture, CSSR is capableof inferring the appropriate architecture as well. In fact, under certainconditions, CSSR will converge on the optimal model of the underlyingdata-generating process. <P>CSSR has been implemented and successfully tested on a range of differentdiscrete time series and sequential data streams. This page provides the fullsource code, released under the <a href="http://www.gnu.org/">GNU</a> <ahref="http://www.gnu.org/copyleft/gpl.html">Public License</a>, documentation,and links to scientific papers using the CSSR algorithm.</P> <P>The theory behind the algorithm was developed by <ahref="http://bactra.org/">Cosma Shalizi</a> and Kristina Klinkner, underthe sponsorship of <a href="http://www.santafe.edu/~chaos/">JamesCrutchfield</a>. The code for this implementation was written by KristinaKlinkner. For full credits, see the comments to the code, and the paper "BlindConstruction of Optimal Nonlinear Recursive Predictors for Discrete Sequences". <h2>What's Available</h2> <P>The C++ source code, plus documentation and license, is now on <a href="https://github.com/stites/CSSR">Github</a>. The documentation gives a brief overview of whatCSSR does and how it works, describes usage, offers some hints on parameters,and explains the known issues with this implementation of the basicalgorithm. <P>Please note especially that CSSR is provided with ABSOLUTELY NOWARRANTY. <P>There is a thorough explanation of the theory behind CSSR in the paper"Blind Construction of Optimal Nonlinear Recursive Predictors for DiscreteSequences" (Cosma Rohilla Shalizi and Kristina Lisa Shalizi, pp. 504--511 inMax Chickering and Joseph Halpern (eds.), <cite>Uncertainty in ArtificialIntelligence: Proceedings of the Twentieth Conference</cite> (Arlington,Virginia: AUAI Press, 2004 = <a href="http://arxiv.org/abs/cs.LG/0406011">arxiv:cs.LG/0406011</a>). Forreasons of space, that paper omits certain details, which can be found in thetechnical report "An Algorithm for Pattern Discovery in Time Series" (CosmaRohilla Shalizi, Kristina Lisa Shalizi and James P. Crutchfield, Santa FeInstitute Working Paper 02-10-060= <a href="http://arxiv.org/abs/cs.LG/0210025">arxiv:cs.LG/0210025</a>). <h2>Publications on CSSR</h2> <P>As mentioned, the principal paper on CSSR is "Blind Construction of OptimalNonlinear Recursive Predictors for DiscreteSequences", <ahref="http://arxiv.org/abs/cs.LG/0406011">arxiv:cs.LG/0406011</a>. Thisdescribes the algorithm and its theoretical basis in detail, gives results ontime complexity and on the convergence on the reconstructed model, and comparesits performance to other approaches, including the EM algorithm andcross-validation. Some details omitted from the "Blind Construction" paper canbe found in the preliminary technical report, "An Algorithm for PatternDiscovery in Time Series". The latest version atarxiv.org, <ahref="http://arxiv.org/abs/cs.LG/0210025">arxiv:cs.LG/0210025</a>, supersedesall earlier drafts. <h4>Citing CSSR in Your Publications</h4> <P><strong>If you use CSSR in a scientific publication</strong>, please citethe "Blind Construction" paper. A sample BibTeX entry: <blockquote><tt>@inproceedings{CSSR-UAI-2004,<br> author = "Cosma Rohilla Shalizi and Kristina Lisa Klinkner",<br> title = "Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences",<br> editor = "Max Chickering and Joseph Y. Halpern",<br> booktitle = "Uncertainty in Artificial Intelligence: Proceedings of the Twentieth Conference (UAI 2004)",<br> publisher = "AUAI Press",<br> address = "Arlington, Virginia",<br> year = 2004,<br> pages = "504--511",<br> url = "http://arxiv.org/abs/cs.LG/0406011"}</tt></blockquote> <P></P> <h4>Publications Using CSSR</h4> <P>Alphabetical by author. (Last updated 2008.) <dl><dt>Fabio Boschetti</dt><dd>"Mapping the complexity of ecological models", <cite>Ecological Complexity</cite> forthcoming (2007) [<a href="http://www.per.marine.csiro.au/staff/Fabio.Boschetti/papers/Complexity_Map.pdf">PDF</a>]</dd><dt>Nicolas Brodu</dt><dd>"Quantifying the Effect of Learning on Recurrent Spiking Neurons",forthcoming in <cite>International Joint Conference on Neural Networks [IJCNN]2007</cite>[<ahref="http://nicolas.brodu.free.fr/common/recherche/publications/drrn2.pdf">PDF</a>]</dd><dt>Jean-Philippe Cointet, Emmanuel Faure and Camille Roth</dt><dd>"Intertemporal topic correlations in online media", in <cite>Proceedings of the International Conference on Weblogs and Social Media [ICWSM]</cite> (Boulder, CO, USA: 2007) [<a href="http://camille.roth.free.fr/travaux/cointetfaureroth-icwsm-cr4p.pdf">PDF</a>]</dd><dt>Davis S. Friedlander, Isanu Chattopadhayay, Asok Ray, Shashi Phoha and NoahJacobson</dt><dd>"Anomaly Prediction in Mechanical System Using Symbolic Dynamics",in <cite>Proceedings of the 2003 American Control Conference, Denver, CO, 4--6June 2003</cite> (2003)</dd><dt>David S. Friedlander, Shashi Phoha and Richard Brooks</dt><dd>"Determination of Vehicle Behavior based on Distributed Sensor Network Data", in Franklin T. Luk (ed.), <cite>Advanced Signal Processing Algorithms, Architectures, and Implementations XIII</cite> (Bellingham, WA: SPIE, 2003)</dd><dt>Kristina Lisa Klinkner, Cosma Rohilla Shalizi and Marcelo F. Camperi</dt><dd>"Measuring Shared Information and Coordinated Activity in NeuronalNetworks", pp. 667--674 in Yair Weiss, Bernhard Sch¨lkopf and John C. Platt(eds.), <cite>Advances in Neural Information Processing Systems 18 [NIPS2005]</cite> (Cambridge, MA: MIT Press, 2006)= <ahref="http://arxiv.org/abs/q-bio.NC/0506009">arxiv:q-bio.NC/0506009</a></dd><dt>Dmitry Nerukh, George Karvounis and Robert C. Glen</dt><dd>"Complexity of classical dynamics of molecular systems.I. Methodology", <cite>Journal of Chemical Physics</cite> <strong>117</strong>(2002): 9611--9617[<a href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/YarI.pdf">PDF</a>]</dd><dd>"Complexity of classical dynamics of molecular systems. II. Finitestatistical complexity of a water--Na+ system", <cite>Journal of ChemicalPhysics</cite> <strong>117</strong> (2002): 9618--9622[<a href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/YarII.pdf">PDF</a>]</dd><dd>"Quantifying the Complexity of Chaos in Multibasin MultidimensionalDynamics of Molecular Systems", <cite>Complexity</cite> <strong>10:2</strong>(2004): 40--46[<ahref="http://www.chem.pwf.cam.ac.uk/~dn232/pub/complexity.pdf">PDF</a>]</dd><dd>"Dynamic Complexity of Chaotic Transitions in High-Dimensional ClassicalDynamics: Leu-Enkephalin Folding", in <cite>Computational Life SciencesII</cite>, pp. 129--140 (Berlin: Springer Verlag, 2006)[<ahref="http://www.chem.pwf.cam.ac.uk/~dn232/pub/ec_CompLife.pdf">PDF</a>]</dd><dt>Muntsa Padró and Lluís Padró</dt><dd>"Applying a Finite Automata Acquisition Algorithm to Named Entity Recognition", in <cite>Proceedings of 5th International Workshop on Finite-State Methods and Natural Language Processing [FSMNLP'05]</cite> (2005) [<a href="http://www.lsi.upc.edu/~nlp/papers/2005/fsmnlp05-pp.pdf">PDF</a>]</dd><dd>"A Named Entity Recognition System Based on a Finite Automata Acquisition Algorithm", <cite>Procesamiento del Lenguaje Natural</cite> <strong>35</strong> (2005): 319--326[<a href="http://www.lsi.upc.edu/~nlp/papers/2005/sepln05-pp.pdf">PDF</a>]</dd><dd>"Approaching Sequential NLP Tasks with an Automata Acquisition Algorithm",in <cite>Proceedings of International Conference on Recent Advances in NLP [RANLP'05]</cite> (2005) [<a href="http://www.lsi.upc.edu/~nlp/papers/2005/ranlp05-pp.pdf">PDF</a>]</dd><dd>"ME-CSSR: an Extension of CSSR using Maximum Entropy Models", in <cite>Proceedings of Finite State Methods for Natural Language Processing (FSMNLP) 2007</cite> [<a href="http://www.lsi.upc.edu/%7Enlp/papers/2007/fsmnlp07-pp.pdf">PDF</a>]</dd><dd>"Studying CSSR Algorithm Applicability on NLP Tasks", <cite>Procesamiento del Lenguaje Natural</cite> <strong>39</strong> (2007): 89--96 [<a href="http://www.lsi.upc.edu/%7Enlp/papers/2007/sepln07-pp.pdf">PDF</a>]</dd><dt>Joongwoo Brian Park, Jeong Won Lee, Jae-Suk Yang, Hang-Hyun Jo and Hie-TaeMoon</dt><dd>"Complexity analysis of the stock market", <cite>Physica A</cite><strong>379</strong> (2007): 179--187 = <a href="http://arxiv.org/abs/physics/0607283">arxiv:physics/0607283</a></dd><dt>Asok Ray</dt><dd>"Symbolic dynamic analysis of complex systems for anomalydetection", <cite>Signal Processing</cite> <strong>84</strong> (2004):1115--1130</dd><dt>Cosma Rohilla Shalizi, Marcelo F. Camperi and Kristina Lisa Klinkner</dt><dd>"Discovering Functional Communities in Dynamical Networks", pp. 140--157 inEdo Airoldi et al. (eds.), <cite>Statistical Network Analysis: Models, Issuesand New Directions</cite> [proceedings of an ICML 2006 workshop] (New York:Springer-Verlag, 2007)= <ahref="http://arxiv.org/abs/q-bio.NC/0609008">arxiv:q-bio.NC/0609008</a></dd><dt>Dowman P. Varn and James P. Crutchfield</dt><dd>"From Finite to Infinite Range Order via Annealing: The Causal Architectureof Deformation Faulting in Annealed Close-Packed Crystals", <cite>PhysicsLetters A</cite> <strong>324</strong> (2004): 299--307= <ahref="http://arxiv.org/abs/cond-mat/0307296">arxiv:cond-mat/0307296</a></dd></dl> <h2>Contact Information</h2> Send e-mail to <a href="mailto:cshalizi at stat dot cmu dot edu">CosmaShalizi</a> or <a href="mailto:kklinkner at gmail dot com">KristinaKlinkner</a>. <P>Please write us to let us know if you use CSSR in an application (especiallya paper), compile it on a new platform, modify it, wish to be kept informed offuture developments, or have a bug or other problem to report. However, beforesending bug reports, please read the documentation carefully, and if possiblethe paper too, so that you're sure what you're experiencing <em>is</em> a bug.Since CSSR is released under the Gnu Public License, feel free to write yourown fix for the bug, and tell us about it! <hr> Created 7 August 2003 by <a href="http://bactra.org/">CRS</a>
<title>CSSR: An Algorithm for Building Markov Models from Time Series</title>
<h1>CSSR</h1>
<h2>An Algorithm for Building Markov Models from Time Series</h2>
<P>This is the homepage for CSSR (Causal State Splitting Reconstruction), an
algorithm for building recursive hidden Markov models from discrete-valued time
series, and other discrete sequential data. Unlike conventional hidden-Markov
algorithms, which tune the parameters in a fixed architecture, CSSR is capable
of inferring the appropriate architecture as well. In fact, under certain
conditions, CSSR will converge on the optimal model of the underlying
data-generating process.
<P>CSSR has been implemented and successfully tested on a range of different
discrete time series and sequential data streams. This page provides the full
source code, released under the <a href="http://www.gnu.org/">GNU</a> <a
href="http://www.gnu.org/copyleft/gpl.html">Public License</a>, documentation,
and links to scientific papers using the CSSR algorithm.</P>
<P>The theory behind the algorithm was developed by <a
href="http://bactra.org/">Cosma Shalizi</a> and Kristina Klinkner, under
the sponsorship of <a href="http://www.santafe.edu/~chaos/">James
Crutchfield</a>. The code for this implementation was written by Kristina
Klinkner. For full credits, see the comments to the code, and the paper "Blind
Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences".
<h2>What's Available</h2>
<P>The C++ source code, plus documentation and license, is now on <a href="https://github.com/stites/CSSR">Github</a>. The documentation
gives a brief overview of what
CSSR does and how it works, describes usage, offers some hints on parameters,
and explains the known issues with this implementation of the basic
algorithm.
<P>Please note especially that CSSR is provided with ABSOLUTELY NO
WARRANTY.
<P>There is a thorough explanation of the theory behind CSSR in the paper
"Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete
Sequences" (Cosma Rohilla Shalizi and Kristina Lisa Shalizi, pp. 504--511 in
Max Chickering and Joseph Halpern (eds.), <cite>Uncertainty in Artificial
Intelligence: Proceedings of the Twentieth Conference</cite> (Arlington,
Virginia: AUAI Press, 2004 =
<a href="http://arxiv.org/abs/cs.LG/0406011">arxiv:cs.LG/0406011</a>). For
reasons of space, that paper omits certain details, which can be found in the
technical report "An Algorithm for Pattern Discovery in Time Series" (Cosma
Rohilla Shalizi, Kristina Lisa Shalizi and James P. Crutchfield, Santa Fe
Institute Working Paper 02-10-060
= <a href="http://arxiv.org/abs/cs.LG/0210025">arxiv:cs.LG/0210025</a>).
<h2>Publications on CSSR</h2>
<P>As mentioned, the principal paper on CSSR is "Blind Construction of Optimal
Nonlinear Recursive Predictors for Discrete
Sequences", <a
href="http://arxiv.org/abs/cs.LG/0406011">arxiv:cs.LG/0406011</a>. This
describes the algorithm and its theoretical basis in detail, gives results on
time complexity and on the convergence on the reconstructed model, and compares
its performance to other approaches, including the EM algorithm and
cross-validation. Some details omitted from the "Blind Construction" paper can
be found in the preliminary technical report, "An Algorithm for Pattern
Discovery in Time Series". The latest version at
arxiv.org, <a
href="http://arxiv.org/abs/cs.LG/0210025">arxiv:cs.LG/0210025</a>, supersedes
all earlier drafts.
<h4>Citing CSSR in Your Publications</h4>
<P><strong>If you use CSSR in a scientific publication</strong>, please cite
the "Blind Construction" paper. A sample BibTeX entry:
<blockquote>
<tt>@inproceedings{CSSR-UAI-2004,
<br> author = "Cosma Rohilla Shalizi and Kristina Lisa Klinkner",
<br> title = "Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences",
<br> editor = "Max Chickering and Joseph Y. Halpern",
<br> booktitle = "Uncertainty in Artificial Intelligence: Proceedings of the Twentieth Conference (UAI 2004)",
<br> publisher = "AUAI Press",
<br> address = "Arlington, Virginia",
<br> year = 2004,
<br> pages = "504--511",
<br> url = "http://arxiv.org/abs/cs.LG/0406011"}</tt>
</blockquote>
<P></P>
<h4>Publications Using CSSR</h4>
<P>Alphabetical by author. (Last updated 2008.)
<dl>
<dt>Fabio Boschetti</dt>
<dd>"Mapping the complexity of ecological models", <cite>Ecological Complexity</cite> forthcoming (2007) [<a href="http://www.per.marine.csiro.au/staff/Fabio.Boschetti/papers/Complexity_Map.pdf">PDF</a>]</dd>
<dt>Nicolas Brodu</dt>
<dd>"Quantifying the Effect of Learning on Recurrent Spiking Neurons",
forthcoming in <cite>International Joint Conference on Neural Networks [IJCNN]
2007</cite>
[<a
href="http://nicolas.brodu.free.fr/common/recherche/publications/drrn2.pdf">PDF</a>]</dd>
<dt>Jean-Philippe Cointet, Emmanuel Faure and Camille Roth</dt>
<dd>"Intertemporal topic correlations in online media", in <cite>Proceedings of the International Conference on Weblogs and Social Media [ICWSM]</cite> (Boulder, CO, USA: 2007) [<a href="http://camille.roth.free.fr/travaux/cointetfaureroth-icwsm-cr4p.pdf">PDF</a>]</dd>
<dt>Davis S. Friedlander, Isanu Chattopadhayay, Asok Ray, Shashi Phoha and Noah
Jacobson</dt>
<dd>"Anomaly Prediction in Mechanical System Using Symbolic Dynamics",
in <cite>Proceedings of the 2003 American Control Conference, Denver, CO, 4--6
June 2003</cite> (2003)</dd>
<dt>David S. Friedlander, Shashi Phoha and Richard Brooks</dt>
<dd>"Determination of Vehicle Behavior based on Distributed Sensor Network Data", in Franklin T. Luk (ed.), <cite>Advanced Signal Processing Algorithms, Architectures, and Implementations XIII</cite> (Bellingham, WA: SPIE, 2003)</dd>
<dt>Kristina Lisa Klinkner, Cosma Rohilla Shalizi and Marcelo F. Camperi</dt>
<dd>"Measuring Shared Information and Coordinated Activity in Neuronal
Networks", pp. 667--674 in Yair Weiss, Bernhard Sch¨lkopf and John C. Platt
(eds.), <cite>Advances in Neural Information Processing Systems 18 [NIPS
2005]</cite> (Cambridge, MA: MIT Press, 2006)
= <a
href="http://arxiv.org/abs/q-bio.NC/0506009">arxiv:q-bio.NC/0506009</a></dd>
<dt>Dmitry Nerukh, George Karvounis and Robert C. Glen</dt>
<dd>"Complexity of classical dynamics of molecular systems.
I. Methodology", <cite>Journal of Chemical Physics</cite> <strong>117</strong>
(2002): 9611--9617
[<a href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/YarI.pdf">PDF</a>]</dd>
<dd>"Complexity of classical dynamics of molecular systems. II. Finite
statistical complexity of a water--Na+ system", <cite>Journal of Chemical
Physics</cite> <strong>117</strong> (2002): 9618--9622
[<a href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/YarII.pdf">PDF</a>]</dd>
<dd>"Quantifying the Complexity of Chaos in Multibasin Multidimensional
Dynamics of Molecular Systems", <cite>Complexity</cite> <strong>10:2</strong>
(2004): 40--46
[<a
href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/complexity.pdf">PDF</a>]</dd>
<dd>"Dynamic Complexity of Chaotic Transitions in High-Dimensional Classical
Dynamics: Leu-Enkephalin Folding", in <cite>Computational Life Sciences
II</cite>, pp. 129--140 (Berlin: Springer Verlag, 2006)
[<a
href="http://www.chem.pwf.cam.ac.uk/~dn232/pub/ec_CompLife.pdf">PDF</a>]</dd>
<dt>Muntsa Padró and Lluís Padró</dt>
<dd>"Applying a Finite Automata Acquisition Algorithm to Named Entity Recognition", in <cite>Proceedings of 5th International Workshop on Finite-State Methods and Natural Language Processing [FSMNLP'05]</cite> (2005) [<a href="http://www.lsi.upc.edu/~nlp/papers/2005/fsmnlp05-pp.pdf">PDF</a>]</dd>
<dd>"A Named Entity Recognition System Based on a Finite Automata Acquisition Algorithm", <cite>Procesamiento del Lenguaje Natural</cite> <strong>35</strong> (2005): 319--326
[<a href="http://www.lsi.upc.edu/~nlp/papers/2005/sepln05-pp.pdf">PDF</a>]</dd>
<dd>"Approaching Sequential NLP Tasks with an Automata Acquisition Algorithm",
in <cite>Proceedings of International Conference on Recent Advances in NLP [RANLP'05]</cite> (2005) [<a href="http://www.lsi.upc.edu/~nlp/papers/2005/ranlp05-pp.pdf">PDF</a>]</dd>
<dd>"ME-CSSR: an Extension of CSSR using Maximum Entropy Models", in <cite>Proceedings of Finite State Methods for Natural Language Processing (FSMNLP) 2007</cite> [<a href="http://www.lsi.upc.edu/%7Enlp/papers/2007/fsmnlp07-pp.pdf">PDF</a>]</dd>
<dd>"Studying CSSR Algorithm Applicability on NLP Tasks", <cite>Procesamiento del Lenguaje Natural</cite> <strong>39</strong> (2007): 89--96 [<a href="http://www.lsi.upc.edu/%7Enlp/papers/2007/sepln07-pp.pdf">PDF</a>]</dd>
<dt>Joongwoo Brian Park, Jeong Won Lee, Jae-Suk Yang, Hang-Hyun Jo and Hie-Tae
Moon</dt>
<dd>"Complexity analysis of the stock market", <cite>Physica A</cite>
<strong>379</strong> (2007): 179--187 = <a href="http://arxiv.org/abs/physics/0607283">arxiv:physics/0607283</a></dd>
<dt>Asok Ray</dt>
<dd>"Symbolic dynamic analysis of complex systems for anomaly
detection", <cite>Signal Processing</cite> <strong>84</strong> (2004):
1115--1130</dd>
<dt>Cosma Rohilla Shalizi, Marcelo F. Camperi and Kristina Lisa Klinkner</dt>
<dd>"Discovering Functional Communities in Dynamical Networks", pp. 140--157 in
Edo Airoldi et al. (eds.), <cite>Statistical Network Analysis: Models, Issues
and New Directions</cite> [proceedings of an ICML 2006 workshop] (New York:
Springer-Verlag, 2007)
= <a
href="http://arxiv.org/abs/q-bio.NC/0609008">arxiv:q-bio.NC/0609008</a></dd>
<dt>Dowman P. Varn and James P. Crutchfield</dt>
<dd>"From Finite to Infinite Range Order via Annealing: The Causal Architecture
of Deformation Faulting in Annealed Close-Packed Crystals", <cite>Physics
Letters A</cite> <strong>324</strong> (2004): 299--307
= <a
href="http://arxiv.org/abs/cond-mat/0307296">arxiv:cond-mat/0307296</a></dd>
</dl>
<h2>Contact Information</h2>
Send e-mail to <a href="mailto:cshalizi at stat dot cmu dot edu">Cosma
Shalizi</a> or <a href="mailto:kklinkner at gmail dot com">Kristina
Klinkner</a>.
<P>Please write us to let us know if you use CSSR in an application (especially
a paper), compile it on a new platform, modify it, wish to be kept informed of
future developments, or have a bug or other problem to report. However, before
sending bug reports, please read the documentation carefully, and if possible
the paper too, so that you're sure what you're experiencing <em>is</em> a bug.
Since CSSR is released under the Gnu Public License, feel free to write your
own fix for the bug, and tell us about it!
<hr>
Created 7 August 2003 by <a href="http://bactra.org/">CRS</a>