On the Convergence of Tsetlin Machines for the XOR Operator

The Tsetlin Machine (TM) [1] employs groups of Tsetlin Automata (TAs) [2], which operate on binary data using propositional logic. Via a game-theoretic collaboration scheme, the TAs self-organize to capture the distinct patterns in the data. In brief, each group of TAs builds a conjunctive clause that captures a specific pattern. The dynamics of the collaboration involves three interacting mechanisms. High pattern recall is enforced by a resource allocation mechanism that diversifies clause construction. Simultaneously, a mechanism that forces the clauses to capture frequent patterns combats overfitting. Finally, without compromising high pattern frequency, the discrimination power of the clauses is optimized by injecting discriminative features. TMs provide two main advantages: transparent inference and learning combined with hardware-near building blocks.