Tsetlin machine

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:

$${\displaystyle \{{\underline {\Phi }},{\underline {\alpha }},{\underline {\beta }},F(\cdot ,\cdot ),G(\cdot )\}.}$$

• A Tsetlin automaton has ${\displaystyle 2n}$ states, here 6:

$${\displaystyle {\underline {\Phi }}=\{\phi _{1},\phi _{2},\phi _{3},\phi _{4},\phi _{5},\phi _{6}\}}$$

• The FSM can be triggered by two input events

$${\displaystyle {\underline {\beta }}=\{\beta _{\mathrm {Penalty} },\beta _{\mathrm {Reward} }\}}$$

• The rules of state migration of the FSM are stated as

$${\displaystyle 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

$${\displaystyle {\underline {\alpha }}=\{\alpha _{1},\alpha _{2}\}}$$

• Which can be generated by the algorithm

$${\displaystyle 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}}}$$

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

A Tsetlin machine pattern is formulated as a conjunctive clause ${\displaystyle C_{j}}$, formed by ANDing a subset ${\displaystyle L_{j}{\subseteq }L}$ of the literal set:

     ${\displaystyle C_{j}(X)=\bigwedge _{{l}{\in }L_{j}}l=\prod _{{l}{\in }L_{j}}l}$.

For example, the clause ${\displaystyle C_{j}(X)=x_{1}\land {\lnot }x_{2}=x_{1}{\bar {x}}_{2}}$ consists of the literals ${\displaystyle L_{j}=\{x_{1},{\bar {x}}_{2}\}}$ and outputs 1 iff ${\displaystyle x_{1}=1}$ and ${\displaystyle x_{2}=0}$.

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 ${\displaystyle u(v)=1~{\text{if}}~v\geq 0~{\text{else}}~0}$:

$${\displaystyle {\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 ${\displaystyle y=1}$ and the negative for ${\displaystyle y=0}$. The classifier

     ${\displaystyle {\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.

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

$${\displaystyle v=\sum _{j=1}^{n/2}C_{j}^{+}(X)-\sum _{j=1}^{n/2}C_{j}^{-}(X)}$$

approaches a user-set target T for ${\displaystyle y=1}$ (${\displaystyle -T}$ for ${\displaystyle 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.

• Tsetlin Machine in C,[31][32] Python,[33][34] multithreaded Python,[35] CUDA[36]
• Convolutional Tsetlin Machine [37][4]
• Weighted Tsetlin Machine in C++[38]

• One of the first FPGA-based hardware implementation[39][40] of the Tsetlin Machine on the Iris dataset was developed by the µSystems (microSystems) Research Group at Newcastle University.
• They also presented the first ASIC[41][42] implementation of the Tsetlin Machine focusing on energy frugality, claiming it could deliver 10 trillion operation per Joule.[43] The ASIC design had demoed on DATA2020.[44]

• An Introduction to Tsetlin Machines [45]

• International Symposium on the Tsetlin Machine (ISTM) [46][47]

• Tsetlin Machine—A new paradigm for pervasive AI[44]
• Keyword Spotting Using Tsetlin Machines [48]
• IOLTS Presentation: Explainability and Dependability Analysis of Learning Automata based AI hardware [49]
• FPGA and uC co-design: Tsetlin Machine on Iris demo [39][40]
• The-Ruler-of-Tsetlin-Automaton [50]
• Interpretable clustering and dimension reduction with Tsetlin automata machine learning.[51]
• Predicting and explaining economic growth using real-time interpretable learning [52]
• Early detection of breast cancer from a simple blood test[53]
• Recent advances in Tsetlin Machines [54]

• On the Convergence of Tsetlin Machines for the XOR Operator [55]
• Learning Automata based Energy-efficient AI Hardware Design for IoT Applications [30]
• On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators [56]
• The Tsetlin Machine - A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic [1]

• A low-power AI alternative to neural networks [43]