Accelerated Tsetlin Machine Inference Through Incremental Model Re-evaluation

Tsetlin Machines (TMs) are a new class of machine learning algorithms that leverage propositional (Boolean) logic. While ensuring transparent and inherently interpretable decision-making, they handle relatively complex pattern recognition tasks, including classification, convolution, and regression. However, like most machine learning approaches, inference is computationally expensive for large models because each new input requires recalculating the model output from scratch. Slow evaluation can be problematic in time-critical tasks, hindering the deployment of more powerful models. This paper proposes a new TM inference approach that drastically reduces computational complexity through incremental model re-evaluation. To this end, we single out small incremental computations by tracing which clauses are impacted by each input feature. Our tailored solution for TM offers a more scalable and efficient inference strategy, particularly beneficial when new inputs are similar to previous ones. The results of our experiments on benchmark datasets demonstrate that our approach not only retains the same precision as the traditional TM but also provides significantly faster inference, achieving up to a 40 times speedup. The code is made available on GitHub.