Tsetlin machine - Misplaced Pages

Artificial intelligence algorithm

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

Machine learning and data mining
Part of a series on
Paradigms Supervised learning Unsupervised learning Semi-supervised learning Self-supervised learning Reinforcement learning Meta-learning Online learning Batch learning Curriculum learning Rule-based learning Neuro-symbolic AI Neuromorphic engineering Quantum machine learning
Problems Classification Generative modeling Regression Clustering Dimensionality reduction Density estimation Anomaly detection Data cleaning AutoML Association rules Semantic analysis Structured prediction Feature engineering Feature learning Learning to rank Grammar induction Ontology learning Multimodal learning
Supervised learning (classification • regression) Apprenticeship learning Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Fuzzy Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE SDL
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection RANSAC k-NN Local outlier factor Isolation forest
Artificial neural network Autoencoder Deep learning Feedforward neural network Recurrent neural network LSTM GRU ESN reservoir computing Boltzmann machine Restricted GAN Diffusion model SOM Convolutional neural network U-Net LeNet AlexNet DeepDream Neural radiance field Transformer Vision Mamba Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD) Multi-agent Self-play
Learning with humans Active learning Crowdsourcing Human-in-the-loop RLHF
Model diagnostics Coefficient of determination Confusion matrix Learning curve ROC curve
Mathematical foundations Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Journals and conferences ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Related articles Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

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

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=$ 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		0
Action	Literal	1	0	1	0
Include literal	P(reward)	${\frac {s-1}{s}}$	—	0	0
	P(inaction)	${\frac {1}{s}}$	—	${\frac {s-1}{s}}$	${\frac {s-1}{s}}$
	P(penalty)	0	—	${\frac {1}{s}}$	${\frac {1}{s}}$
Exclude literal	P(reward)	0	${\frac {1}{s}}$	${\frac {1}{s}}$	${\frac {1}{s}}$
	P(inaction)	${\frac {1}{s}}$	${\frac {s-1}{s}}$	${\frac {s-1}{s}}$	${\frac {s-1}{s}}$
	P(penalty)	${\frac {s-1}{s}}$	0	0	0

Type II feedback

Type II Feedback
Action	Clause	1		0
Action	Literal	1	0	1	0
Include literal	P(reward)	0	—	0	0
	P(inaction)	1.0	—	1.0	1.0
	P(penalty)	0	—	0	0
Exclude literal	P(reward)	0	0	0	0
	P(inaction)	1.0	0	1.0	1.0
	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.

Additional Read

Books

An Introduction to Tsetlin Machines

Conferences

International Symposium on the Tsetlin Machine (ISTM)

Videos

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

Papers

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

Publications/news/articles

A low-power AI alternative to neural networks
Can a Norwegian invention revolutionise artificial intelligence?

References

