---
title: "Variable-order transition trees"
author: "Written by [Mohammed Saqr](https://saqr.me) and [Sonsoles López-Pernas](https://sonsoles.me)"
output:
  rmarkdown::html_vignette:
    toc: true
    toc_depth: 2
vignette: >
  %\VignetteIndexEntry{Variable-order transition trees}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r options, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>", fig.width = 7,
                      fig.height = 4.5, fig.align = "center", dpi = 96)
old_options <- options(digits = 3, width = 90)
```

Sequences of categorical states are among the most common records in the
learning and behavioral sciences: the weekly engagement of a student, the
moves of a group negotiating a task, the turns of a person working with an
AI assistant. A first-order Markov chain summarizes such data by the
probability of each next state given the current one. Its assumption is
that memory has the same length everywhere. A higher-order chain relaxes
the length but keeps it fixed, and the number of parameters grows
geometrically with the order, so most of the longer histories are estimated
from very few observations.

A variable-order Markov chain lets the length of the relevant history
depend on the history itself. After some states the next state is well
predicted by the current state alone; after others, one or two earlier
states change the prediction. The model is stored as a prediction suffix
tree (Ron, Singer, & Tishby, 1996): each node is a context, a short run of
recent states, and carries a distribution over the next state. Contexts are
kept only where the data support them, so the tree is deep where history
matters and shallow where it does not (Bühlmann & Wyner, 1999; Gabadinho &
Ritschard, 2016). The `transitiontrees` package fits these trees, reports
them as tables of pathways, prunes them by likelihood-ratio tests or
information criteria, and uses them to predict, score and compare
sequences.

## The model

Let $S$ be a finite set of states (the alphabet) and $x_1, \dots, x_T$ a
sequence over $S$. A **context** of length $k$ is a run of $k$ consecutive
states $c = (x_{t-k}, \dots, x_{t-1})$ that precedes position $t$. The
model specifies, for each context in a set $\mathcal{C}$, a next-state
distribution

$$
P(x_t = s \mid c), \qquad s \in S .
$$

The set $\mathcal{C}$ is closed under suffixes: if a context is in the
tree, so is every shorter run obtained by dropping its oldest states. It
therefore forms a tree whose root is the empty context, written
`(start)`, and in which each child extends its parent by one state further
into the past.

**The longest-suffix rule.** To predict $x_t$ from the history
$x_1, \dots, x_{t-1}$, the model uses the longest suffix of the history
that is a context in the tree,

$$
c^*(t) = \arg\max_{c \in \mathcal{C}} \{\, |c| : c \text{ is a suffix of }
(x_1, \dots, x_{t-1}) \,\},
\qquad
\hat P(x_t \mid x_1, \dots, x_{t-1}) = \hat P(x_t \mid c^*(t)).
$$

A first-order chain is the special case in which $\mathcal{C}$ holds the
root and every single state; a fixed $k$-th order chain holds every
context up to length $k$.

**Estimation.** Let $N(c, s)$ be the number of times context $c$ is
followed by state $s$ in the data and $N(c) = \sum_s N(c, s)$. A context
receives its own node when it is no longer than `max_depth` and
$N(c) \ge$ `min_count`. Its maximum likelihood distribution is
$\hat p(s \mid c) = N(c, s) / N(c)$.

**Smoothing.** A state never observed after $c$ would receive probability
zero, and one such event in new data would make the likelihood zero. The
default floor smoother leaves a fully observed distribution unchanged and
otherwise shifts it toward the uniform distribution,

$$
\tilde p(s \mid c) = (1 - |S|\, y_{\min})\, \hat p(s \mid c) + y_{\min},
$$

so that each unobserved state receives exactly $y_{\min}$ (default
0.001). Laplace, Kneser-Ney, Witten-Bell and Jelinek-Mercer smoothers are
available through `smoothing =`.

**Pruning.** Let $\pi(c)$ be the parent of $c$, the context with the
oldest state removed. A leaf $c$ is kept when its counts differ from the
prediction of its parent by more than chance. The likelihood-ratio
statistic

$$
G^2(c) = 2 \sum_{s \in S} N(c, s)\,
\log \frac{N(c, s)}{N(c)\, \tilde p(s \mid \pi(c))}
$$

is compared with the $1 - \alpha$ quantile of a $\chi^2$ distribution with
$|S| - 1$ degrees of freedom; leaves that fail are removed, and the test
is repeated on the new leaves until every leaf passes. The `AIC` and `BIC`
criteria keep a leaf when its log likelihood, penalized by $2(|S| - 1)$ or
$\log N(c)\,(|S| - 1)$, exceeds that of its parent's prediction.

**Fit.** The log likelihood of the data is
$\ell = \sum_t \log \tilde p(x_t \mid c^*(t))$, with $|\mathcal{C}|(|S| -
1)$ free parameters. Perplexity, $\exp(-\ell / n)$ for $n$ predicted
states, is the effective number of equally likely next states: it equals
$|S|$ for a uniform guess and 1 for perfect prediction.

**Divergence.** The pathway tables report, for each context, the
Kullback-Leibler divergence in bits of its next-state distribution from
its parent's,
$D(c) = \sum_s \tilde p(s \mid c) \log_2 [\tilde p(s \mid c) /
\tilde p(s \mid \pi(c))]$. A large divergence marks a history that changes
the prediction made from the shorter history.

## Data

`engagement` holds the weekly engagement states of 1,000 students, one
student per row and one week per column (`T1` to `T25`).

- **Sequence:** each row is one student's trajectory, read from left to
  right.
- **States:** `Active`, `Average` and `Disengaged`.
- **Missing cells:** `NA` marks weeks after a student's record ends; such
  cells are dropped, not treated as a state.

```{r setup}
library(transitiontrees)
head(engagement, 3)
```

## Fitting a tree

`context_tree()` takes a wide data frame or matrix, a list of character
vectors, or a long event log. The tree below allows histories of up to
three weeks and gives a context its own node when it occurs at least ten
times.

```{r fit}
tree <- context_tree(engagement, max_depth = 3, min_count = 10)
tree
```

The banner reports `r n_nodes(tree)` nodes over 1,000 sequences and
24,555 observed states. Each line of the tree is a context with its count
and its most likely next state. Children extend their parent into the
past: the line `Disengaged` indented under `Active` is the context
`Disengaged -> Active`, a disengaged week followed by an active one. The
root line is the marginal distribution, the prediction made with no
history: `Active` with probability 0.51.

`state_frequencies()` gives the shares of the three states.

```{r frequencies}
state_frequencies(tree)
```

Half of all observed weeks are `Active`, 28% `Disengaged` and 21%
`Average`.

## Reading the tree

`summary()` returns the pathway table, one row per context, sorted by
count; `as.data.frame()` returns the same table for every node.

```{r summary}
summary(tree)
```

Each row is a **pathway**, written oldest state first, so
`Average -> Disengaged` is an average week followed by a disengaged one.
`likely_next` and `next_probability` give the modal next state and its
probability, `divergence` is $D(c)$ in bits, and `changes_prediction`
flags a context whose modal next state differs from its parent's.

`tree_pathways()` returns the full table with a choice of sort order, and
three verbs fix the sorts used most often. `common_pathways()` ranks by
count:

```{r common}
common_pathways(tree, top = 5)
```

`divergent_pathways()` ranks by divergence from the shorter history. A
`min_count` of 50 keeps contexts with enough support to be read.

```{r divergent}
divergent_pathways(tree, top = 6, min_count = 50)
```

The single states diverge most from the root, and two of them redirect the
prediction: after a `Disengaged` week the most likely next week is
`Disengaged` (0.786), and after an `Average` week it is `Average` (0.548),
whereas the marginal prediction is `Active`. Beyond one week the
divergences are an order of magnitude smaller; the largest,
`Average -> Active -> Disengaged` (82 occurrences, 0.0445 bits), raises
the probability of staying disengaged to 0.902.

`sharp_pathways()` ranks by the probability of the modal next state, the
contexts after which the next state is most predictable.

```{r sharp}
sharp_pathways(tree, top = 5, min_count = 50)
```

Each of the sharpest contexts ends in a state that tends to repeat.
`Average -> Active -> Disengaged` is followed by another disengaged week
with probability 0.902, and four three-week histories ending in `Active`
are followed by `Active` with probabilities between 0.861 and 0.867.

## Pruning

Most of the grown contexts may predict no better than their parents.
`prune_tree()` removes leaves that fail the $G^2$ test at
$\alpha = 0.05$.

```{r prune}
pruned <- prune_tree(tree, criterion = "G2", alpha = 0.05)
pruned
```

The test keeps `r n_nodes(pruned)` of the `r n_nodes(tree)` nodes. The
surviving structure is mostly first order. The longer histories that
remain all involve disengagement: an `Average` week before a disengaged
one lowers the probability of staying disengaged (0.734 against 0.786),
and the history `Active -> Disengaged -> Disengaged` is kept as well.

`plot()` draws the tree from the root on the left. Node size is the
context count, edge width the number of observations flowing into the
child, node color the most recent state of the pathway, and the label
under each node the modal next state with its probability.

```{r plot-tree, fig.width = 9, fig.height = 5}
plot(pruned)
```

`compare_pruning()` applies each criterion to the same tree and reports
how many nodes it keeps.

```{r compare-pruning}
compare_pruning(tree)
```

BIC, whose penalty grows with the context count, is the strictest (6
nodes); the KL threshold is the most lenient (19 nodes); $G^2$ and AIC lie
between. The [smoothing and pruning](https://pak.dynasite.org/transitiontrees/articles/smoothing-and-pruning.html)
guide compares the criteria and smoothers in detail.

## Fit

`model_fit()` returns the log likelihood, degrees of freedom, number of
predicted states, AIC, BIC and perplexity in one row.

```{r fit-unpruned}
model_fit(tree)
```

```{r fit-pruned}
model_fit(pruned)
```

Pruning lowers the log likelihood only slightly (from -16,163 to
-16,181) while reducing the parameters from 80 to 20, so both AIC
(32,486 to 32,403) and BIC (33,134 to 32,565) favor the pruned tree. The
perplexity of both trees is 1.93: knowing the recent weeks reduces the
three possible next states to about two equally likely ones. These values
are computed on the fitting data. Out-of-sample perplexity by
cross-validation is the subject of the
[model selection](https://pak.dynasite.org/transitiontrees/articles/model-selection.html)
guide.

## Prediction

`predict()` applies the longest-suffix rule to new histories. With
`tidy = TRUE` it returns one row per history: the context used, the
predicted state, its probability, and the full distribution.

```{r predict}
histories <- list(c("Active", "Average"),
                  c("Average", "Disengaged"),
                  c("Disengaged", "Active", "Disengaged"))
