Tsetlin machine

A Tsetlin Machine is an 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.
As of April 2018 it has shown promising results on a number of test sets.
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 an FSM that changes its states based on the inputs. The FSM will generate its outputs based on the current states. 
formula_1
formula_4
formula_5
formula_6
formula_7
formula_8
Boolean Input.
A basic Tsetlin Machine takes a vector formula_9 of formula_10 Boolean features as input, to be classified into one of two classes, formula_11 or formula_12. Together with their negated counterparts, formula_13, the features form a literal set formula_14.
Clause Computing Module.
A Tsetlin Machine pattern is formulated as a conjunctive clause formula_15, formed by ANDing a subset formula_16 of the literal set:
formula_17.
For example, the clause formula_18 consists of the literals formula_19 and outputs formula_20 iff formula_21.
Summation and Thresholding Module.
The number of clauses employed is a user-configurable parameter formula_22. 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 formula_23:
formula_24
In other words, classification is based on a majority vote, with the positive clauses voting for formula_12 and the negative for formula_11. The classifier
formula_27,
for instance, captures the XOR-relation.
Feedback Module.
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 formula_28, the probability of reinforcing a clause gradually drops to zero as the clause output sum
formula_29
approaches a user-set target formula_30 for formula_12 (formula_32 for formula_11).
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 formula_34 equals or exceeds the target formula_30 (the Tsetlin Machine has successfully recognized the input formula_28), no clauses are reinforced. Accordingly, they are free to learn new patterns, naturally balancing the pattern representation resources.