CSSR algorithm

CSSR algorithm
Class	Statistical
Worst-case performance	$O(k^{2L_{\max }+1})+O(N)$

Causal-state splitting reconstruction (CSSR) is an algorithm for learning a predictive model of a discrete-valued time series or other symbol sequence. It estimates the process's causal states, groups of histories that imply the same conditional distribution over future observations. The resulting model is a unifilar hidden Markov model: the current state and the next observed symbol determine the next state, while the symbols themselves are generated probabilistically. CSSR infers the number of states and their transitions as well as the probabilities associated with them.

The algorithm was developed by Cosma Shalizi and Kristina Lisa Klinkner. It was described in a 2002 Santa Fe Institute working paper coauthored with James P. Crutchfield and presented at the 2004 Conference on Uncertainty in Artificial Intelligence. Applications include neural spike trains, natural language processing, single-molecule measurements and social-media activity.

Background

CSSR draws on computational mechanics, an approach to discovering structure in stochastic processes introduced by Crutchfield and Karl Young in 1989. In this framework, two histories are equivalent if they give the same conditional probabilities for all possible future observations. A causal state is an equivalence class under this relation.

The causal state is a sufficient statistic of the past for predicting the future: retaining it preserves the past's predictive information. It is also minimal, because any other sufficient statistic of the past determines the causal state. The causal-state sequence forms a Markov process, and its states can be updated recursively from the current state and the next symbol. The resulting predictive representation is called an ε-machine.

A statistic that is sufficient for predicting just the next symbol and can be updated recursively is sufficient for predicting the whole future. CSSR uses this result to seek a minimal partition of histories satisfying both requirements. It first groups histories according to estimated next-symbol distributions, then refines those groups until their transitions can be updated recursively.

Algorithm

CSSR takes a finite alphabet of $k$ symbols, an observed sequence of length $N$, a maximum history length $L_{\max }$, and a significance level $\alpha$ for hypothesis tests. It represents histories by finite suffixes, the most recently observed symbols. Counts of words up to length $L_{\max }+1$ provide estimates of next-symbol probabilities; a state's distribution pools information from the suffixes assigned to it. The procedure has three phases.

Phase I

Initialization

CSSR begins with one state containing the empty suffix. The initial model treats the observations as independent and identically distributed, with symbol probabilities estimated from the whole sequence.

Phase II

Next-step prediction

The algorithm considers progressively longer suffixes, up to $L_{\max }$, by prepending an older symbol to each suffix. It tests whether the extended suffix's next-symbol distribution differs from that of the current state. If the test does not reject equality at level $\alpha$, the extension remains in that state. Otherwise, CSSR tests whether it can be assigned to another existing state; if none matches, it creates a new state. The original description permits chi-squared or Kolmogorov–Smirnov tests. This phase groups suffixes with statistically indistinguishable next-symbol distributions.

Phase III

Recursive updating

Transient states are removed. CSSR then checks whether appending a given new symbol to every suffix in a state leads to the same next state. If different suffixes lead to different states, it splits the original state. Because a split can affect other transitions, refinement continues until the current state and next symbol uniquely determine the successor state.

Thus, states can be created for two reasons: a statistical test detects different next-symbol distributions, or a further split is needed to make the state updates recursive.

Properties

Convergence and history length

The original papers present convergence arguments under assumptions about the generating process. These include conditional stationarity, finitely many causal states, and a finite bound $\Lambda$ such that every causal state can be identified by at least one suffix of length at most $\Lambda$. This condition does not require every suffix of that length to identify a state. The analysis assumes $L_{\max }\geq \Lambda$, so that the histories considered can distinguish the states.

These asymptotic arguments do not guarantee recovery from a particular finite sample. At finite sample sizes, the significance level affects how readily sampling fluctuations produce additional states. Histories must also occur often enough for their next-symbol distributions to be estimated reliably. Longer histories can reveal predictive distinctions, but they require more observations and increase the computational cost.

The CSSR papers discuss results on estimating word distributions that permit word length to grow logarithmically with sample size under suitable assumptions. These results inform the choice of maximum history length; they are not a universal cutoff guaranteeing recovery of a state model. In an application to Twitter activity, Darmon and colleagues used a logarithmic upper bound and selected among shorter history lengths by cross-validation.

Computational complexity

The published worst-case running-time bound is

$O(k^{2L_{\max }+1})+O(N).$

