The Tsetlin Machine -- A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic

Abstract

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.

42 pages, 14 figures, further formalizing key concepts

References in corpus (3)

• Deep Learning in Neural Networks: An Overview
• The Convolutional Tsetlin Machine
• Interpretable Two-level Boolean Rule Learning for Classification

Cited by in corpus (15)

• The Convolutional Tsetlin Machine
• On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators
• Explainable Tsetlin Machine framework for fake news detection with credibility score assessment
• Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling
• Coalesced Multi-Output Tsetlin Machines with Clause Sharing
• Closed-Form Expressions for Global and Local Interpretation of Tsetlin Machines with Applications to Explaining High-Dimensional Data
• A Regression Tsetlin Machine with Integer Weighted Clauses for Compact Pattern Representation
• A Comparison Between Tsetlin Machines and Deep Neural Networks in the Context of Recommendation Systems
• The Weighted Tsetlin Machine: Compressed Representations with Weighted Clauses
• Measuring the Novelty of Natural Language Text Using the Conjunctive Clauses of a Tsetlin Machine Text Classifier
• Low-Power Audio Keyword Spotting using Tsetlin Machines
• On the Convergence of Tsetlin Machines for the AND and the OR Operators
• Towards Coinductive Models for Natural Language Understanding. Bringing together Deep Learning and Deep Semantics
• On the Complexity of Learning Description Logic Ontologies
• Enhancing Interpretable Clauses Semantically using Pretrained Word Representation