PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ole-Christoffer Granmo

arXiv:1804.01508v15cs.AIcs.CVcs.LG

TL;DR

Learning Automata have faced scale, representation, and vanishing signal-to-noise challenges in complex pattern recognition. The Tsetlin Machine addresses these challenges with propositional formulas formed by cooperating Tsetlin Automata and a game-theoretic learning scheme, achieving globally aligned equilibria and competitive performance across five datasets.

  • Problem

    Previous Learning Automata schemes mainly addressed small-scale tasks, had constrained pattern representations, and suffered vanishing signal-to-noise ratio as automata teams grew.

  • Method

    The Tsetlin Machine represents complex pattern recognition with propositional formulas composed by Tsetlin Automata and guides them using a game-theoretic scheme with Type I and Type II Feedback.

  • Results

    Theoretical analysis aligns Nash equilibria with formulas providing optimal pattern recognition accuracy, while evaluation on five datasets shows competitive performance against established classifiers.

  • Takeaways & Limitations

    The designed game enables millions of Tsetlin Automata to cooperate in complex pattern recognition without local optima, according to the paper's theoretical analysis.

  • Takeaways & Limitations

    Earlier Learning Automata solutions were limited to relatively small-scale tasks and constrained representations, while the formal problem assumes a specified binary input-output distribution related to n sub-patterns.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces the Tsetlin Machine, which combines Tsetlin Automata through a game-theoretic learning scheme to recognize complex patterns with propositional formulas. It targets limited pattern representation and vanishing signal-to-noise ratio while emphasizing interpretability and computational simplicity.

  • Previous Learning Automata schemes mainly addressed small-scale tasks and had limited representation capability, often restricted to linearly separable classes and simple decision trees.
  • As the number of automata grows, feedback variance increases and the signal-to-noise ratio can vanish, hindering decentralized Learning Automata.
  • The Tsetlin Machine solves complex pattern recognition problems with propositional formulas composed by a collective of Tsetlin Automata.
  • A game-theoretic learning mechanism guides the automata toward pattern recognition and is designed to address the vanishing signal-to-noise ratio problem.
  • Theoretical analysis aligns Nash equilibria of the game with propositional formulas yielding optimal pattern recognition accuracy, corresponding to learning without local optima.
  • In five datasets, the Tsetlin Machine provides competitive performance against multilayer perceptrons, SVMs, decision trees, random forests, Naive Bayes, and logistic regression.

2 The Pattern Recognition Problem

The paper formulates pattern recognition as recovering conjunctive clauses that partition a Boolean input space into sub-patterns associated with output classes. The target partition maximizes classification accuracy using samples from an unknown input-output distribution.

  • Figure 2 represents distinct sub-patterns within the input space, with patterns most likely belonging to y = 1 on the right and y = 0 on the left.
  • Inputs are Boolean vectors, and each input variable together with its negation forms a literal set from which conjunctive patterns are constructed.
  • Conjunctive clauses AND selected literals and can represent complex nonlinear patterns because propositional formulas can be rewritten in disjunctive normal form.
  • The input space is partitioned into X 1 and X 0 according to which output value has the higher posterior probability.
  • The learning problem is to recover n class-associated conjunctive clauses solely from input-output samples drawn from an unknown distribution.
  • In practice, the quantities n and s may be unknown and can be treated as hyperparameters optimized through hyperparameter search.

3 The Tsetlin Machine

The Tsetlin Machine represents complex pattern-recognition problems with conjunctive propositional clauses, whose teams are coordinated by a game optimizing accuracy through feedback and resource allocation.

  • The Tsetlin Machine decomposes problems into self-contained patterns expressed as conjunctive clauses in propositional logic.
  • Tsetlin Automata teams compose the clauses, while a coordinating game uses Type I and Type II Feedback with resource allocation dynamics.

3.1 Tsetlin Machine Inference Structure

The inference structure evaluates binary inputs with positive- and negative-polarity clauses, then combines their outputs by summation and thresholding to produce a majority-vote decision.

  • A binary input vector X is evaluated by several conjunctive clauses, with the user setting the total number of clauses.
  • Half the clauses have positive polarity and half have negative polarity, representing evidence for outputs 1 and 0 respectively.
  • Clauses without literals output 1 during learning but 0 during classification, so they can be pruned from inference after learning.
  • Clause outputs are summed and passed through a unit-step threshold, yielding a majority-vote classification; one example captures XOR.

3.2 The Tsetlin Automata Team for Composing Clauses

Each clause is composed by a team of Tsetlin Automata, with one automaton per literal deciding whether that literal is included or excluded; clause teams collectively support majority voting.

  • A clause is composed by a team of Tsetlin Automata, with one automaton assigned to each literal.
  • Each automaton’s state determines whether its assigned literal is excluded or included in the clause.
  • In the illustrated teams, automaton decisions produce conjunctive clauses with opposite polarities, and the overall output uses majority voting.

3.3 The Tsetlin Machine Game for Learning Conjunctive Clauses

