HVTM — Hyperdimensional Vector Tsetlin Machine (Python)

Pure-Python / NumPy implementation of the architecture in Blakely 2024 — Hyperdimensional Vector Tsetlin Machines with Applications to Sequence Learning and Generation: HV encoding of scalar sequences, an associative memory, and a coalesced multi-output Tsetlin Machine, wired into a sequence classifier and a recursive forecaster.

Status

This repository is a faithful reimplementation of the HV+TM family. That status is supported by three independent classes of evidence — all runnable here, with deterministic seeds where applicable:

1. Architecture and primitives — faithful. The HVC algebra, N-Gram encoding, interval embedding, associative memory, and Tsetlin-Machine forward pass are each pinned by an [EXACT] assertion in tests/ (see FIDELITY.md); the TM feedback rules are pinned [ORACLE]-equivalent to pyTsetlinMachine on identical inputs (mean |ours − oracle| = 0.043). Latest run: python -m unittest discover -s tests -v → 29/29 OK (one skipped: external oracle).
2. Reachable paper findings.
   • Encoder lever — reproduced. The bake-off independently shows a family-level lever: thermometer +6 pp over the Blakely-literal random+uniform default at 8-seed CI (results_encoder_sweep.txt).
   • Deterministic forecasting — architecture works in the regime; we have not been able to match the paper's literal-formula result. A curated reliably-periodic substituted signal (periodic mixture; on the natural integer grid the paper's literal chirp formula aliases above Nyquist — see the Open question section) forecasts to MAE ≈ 0.010 at exact paper capacity (scripts/validate_pipeline.py L1b). This is not a same-signal comparison with Blakely's Table-1 0.044 — it shows the architecture can forecast in the regime, on a different series. On the 50-trial paper-config protocol over the substitute, the result is ≈ 0.32 (per-instance phase-lottery from random a,b,c), nowhere near 0.044. We did not find the t-range / sampling step in the paper text we have; a pointer to it would let us run the literal-signal comparison.
   • UCR classification — same regime, not the paper's headline. Lands at mean 0.712 (best-of-4-encoders, distributional 8-seed CI), ≈9 pp below DTW; does not reach the paper's "78 % within 2 pp" claim.
3. Stochastic AR/ARMA Table-1 rows — what we computed. Blakely §4.2.1 verbatim states "For each forecast, we compute the error with the ground truth next value in that sequence"; we read this as a realized-next-value target. Under that reading, scripts/mmse_floor.py (deterministic, fixed seed, 2000 trials) computes an MMSE lower bound per process. For 4 of the 6 stochastic Table-1 rows (AR(1)φ=0.4, AR(1)φ=0.7, AR(2)0.1;0.7, ARMA(1,1)) the Table-1 value sits below that bound — e.g. for AR(1)φ=0.4 we compute 0.287±0.06 (recursive) / 0.256 (1-step), against the Table-1 0.102. The two SAR rows are above the bound; the deterministic harmonic is above and reproduced. We have not identified a setup that reaches the four affected values; a clarification of any detail we may have missed would be useful.

This repository can be used as the authoritative HV+TM-family baseline-of-capability. One open question remains for us: the harmonic-series sampling grid / t-range, which we did not find in the paper text we have. On the natural integer grid the literal formula's chirp term aliases above Nyquist. See Open question.

Layout

hvtm/                               (the model — importable package)
  hvc.py        Binary spatter codes: random HV, bundle (majority),
                bind (XOR), perturb (cyclic shift), Hamming distance.
  encoding.py   IntervalEmbedding (scalar -> bucket HV; scheme =
                random|thermometer|linear, bucketing = uniform|quantile)
                and N-gram sequence encoding.
  memory.py     Associative memory: store (gv, label), retrieve by
                arg-min Hamming distance.
  tm.py         CoalescedTsetlinMachine: shared clause pool, signed
                per-class weights, Type I/Ia/Ib + Type II feedback,
                boost_true_positive_feedback, optional max-literal cap.
  hvtm.py       HVTMClassifier (one HV per sequence -> K-class TM) and
                HVTMForecaster (recursive 1-step TM + memory ensemble).

