On the Convergence of Tsetlin Machines for the AND and the OR Operators

Lei Jiao, Lei Jiao 0001, Xuan Zhang, Ole-Christoffer GranmoarXiv 2021 · arXiv

Abstract

Tsetlin Machines (TMs) represent a paradigm shift in machine learning, utilizing propositional logic and finite-state machines instead of continuous weights. While empirically successful, their theoretical guarantees have been a work in progress. This paper provides the rigorous mathematical proof that TMs will almost surely converge when learning the fundamental Boolean AND and OR operators. By completing the convergence analysis for all basic digital operators, this work solidifies the mathematical foundation of Tsetlin Machines as a robust alternative to neural networks.

Introduction: The Interpretability Challenge

Deep neural networks are powerful but often function as "black boxes," making their decision-making processes opaque. Tsetlin Machines (TMs) address this by using groups of finite-state machines, known as Tsetlin Automata (TAs), to learn human-readable logical rules (e.g., IF $x_1$ AND NOT $x_2$ THEN Class A). Beyond interpretability, TMs are highly efficient, relying on simple increment and decrement operations that are ideal for hardware implementation.

While TMs have demonstrated state-of-the-art performance in pattern recognition, establishing mathematical guarantees for their learning behavior is essential. Previous research proved convergence for 1-bit operations (IDENTITY, NOT) and the non-linear XOR operation. This paper fills the remaining gap by proving convergence for the foundational AND and OR operators.

The Tsetlin Automaton: The Core Learning Unit

At the heart of a TM is the Tsetlin Automaton. Each TA acts as a decentralized learner that moves between states based on feedback from the environment.

The finite-state structure of a Tsetlin Automaton showing reward and penalty transitions.

The TA decides whether to "Include" or "Exclude" a specific input feature. As shown in the state transition diagram, "Reward" signals push the TA toward the extremes (0 or $2N-1$), reinforcing a stable decision, while "Penalty" signals push it toward the center boundary ($N-1$ to $N$), encouraging a change in decision.

Constructing Logical Clauses

A TM organizes TAs into "teams" to form conjunctive clauses. Each TA in the team corresponds to a literal (either an input $x_k$ or its negation $\neg x_k$).

Structure of a single logical clause formed by a team of Tsetlin Automata.

The collective decisions of the TA team determine the output of the clause $C_j^i$. The learning process is driven by two types of feedback:

  • Type I Feedback: Triggered by positive training samples to reward correct inclusions and combat false negatives.
  • Type II Feedback: Triggered by negative training samples to penalize incorrect inclusions and combat false positives.

Proving Convergence for AND and OR

The authors utilized Markov chain analysis to map the state transitions of TAs during training.

The AND Operator

For the AND operator, which outputs "True" only when all inputs are 1, a single-clause TM is sufficient. The authors proved that the transition probabilities under Type I and Type II feedback inevitably lead the system to a single "absorbing state." Once the TAs reach this state, they perfectly represent the AND logic and will not leave it under noise-free conditions.

The OR Operator

The OR operator is more complex because it encompasses multiple positive sub-patterns (e.g., (1,0), (0,1), and (1,1)). A single conjunctive clause cannot capture all these variations. Consequently, the authors analyzed a multi-clause architecture where clauses must work together to cover the pattern space.

A critical finding is the role of the hyperparameter $T$ (the target sum of votes). $T$ acts as a resource allocation mechanism. When a sub-pattern is already covered by $T$ clauses, the TM stops providing feedback for that pattern, forcing remaining "lazy" clauses to learn the other uncovered sub-patterns. The paper proves that for the OR operator to converge to a stable state, $T$ must be less than or equal to half the total number of clauses ($T \le \lfloor m/2 \rfloor$).

Conclusion

This research completes the theoretical framework for basic Boolean logic in Tsetlin Machines. By proving that TMs almost surely converge for AND and OR operations, the authors have demonstrated that the decentralized game played by Tsetlin Automata is a mathematically sound method for learning fundamental digital logic. This paves the way for future analysis of TMs in noisy environments and more complex real-world applications.

Summary updated

Abstract

The Tsetlin Machine (TM) is a novel machine-learning algorithm based on propositional logic, which has obtained state-of-the-art performance on several pattern recognition problems. In previous studies, the convergence properties of TM for 1-bit operation and XOR operation have been analyzed. To make the analyses for the basic digital operations complete, in this article, we analyze the convergence when input training samples follow AND and OR operators respectively. Our analyses reveal that the TM can converge almost surely to reproduce AND and OR operators, which are learnt from training data over an infinite time horizon. The analyses on AND and OR operators, together with the previously analysed 1-bit and XOR operations, complete the convergence analyses on basic operators in Boolean algebra.
BibTeX
@misc{jiao2021convergence,
  author = {Lei Jiao and Lei Jiao and Xuan Zhang and Ole-Christoffer Granmo},
  title = {{On the Convergence of Tsetlin Machines for the AND and the OR Operators}},
  year = {2021},
  eprint = {2109.09488},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.09488},
}
Figure