This article is presumed to be AI-generated. It was created around the same time as other AI-generated contributions by the same user, shows similar patterns, and has received few significant contributions from other editors. AI pages usually violate Wikipedia's policies and guidelines. If no editor takes responsibility for it within a five-day grace period, this article may be deleted. To object to proposed deletion, an editor may take responsibility for the content and assume the onus to achieve consensus for its inclusion. Assuming responsibility requires that all content and its sources be closely reviewed and reworked as needed to ensure that they comply with policies and guidelines. This may involve checking that the cited sources support the content and are reliable, determining whether the content is due for inclusion, and rewriting the content to revise any tone issues and resolve possible copyright violations. Once this has been done, this template may be removed. The nominator also gave the following reason for this proposed deletion:
Find sources: "CSSR algorithm" – news · newspapers · books · scholar · JSTOR Reviewer tools: guideline project (talk • log) The article may be deleted if this message remains in place for five days, i.e., after 19:11, 19 November 2026 (UTC). |
| CSSR algorithm | |
|---|---|
| Class | Statistical |
| Worst-case performance | |
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.
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.
CSSR takes a finite alphabet of symbols, an observed sequence of length , a maximum history length , and a significance level for hypothesis tests. It represents histories by finite suffixes, the most recently observed symbols. Counts of words up to length provide estimates of next-symbol probabilities; a state's distribution pools information from the suffixes assigned to it. The procedure has three phases.
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.
The original papers present convergence arguments under assumptions about the generating process. These include conditional stationarity, finitely many causal states, and a finite bound such that every causal state can be identified by at least one suffix of length at most . This condition does not require every suffix of that length to identify a state. The analysis assumes , 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.
The published worst-case running-time bound is
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.
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.
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.
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.
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.
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.