The Tsetlin Machine game guides clause-building automata through feedback based on clause outputs and literal decisions, addressing vanishing signal-to-noise and steering learning toward accurate global solutions.

  • The game theoretic learning mechanism is designed to address the vanishing signal-to-noise ratio in learning automata games.
  • Because automata jointly determine clause behavior, payoff design must prevent individual decisions from disrupting clauses through contradictions.
  • Payoffs decompose clause outcomes into true positives, false negatives, and false positives, reinforcing true positives while suppressing errors.
  • Inaction leaves an automaton unchanged and extends the traditional reward-or-penalty feedback scheme.
  • Type I and Type II Feedback interact to minimize expected output error and move learning toward a global optimum.
  • Type I Feedback increases clauses correctly evaluating to 1, while Type II Feedback adds excluded zero-valued literals to combat false positives.
  • The summation target T distributes clauses across sub-patterns, while resource allocation reduces feedback intensity near that target.

T + clip

Type II feedback is generated by randomly selecting clauses whose class differs from the observed output, with its probability determined using a clipped clause-output difference.

  • The clip operation restricts the relevant sum to the interval −T to T.
  • Type II Feedback randomly selects clauses Cω where ω ≠ y.
  • The probability of Type II Feedback is computed from the clipped difference between the clause-output sum and the target threshold T.

T + clip

Feedback is reduced as clause outputs approach the target bounds, allowing well-supported clauses to stop updating and leaving automata available for other sub-patterns.

  • Feedback vanishes as the number of correctly triggering clauses approaches T or −T.
  • When the correct output is y = 1 and the clause-output sum reaches T or more, involved automata receive neither rewards nor penalties.
  • With no update applied in this situation, the Tsetlin Automata remain free to learn other sub-patterns.

3.3.6 The Tsetlin Machine Algorithm

The Tsetlin Machine learns conjunctive clauses online by coordinating teams of Tsetlin Automata, evaluating clause outputs, and applying feedback until a stopping criterion is met.

  • Clause construction: One team of Tsetlin Automata is formed for each clause, with each team containing 2^o automata assigned user-specified states.
  • Training loop: Each training example is sampled from P(X, y) and processed one at a time, enabling online learning.
  • Algorithm inputs and outputs: The algorithm takes training examples, clause count, input count, precision, and target T as input and outputs trained conjunctive clauses.
  • Clause construction: Automata choose whether to Include or Exclude assigned literals, producing clauses for predicting y.
  • Training loop: The current example is evaluated by summing clause outputs, while training omits the unit step because examples are not classified during training.
  • Feedback updates: Feedback clauses are randomly selected for Type I or Type II updates according to the clipped difference between v and T, then automata are rewarded or penalized.
  • Termination: Training repeats until a stopping criterion is fulfilled, after which clauses without literals are removed before returning the result.

3.4 Implementation Using Bitwise Operators

The Tsetlin Machine’s bitwise implementation represents automata states in parallel bit sequences, enabling fast clause computation and parallel updates while reducing memory usage.

  • Bitwise design: The architecture can be represented with bits and manipulated using bitwise operators, but automata states require a specialized representation and update procedure.
  • State representation: State indexes for all automata in a clause are stored across multiple bit sequences, with each sequence holding one bit position from every state index.
  • Bitwise computation: Automata actions are obtained directly from the most significant bit, and clause outputs are computed with NOT, AND, and CMP operations.
  • Noisy XOR representation: For Noisy XOR, a 12-bit input is extended to 24 bits by concatenating the original input with its inverse, controlling non-negated and negated literals.
  • Efficiency: Memory usage is reduced four times compared with full 32-bit integers, while customized bitwise procedures increment or decrement all automata states in parallel.
  • Deployment: After training, only the most-significant-bit sequence is needed because the remaining sequences only track learning.

4 Theoretical Analysis

The analysis models Tsetlin Machine learning as a game among literal-inclusion automata and characterizes equilibria through input-space partitions. Under noiseless and static-noise conditions, the equilibria correspond to the problem's sub-patterns, while the game also supports clause coordination and longer-horizon corrective updates.

  • Game formulation: Theoretical analysis partitions the input space into subsets to isolate how one automaton affects classification through its clause.The analysis examines both output scenarios, y = 0 and y = 1, and compares equilibrium clauses with optimal sub-patterns.
  • Game formulation: The Tsetlin Machine game has one two-action automaton per literal and clause, with Include and Exclude controlling literal membership.Training examples are sampled from P(X, y), and each payoff-matrix cell represents a joint action configuration with stochastic feedback.
  • Convergence criteria: A stable equilibrium requires each automaton action to have both the largest expected payoff and a positive expected payoff.When expected payoff is not positive, the automaton moves toward center states rather than committing to the action.
  • Nash equilibria without noise: Without noise, the pattern-recognition sub-patterns are the only Nash equilibria for the single-clause game, and every equilibrium action has positive expected payoff.The result combines convergence, equilibrium existence for sub-pattern clauses, and exclusion of clauses that deviate from all sub-patterns.
  • Nash equilibria with static noise: Under static noise with equal-sized classes, scaling the feedback parameter s by a factor t recovers equilibria corresponding to the problem's sub-patterns within a derived range.The admissible range depends on the noise level γ and parameters b1, b2, and b3.
  • Coordination of multiple teams: The coordinated multi-clause system retains the equilibrium structure, while load balancing distributes clauses among available sub-patterns when fewer clauses are available.The game matrix can reward literal updates that do not immediately change accuracy, enabling later correction of false negatives and false positives without creating additional Nash equilibria.