scripts/
  test_smoke.py                 correctness gate.
  validate_pipeline.py          forecasting gates L0/L1/L1b/L2.
  generate_forecast_results.py  writes results_forecast*.txt
  generate_encoder_results.py   writes results_encoder_sweep.txt
                                (distributional, parallel).
  forecast_models.py            synthetic series generators.
  ucr_data.py                   load_ucr() + DATASETS_DIR; optional
                                standalone UCR-classify diagnostic.
  mmse_floor.py                 MMSE lower bound on attainable
                                forecast MAE for AR/ARMA/SAR series.
  harmonic_degeneracy.py        harmonic sampling-grid analysis.
  tie_sensitivity.py            encoder tie-break sensitivity.
  weight_sweep.py               TM⊕memory weight grid (11 values).

tests/           unittest suite: HVC/encoding/memory/TM pinning +
                 oracle-equivalence; oracle_equivalence_result.txt.

datasets/        Extracted UCR datasets, one folder per dataset
                 (<name>/<name>_{TRAIN,TEST}.txt). load_ucr() resolves
                 these relative to the project root, cwd-independent.

Dependencies: numpy only. generate_encoder_results.py and tests/test_oracle_equivalence.py additionally need pyTsetlinMachine as an external reference TM. It is vendored as a git submodule under extern/pyTsetlinMachine (cair/pyTsetlinMachine, MIT, version 0.6.6). After cloning, fetch and build it once:

git submodule update --init extern/pyTsetlinMachine
pip install -e extern/pyTsetlinMachine    # builds the C extension

Installing pyTsetlinMachine from PyPI works as well — the oracle-equivalence test only requires that from pyTsetlinMachine.tm import MultiClassTsetlinMachine succeeds. If it does not, the test skips and the recorded numbers in tests/oracle_equivalence_result.txt stand as the portable evidence. The other entry points have no external dependency.

Datasets (not committed)

