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

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:

 A Tsetlin automaton has  states, here :

 The FSM can be triggered by two input events

 The rules of state migration of the FSM are stated as

 It includes two output actions

 Which can be generated by the algorithm

Boolean input 

A basic Tsetlin machine takes a vector  of  Boolean features as input, to be classified into one of two classes,  or . Together with their negated counterparts, , the features form a literal set .

Clause computing module 

A Tsetlin machine pattern is formulated as a conjunctive clause , formed by ANDing a subset  of the literal set:

.

For example, the clause  consists of the literals  and outputs  iff  and  .

Summation and thresholding module 

The number of clauses employed is a user-configurable parameter . 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 :

In other words, classification is based on a majority vote, with the positive clauses voting for  and the negative for . The classifier

,

for instance, captures the XOR-relation.

Feedback module

Type I feedback

Type II feedback

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 , the probability of reinforcing a clause gradually drops to zero as the clause output sum

approaches a user-set target  for  ( for ).

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  equals or exceeds the target  (the Tsetlin Machine has successfully recognized the input ), 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 

Finite automata
Classification algorithms
Logic gates