ctxchain

Context-dependent Markov transition models for sequence data.

Status: pre-alpha. Everything described here works and is tested. The API is the one the design was written against, not one that grew out of the implementation.

What it is

Estimate transition structure from sequences — customer histories, visit paths, holding-size trajectories — and answer "given where they are now, where are they in N periods?" as a probability distribution, with an interval around it.

>>> import ctxchain as cx
>>> ds = cx.SequenceDataset.from_sequences(
...     [["browse", "cart", "buy"], ["browse", "browse", "cart"], ["cart", "buy"]] * 20
... )
>>> spec = cx.Order(1)
>>> model = cx.fit(cx.accumulate(ds, spec), spec)
>>> model.predict_next(["cart"]).top(2)
[('buy', 0.97...), ('cart', 0.01...)]
>>> round(float(model.forward("browse", steps=3).mean.sum()), 6)
1.0

Every model in the library has one shape:

P(next_state | context(history, covariates))

A first-order chain, a variable-length chain, a time-inhomogeneous chain and a per-segment chain differ only in how context is defined. You declare the context; estimation and prediction are shared.

>>> cx.Order(2)                                    # the previous two states
Order(2, padding='bos')
>>> cx.VariableOrder(max_depth=5).max_depth        # depth chosen per context
5
>>> (cx.Order(1) * cx.TimeIndexed(index="tenure")).state_slot   # state x tenure
0

Why not the usual implementation

The pipeline

SequenceDataset → accumulate → CountStore → fit → FittedChain

CountStore holds sufficient statistics. Once counting is done the raw data is no longer needed, memory stops depending on how much of it there was, and any number of estimators can be run against the same counts.

>>> counts = cx.accumulate(ds, spec)
>>> counts.n_contexts            # only what was observed, never S**k
2
>>> mle = cx.fit(counts, spec, estimator=cx.estimators.MLE())
>>> backoff = cx.fit(counts, spec, estimator=cx.estimators.Backoff())
>>> mle.n_states == backoff.n_states
True

Getting answers out

The step column may be a date, as long as you say what one step means -- the unit decides what counts as a gap, so it is asked for rather than guessed.

>>> import pandas as pd
>>> frame = pd.DataFrame(
...     {
...         "id": ["u", "u", "u"],
...         "month": pd.to_datetime(["2024-01-31", "2024-02-29", "2024-03-31"]),
...         "plan": ["free", "pro", "pro"],
...     }
... )
>>> monthly = cx.SequenceDataset.from_dataframe(
...     frame, entity="id", step="month", state="plan", step_unit="M"
... )
>>> next(iter(monthly)).steps          # calendar months, not elapsed days
[24288, 24289, 24290]

A fitted model exports a labelled table, answers the long-run question, and survives the session:

>>> plans = cx.SequenceDataset.from_sequences([["free", "pro", "pro"] * 8] * 25)
>>> plan_model = cx.fit(cx.accumulate(plans, spec), spec, estimator=cx.estimators.MLE())
>>> plan_model.to_frame().round(2)     # doctest: +NORMALIZE_WHITESPACE
to     free   pro
from
free   0.00  1.00
pro    0.47  0.53
>>> plan_model.stationary().top(2)     # long-run share of time in each state
[('pro', 0.68...), ('free', 0.31...)]
>>> import tempfile, pathlib
>>> with tempfile.TemporaryDirectory() as tmp:
...     saved = plan_model.save(pathlib.Path(tmp) / "model")
...     cx.FittedChain.load(saved).stationary().top(1)
[('pro', 0.68...)]

stationary() refuses a chain with two closed classes rather than picking one: where such a process settles depends on where it started. With a posterior it solves once per draw, because π is non-linear in P -- the same reason forward never powers the mean matrix.

Estimators

Install

pip install ctxchain

Optional extras: ctxchain[bayes] (NumPyro posterior inference), ctxchain[io] (pandas/parquet readers), ctxchain[viz], ctxchain[sparse].

Tutorials

• Holdings that drift with tenure — small ordered state space, time-varying matrices, censoring, exit analysis, credible intervals.
• What visitors do next — large sparse state space, variable-order backoff, streaming input, order selection.

Both are executable: the test suite runs them.

On uncertainty

Three things this library refuses to do quietly.

Power the mean matrix. E[P]ⁿ ≠ E[Pⁿ]. Posterior draws are propagated one at a time and summarised at the end, so intervals do not collapse as the horizon grows.

Power a matrix that does not describe the chain. A model conditioning on more than one state is not Markov on the states, so there is no S × S matrix to raise to a power at all. forward walks paths that carry their history instead, and transition_matrix asks for the states it is missing rather than quietly returning the start-of-sequence rows.

>>> deep = cx.VariableOrder(max_depth=3)
>>> chain = cx.fit(cx.accumulate(ds, deep), deep)
>>> try:
...     chain.transition_matrix()
... except ValueError as error:
...     print(str(error).split(". ")[0])
VariableOrder(...) conditions on 3 states, so a transition matrix needs the 2 preceding one(s) in history=; got 0
>>> chain.forward(["browse", "cart"], steps=4, n_paths=2000, seed=0).n_paths
2000

Report a number without its support. FittedChain.diagnostics reports per-context coverage, prior dominance and effective order, and the serious warnings appear in the chain's repr whether or not you ask for them.

>>> thin = cx.SequenceDataset.from_sequences([["a", "b", "c"]])
>>> deep = cx.VariableOrder(max_depth=3)
>>> shown = repr(cx.fit(cx.accumulate(thin, deep), deep))
>>> "[error] thin_contexts: 7 of 7 contexts (100%)" in shown
True

Call a what-if a causal effect. replace_transition recomputes a forecast under a modified matrix. Identification is not this library's job, and it does not pretend otherwise — which is why the method is not called intervene.

Not in scope

HMMs and latent-state models, continuous-time chains, deep sequence models, causal-effect estimation, plotting beyond a few inspection helpers. See §2.2 of the design document, and DECISIONS.md for the reasoning behind every choice that was not obvious.

Development

python -m venv .venv && . .venv/bin/activate
pip install -e '.[dev]'
ruff check . && ruff format --check . && mypy && pytest

The suite covers 100% of the package, and pytest --cov fails below 99%. The only coverage exclusions are pragma: no cover on nine environment-dependent or defensive lines, each with its reason written next to it.

Benchmarks are in benchmarks/ and are not run by CI:

python benchmarks/bench_accumulate.py --states 1000 --depth 5 --transitions 10_000_000

License

MIT