Tsetlin machine

A simple block diagram of the Tsetlin Machine

Overview

Tsetlin Machine, a state-of-the-art Artificial Intelligence algorithm based on propositional logic.

Background

A Tsetlin machine is a form of learning automaton based upon algorithms from reinforcement learning to learn expressions from propositional logic. Ole-Christoffer Granmo gave the method its name after Michael Lvovitch Tsetlin and his Tsetlin automata. The method uses computationally simpler and more efficient primitives compared to more ordinary artificial neural networks, but while the method may be faster it has a steep drop in signal-to-noise ratio as the signal space increases.[1]

As of April 2018 it has shown promising results on a number of test sets.[2][3]

Types

• Original Tsetlin Machine[1]
• Convolutional Tsetlin Machine[4]
• Weighted Tsetlin Machine[1]
• Arbitrarily Deterministic Tsetlin Machine [5]

Original Tsetlin Machine

A detailed blcok diagram of the original Tsetlin Machine

List of Hyperparameters[6]

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

Tsetlin Automaton

The Tsetlin Automaton is the fundamental 'learning unit' of the Tsetlin machine which able to store the generalized learning outcome based on the input feature. It can be seen as an FSM which changes its states based on the inputs. The FSM will generate its outputs based on the current states.

• The quintuple describes a two-action Tsetlin Automaton.

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

• The TA consists 6 states

Φ = {Φ1, Φ2, Φ3, Φ4, Φ5, Φ6}

• The FSM can be triggered by two input events

β = {β_Penalty, β_Reward}

• The rules of states migration of the FSM is stated as

${\displaystyle F(\phi _{u},\beta _{v})={\begin{cases}\phi _{u+1},&\mathbf {if} ~1\leq u\leq 3~\mathbf {and} ~v={\text{Penalty}}\\\phi _{u-1},&\mathbf {if} ~4\leq u\leq 6~\mathbf {and} ~v={\text{Penalty}}\\\phi _{u-1},&\mathbf {if} ~1<u\leq 3~\mathbf {and} ~v={\text{Reward}}\\\phi _{u+1},&\mathbf {if} ~4\leq u<6~\mathbf {and} ~v={\text{Reward}}\\\phi _{u},&\mathbf {otherwise} .\end{cases}}}$

• It includes two output actions

α = {α1, α2}

• Which can be generated by the algorithm

${\displaystyle G(\phi _{u})={\begin{cases}\alpha _{1},&\mathbf {if} ~1\leq u\leq 3\\\alpha _{2},&\mathbf {if} ~4\leq u\leq 6.\end{cases}}}$

Clauses Computing Module

${\displaystyle C_{j}^{i}=1\wedge \left(\bigwedge _{k\in I_{j}^{i}}x_{k}\right)\wedge \left(\bigwedge _{k\in {\overline {I}}_{j}^{i}}\neg x_{k}\right)}$

Summation and Threshold Module

Feedback Module

Implementations

Software

• Tsetlin Machine in C language [7], on Python[8] [9], on multithreaded Python [10]， on CUDA [11]
• Convolutional Tsetlin Machine [12][4]
• Weighted Tsetlin Machine in C++ [13]

Hardware

An overview of the Tsetlin Machine on ASIC

• The one of first FPGA-based hardware implementation[14][15] of the Tsetlin Machine on Iris dataset had developed by µSystems (microSystems) Research Group at Newcastle University.
• They also presented the first ASIC [16] [17]implementation of the Tsetlin Machine focusing energy frugality, claims it could deliver 10 trillion operation per Joule[18]. The ASIC design had demoed on DATA2020 [19].

Additional Read

Videos

• Tsetlin Machine -- A new paradigm for pervasive AI [19]
• IOLTS Presentation: Explainability and Dependability Analysis of Learning Automata based AI hardware [20]
• FPGA and uC co-design: Tsetlin Machine on Iris demo [14][15]
• The-Ruler-of-Tsetlin-Automaton [21]
• Interpretable clustering and dimension reduction with Tsetlin automata machine learning. [22]
• Predicting and explaining economic growth using real-time interpretable learning [23]
• Early detection of breast cancer from a simple blood test[24]
• Recent advances in Tsetlin Machines [25]

Papers

• Learning Automata based Energy-efficient AI Hardware Design for IoT Applications [6]

Publications/News/Articles

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

Partners

• 
  The Centre for Artificial Intelligence Research (CAIR) at the University of Agder https://twitter.com/CairEnglish https://cair.uia.no/about-cair/
• 
  uSystems Research Group at Newcastle University https://twitter.com/nclmicrosystems https://www.ncl.ac.uk/engineering/research/eee/microsystems/

Gallery

References

1. Granmo, Ole-Christoffer (2018-04-04). "The Tsetlin Machine - A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic". arXiv:1804.01508 [cs.AI].
2. Christiansen, Atle. "The Tsetlin Machine outperforms neural networks - Center for Artificial Intelligence Research". cair.uia.no. Retrieved 2018-05-03.
3. Øyvann, Stig. "AI-gjennombrudd i Agder | Computerworld". Computerworld (in Norwegian). Retrieved 2018-05-04.
4. Granmo, Ole-Christoffer; Glimsdal, Sondre; Jiao, Lei; Goodwin, Morten; Omlin, Christian W.; Berge, Geir Thore (2019-12-27). "The Convolutional Tsetlin Machine". arXiv:1905.09688 [cs, stat].
5. Abeyrathna, K. Darshana; Granmo, Ole-Christoffer; Shafik, Rishad; Yakovlev, Alex; Wheeldon, Adrian; Lei, Jie; Goodwin, Morten (2020-07-04). "A Novel Multi-Step Finite-State Automaton for Arbitrarily Deterministic Tsetlin Machine Learning". arXiv:2007.02114 [cs].
6. Wheeldon, A.; Shafik, R.; Rahman, T.; Lei, J.; Yakovlev, A.; Granmo, O. C. (2020). "Learning Automata based Energy-efficient AI Hardware Design for IoT Applications". Philosophical Transactions of the Royal Society A.
7. cair/TsetlinMachineC, Centre for Artificial Intelligence Research (CAIR), 2019-04-18, retrieved 2020-07-27
8. cair/pyTsetlinMachine, Centre for Artificial Intelligence Research (CAIR), 2020-07-07, retrieved 2020-07-27
9. cair/TsetlinMachine, Centre for Artificial Intelligence Research (CAIR), 2020-07-27, retrieved 2020-07-27
10. cair/pyTsetlinMachineParallel, Centre for Artificial Intelligence Research (CAIR), 2020-07-07, retrieved 2020-07-27
11. cair/PyTsetlinMachineCUDA, Centre for Artificial Intelligence Research (CAIR), 2020-07-27, retrieved 2020-07-27
12. "cair/convolutional-tsetlin-machine-tutorial". GitHub. Retrieved 2020-07-27.
13. Phoulady, Adrian (2020-04-13), adrianphoulady/weighted-tsetlin-machine-cpp, retrieved 2020-07-27
14. JieGH (2020-03-22), JieGH/Hardware_TM_Demo, retrieved 2020-07-22
15. JieGH. "Tsetlin Machine on Iris Data Set Demo, Handheld #MignonAI". Youtube.
16. "https://twitter.com/olegranmo/status/1279045633916182528". Twitter. Retrieved 2020-07-27. External link in |title= (help)
17. "mignon". www.mignon.ai. Retrieved 2020-07-27.
18. Bush, Steve (2020-07-27). "A low-power AI alternative to neural networks". Electronics Weekly. Retrieved 2020-07-27.
19. "Tsetlin Machine -- A new paradigm for pervasive AI".
20. "IOLTS Presentation: Explainability and Dependability Analysis of Learning Automata based AI hardware".
21. "The-Ruler-of-Tsetlin-Automaton".
22. "Interpretable Clustering & Dimension Reduction with Tsetlin Automata machine learning".
23. "Predicting and explaining economic growth using real-time interpretable learning".
24. "Early detection of breast cancer from a simple blood test".
25. "Recent advances in Tsetlin Machines".
26. Bush, Steve (2020-07-27). "A low-power AI alternative to neural networks". Electronics Weekly. Retrieved 2020-07-27.