5 Empirical Results

Across five datasets, the Tsetlin Machine achieved competitive or leading accuracy, including robustness to noise, irrelevant features, and reduced training data. Its propositional clauses also support interpretation, while larger clause counts and summation targets improve learning at greater computational cost.

  • The evaluation covers binary Iris, binary digits, Axis & Allies, noisy XOR with non-informative features, and MNIST datasets.
  • 5.4 The Noisy XOR Dataset with Non-informative Features: On noisy XOR, the Tsetlin Machine and neural network captured the underlying XOR pattern, while Logistic Regression and Naive Bayes resorted to random guessing.SVM was distracted by the added non-informative features.
  • 5.5 The MNIST Dataset: The Tsetlin Machine’s accuracy advantage over neural networks increased with less training data, and it performed robustly with small training sets.
  • 5.5 The MNIST Dataset: More clauses and a higher summation target T increased learning speed, stability, and accuracy at the expense of greater computational cost.
  • 5.5 The MNIST Dataset: On MNIST, the Tsetlin Machine provided competitive accuracy, outperforming K-nearest neighbor and a 3-layer neural network but losing to a larger 2-layer neural network.The comparison used binarized pixel values, and improved binarization was identified as future work.

6 The Tsetlin Machine as a Building Block in More Advanced Architectures

The paper extends the Tsetlin Machine into multi-class, fully connected deep, convolutional, and recurrent architectures. These designs compose clause outputs across classes, layers, image regions, or time steps, while recurrent credit assignment remains unresolved for advanced sequential patterns.

  • 6.1 The Multi-Class Tsetlin Machine: The Multi-Class Tsetlin Machine replaces each output threshold with an argmax that selects the class having the largest clause-sum output.
  • 6.1 The Multi-Class Tsetlin Machine: Multi-class training reinforces the observed class as positive and a randomly selected alternative class as negative.
  • 6.2 The Fully Connected Deep Tsetlin Machine: The Fully Connected Deep Tsetlin Machine sequences Tsetlin Machines so clause outputs from one layer become inputs to the next, composing increasingly complex propositional formulas.
  • 6.3 The Convolutional Tsetlin Machine: The Convolutional Tsetlin Machine reuses a kernel Tsetlin Machine across image patches, then downsamples feature maps to increase clause abstraction across layers.
  • 6.4 The Recurrent Tsetlin Machine: The Recurrent Tsetlin Machine reuses one Tsetlin Machine across time steps, combining prior outputs with current inputs to form an infinitely deep sequence.Learning advanced sequential patterns requires reward and penalty propagation backward through time, which remains an open research question.

7 Conclusion and Further Work

The Tsetlin Machine coordinates large collectives of Tsetlin Automata to recognize complex patterns with propositional logic, while addressing vanishing signal-to-noise ratio through a game-theoretic mechanism. Theory and five-benchmark evaluations support global-optimum learning, competitive accuracy, computational simplicity, and interpretability, while training advanced architectures remains unresolved.

  • Contributions: The Tsetlin Machine solves vanishing signal-to-noise ratio in collectives of Tsetlin Automata, enabling coordination of millions of automata.This addresses a longstanding obstacle in scaling Learning Automata to complex pattern recognition.
  • Contributions: Teams of Tsetlin Automata express complex patterns in propositional logic and use decentralized resource allocation to capture unlabelled sub-patterns.The mechanism maximizes the effectiveness of sparse pattern-recognition capacity.
  • Theory: Nash equilibria map to propositional formulas maximizing pattern-recognition accuracy, so the learning process has no local optima, only global ones.The analysis links the game’s equilibria to accurate convergence across five diverse pattern-recognition problems.
  • Computation: Bit-pattern inputs, hidden patterns, and outputs, together with AND-, OR-, and NOT-gate manipulation, make the Tsetlin Machine computationally simple for digital computers.The representation covers all three stages: input, internal patterns, and output.
  • Evaluation: On five benchmarks, the Tsetlin Machine achieved competitive accuracy against multilayer perceptrons, SVMs, decision trees, random forests, Naive Bayes, and logistic regression.It also required less data than neural networks and outperformed Naive Bayes in data-sparse environments.
  • Further Work: The game-theoretic framework recasts pattern recognition and could support introducing other bandit algorithms into large-scale pattern recognition.The paper specifically suggests investigating Thompson Sampling and Upper Confidence Bounds as alternatives.
  • Further Work: Training methods for Fully Connected Deep, Convolution, and Recurrent Tsetlin Machine architectures remain unclear.These architectures are proposed as starting points that may improve pattern-representation compactness and learning speed.
  • Applications: High accuracy and self-contained, interpretable propositional formulas make the Tsetlin Machine attractive for applied research, including safety-critical medicine.The stated appeal combines performance with explanations that are easy to interpret.
Loading 1804.01508v15…