An Implementation of the Context Tree Weighting (CTW) Sequence Prediction Algorithm

Related tags

Machine learning ctw
Overview

Context Tree Weighting (CTW)

CTW is a lightweight, practical and well performing sequence prediction algorithm discovered by Frans Willems, Yuri Shtarkov and Tjalling Tjalkens (1995).

It has good query and update performance (linear in the context length).

Useage

The following example demonstrates CTW learning the altenating binary sequence 101010...

"prediction: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]" assert_eq!(predictions, vec![1,0,1,0,1,0,1,0,1,0]);">
use ctw::CtwTree;
let mut rng = rand::thread_rng();
let mut tree = CtwTree::new(8); // context length is 8

let pattern = [true, false].into_iter().cycle().take(100); // true, false, true, ..
tree.update_batch(&Vec::from_iter(pattern));

let mut predictions = Vec::new();

for _ in 0..10 {
    let prediction = tree.sample(&mut rng);
    tree.update(prediction);

    // convert bool to 1 and 0 for legibility
    let bit = if prediction { 1 } else { 0 };
    predictions.push(bit);
}

println!("predictions: {predictions:?}"); // --> "prediction: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]"
assert_eq!(predictions, vec![1,0,1,0,1,0,1,0,1,0]);

Resources

  1. http://www.hutter1.net/publ/sctw.pdf
  2. https://web.stanford.edu/class/ee378a/lecture-notes/lecture_9.pdf
  3. http://www.data-compression.info/Algorithms/CTW/
  4. https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/CTW.pdf (original paper)
You might also like...
A rust library inspired by kDDBSCAN clustering algorithm
A rust library inspired by kDDBSCAN clustering algorithm

kddbscan-rs Rust implementation of the kddbscan clustering algorithm. From the authors of kDDBSCAN algorithm. Due to the adoption of global parameters

k-Medoids clustering in Rust with the FasterPAM algorithm

k-Medoids Clustering in Rust with FasterPAM This Rust crate implements k-medoids clustering with PAM. It can be used with arbitrary dissimilarites, as

Rust port of the extended isolation forest algorithm for anomaly detection

Extended Isolation Forest This is a rust port of the anomaly detection algorithm described in Extended Isolation Forest and implemented in https://git

A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the loss function.

random_search A neural network model that can approximate any non-linear function by using the random search algorithm for the optimization of the los

K-dimensional tree in Rust for fast geospatial indexing and lookup

kdtree K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup Crate Documentation Usage Benchmark License Usage Add kdtr

Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space

hwt Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space To understand how the data structure works, please see the docs

A simple neural net implementation.

PROPHET - Neural Network Library Linux Windows Codecov Coveralls Docs Crates.io A simple neural net implementation written in Rust with a focus on cac

Rust implementation of real-coded GA for solving optimization problems and training of neural networks
Rust implementation of real-coded GA for solving optimization problems and training of neural networks

revonet Rust implementation of real-coded genetic algorithm for solving optimization problems and training of neural networks. The latter is also know

Instance Distance is a fast pure-Rust implementation of the Hierarchical Navigable Small Worlds paper

Fast approximate nearest neighbor searching in Rust, based on HNSW index

Owner
null
Network-agnostic, high-level game networking library for client-side prediction and server reconciliation.

WARNING: This crate currently depends on nightly rust unstable and incomplete features. crystalorb Network-agnostic, high-level game networking librar

Ernest Wong 175 Dec 31, 2022
Nearest neighbor search algorithms including a ball tree and a vantage point tree.

petal-neighbors Nearest neighbor search algorithms including a ball tree and a vantage point tree. Examples The following example shows how to find tw

Petabi 6 Oct 19, 2022
An evaluation context for Rust.

Evcxr An evaluation context for Rust. This project consists of several related crates. evcxr_jupyter - A Jupyter Kernel evcxr_repl - A Rust REPL evcxr

Google 3.9k Dec 30, 2022
An implementation of the Pair Adjacent Violators algorithm for isotonic regression in Rust

Pair Adjacent Violators for Rust Overview An implementation of the Pair Adjacent Violators algorithm for isotonic regression. Note this algorithm is a

Ian Clarke 3 Dec 25, 2021
Rust implementation for DBSCANSD, a trajectory clustering algorithm.

DBSCANSD Rust implementation for DBSCANSD, a trajectory clustering algorithm. Brief Introduction DBSCANSD (Density-Based Spatial Clustering of Applica

Nick Gu 2 Mar 14, 2021
TopK algorithm implementation in Rust (Filtered Space-Saving)

TopK TopK algorithm implementation in Rust. This crate currently provides the Filtered Space-Saving algorithm. Version numbers follow the semver conve

null 6 Feb 24, 2023
Execute genetic algorithm (GA) simulations in a customizable and extensible way.

genevo genevo provides building blocks to run simulations of optimization and search problems using genetic algorithms (GA). The vision for genevo is

Innoave 110 Dec 21, 2022
🚀 efficient approximate nearest neighbor search algorithm collections library written in Rust 🦀 .

?? efficient approximate nearest neighbor search algorithm collections library written in Rust ?? .

Hora-Search 2.3k Jan 3, 2023
Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). LGC and CAMLP have been implemented.

label-propagation-rs Label Propagation Algorithm by Rust. Label propagation (LP) is graph-based semi-supervised learning (SSL). A simple LGC and a mor

vaaaaanquish 4 Sep 15, 2021
A naive density-based clustering algorithm written in Rust

Density-based clustering This a pure Rust implementation of a naive density-based clustering algorithm similar to DBSCAN. Here, 50 points are located

chris m 0 Mar 19, 2020