Abstract
Although simple individually, artificial neurons provide state-of-the-artperformance when interconnected in deep networks. Unknown to many, there existsan arguably even simpler and more versatile learning mechanism, namely, theTsetlin Automaton. Merely by means of a single integer as memory, it learns theoptimal action in stochastic environments through increment and decrementoperations. In this paper, we introduce the Tsetlin Machine, which solvescomplex pattern recognition problems with easy-to-interpret propositionalformulas, composed by a collective of Tsetlin Automata. To eliminate thelongstanding problem of vanishing signal-to-noise ratio, the Tsetlin Machineorchestrates the automata using a novel game. Our theoretical analysisestablishes that the Nash equilibria of the game align with the propositionalformulas that provide optimal pattern recognition accuracy. This translates tolearning without local optima, only global ones. We argue that the TsetlinMachine finds the propositional formula that provides optimal accuracy, withprobability arbitrarily close to unity. Empirically, these properties manifestas monotonically increasing mean training and test accuracy. In fivebenchmarks, the Tsetlin Machine provides competitive accuracy compared withSVMs, Decision Trees, Random Forests, Naive Bayes Classifier, LogisticRegression, and Neural Networks. The Tsetlin Machine has an inherentcomputational performance advantage since both inputs, patterns, and outputsare expressed as bits, while both recognition and learning rely on bitmanipulation. The combination of accuracy, interpretability, and computationalsimplicity makes the Tsetlin Machine a promising tool for a wide range ofdomains. Being the first of its kind, we believe the Tsetlin Machine willkick-start new paths of research, with a potentially significant impact on theAI field and the applications of AI.