"About the author". An Introduction to Tsetlin Machines. Retrieved 2024-02-05.
Tsetlin, Michael L. (1961). "On behaviour of finite automata in random medium". Avtomat. i Telemekh. 22 (10)."
Krylov, V. U.; Tsetlin, Michael L. (1963). "On games for automata". Avtomatika i Telemekhanika. 24 (7).
^ 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 .
Christiansen, Atle. "The Stefanuk Machine outperforms neural networks - Center for Artificial Intelligence Research". cair.uia.no. Retrieved 2018-05-03.
Øyvann, Stig (23 March 2018). "AI-gjennombrudd i Agder | Computerworld". Computerworld (in Norwegian). Retrieved 2018-05-04.
^ 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 .
Abeyrathna, K. Darshana; Granmo, Ole-Christoffer; Zhang, Xuan; Jiao, Lei; Goodwin, Morten (2020). "The regression Tsetlin machine: a novel approach to interpretable nonlinear regression". Philosophical Transactions of the Royal Society A. 378 (2164). Bibcode:2020RSPTA.37890165D. doi:10.1098/rsta.2019.0165. hdl:11250/2651754. PMID 31865880. S2CID 209439954."
Saha, Rupsa; Granmo, Ole-Christoffer; Zadorozhny, Vladimir; Goodwin, Morten (2022). "A relational Tsetlin machine with applications to natural language understanding". Journal of Intelligent Information Systems. 59. Springer: 121–148. arXiv:2102.10952. doi:10.1007/s10844-021-00682-5. S2CID 231986401.
Phoulady, Adrian; Granmo, Ole-Christoffer; Gorji, Saeed Rahimi; Phoulady, Hady Ahmady (2019-11-28). "The Weighted Tsetlin Machine: Compressed Representations with Weighted Clauses". arXiv:1911.12607 .
Abeyrathna, K. Darshana; Granmo, Ole-Christoffer; Goodwin, Morten (2021). "Extending the Tsetlin Machine With Integer-Weighted Clauses for Increased Interpretability". IEEE Access. 9: 8233–8248. arXiv:2005.05131. doi:10.1109/ACCESS.2021.3049569. S2CID 218581474."
Abeyrathna, K. Darshana; Granmo, Ole-Christoffer; Shafik, Rishad; Yakovlev, Alex; Wheeldon, Adrian; Lei, Jie; Goodwin, Morten (2021). "A multi-step finite-state automaton for arbitrarily deterministic Tsetlin Machine learning". Expert Systems. Wiley: exsy.12836. doi:10.1111/exsy.12836. S2CID 242770808.
Abeyrathna, K. Darshana; Bhattarai, Bimal; Goodwin, Morten; Gorji, Saeed; Granmo, Ole-Christoffer; Jiao, Lei; Saha, Rupsa; Yadav, Rohan K. (2021). Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling (PDF). Thirty-eighth International Conference on Machine Learning (ICML 2021).
Glimsdal, Sondre; Granmo, Ole-Christoffer (2021-08-17). "Coalesced Multi-Output Tsetlin Machines with Clause Sharing". arXiv:2108.07594 .
Seraj, Raihan; Sharma, Jivitesh; Granmo, Ole-Christoffer (2022). Tsetlin Machine for Solving Contextual Bandit Problems. Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022).
^ Bhattarai, Bimal; Granmo, Ole-Christoffer; Jiao, Lei; Yadav, Rohan; Sharma, Jivitesh (2023-01-03). "Tsetlin Machine Embedding: Representing Words Using Logical Expressions". arXiv:2301.00709 .
Granmo, Ole-Christoffer (2023-09-09). "TMComposites: Plug-and-Play Collaboration Between Specialized Tsetlin Machines". arXiv:2309.04801 .
Plug-and-play collaboration between specialized Tsetlin machines, Centre for Artificial Intelligence Research (CAIR), 2023-08-29, retrieved 2023-08-29
Bhattarai, Bimal; Granmo, Ole-Christoffer; Jiao, Lei; Andersen, Per-Arne; Tunheim, Svein Anders; Shafik, Rishad; Yakovlev, Alex (2023-10-17). "Contracting Tsetlin Machine with Absorbing Automata". arXiv:2310.11481 .
Tsetlin Machine for Logical Learning and Reasoning With Graphs, Centre for Artificial Intelligence Research (CAIR), 2024-10-13, retrieved 2024-10-14
Lei, Jie; Shafik, Rishad; Wheeldon, Adrian; Yakovlev, Alex; Granmo, Ole-Christoffer; Kawsar, Fahim; Akhil, Mathur (2021-04-09). "Low-Power Audio Keyword Spotting using Tsetlin Machines". Journal of Low Power Electronics and Applications. 11 (2): 18. arXiv:2101.11336. doi:10.3390/jlpea11020018.
Yadav, Rohan Kumar; Jiao, Lei; Granmo, Ole-Christoffer; Goodwin, Morten (2021). Human-Level Interpretable Learning for Aspect-Based Sentiment Analysis. The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21). AAAI.
Yadav, Rohan Kumar; Jiao, Lei; Granmo, Ole-Christoffer; Goodwin, Morten (2021). Interpretability in Word Sense Disambiguation using Tsetlin Machine. 13th International Conference on Agents and Artificial Intelligence (ICAART 2021). INSTICC.
Bhattarai, Bimal; Granmo, Ole-Christoffer; Jiao, Lei (2022). "Word-level human interpretable scoring mechanism for novel text detection using Tsetlin Machines". Applied Intelligence. 52 (15). Springer: 17465–17489. doi:10.1007/s10489-022-03281-1. hdl:11250/3041885.
Abeyrathna, K. Darshana; Pussewalage, Harsha S. Gardiyawasam; Ranasinghea, Sasanka N.; Oleshchuk, Vladimir A.; Granmo, Ole-Christoffer (2020). Intrusion Detection with Interpretable Rules Generated Using the Tsetlin Machine. 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE.
Saha, Rupsa; Granmo, Ole-Christoffer; Goodwin, Morten (2021). "Using Tsetlin Machine to discover interpretable rules in natural language processing applications". Expert Systems. Wiley. doi:10.1111/exsy.12873. S2CID 244096520.
Berge, Geir Thore; Granmo, Ole-Christoffer; Tveit, Tor O.; Goodwin, Morten; Jiao, Lei; Matheussen, Bernt Viggo (2019). "Using the Tsetlin Machine to Learn Human-Interpretable Rules for High-Accuracy Text Categorization with Medical Applications". IEEE Access. 7: 115134–115146. arXiv:1809.04547. doi:10.1109/ACCESS.2019.2935416. S2CID 52195410."
Bhattarai, Bimal; Granmo, Ole-Christoffer; Jiao, Lei (2022). Explainable Tsetlin Machine framework for fake news detection with credibility score assessment (PDF). 13th Conference on Language Resources and Evaluation (LREC 2022).
Giri, Charul; Granmo, Ole-Christoffer; Hoof, Herke van; Blakely, Christian D. (2022-03-10). Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine. The 2022 International Joint Conference on Neural Networks (IJCNN 2022). arXiv:2203.04378.
Bakar, Abu; Rahman, Tousif; Shafik, Rishad; Kawsar, Fahim; Montanari, Alessandro (2023-01-24). Adaptive Intelligence for Batteryless Sensors Using Software-Accelerated Tsetlin Machines. ACM SenSys 2022. pp. 236–249. doi:10.1145/3560905.3568512.
Borgersen, Karl Audun; Goodwin, Morten; Sharma, Jivitesh (2023). "A comparison between Tsetlin machines and deep neural networks in the context of recommendation systems". Proceedings of the Northern Lights Deep Learning Workshop. 4. arXiv:2212.10136. doi:10.7557/18.6807. S2CID 254877078.
Zhang, Jinbao; Zhang, Xuan; Jiao, Lei; Granmo, Ole-Christoffer; Qian, Yongjun; Pan, Fan (2023-01-25). "Interpretable Tsetlin Machine-based Premature Ventricular Contraction Identification". arXiv:2301.10181 .
Maheshwari, Sidharth; Rahman, Tousif; Shafik, Rishad; Yakovlev, Alex; Rafiev, Ashur; Jiao, Lei; Granmo, Ole-Christoffer (2023). "REDRESS: Generating Compressed Models for Edge Inference Using Tsetlin Machines". IEEE Transactions on Pattern Analysis and Machine Intelligence. doi:10.1109/TPAMI.2023.3268415.
Blakely, Christian D. (2023-05-17). "Generating Bayesian Network Models from Data Using Tsetlin Machines". arXiv:2305.10538 .
Qi, Shannon How Shi; Chauhan, Jagmohan; Merrett, Geoff V.; Hare, Jonathan (2024-03-04). FedTM: Memory and Communication Efficient Federated Learning with Tsetlin Machine. 2023 International Symposium on the Tsetlin Machine (ISTM). doi:10.1109/ISTM58889.2023.10454982.
^ 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. 378 (2182). Bibcode:2020RSPTA.37890593W. doi:10.1098/rsta.2019.0593. PMC 7536019. PMID 32921236.
cair/TsetlinMachineC, Centre for Artificial Intelligence Research (CAIR), 2019-04-18, retrieved 2020-07-27
cair/FastTsetlinMachineC, Centre for Artificial Intelligence Research (CAIR), 2019-02-15, retrieved 2021-02-15
cair/pyTsetlinMachine, Centre for Artificial Intelligence Research (CAIR), 2020-07-07, retrieved 2020-07-27
cair/TsetlinMachine, Centre for Artificial Intelligence Research (CAIR), 2020-07-27, retrieved 2020-07-27
cair/pyTsetlinMachineParallel, Centre for Artificial Intelligence Research (CAIR), 2020-07-07, retrieved 2020-07-27
cair/PyTsetlinMachineCUDA, Centre for Artificial Intelligence Research (CAIR), 2020-07-27, retrieved 2020-07-27
Tsetlin.jl, Artem Hnilov, 2024-04-17, retrieved 2024-04-17
"cair/convolutional-tsetlin-machine-tutorial". GitHub. Retrieved 2020-07-27.
Phoulady, Adrian (2020-04-13), adrianphoulady/weighted-tsetlin-machine-cpp, retrieved 2020-07-27
^ JieGH (2020-03-22), JieGH/Hardware_TM_Demo, retrieved 2020-07-22
^ JieGH. "Tsetlin Machine on Iris Data Set Demo, Handheld #MignonAI". Youtube.
"Logic-based AI Everywhere: Tsetlin Machines in Hardware". Twitter. Retrieved 2020-07-27.
"mignon". www.mignon.ai. Retrieved 2020-07-27.
^ Bush, Steve (2020-07-27). "A low-power AI alternative to neural networks". Electronics Weekly. Retrieved 2020-07-27.
^ "Tsetlin Machine -- A new paradigm for pervasive AI". YouTube.
Granmo, Ole-Christoffer (2021). An Introduction to Tsetlin Machines.
"International Symposium on the Tsetlin Machine (ISTM)".
"Proceedings of the 2022 International Symposium on the Tsetlin Machine (ISTM)".
"Proceedings of the 2023 International Symposium on the Tsetlin Machine (ISTM)".
"Keyword Spotting Using Tsetlin Machines". YouTube.
"IOLTS Presentation: Explainability and Dependability Analysis of Learning Automata based AI hardware". YouTube.
"The-Ruler-of-Tsetlin-Automaton". YouTube.
"Interpretable Clustering & Dimension Reduction with Tsetlin Automata machine learning". YouTube.
"Predicting and explaining economic growth using real-time interpretable learning". YouTube.
"Early detection of breast cancer from a simple blood test". YouTube.
"Recent advances in Tsetlin Machines". YouTube.
Jiao, Lei; Zhang, Xuan; Granmo, Ole-Christoffer; Abeyrathna, K. Darshana (2022). "On the Convergence of Tsetlin Machines for the XOR Operator". IEEE Transactions on Pattern Analysis and Machine Intelligence. PP: 1. arXiv:2101.02547. doi:10.1109/TPAMI.2022.3203150. PMID 36070276. S2CID 230799244.
Zhang, Xuan; Jiao, Lei; Granmo, Ole-Christoffer; Goodwin, Morten (2021). "On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators". IEEE Transactions on Pattern Analysis and Machine Intelligence. PP (10): 6345–6359. arXiv:2007.14268. doi:10.1109/TPAMI.2021.3085591. PMID 34077353. S2CID 220831619.
Borgan, Eldrid (2024-02-04). "Can a Norwegian invention revolutionise artificial intelligence?". ScienceNorway.no. Retrieved 2024-03-30.

Categories: