--- 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. Gabadinho, A., & Ritschard, G. (2016). Analyzing state sequences with probabilistic suffix trees: The PST R package. *Journal of Statistical Software*, *72*(3). 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. ```{r restore-options, include = FALSE} options(old_options) ```