# On the Convergence of Tsetlin Machines for the XOR Operator

arXiv: https://arxiv.org/abs/2101.02547 · HTML: https://mlsanity.com/paper/2101.02547/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 7 Jan 2021.

## Builds on (most cited first, 11 of 11)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [The Tsetlin Machine -- A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic](https://mlsanity.com/paper/1804.01508/) (2018)
- [The Convolutional Tsetlin Machine](https://mlsanity.com/paper/1905.09688/) (2019)
- [Using the Tsetlin Machine to Learn Human-Interpretable Rules for High-Accuracy Text Categorization with Medical Applications](https://mlsanity.com/paper/1809.04547/) (2018)
- [On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators](https://mlsanity.com/paper/2007.14268/) (2020)
- [Extending the Tsetlin Machine With Integer-Weighted Clauses for Increased Interpretability](https://mlsanity.com/paper/2005.05131/) (2020)
- [Measuring the Novelty of Natural Language Text Using the Conjunctive Clauses of a Tsetlin Machine Text Classifier](https://mlsanity.com/paper/2011.08755/) (2020)
- [Closed-Form Expressions for Global and Local Interpretation of Tsetlin Machines with Applications to Explaining High-Dimensional Data](https://mlsanity.com/paper/2007.13885/) (2020)
- [A Scheme for Continuous Input to the Tsetlin Machine with Applications to Forecasting Disease Outbreaks](https://mlsanity.com/paper/1905.04199/) (2019)
- [Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing](https://mlsanity.com/paper/2004.03188/) (2020)
- [A Regression Tsetlin Machine with Integer Weighted Clauses for Compact Pattern Representation](https://mlsanity.com/paper/2002.01245/) (2020)

## Built on by (most cited first, 16 of 16)

- [Coalesced Multi-Output Tsetlin Machines with Clause Sharing](https://mlsanity.com/paper/2108.07594/) (2021)
- [Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size](https://mlsanity.com/paper/2301.08190/) (2023)
- [Word-level Human Interpretable Scoring Mechanism for Novel Text Detection Using Tsetlin Machines](https://mlsanity.com/paper/2105.04708/) (2021)
- [Drop Clause: Enhancing Performance, Interpretability and Robustness of the Tsetlin Machine](https://mlsanity.com/paper/2105.14506/) (2021)
- [Exploring Effects of Hyperdimensional Vectors for Tsetlin Machines](https://mlsanity.com/paper/2406.02648/) (2024)
- [On the Convergence of Tsetlin Machines for the AND and the OR Operators](https://mlsanity.com/paper/2109.09488/) (2021)
- [Interpretable Tsetlin Machine-based Premature Ventricular Contraction Identification](https://mlsanity.com/paper/2301.10181/) (2023)
- [The Tsetlin Machine Goes Deep: Logical Learning and Reasoning With Graphs](https://mlsanity.com/paper/2507.14874/) (2025)
- [On the Equivalence of the Weighted Tsetlin Machine and the Perceptron](https://mlsanity.com/paper/2212.13634/) (2022)
- [VDHLA: Variable Depth Hybrid Learning Automaton and Its Application to Defense Against the Selfish Mining Attack in Bitcoin](https://mlsanity.com/paper/2302.12096/) (2023)
- [Runtime Tunable Tsetlin Machines for Edge Inference on eFPGAs](https://mlsanity.com/paper/2502.07823/) (2025)
- [Omni TM-AE: A Scalable and Interpretable Embedding Model Using the Full Tsetlin Machine State Space](https://mlsanity.com/paper/2505.16386/) (2025)
- [Uncertainty Quantification in the Tsetlin Machine](https://mlsanity.com/paper/2507.04175/) (2025)
- [Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic Approach to Concept Learning](https://mlsanity.com/paper/2310.02005/) (2023)
- [A Methodology for Transparent Logic-Based Classification Using a Multi-Task Convolutional Tsetlin Machine](https://mlsanity.com/paper/2510.01906/) (2025)
- [Scalable Bayesian Network Structure Learning Using Tsetlin Machine to Constrain the Search Space](https://mlsanity.com/paper/2511.19273/) (2025)

## Abstract (arXiv)

The Tsetlin Machine (TM) is a novel machine learning algorithm with several distinct properties, including transparent inference and learning using hardware-near building blocks. Although numerous papers explore the TM empirically, many of its properties have not yet been analyzed mathematically. In this article, we analyze the convergence of the TM when input is non-linearly related to output by the XOR-operator. Our analysis reveals that the TM, with just two conjunctive clauses, can converge almost surely to reproducing XOR, learning from training data over an infinite time horizon. Furthermore, the analysis shows how the hyper-parameter T guides clause construction so that the clauses capture the distinct sub-patterns in the data. Our analysis of convergence for XOR thus lays the foundation for analyzing other more complex logical expressions. These analyses altogether, from a mathematical perspective, provide new insights on why TMs have obtained state-of-the-art performance on several pattern recognition problems