# Coalesced Multi-Output Tsetlin Machines with Clause Sharing

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 17 Aug 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Neural Additive Models: Interpretable Machine Learning with Neural Nets](https://mlsanity.com/paper/2004.13912/) (2020)
- [InterpretML: A Unified Framework for Machine Learning Interpretability](https://mlsanity.com/paper/1909.09223/) (2019)
- [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)
- [Explainable Tsetlin Machine framework for fake news detection with credibility score assessment](https://mlsanity.com/paper/2105.09114/) (2021)
- [Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling](https://mlsanity.com/paper/2009.04861/) (2020)
- [Extending the Tsetlin Machine With Integer-Weighted Clauses for Increased Interpretability](https://mlsanity.com/paper/2005.05131/) (2020)
- [On the Convergence of Tsetlin Machines for the XOR Operator](https://mlsanity.com/paper/2101.02547/) (2021)
- [Measuring the Novelty of Natural Language Text Using the Conjunctive Clauses of a Tsetlin Machine Text Classifier](https://mlsanity.com/paper/2011.08755/) (2020)
- [Learning Logistic Circuits](https://mlsanity.com/paper/1902.10798/) (2019)
- [Low-Power Audio Keyword Spotting using Tsetlin Machines](https://mlsanity.com/paper/2101.11336/) (2021)
- [Word-level Human Interpretable Scoring Mechanism for Novel Text Detection Using Tsetlin Machines](https://mlsanity.com/paper/2105.04708/) (2021)
- [A Tsetlin Machine with Multigranular Clauses](https://mlsanity.com/paper/1909.07310/) (2019)
- [A Novel Multi-Step Finite-State Automaton for Arbitrarily Deterministic Tsetlin Machine Learning](https://mlsanity.com/paper/2007.02114/) (2020)
- [Low-Latency Asynchronous Logic Design for Inference at the Edge](https://mlsanity.com/paper/2012.03402/) (2020)
- [Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing](https://mlsanity.com/paper/2004.03188/) (2020)
- [Accelerating Deterministic and Stochastic Binarized Neural Networks on FPGAs Using OpenCL](https://mlsanity.com/paper/1905.06105/) (2019)
- [StructureBoost: Efficient Gradient Boosting for Structured Categorical Variables](https://mlsanity.com/paper/2007.04446/) (2020)

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

- [Tsetlin Machine Embedding: Representing Words Using Logical Expressions](https://mlsanity.com/paper/2301.00709/) (2023)
- [Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size](https://mlsanity.com/paper/2301.08190/) (2023)
- [Exploring Effects of Hyperdimensional Vectors for Tsetlin Machines](https://mlsanity.com/paper/2406.02648/) (2024)
- [Adversarial Attacks on AI-Generated Text Detection Models: A Token Probability-Based Approach Using Embeddings](https://mlsanity.com/paper/2501.18998/) (2025)
- [Exploring State Space and Reasoning by Elimination in Tsetlin Machines](https://mlsanity.com/paper/2407.09162/) (2024)
- [IMBUE: In-Memory Boolean-to-CUrrent Inference ArchitecturE for Tsetlin Machines](https://mlsanity.com/paper/2305.12914/) (2023)
- [MATADOR: Automated System-on-Chip Tsetlin Machine Design Generation for Edge Applications](https://mlsanity.com/paper/2403.10538/) (2024)
- [An All-digital 8.6-nJ/Frame 65-nm Tsetlin Machine Image Classification Accelerator](https://mlsanity.com/paper/2501.19347/) (2025)
- [Scalable Multi-phase Word Embedding Using Conjunctive Propositional Clauses](https://mlsanity.com/paper/2501.19018/) (2025)
- [Dynamic Tsetlin Machine Accelerators for On-Chip Training at the Edge using FPGAs](https://mlsanity.com/paper/2504.19797/) (2025)
- [The Tsetlin Machine Goes Deep: Logical Learning and Reasoning With Graphs](https://mlsanity.com/paper/2507.14874/) (2025)
- [The Sparse Tsetlin Machine: Sparse Representation with Active Literals](https://mlsanity.com/paper/2405.02375/) (2024)
- [Omni TM-AE: A Scalable and Interpretable Embedding Model Using the Full Tsetlin Machine State Space](https://mlsanity.com/paper/2505.16386/) (2025)
- [Generating Bayesian Network Models from Data Using Tsetlin Machines](https://mlsanity.com/paper/2305.10538/) (2023)
- [Green Tsetlin Redefining Efficiency in Tsetlin Machine Frameworks](https://mlsanity.com/paper/2405.04212/) (2024)
- [Hyperdimensional Vector Tsetlin Machines with Applications to Sequence Learning and Generation](https://mlsanity.com/paper/2408.16620/) (2024)
- [Symbolic Graph Intelligence: Hypervector Message Passing for Learning Graph-Level Patterns with Tsetlin Machines](https://mlsanity.com/paper/2507.16537/) (2025)
- [Fuzzy-Pattern Tsetlin Machine](https://mlsanity.com/paper/2508.08350/) (2025)
- [A Methodology for Transparent Logic-Based Classification Using a Multi-Task Convolutional Tsetlin Machine](https://mlsanity.com/paper/2510.01906/) (2025)
- [Event-Driven Digital-Time-Domain Inference Architectures for Tsetlin Machines](https://mlsanity.com/paper/2511.09527/) (2025)
- [FastOmniTMAE: Parallel Clause Learning for Scalable and Hardware-Efficient Tsetlin Embeddings](https://mlsanity.com/paper/2605.06982/) (2026)
- [Macroeconomic Message Passing for Anticipating Foreign Exchange Regime Changes: A Deep Logical Learning Approach using Graph Tsetlin Machines](https://mlsanity.com/paper/2607.06719/) (2026)

## Abstract (arXiv)

Using finite-state machines to learn patterns, Tsetlin machines (TMs) have obtained competitive accuracy and learning speed across several benchmarks, with frugal memory- and energy footprint. A TM represents patterns as conjunctive clauses in propositional logic (AND-rules), each clause voting for or against a particular output. While efficient for single-output problems, one needs a separate TM per output for multi-output problems. Employing multiple TMs hinders pattern reuse because each TM then operates in a silo. In this paper, we introduce clause sharing, merging multiple TMs into a single one. Each clause is related to each output by using a weight. A positive weight makes the clause vote for output 1, while a negative weight makes the clause vote for output 0. The clauses thus coalesce to produce multiple outputs. The resulting coalesced Tsetlin Machine (CoTM) simultaneously learns both the weights and the composition of each clause by employing interacting Stochastic Searching on the Line (SSL) and Tsetlin Automata (TA) teams. Our empirical results on MNIST, Fashion-MNIST, and Kuzushiji-MNIST show that CoTM obtains significantly higher accuracy than TM on 50- to 1K-clause configurations, indicating an ability to repurpose clauses. E.g., accuracy goes from 71.99% to 89.66% on Fashion-MNIST when employing 50 clauses per class (22 Kb memory). While TM and CoTM accuracy is similar when using more than 1K clauses per class, CoTM reaches peak accuracy 3× faster on MNIST with 8K clauses. We further investigate robustness towards imbalanced training data. Our evaluations on imbalanced versions of IMDb- and CIFAR10 data show that CoTM is robust towards high degrees of class imbalance. Being able to share clauses, we believe CoTM will enable new TM application domains that involve multiple outputs, such as learning language models and auto-encoding.