The Tsetlin Machine -- A Game Theoretic Bandit Driven Approach to
  Optimal Pattern Recognition with Propositional Logic
  Although simple individually, artificial neurons provide state-of-the-art
performance when interconnected in deep networks. Arguably, the Tsetlin
Automaton is an even simpler and more versatile learning mechanism, capable of
solving the multi-armed bandit problem. Merely by means of a single integer as
memory, it learns the optimal action in stochastic environments through
increment and decrement operations. In this paper, we introduce the Tsetlin
Machine, which solves complex pattern recognition problems with propositional
formulas, composed by a collective of Tsetlin Automata. To eliminate the
longstanding problem of vanishing signal-to-noise ratio, the Tsetlin Machine
orchestrates the automata using a novel game. Further, both inputs, patterns,
and outputs are expressed as bits, while recognition and learning rely on bit
manipulation, simplifying computation. Our theoretical analysis establishes
that the Nash equilibria of the game align with the propositional formulas that
provide optimal pattern recognition accuracy. This translates to learning
without local optima, only global ones. In five benchmarks, the Tsetlin Machine
provides competitive accuracy compared with SVMs, Decision Trees, Random
Forests, Naive Bayes Classifier, Logistic Regression, and Neural Networks. We
further demonstrate how the propositional formulas facilitate interpretation.
In conclusion, we believe the combination of high accuracy, interpretability,
and computational simplicity makes the Tsetlin Machine a promising tool for a
wide range of domains.
