Metadata-Version: 2.4
Name: vlmc
Version: 0.3.0
License-File: LICENSE.md
Summary: Fast variable-length Markov chain estimation for discrete sequences
Home-Page: https://github.com/antonio-leitao/vlmc
Author-email: António Leitão <aleitao@novaims.unl.pt>
License-Expression: BSD-3-Clause
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: homepage, https://github.com/antonio-leitao/vlmc
Project-URL: repository, https://github.com/antonio-leitao/vlmc

<p align="center">
  <img src="https://raw.githubusercontent.com/antonio-leitao/vlmc/master/assets/logo.svg" width="200" alt="VLMC logo">
</p>

<h3 align="center">Variable-Length Markov Chains for Python</h3>

`vlmc` fits variable-length Markov chains to discrete sequences. It provides one
Python model class with three context-tree selection methods:

| Method | Purpose | Main control |
| --- | --- | --- |
| `bct` | Exact Bayesian context-tree MAP estimator; the default | `beta` |
| `bic` | Penalized maximum-likelihood / MDL baseline | `penalty` |
| `peres_shield` | Peres–Shields maximal-fluctuation estimator | sample size |

The implementation is written in Rust and exposed through Python bindings.

## Installation

Published wheels can be installed with:

```sh
pip install vlmc
```

To build this checkout, install Rust and Maturin, activate a Python environment, and
run:

```sh
pip install maturin
maturin develop --release
```

## Quick start

```python
import vlmc

rows = [
    [0, 1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 0],
]

model = vlmc.VLMC(
    alphabet_size=2,
    max_depth=2,
    method="bct",       # default
)
model.fit(rows)

contexts = model.get_contexts()
context = model.get_suffix([1, 0, 1])

model.get_counts(context)            # observations following this context
model.get_transition_counts(context) # raw next-symbol counts
model.get_distribution(context)      # Jeffreys-smoothed probabilities
model.predict_proba([1, 0, 1])       # suffix lookup + probabilities
```

Symbols must be integers in `0 <= symbol < alphabet_size`. Invalid symbols raise a
`ValueError` instead of panicking.

## Constructor

```python
vlmc.VLMC(
    alphabet_size,
    max_depth=10,
    method="bct",
    beta=None,
    penalty=None,
    boundary="condition",
)
```

- `alphabet_size` must be at least two.
- `max_depth` is the largest candidate history length.
- `method` is `"bct"`, `"bic"`, or `"peres_shield"`.
- `beta` is BCT-only and must satisfy `0.5 <= beta < 1`, the range in which the
  algorithm identifies the exact MAP tree. When omitted it is
  `1 - 2 ** (-(alphabet_size - 1))`, the value recommended by the BCT paper.
- `penalty` is BIC-only and multiplies the standard BIC penalty. It defaults to 1.
- `boundary="condition"` treats every row as an independent realization. For a
  depth `D`, its first `D` symbols form the conditioned initial history and only
  later symbols are fitted. Rows are never concatenated. A row of length at most
  `D` therefore contributes no fitted outcomes.

The fitted `sample_size` property reports the exact number of outcomes used by every
node comparison. `node_count` and `context_count` report the retained model size.
`effective_max_depth` equals `max_depth` for BCT/BIC and the data-dependent
`ln(ln(sample_size))` cap for Peres–Shields.

## Selection methods

### BCT (default)

BCT selects a maximum a posteriori context tree using a Dirichlet-1/2 (Jeffreys)
prior for transition probabilities. It is the recommended general-purpose default.

### BIC

BIC maximizes

```text
log maximum likelihood - penalty * leaves * (alphabet_size - 1) / 2 * log(sample_size)
```

This is useful when a conventional penalized maximum-likelihood model is preferred.

### Peres–Shields

For an extension `v` and suffix `w`, this method uses the paper's raw-count
fluctuation

```text
max_a |N(va) - N(wa) * N(v) / N(w)|
```

and the asymptotic threshold `sample_size ** (3/4)`. Eligible extensions have
absolute depth at most `min(max_depth, floor(ln(ln(sample_size))))`. Because this is
an asymptotic criterion, it can be conservative for moderate samples.

## Probability and context semantics

`get_contexts()` returns selected predictive contexts, ordered by length and then
lexically. BCT and BIC return leaves of a proper context tree. Peres–Shields may also
return an internal sparse fallback context together with deeper exceptional contexts,
as allowed by its prediction suffix tree construction.

`get_distribution(context)` always returns probabilities, using Jeffreys smoothing:

```text
P(a | context) = (N(context, a) + 1/2) /
                 (N(context) + alphabet_size / 2)
```

Use `get_transition_counts(context)` when raw next-symbol counts are required.
`get_counts(context)` returns `N(context)`, the number of usable outcomes following
that context.

## References

- Kontoyiannis et al., [Bayesian Context Trees: modelling and exact inference for
  discrete time series](https://doi.org/10.1111/rssb.12511).
- Csiszár and Talata, [Context tree estimation for not necessarily finite memory
  processes, via BIC and MDL](https://doi.org/10.1109/TIT.2005.864431).
- Dalevi and Dubhashi, [The Peres–Shields Order Estimator for Fixed and Variable
  Length Markov Models](https://doi.org/10.1007/11557067_24).