For a fixed alphabet and maximum history length, this is linear in the number of observations. Its dependence on maximum history length is exponential. The data are processed to collect word counts, after which the reconstruction operates on those counts and the inferred states. The authors report substantially faster practical performance than the worst-case bound suggests.

Comparison with other methods

Variable-length Markov models

In a variable-length Markov model (VLMM), prediction is based on a suffix context. A causal state can group several different suffix contexts with the same predictive consequences. The causal-state representation coincides with the minimal VLMM representation when each causal state can be represented by a single suffix context.

Finite causal-state models can represent processes requiring an unbounded set of VLMM contexts. An example is the even process, in which runs of one symbol between occurrences of another have even length. It has a two-state causal representation, but no finite context tree represents it exactly. This comparison concerns the models' representational capacity; learning them from finite observations also depends on the data and reconstruction settings.

Using symbols A and B, the first state emits either symbol with equal probability: A leaves the state unchanged, whereas B leads to the second state. The second state always emits B and returns to the first. The model thus records the parity of the number of Bs since the most recent A. A fixed suffix cutoff cannot always recover that parity, since the last A may lie arbitrarily far in the past; the two-state model retains it through its transitions.

Hidden Markov models fitted by EM

In their 2004 experiments, Shalizi and Shalizi compared CSSR with fully connected HMMs having one to ten states, fitted by the expectation–maximization algorithm and selected using an independent validation sequence. They evaluated the models on an even process and a seven-state process, measuring predictive error by the total variation distance between distributions of ten-symbol sequences. CSSR's error generally decreased with increasing sample size. The authors reported that the comparison procedure did not recover the minimal correct structure in these experiments, while noting that a better choice of candidate HMM structures would probably improve its performance.

Other reconstruction methods

Asok Ray described CSSR as an improvement on earlier subtree-merging methods for constructing ε-machines. For anomaly detection, he proposed a D-Markov machine, whose states are words of a fixed length. He presented this as a suboptimal approximation to an ε-machine and argued that its fixed structure reduced computational work.

Applications

• Neuroscience. Haslinger, Klinkner and Shalizi applied CSSR to simulated spike trains and experimental recordings from rat barrel cortex. Reconstructed predictive states have also been used to define informational coherence, a measure of coordinated activity based on normalized mutual information. Klinkner, Shalizi and Camperi demonstrated this measure in simulations of a neuronal network.
• Natural language processing. Muntsa Padró and Lluís Padró applied CSSR to named-entity recognition. They subsequently proposed ME-CSSR, which represents histories as sets of features and uses maximum-entropy models to estimate next-symbol probabilities, addressing data sparsity associated with encoding information in the alphabet. In preliminary experiments, combining maximum-entropy probabilities with a standard CSSR automaton improved on maximum-entropy tagging alone, while their feature-based ME-CSSR implementation performed worse.
• Biophysics. Kelly and colleagues adapted CSSR to noisy single-molecule FRET measurements, using a Gaussian mixture model to discretize observations and excluding ambiguous assignments. On simulated data, their method distinguished hidden states with the same FRET level, which the comparison program HaMMy did not. They also applied it to experimental Holliday-junction data. They reported that the method required more or better-quality data than HaMMy and could infer spurious structure from noise.
• Social media. Darmon and colleagues used CSSR to model Twitter users' posting activity and predict whether a user would post during the next ten-minute interval. Their causal-state models and echo state networks achieved similar predictive accuracy for a large proportion of users.

Limitations and extensions

CSSR's reconstruction depends on the alphabet, available data, history cutoff and testing threshold. The original algorithm infers the transition structure from sequence statistics and does not provide a mechanism for imposing prior restrictions on that structure. Encoding many features as distinct symbols can make the observed histories sparse, motivating extensions such as ME-CSSR.

A finite-state HMM need not have finitely many causal states. Henter and Kleijn showed that random errors in observations can give even simple processes infinitely many predictive states, preventing exact recovery by a finite CSSR model. They proposed robust causal states (RCS), an extension that permits approximations, and demonstrated recovery of underlying structure in an example with corrupted observations. This addresses a limitation of exact reconstruction when measurement noise changes the predictive structure.

Software

Klinkner wrote the original CSSR implementation in C++, released under the GNU General Public License. The project's website provides documentation and links to publications.

See also

• Hidden Markov model
• Variable-order Markov model
• Sufficient statistic
• Symbolic dynamics

External links

• CSSR project website
• Original software documentation