<a name="top"></a>

tsetlin-rs

<p align="center"> <a href="https://crates.io/crates/tsetlin-rs"><img src="https://img.shields.io/crates/v/tsetlin-rs?style=for-the-badge&logo=rust&logoColor=white&label=crates.io&color=e6522c" alt="Crates.io"/></a> <a href="https://docs.rs/tsetlin-rs"><img src="https://img.shields.io/docsrs/tsetlin-rs?style=for-the-badge&logo=docsdotrs&logoColor=white&label=docs.rs&color=blue" alt="docs.rs"/></a> <a href="https://github.com/RAprogramm/tsetlin-rs/actions/workflows/ci.yml"><img src="https://img.shields.io/github/actions/workflow/status/RAprogramm/tsetlin-rs/ci.yml?style=for-the-badge&logo=githubactions&logoColor=white&label=CI" alt="CI"/></a> </p> <p align="center"> <a href="https://codecov.io/gh/RAprogramm/tsetlin-rs"><img src="https://img.shields.io/codecov/c/github/RAprogramm/tsetlin-rs?style=for-the-badge&logo=codecov&logoColor=white&color=f01f7a" alt="codecov"/></a> <a href="LICENSE"><img src="https://img.shields.io/badge/license-MIT-green?style=for-the-badge&logo=opensourceinitiative&logoColor=white" alt="License"/></a> <a href="https://api.reuse.software/info/github.com/RAprogramm/tsetlin-rs"><img src="https://img.shields.io/badge/REUSE-compliant-4cc61e?style=for-the-badge&logo=data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHZpZXdCb3g9IjAgMCAyNCAyNCI+PHBhdGggZmlsbD0iI2ZmZiIgZD0iTTEyIDJDNi40OCAyIDIgNi40OCAyIDEyczQuNDggMTAgMTAgMTAgMTAtNC40OCAxMC0xMFMxNy41MiAyIDEyIDJ6bS0yIDE1bC01LTUgMS40MS0xLjQxTDEwIDE0LjE3bDcuNTktNy41OUwxOSA4bC05IDl6Ii8+PC9zdmc+" alt="REUSE"/></a> <a href="https://www.rust-lang.org"><img src="https://img.shields.io/badge/rust-1.92+-93450a?style=for-the-badge&logo=rust&logoColor=white" alt="Rust"/></a> </p> <p align="center"> <strong>A production-grade Rust implementation of the Tsetlin Machine algorithm for interpretable machine learning.</strong> </p> <p align="center"> <em>Lock-free parallel training | 116x bitwise speedup | Zero-allocation inference | Full interpretability</em> </p>

---

Highlights

Performance:  4.4x parallel speedup  |  116x bitwise evaluation  |  O(1) inference
Memory:       Zero-allocation SmallClause  |  Cache-aligned structures  |  no_std support
Correctness:  99%+ test coverage  |  Property-based testing  |  Deterministic seeds

---

Table of Contents

• Overview
• Installation
• Quick Start
• Models
• Parallel Training
• Clause Implementations
• Advanced Features
• Benchmarks
• Algorithm Reference
• API Reference
• Coverage
• In Memory of Michael Tsetlin
• References
• License

---

Overview

The Tsetlin Machine is a machine learning algorithm based on propositional logic and game theory. Unlike neural networks, it learns human-readable rules (conjunctions of literals) that can be directly interpreted and verified.

Key Properties:

| Property | Tsetlin Machine | Neural Network | |----------|-----------------|----------------| | Interpretability | Rules in propositional logic | Black box | | Training | Reinforcement learning | Gradient descent | | Inference | Boolean operations | Matrix multiplication | | Hardware | FPGA/ASIC friendly | GPU optimized | | Memory | O(clauses × features) | O(layers × neurons²) |

<details> <summary><strong>Terminology & Abbreviations</strong></summary> <br/>

| Term | Definition | Category | |:-----|:-----------|:--------:| | AL | Active Literals — literals that actively contribute to predictions | sparse | | AoS | Array of Structures — traditional object layout | opt | | Bit-plane | Transposed bit representation for parallel operations | opt | | Clause | Conjunction (AND) of literals; votes for/against a class | core | | CoTM | Coalesced Tsetlin Machine | abbr | | CSR | Compressed Sparse Row — sparse matrix format using data/indices/offsets arrays | sparse | | CTM | Convolutional Tsetlin Machine | abbr | | Early exit | Terminating clause evaluation on first literal violation | opt | | False sharing | Cache line contention between CPU cores | opt | | FPGA | Field-Programmable Gate Array | abbr | | Literal | Boolean variable (xₖ) or its negation (¬xₖ) | core | | MSB | Most Significant Bit — encodes automaton action | opt | | Polarity | Clause vote direction: +1 or −1 | core | | Ripple-carry | Bit-level addition/subtraction algorithm | opt | | RNG | Random Number Generator | abbr | | SIMD | Single Instruction Multiple Data | abbr | | SmallVec | Inline vector — stack storage up to N elements, heap beyond | opt | | SoA | Structure of Arrays — cache-friendly layout | opt | | Sparsity | Fraction of active literals vs total possible (lower = sparser) | sparse | | Specificity (s) | Controls pattern generality; higher = fewer literals | train | | STM | Sparse Tsetlin Machine | abbr | | TA | Tsetlin Automaton | abbr | | Threshold (T) | Controls feedback probability | train | | TM | Tsetlin Machine | abbr |

