# Tsetlin machine

A Tsetlin machine is an artificial intelligence algorithm based on propositional logic.

## Background

A Tsetlin machine is a form of learning automaton collective for learning patterns using propositional logic. Ole-Christoffer Granmo created and gave the method its name after Michael Lvovitch Tsetlin, who invented the Tsetlin automaton and worked on Tsetlin automata collectives and games. Collectives of Tsetlin automata were originally constructed, implemented, and studied theoretically by Vadim Stefanuk in 1962.
The Tsetlin machine uses computationally simpler and more efficient primitives compared to more ordinary artificial neural networks.
As of April 2018 it has shown promising results on a number of test sets.

## Types

* Original Tsetlin machine
* Convolutional Tsetlin machine
* Regression Tsetlin machine
* Relational Tsetlin machine
* Weighted Tsetlin machine
* Arbitrarily deterministic Tsetlin machine
* Parallel asynchronous Tsetlin machine
* Coalesced multi-output Tsetlin machine
* Tsetlin machine for contextual bandit problems
* Tsetlin machine autoencoder
* Tsetlin machine composites: plug-and-play collaboration between specialized Tsetlin machines
* Contracting Tsetlin machine with absorbing automata
* Graph Tsetlin machine

## Applications

* Keyword spotting
* Aspect-based sentiment analysis
* Word-sense disambiguation
* Novelty detection
* Intrusion detection
* Semantic relation analysis
* Image analysis
* Text categorization
* Fake news detection
* Game playing
* Batteryless sensing
* Recommendation systems
* Word embedding
* ECG analysis
* Edge computing
* Bayesian network learning
* Federated learning

## Original Tsetlin machine

List of hyperparameters :
| Description | Symbol |
| Number of binary inputs | $N_{\text{Inputs}}$ |
| Number of classes | $N_{\text{Classes}}$ |
| Number of clauses per class | $N_{\text{Clauses}}$ |
| Number of automaton states | $2n$ |
| Automaton decision boundary | n |
| Automaton initialization state | $\varnothing _{\text{Init}}$ |
| Feedback threshold | T |
| Learning sensitivity | s |

### Tsetlin automaton

The Tsetlin automaton is the fundamental learning unit of the Tsetlin machine. It tackles the multi-armed bandit problem, learning the optimal action in an environment from penalties and rewards. Computationally, it can be seen as a finite-state machine (FSM) that changes its states based on the inputs. The FSM will generate its outputs based on the current states.
* A quintuple describes a two-action Tsetlin automaton:
$\{{\underline {\Phi }},{\underline {\alpha }},{\underline {\beta }},F(\cdot ,\cdot ),G(\cdot )\}.$
* A Tsetlin automaton has $2n$ states, here 6:
${\underline {\Phi }}=\{\phi _{1},\phi _{2},\phi _{3},\phi _{4},\phi _{5},\phi _{6}\}$
* The FSM can be triggered by two input events
${\underline {\beta }}=\{\beta _{\mathrm {Penalty} },\beta _{\mathrm {Reward} }\}$
* The rules of state migration of the FSM are stated as
$F(\phi _{u},\beta _{v})={\begin{cases}\phi _{u+1},&{\text{if}}~1\leq u\leq 3~{\text{and}}~v={\text{Penalty}}\\\phi _{u-1},&{\text{if}}~4\leq u\leq 6~{\text{and}}~v={\text{Penalty}}\\\phi _{u-1},&{\text{if}}~1<u\leq 3~{\text{and}}~v={\text{Reward}}\\\phi _{u+1},&{\text{if}}~4\leq u<6~{\text{and}}~v={\text{Reward}}\\\phi _{u},&{\text{otherwise}}.\end{cases}}$
* It includes two output actions
${\underline {\alpha }}=\{\alpha _{1},\alpha _{2}\}$
* Which can be generated by the algorithm
$G(\phi _{u})={\begin{cases}\alpha _{1},&{\text{if}}~1\leq u\leq 3\\\alpha _{2},&{\text{if}}~4\leq u\leq 6.\end{cases}}$

### Boolean input

A basic Tsetlin machine takes a vector $X=[x_{1},\ldots ,x_{o}]$ of o Boolean features as input, to be classified into one of two classes, $y=0$ or $y=1$. Together with their negated counterparts, ${\bar {x}}_{k}={\lnot }{x}_{k}=1-x_{k}$, the features form a literal set $L=\{x_{1},\ldots ,x_{o},{\bar {x}}_{1},\ldots ,{\bar {x}}_{o}\}$.

### Clause computing module

