MaxSAT-Based Compression for Tsetlin Machines

We consider the computational problem of compacting Tsetlin Machine classifiers by reducing the number of propositional clauses while preserving predictive accuracy. TMs trained with limited clause capacity often perform poorly because stochastic optimization cannot reliably find the few precise clauses needed in a vast configuration space. High-quality compact subsets also exist in the case of larger Tsetlin Machines. The difficulty here lies in extracting them. Local pruning heuristics can fail badly on TMs because clauses interact through Boolean logic: a clause may appear unimportant in isolation yet becomes critical when others are removed. We formalize compression as the Minimum Discriminating Clause Set (MDCS) problem, which asks to find a smallest subset of clauses that preserves the trained model's discrimination of training samples. We show that MDCS is NP-hard. We solve MDCS using weighted partial Maximum Satisfiability (MaxSAT). A partition-and-merge strategy allows us to scale to 100,000 samples. Across 13 datasets, the compressed model preserves the 200-clause teacher's accuracy within a few percentage points while using a median of only 16 clauses, and outperforms a matched-capacity TM trained from scratch on every dataset where direct training has room to improve, by up to 45 percentage points.

A Tsetlin Machine is a type of classifier that, instead of using the numerical weights of a neural network, learns a set of plain Boolean rules: short "if-this-and-not-that" patterns over the input features. This makes it attractive in two settings where neural networks are awkward: when a human needs to read off why a prediction was made (medical decisions, regulatory review), and when the model has to run on tiny, battery-powered hardware that cannot hold a large neural network in memory. Tsetlin Machines trained directly with a small number of rules tend to perform poorly: the random search used during training rarely finds the few precise rules that the problem requires. Larger models, with hundreds of rules to spare, work much better, but they are too big for the constrained settings these models target. We close this gap in two steps. We first train a large Tsetlin Machine. We then use a mathematical optimization technique called MaxSAT to find the smallest subset of its rules that preserves the trained model's classification behavior on the training data. Across thirteen standard benchmarks, the resulting compact models, typically using only a few percent of the original rules, match the accuracy of the larger model they were extracted from, and substantially outperform Tsetlin Machines trained directly at the same small size.