How a Tsetlin machine learns

This page summarises the algorithm implemented by torchtsetlin, using the vocabulary of Granmo's textbook An Introduction to Tsetlin Machines and the original paper (Granmo, 2018). If you know the book, the mapping is:

Book	Paper / code
Memorize / Forget value	(s-1)/s and 1/s (specificity s)
Recognize feedback	Type Ia feedback
Erase feedback	Type Ib feedback
Reject feedback	Type II feedback
Vote margin	threshold T
memory position 1…2N	automaton state 0…2N-1, included when >= N
Memorize Value + Forget Value = 1 (Chapter 1, e.g. 0.1 / 0.9)	(s-1)/s and 1/s, or memorize with probability 1 (boost_true_positive=True, the default, which is also the book's choice from Chapter 2 on)

The machine combines three strategies, one per part of the algorithm:

1. Frequent pattern mining. Type Ia and Type Ib feedback make a clause describe what is typical of its class, for example "most cars have four wheels".
2. Discrimination. Type II feedback makes the clause reject look-alikes from other classes, for example "cars have no wings".
3. Data dissection. The vote margin T spreads the clauses over different sub-patterns, so together they cover the whole class instead of all describing its most common case.

It is rule-based like a decision tree, adds up evidence like logistic regression, and works on bits, which keeps inference cheap and the learned rules readable.

Literals, clauses and votes

An example is a vector of F Boolean features. Its literals are the features and their negations, [x, NOT x] (length 2F). A clause is an AND of a subset of literals; it matches an example when all its literals are True. Each clause belongs to a class and has a polarity: positive clauses vote for the class, negative clauses vote against it.

The class sum (vote sum) is

\[v_k = \sum_{j \in \text{pos}(k)} w_j c_j(x) - \sum_{j \in \text{neg}(k)} w_j c_j(x), \qquad \hat y = \arg\max_k \operatorname{clip}(v_k, -T, T)\]

with w_j = 1 for the standard TM (integer weights for the weighted TM).

In everyday terms: the machine turns the input into a list of yes/no facts, each clause is a small checklist that fires only when every item on it is true, and the class with the most net votes wins.

Deciding “beach day?” for a sunny, windy weekend. Each clause is an AND of literals; it votes only if all of its literals are true. Two clauses vote for, one against, so the total is +1 and the answer is yes.

While learning, an empty clause (no included literals) evaluates to True so that it can start memorising; while predicting it evaluates to False.

A clause may include both x and NOT x. Such a clause can never match, so it receives only Type Ib (forget) feedback until one of the two literals is dropped. Contradictions disappear without a special rule.

Memory: Tsetlin automata

Every (clause, literal) pair owns a Tsetlin automaton whose state is an integer in [0, 2N-1]. States >= N mean the literal is included (memorised) in the clause, states < N mean it is excluded (forgotten). N (n_states) is the memory depth: deep states are hard to change, states near the boundary flip easily. Automata start just below the boundary (N-1), "about to be memorised but currently forgotten". The starting point does not decide where learning ends up: the outcome is a probability distribution over clauses that does not depend on the initial state (see Why a Tsetlin machine learns what it learns). init="random" is therefore a valid alternative to the default init="boundary".

Think of each automaton as a token on a track: rewards push it towards remember, penalties towards forget, and the literal is part of the clause only while the token sits on the remember side. A token deep in either half needs many consistent signals to change its mind — that is what makes learning robust to noise.

One Tsetlin automaton with N = 4 (8 states). The token starts just left of the line (N-1); each step right is a reward, each step left a penalty. Sunny is in the clause only while the token is on the right.

Feedback

For a training example of class y:

1. Evaluate all clauses and compute the clamped vote sums.
2. Draw a random negative class q != y.
3. Each clause of class y receives feedback with probability \((T - v_y) / 2T\): Type I if it is positive, Type II if it is negative.
4. Each clause of class q receives feedback with probability \((T + v_q) / 2T\): Type II if it is positive, Type I if it is negative.

The probabilities implement the vote margin: once a class already wins by T votes, its clauses stop being updated, which frees them to specialise on other examples (resource allocation).

The vote margin T. The class of the example is taught with probability (T - v)/2T — always when it clearly says no, never once it wins by T. A randomly drawn wrong class is corrected with probability (T + v)/2T.

Type I feedback makes a clause recognise frequent patterns:

• If the clause matches the example (Type Ia / Recognize): every True literal is memorised (state +1) with probability (s-1)/s — or with probability 1 when boost_true_positive=True, the default — and every False literal is forgotten (-1) with probability 1/s.
• If the clause does not match (Type Ib / Erase): all literals are forgotten with probability 1/s.

Type II feedback makes a clause reject examples of other classes: if the clause matches, every False literal that is currently excluded moves one step towards inclusion (deterministically). As soon as one such literal is included the clause no longer matches.

The same clause, Sunny, under each kind of feedback. Type I (an example of its own class): true literals step towards remember, false ones occasionally towards forget. Type II (a look-alike from another class): false literals step towards remember, so the clause stops matching. Both end at Sunny AND Weekend by different routes.

Specificity as a frequency threshold

Larger s means forgetting is rarer, so clauses keep more literals and become more specific. The book's breast-cancer example shows the arithmetic. Take a literal that is true for 2 of 3 patients of the clause's class, and a memorise/forget pair of 0.2/0.8. Per pass over the three patients it moves up 2 × 0.2 = 0.4 steps and down 1 × 0.8 = 0.8 steps on average, so it drifts out of the clause. With 0.5/0.5 it moves up 1.0 and down 0.5, so it stays. In the library's terms: a literal survives in a clause roughly when it is true in more than about 1/s of the examples that train the clause. Why a Tsetlin machine learns what it learns makes this exact.

T controls how many clauses cooperate on each example; larger T needs more clauses.

How clauses coordinate

No clause knows about the others. They coordinate only through the shared vote sum, and the book's Section 1.6 lists three effects:

• Examples are prioritised by how far they are from the margin. With T = 2, the probability that a clause of the example's class gets feedback is (T - v)/2T:

  vote sum v of the true class	-2	-1	0	1	2
  chance each clause is updated	1	0.75	0.5	0.25	0

  Misclassified examples get the most attention; solved ones get none. * Type II only reaches clauses that voted wrongly. A clause that does not match an example of another class is left alone, so correct clauses are shielded. * Good clauses are memorised deepest. A clause that matches most of its class and never votes wrongly gets the most Type Ia and no Type II, so its literals sit far from the boundary. Clauses that keep being disrupted stay shallow, which leaves them free to move to a better pattern. Duplicate clauses are not waste: two copies of a good clause add their votes and help the class reach the margin.

Variants implemented

• Weighted / integer-weighted TM (weighted=True): each clause has an integer weight that grows by 1 on Type Ia and shrinks by 1 on Type II feedback.
• Coalesced TM (CoalescedTsetlinMachine): one pool of clauses shared by all outputs, each with a signed integer weight per output. Weights move away from zero on Type I and towards zero on Type II, so a clause can change sides. Supports multi-label targets.
• Regression TM (RegressionTsetlinMachine): all clauses positive, v in [0, T] mapped linearly to the target range; Type I when the prediction is too low, Type II when too high, with probability proportional to the error.
• Convolutional TM — see Convolution.
• Graph TM (GraphTsetlinMachine): deep clauses over graph input, one component per layer, connected by messages along typed edges — see Graph Tsetlin machines.
• Clause size constraint (max_included_literals): clauses above the budget receive only forgetting feedback until they shrink (Abeyrathna et al., 2023). By default (budget_mode="soft", the reference implementation's rule) a clause may overshoot the budget and is then pruned, which keeps its contents changing. budget_mode="hard" also reverts every inclusion beyond the budget. With that, no clause ever exceeds it, the pruning never triggers, and clauses freeze at exactly the budget. On the TM Composites CIFAR-10 colour-thermometer specialists that cost 10-11 pp (experiments/multi_convtm/REPORT.md).
• Drop clause / drop literal (drop_clause_p, drop_literal_p): randomly excluded clauses neither vote nor learn for one batch or epoch (Sharma et al., 2023).
• Focused negative sampling: choose the negative class proportionally to its current vote sum, i.e. correct confusions first.

Where each piece lives

Step	Function / method
literals	functional.to_literals
clause evaluation	functional.clause_outputs (one matmul + comparison)
vote sums	functional.vote_sums, model._votes
feedback probabilities	functional.feedback_probabilities
which clause gets which feedback	model._select_feedback
counting feedback events over a batch	functional.type_i_counts, functional.type_ii_counts
moving the automata	functional.apply_feedback

References

• O.-C. Granmo, The Tsetlin Machine – A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic, arXiv:1804.01508 (2018).
• O.-C. Granmo, An Introduction to Tsetlin Machines, tsetlinmachine.org.
• A. Phoulady et al., The Weighted Tsetlin Machine, arXiv:1911.12607 (2019).
• S. Glimsdal, O.-C. Granmo, Coalesced Multi-Output Tsetlin Machines with Clause Sharing, arXiv:2108.07594 (2021).
• K. D. Abeyrathna et al., Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size, arXiv:2301.08190 (2023).
• J. Sharma et al., Drop Clause: Enhancing Performance, Interpretability and Robustness of Tsetlin Machines, AAAI (2023).