A Tsetlin machine pattern is formulated as a conjunctive clause $C_{j}$, formed by ANDing a subset $L_{j}{\subseteq }L$ of the literal set:
$C_{j}(X)=\bigwedge _{{l}{\in }L_{j}}l=\prod _{{l}{\in }L_{j}}l$.
For example, the clause $C_{j}(X)=x_{1}\land {\lnot }x_{2}=x_{1}{\bar {x}}_{2}$ consists of the literals $L_{j}=\{x_{1},{\bar {x}}_{2}\}$ and outputs 1 iff $x_{1}=1$ and $x_{2}=0$.

### Summation and thresholding module

The number of clauses employed is a user-configurable parameter n. Half of the clauses are assigned positive polarity. The other half is assigned negative polarity. The clause outputs, in turn, are combined into a classification decision through summation and thresholding using the unit step function $u(v)=1~{\text{if}}~v\geq 0~{\text{else}}~0$:
${\hat {y}}=u\left(\sum _{j=1}^{n/2}C_{j}^{+}(X)-\sum _{j=1}^{n/2}C_{j}^{-}(X)\right).$ In other words, classification is based on a majority vote, with the positive clauses voting for $y=1$ and the negative for $y=0$. The classifier
${\hat {y}}=u\left(x_{1}{\bar {x}}_{2}+{\bar {x}}_{1}x_{2}-x_{1}x_{2}-{\bar {x}}_{1}{\bar {x}}_{2}\right)$,
for instance, captures the XOR-relation.

### Feedback module
#### Type I feedback

Type I Feedback :
| Action | Clause | 1 | 1 | 0 | 0 |
| Action | Literal | 1 | 0 | 1 | 0 |
| Include literal | P(reward) | ${\frac {s-1}{s}}$ | — | 0 | 0 |
| Include literal | P(inaction) | ${\frac {1}{s}}$ | — | ${\frac {s-1}{s}}$ | ${\frac {s-1}{s}}$ |
| Include literal | P(penalty) | 0 | — | ${\frac {1}{s}}$ | ${\frac {1}{s}}$ |
| Exclude literal | P(reward) | 0 | ${\frac {1}{s}}$ | ${\frac {1}{s}}$ | ${\frac {1}{s}}$ |
| Exclude literal | P(inaction) | ${\frac {1}{s}}$ | ${\frac {s-1}{s}}$ | ${\frac {s-1}{s}}$ | ${\frac {s-1}{s}}$ |
| Exclude literal | P(penalty) | ${\frac {s-1}{s}}$ | 0 | 0 | 0 |

#### Type II feedback

Type II Feedback :
| Action | Clause | 1 | 1 | 0 | 0 |
| Action | Literal | 1 | 0 | 1 | 0 |
| Include literal | P(reward) | 0 | — | 0 | 0 |
| Include literal | P(inaction) | 1.0 | — | 1.0 | 1.0 |
| Include literal | P(penalty) | 0 | — | 0 | 0 |
| Exclude literal | P(reward) | 0 | 0 | 0 | 0 |
| Exclude literal | P(inaction) | 1.0 | 0 | 1.0 | 1.0 |
| Exclude literal | P(penalty) | 0 | 1.0 | 0 | 0 |

#### Resource allocation

Resource allocation dynamics ensure that clauses distribute themselves across the frequent patterns, rather than missing some and overconcentrating on others. That is, for any input X, the probability of reinforcing a clause gradually drops to zero as the clause output sum
$v=\sum _{j=1}^{n/2}C_{j}^{+}(X)-\sum _{j=1}^{n/2}C_{j}^{-}(X)$ approaches a user-set target T for $y=1$ ($-T$ for $y=0$).
If a clause is not reinforced, it does not give feedback to its Tsetlin automata, and these are thus left unchanged. In the extreme, when the voting sum v equals or exceeds the target T (the Tsetlin Machine has successfully recognized the input X), no clauses are reinforced. Accordingly, they are free to learn new patterns, naturally balancing the pattern representation resources.

## Implementations
### Software

* Tsetlin Machine in C, Python, multithreaded Python, CUDA, Julia (programming language)
* Convolutional Tsetlin Machine
* Weighted Tsetlin Machine in C++

### Hardware

* One of the first FPGA-based hardware implementation of the Tsetlin Machine on the Iris flower data set was developed by the μSystems (microSystems) Research Group at Newcastle University.
* They also presented the first ASIC implementation of the Tsetlin Machine focusing on energy frugality, claiming it could deliver 10 trillion operation per Joule. The ASIC design had demoed on DATA2020.