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 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$).
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