predict(pruned, newdata = histories, tidy = TRUE)
```

The first history ends in `Average`, and no longer context ending in
`Average` survived pruning, so the prediction is made from `Average`
alone. The second history is itself a context. The third has no matching
two- or three-week context, so the model falls back to `Disengaged` and
predicts another disengaged week with probability 0.786.

## Further reading

The guides and case studies on the
[package website](https://pak.dynasite.org/transitiontrees/) continue from
here:

- [Comparing groups](https://pak.dynasite.org/transitiontrees/articles/comparing-groups.html):
  fitting one tree per group and testing where the groups differ.
- [A complete workflow](https://pak.dynasite.org/transitiontrees/articles/workflow.html):
  every step of an analysis on one dataset.
- [Data input](https://pak.dynasite.org/transitiontrees/articles/data-input.html):
  wide sequences, event logs and network objects.
- [Smoothing and pruning](https://pak.dynasite.org/transitiontrees/articles/smoothing-and-pruning.html).
- [Model selection: tuning, fit and perplexity](https://pak.dynasite.org/transitiontrees/articles/model-selection.html).
- [Pathway reliability with the bootstrap](https://pak.dynasite.org/transitiontrees/articles/pathway-reliability.html).
- [Prediction, scoring, imputation and mining](https://pak.dynasite.org/transitiontrees/articles/prediction-and-scoring.html).
- [Visualizing transition trees](https://pak.dynasite.org/transitiontrees/articles/visualization.html).
- [Verification against the PST package](https://pak.dynasite.org/transitiontrees/articles/verification.html).
- Case studies:
  [collaborative regulation by achievement](https://pak.dynasite.org/transitiontrees/articles/case-regulation-achievement.html),
  [engagement trajectories](https://pak.dynasite.org/transitiontrees/articles/case-engagement.html)
  and [human-AI collaboration](https://pak.dynasite.org/transitiontrees/articles/case-ai-collaboration.html).

## Assumptions

- The sequences are independent of one another, and the process is the
  same at every position (stationarity).
- The next state depends on the past only through its longest context in
  the tree.
- `max_depth` and `min_count` bound which contexts can be represented;
  contexts rarer than `min_count` are absorbed into their parent.
- The $G^2$ pruning test is applied per leaf without correction for
  multiple testing.

## References

Bühlmann, P., & Wyner, A. J. (1999). Variable length Markov chains.
*The Annals of Statistics*, *27*(2), 480--513.
<https://doi.org/10.1214/aos/1018031204>

Gabadinho, A., & Ritschard, G. (2016). Analyzing state sequences with
probabilistic suffix trees: The PST R package. *Journal of Statistical
Software*, *72*(3). <https://doi.org/10.18637/jss.v072.i03>

Ron, D., Singer, Y., & Tishby, N. (1996). The power of amnesia: Learning
probabilistic automata with variable memory length. *Machine Learning*,
*25*(2--3), 117--149. <https://doi.org/10.1023/A:1026490906255>

```{r restore-options, include = FALSE}
options(old_options)
```