The 12 UCR datasets used by the encoder sweep / UCR diagnostic are not in the repo (.gitignored — redistributable UCR data, not this project's content). load_ucr() expects datasets/<name>/<name>_{TRAIN, TEST}.txt. Fetch them with:

mkdir -p datasets
for d in GunPoint ECG200 Coffee ItalyPowerDemand Trace Wine Beef \
         ArrowHead BeetleFly Computers ECGFiveDays MoteStrain; do
  curl -fsSL -o "$d.zip" "https://timeseriesclassification.com/aeon-toolkit/$d.zip"
  python -c "import zipfile,os;zipfile.ZipFile('$d.zip').extractall('datasets/$d');os.remove('$d.zip')"
done

The forecasting scripts use synthetic generators (forecast_models.py) and need no download.

How to run

# correctness gate
python scripts/test_smoke.py

# regenerate the canonical result files
python scripts/generate_forecast_results.py --trials 3 --dim 2000 \
    --clauses 400 --epochs 4 --n_grams 3 5 --weight_memory 0.5
python scripts/generate_encoder_results.py

# weight-memory sweep — full grid for the "weighted average"
python scripts/weight_sweep.py                  # directional (default)

# optional UCR-classify diagnostic (not a canonical result)
python scripts/ucr_data.py --datasets GunPoint ECG200 Coffee \
    ItalyPowerDemand Trace --trials 5 --epochs 10

Results

Forecasting. At Blakely §4.2.1's exact hyperparameters (D=5000, C=1000, Q=50, max-lit=50, T=100, s=15, N=5) a reliably-periodic harmonic has MAE 0.010–0.011 vs the paper's Table-1 harmonic 0.044 — the implementation operates in the paper's deterministic regime (gated by scripts/validate_pipeline.py L1b). The per-series TM is capacity-sensitive: C=1000/E=20 gives 0.010–0.019, C=400/E=4 underfits (0.41). For the stochastic AR/ARMA rows, under a realized-next-value target the MMSE lower bound that we compute for [−1,1]-normalized AR(1) φ=0.4 is 0.287 (24-step recursive) / 0.256 (1-step); Blakely's Table-1 0.102 sits below this bound. Blakely §4.2.1 verbatim defines the target as the "ground truth next value" (the realized-next-value reading). Under a conditional-mean (denoised) target the implementation reaches ≈0.17 at paper capacity; this is recorded for reference but is not the paper's stated reading. The SAR rows are above the bound and reachable. AR(1) under [−1,1] min-max norm is σ-invariant.

• results_forecast_paperconfig.txt — full Table-1 grid at exact paper hyperparameters, 50 trials, N∈{3,5,7}, per-component breakdown. This is the substitute-harmonic run (high variance on the stochastic models for the reasons above); the alignment evidence is validate_pipeline.py L1b, not this file.
• results_forecast.txt — reduced-scale (C=400/E=4) directional run; undertrained, included for the capacity-sensitivity contrast.

Comparison artifacts (this impl vs DTW vs the paper), self-contained with methodology + caveats:

• comparison_ucr_classification.txt — per-dataset table over the 12-dataset stratified sweep plus aggregates. Key finding: this implementation lands in the DTW-class regime (distributional mean 0.712, ~9pp below DTW) and does not reach the paper's 78%-within-2pp headline; the implementation is oracle/test-pinned (FIDELITY.md), so the gap sits in protocol details we did not match.

• comparison_forecasting.txt — Blakely Table 1 vs this impl (deterministic: the L1b substitute reaches 0.010, but this is not a same-signal comparison with the paper's 0.044; stochastic: Table-1 values for AR/ARMA sit below the MMSE lower bound we compute under the realized-next-value reading, ≈0.17 under a denoised target).

• results_encoder_sweep.txt — interval-encoder bake-off: 4 encoders × 12 UCR datasets stratified by DTW (0.574–1.000) × 8 seeds, with pyTsetlinMachine as a fixed reference TM and a 15-config top-of-8 selection. Distributional (mean ± 95% CI over seeds), because the tie-break alone swings accuracy 3–14pp (scripts/tie_sensitivity.py); point numbers are not trustworthy. Ranking:

  Encoder	Mean acc	Mean Δ vs DTW
  thermometer+uniform	0.702	−0.103
  linear+uniform	0.686	−0.118
  random+uniform (Blakely §2.3 literal)	0.642	−0.162
  random+quantile	0.617	−0.187

  thermometer and linear are tied within CI and both exceed the Blakely-literal random+uniform by ~+4–6pp (non-overlapping CIs); random+quantile is the weakest. No encoder reaches Blakely's "78% within 2pp of DTW"; the residual comes from whole-sequence bundle saturation on long series, low capacity on small multi-class training sets, and selection-protocol generosity. Deterministic: fixed seeds 1–8.

Implementation notes

• TM correctness. hvtm/tm.py follows the canonical coalesced multi-output rules (Glimsdal & Granmo 2021): weights ±1 per active cout=1 clause regardless of sign (target +1, non-target −1); Type I on W≥0 / Type II on W<0 for the target, flipped for the non-target; boost_true_positive_feedback on by default. The feedback rules are pinned empirically to pyTsetlinMachine on identical inputs (mean |diff| = 0.043, 3 datasets × 2 seeds) — behavioral corroboration against an independent implementation. Per-component evidence map and limits: see FIDELITY.md and the tests/ suite.
• Encoder schemes. IntervalEmbedding(scheme=, bucketing=, fit_data=). Defaults are random / uniform (the Blakely §2.3 literal reading); thermometer and linear are HDC level encodings that preserve value ordering.

Deviations from the paper

• Scale. results_forecast.txt is a reduced-scale (C=400/E=4) run, undertrained relative to paper capacity. The exact paper config is in results_forecast_paperconfig.txt; the alignment evidence is scripts/validate_pipeline.py L1b.

• Harmonic series. On the natural integer grid the paper's a·sin(t²)·cos(b·t²+c·t) + sin(2+t) has a chirp term ~99% above Nyquist (scripts/harmonic_degeneracy.py; chirp-unpredictable MAE bound ≈0.15, well above the paper's 0.044 — see the Open question), so a periodic mixture a·sin(t) + b·sin(2t) + c·sin(3t) over t ∈ [0,8π] is substituted. At the exact paper config over 50 trials this substitute does not reproduce the paper's harmonic figure: memory-only ≈ 0.32 ±0.30 (a per-instance phase-alignment lottery) vs the paper's tight 0.044 ±0.012. The substitution is a genuine source of non-alignment.

• Forecast combination. The paper combines memory and TM by "weighted average"; we did not find the weight in the paper text we have, so we sweep it (scripts/weight_sweep.py → results_weight_sweep.txt, 11 values from 0.0 to 1.0 in 0.1 steps). The historical default weight_memory=0.5 is one point on that grid. Three things the sweep shows:

  1. Best weight differs by row — Harmonic 1.0, AR(1) 0.4 → 0.2, AR(1) 0.7 → 0.1, AR(2) → 0.4, SAR(1) 0.3;0.7 → 0.5, SAR(1) 0.7;-0.1 → 0.3, ARMA(1,1) → 0.5. No single weight wins across rows; 0.5 is best on only 2 of 7.
  2. No argmin in the 11-point grid landed between 0.5 and 1.0 — the argmin is either pure memory (Harmonic) or w ≤ 0.5 (stochastic rows). A "mostly memory + a bit of TM" blend was not the argmin on any row in this sweep.
  3. No weight in the grid reaches the paper's AR/ARMA numbers — the lowest MAE across all weights is 0.328 (AR(1) 0.4) / 0.355 (AR(1) 0.7) / 0.348 (ARMA(1,1)), against paper values of 0.102 / 0.152 / 0.152. The MMSE lower bound from scripts/mmse_floor.py sits above these paper values under the realized-next-value reading, so the gap is not a weight-tuning question in this implementation.

• Max-literal cap. The paper gives a max-literal value (50); we did not find the mechanism for exceeding it in the paper text we have (the canonical TM has no explicit hard cap). This implementation uses a soft cap: excess Type-I include events over the cap are randomly dropped. Toggling the cap (50 vs none) moves results within seed noise — forecast MAE Δ=0.000, ECG200 acc Δ=0.010 (scripts/maxlit_ablation.py) — and the classification headline runs on the pyTsetlinMachine oracle, so this mechanism is off that path entirely.

Open question

Harmonic-series sampling grid / t-range (scripts/harmonic_degeneracy.py). Blakely §4.2.1 states the formula s(t) = a sin(t²·π) · cos(b·t²·π + c·t) + sin(2π + t) and "we sample 220 observations". We did not find the t-range or sampling step in the paper text we have. On the natural integer-index grid the chirp instantaneous frequency aliases above Nyquist for moderate t, giving a chirp-unpredictable MAE lower bound of ≈0.15 (above Table 1's 0.044). On a fine grid the chirp is well-sampled, so the reported 0.044 is grid-dependent in our hands. A pointer to the sampling grid the paper used would let us run the literal-signal comparison.

Pointers welcome via a repo issue.

Not included

• Full UCR archive (128 datasets), image / EMG / spectra inputs, multivariate sequences.
• Reference [1] (Halenka et al. 2024) has no public source; the HVC primitives and N-gram encoder follow the paper's stated equations and are unit-tested for round-trip and shape correctness only.