_{core — fundamentals · train — training · opt — optimization · sparse — sparse representation · abbr — abbreviation}

</details> <div align="right"><a href="#top">Back to top</a></div>

---

Installation

[dependencies]
tsetlin-rs = "0.3"

With parallel training and serialization:

[dependencies]
tsetlin-rs = { version = "0.3", features = ["parallel", "serde"] }

Feature Flags

| Feature | Default | Description | |---------|:-------:|-------------| | std | Yes | Standard library (disable for embedded) | | parallel | No | Lock-free parallel training via rayon | | serde | No | Serialization/deserialization | | simd | No | SIMD optimization (requires nightly) | | gpu | No | GPU acceleration foundation (backend traits) |

<div align="right"><a href="#top">Back to top</a></div>

---

Quick Start

use tsetlin_rs::{Config, TsetlinMachine};

// Configure: 20 clauses, 2 features
let config = Config::builder()
    .clauses(20)
    .features(2)
    .build()
    .unwrap();

// Create machine with threshold T=15
let mut tm = TsetlinMachine::new(config, 15);

// XOR dataset
let x = vec![vec![0, 0], vec![0, 1], vec![1, 0], vec![1, 1]];
let y = vec![0, 1, 1, 0];

// Train for 200 epochs with seed=42
tm.fit(&x, &y, 200, 42);

// Evaluate
let accuracy = tm.evaluate(&x, &y);
println!("Accuracy: {:.1}%", accuracy * 100.0);

// Extract learned rules
for rule in tm.rules() {
    println!("{}", rule);
}

Output:

Accuracy: 100.0%
+: x₀ ∧ ¬x₁
+: ¬x₀ ∧ x₁
-: x₀ ∧ x₁
-: ¬x₀ ∧ ¬x₁

<div align="right"><a href="#top">Back to top</a></div>

---

Models

Binary Classification — TsetlinMachine

Standard two-class classification with weighted clause voting.

use tsetlin_rs::{Config, TsetlinMachine};

let config = Config::builder().clauses(100).features(64).build().unwrap();
let mut tm = TsetlinMachine::new(config, 15);

tm.fit(&x_train, &y_train, 100, 42);
let prediction = tm.predict(&x_test[0]);  // 0 or 1

// Online learning (incremental updates)
tm.partial_fit(&new_sample, label, 123);
tm.partial_fit_batch(&new_samples, &labels, 456, true);

Multi-class Classification — MultiClass

One-vs-all ensemble of binary classifiers.

use tsetlin_rs::{Config, MultiClass};

let config = Config::builder().clauses(100).features(64).build().unwrap();
let mut tm = MultiClass::new(config, 10, 15);  // 10 classes

tm.fit(&x_train, &y_train, 100, 42);
let class = tm.predict(&x_test[0]);  // 0..9

Regression — Regressor

Continuous output via clause voting with binning.

use tsetlin_rs::{Config, Regressor};

let config = Config::builder().clauses(100).features(64).build().unwrap();
let mut reg = Regressor::new(config, 15);

reg.fit(&x_train, &y_train, 100, 42);
let value = reg.predict(&x_test[0]);  // f32

Convolutional — Convolutional

2D patch extraction for image-like data.

use tsetlin_rs::{ConvConfig, Convolutional};

let config = ConvConfig {
    clauses: 100,
    image_height: 28,
    image_width: 28,
    patch_height: 10,
    patch_width: 10,
    n_classes: 10,
};
let mut ctm = Convolutional::new(config, 15);

Sparse Inference — SparseTsetlinMachine

Memory-efficient inference using sparse clause representation. Convert trained model for deployment with 50-125x memory reduction.

use tsetlin_rs::{Config, TsetlinMachine};

// Train as usual
let config = Config::builder().clauses(200).features(784).build().unwrap();
let mut tm = TsetlinMachine::new(config, 15);
tm.fit(&x_train, &y_train, 100, 42);

// Convert to sparse for deployment
let sparse = tm.to_sparse();

// Same predictions, much less memory
assert_eq!(tm.predict(&x_test[0]), sparse.predict(&x_test[0]));

// Check compression ratio
println!("Compression: {:.1}x", sparse.compression_ratio());

Sparse Representation:

┌─────────────────────────────────────────────────────────────────────┐
│                    DENSE (ClauseBank)                                │
├─────────────────────────────────────────────────────────────────────┤
│  Clause 0: [TA₀, TA₁, TA₂, ..., TA₂ₙ₋₁]  ← stores ALL 2N automata   │
│  Clause 1: [TA₀, TA₁, TA₂, ..., TA₂ₙ₋₁]                             │
│  ...                                                                 │
│  Memory: O(clauses × 2 × features × sizeof(i16))                     │
└─────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────┐
│                    SPARSE (SparseClauseBank) — CSR Format           │
├─────────────────────────────────────────────────────────────────────┤
│  include_indices: [0, 5, 12 | 3, 7