# Drop Clause: Enhancing Performance, Interpretability and Robustness of the
Tsetlin Machine

Jivitesh Sharma  Rohan Yadav  Ole-Christoffer Granmo  Lei Jiao

###### Abstract

In this article, we introduce a novel variant of the Tsetlin machine (TM) that
randomly drops clauses, the key learning elements of a TM. In effect, TM with
drop clause ignores a random selection of the clauses in each epoch, selected
according to a predefined probability. In this way, additional stochasticity
is introduced in the learning phase of TM. To explore the effects drop clause
has on accuracy, training time, interpretability and robustness, we conduct
extensive experiments on nine benchmark datasets in natural language
processing (NLP) (IMDb, R8, R52, MR and TREC) and image classification (MNIST,
Fashion MNIST, CIFAR-10 and CIFAR-100). Our proposed model outperforms
baseline machine learning algorithms by a wide margin and achieves competitive
performance in comparison with recent deep learning model such as BERT and
AlexNET-DFA. In brief, we observe up to $+10$% increase in accuracy and
$2\times$ to $4\times$ faster learning compared with standard TM. We further
employ the Convolutional TM to document interpretable results on the CIFAR
datasets, visualizing how the heatmaps produced by the TM become more
interpretable with drop clause. We also evaluate how drop clause affects
learning robustness by introducing corruptions and alterations in the
image/language test data. Our results show that drop clause makes TM more
robust towards such changes111The code is available online on: github.

Machine Learning, ICML

##  1 Introduction

Researchers across various fields are increasingly paying attention to the
interpretability of AI techniques. While interpretability previously was
inherent in most machine learning approaches, state-of-the-art methods now
increasingly rely on black-box deep neural network-based models. Natively,
these can neither be interpreted during the learning stage nor while producing
outputs. For this reason, a surge of techniques attempts to open the black box
by visual explanations and gradient-based interpretability (Simonyan et al.,
2014; Zhang et al., 2018; Radhakrishnan et al., 2018; Bau et al., 2017;
Selvaraju et al., 2017).
The Tsetlin Machine (TM) is a natively interpretable rule-based machine
learning algorithm that produces logical rules (Granmo, 2018). Despite being
logic-based, the TM is a universal function approximator, like a neural
network. In brief, it employs an ensemble of Tsetlin Automata (TA) that learns
propositional logic expressions from Boolean input features. Due to its
Boolean representations and finite-state automata learning mechanisms, it has
a minimalistic memory footprint. Propositional logic drives learning,
eliminating the need for floating-point operations. More importantly, TM
achieves interpretability by leveraging sparse disjunctive normal form.
Indeed, humans are particularly good at understanding flat and short logical
AND-rules, reflecting human reasoning (Noveck et al., 1991).
However, the TM suffers from overfitting in the sense that its learning
elements, i.e. clauses, are prone to capture noise and redundant patterns that
are detrimental to performance. Initially, we conjectured that this could be
simply because there are too many clauses. However, on decreasing the number
of clauses, there was a proportionate decrease in performance. So, in order to
reduce overfitting and increase generalization performance, we take
inspiration from Dropout (Srivastava et al., 2014) and propose a method we
call _Drop Clause_ (DC). The drop clause method randomly _drops_ or switches
off a set of clauses during training. This is similar to what dropout does in
neural networks. However, unlike dropout, drop clause induces stochasticity in
TM learning, boosting performance in terms of accuracy and learning speed. It
further improves the patterns captured by the clauses, making them more
interpretable and robust towards input perturbations. As a direct consequence
of dropping clauses during training, the training time is reduced
proportionally.

#### Paper Contributions:

Our paper’s contributions can be summarized as follows:

  1. 1.

We propose to drop clauses randomly during each TM training iteration, which
introduces additional stochasticity in the learning process.

  2. 2.

We demonstrate that dropping clauses makes the TM capture more unique
patterns, improving its generalization performance significantly.

  3. 3.

The improved patterns lead to competitive TM results compared to state-of-the-
art models on $9$ benchmark datasets from NLP and image classification. Since
TM is more akin to a standard machine learning algorithm, like a decision
tree, than a deep learning model, we also compare the drop clause TM with
well-known machine learning algorithms, documenting superior performance
across all the datasets.

  4. 4.

We visualize several examples of enhanced interpretability, and measure
increased robustness on image classification and natural language sentiment
analysis.

#### Paper Organization.

The rest of the paper is laid out as follows: Section 2 introduces our
proposed drop clause method. Section 3 then presents the outcomes of our NLP
and image classification experiments, while Section 4 investigates the
interpretability of the drop clause TM over the standard TM, both on natural
language sentiment analysis and image classification. We then show how drop
clause enhances TM robustness towards corrupted or noisy test data in Section
5. Section 6 contains a brief discussion of our main results and findings,
with Section 7 providing the main conclusions of our research.

##  2 Drop Clause for Tsetlin Machines

As discussed in the previous section, neural networks are difficult to
interpret. Therefore, applications leverage them as black boxes, with the
adverse effects that entail. However, for high-stakes applications, such as
healthcare, black-box approaches are not sufficient. Modern society needs
reliable, unbiased, and trustworthy AI systems. Researchers have shown that
neural networks are not fully mature for integration into society. For
example, neural network interpretability is fragile towards adversarial
examples (Ghorbani et al., 2019). Generating adversarial perturbations that
produce visually indistinguishable images for humans leads to dramatically
different neural network interpretations, without changing the label.
Lack of interpretability is another concern. Rudin et al. argue that neural
networks are black boxes that cannot be fully explained, and offer several
reasons for choosing interpretable models over attempting to explain black box
ones (Rudin, 2019). They further raise three algorithmic challenges that the
machine learning community faces to succeed with human-level interpretability.
Although neural networks are inherently inadequate for these challenges, the
TM addresses them natively:

  1. 1.

_Challenge 1: Rule-based logical models_. The TM learns a rule-based model
using logical operations. Learning is game-theoretic with Nash equilibria that
correspond to the optimal propositional logic expressions (Granmo, 2018; Zhang
et al., 2021; Jiao et al., 2021).

  2. 2.

_Challenge 2: Linear models with sparse scoring systems._ The TM is a linear
model that produces sparse clauses and integer weighted scores (Abeyrathna et
al., 2021).

  3. 3.

_Challenge 3: Domain-specific interpretable AI._ The TM is inherently
interpretable, used for producing interpretable models across several domains
(Abeyrathna et al., 2020; Berge et al., 2019; Lei et al., 2021; Yadav et al.,
2021).

In this section, we first briefly present the basic TM as well as the
convolutional version. Thereafter, we introduce the details of our drop clause
technique, which enhances the stochasticity of TM learning. Our goal is to
reduce overfitting behaviour and considerably increase performance. We also
show enhanced interpretability on CIFAR-10 at the pixel-level and on MR
dataset at the word-level. And, as the TM is based on Boolean data and
propositional logic, it has very low memory footprint and computational
complexity _(zero FLOPs)_. This makes the usage of TM advantageous for on-
device and federated learning on mobile devices and devices with limited
compute.

###  2.1 TM and Convolutional TM

A TM in its simplest form takes a feature vector
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{o}]\in\\{0,1\\}^{o}$ of $o$ Boolean values
as input, producing a Boolean output $\hat{y}\in\\{0,1\\}$ (Granmo, 2018).
Patterns are expressed as conjunctive clauses (AND-rules), built from literals
$L=\\{l_{1},l_{2},\ldots,l_{2o}\\}=\\{x_{1},x_{2},\ldots,x_{o},\lnot
x_{1},\lnot x_{2},\ldots,\lnot x_{o}\\}$:

$\hat{y}=0\leq\sum_{j=1,3,\ldots}^{n-1}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right]\\\
-\sum_{j=2,4,\ldots}^{n}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right].$ (1)

In Equation 1, $a^{j}_{k}$ is the TA state that controls inclusion of literal
$l_{k}$ in clause $j$ and $g(\cdot)$ maps the TA state to action $0$ or $1$.
The imply operator, in turn, implements the action in the clause. Even-
indexed/odd-indexed clauses vote for output $\hat{y}=0$/$\hat{y}=1$. A
detailed explanation can be found in the Appendix A.1.
The Convolutional TM (CTM) is as an interpretable alternative to CNNs (Granmo
et al., 2019). Whereas the TM categorizes an image by employing each clause
once to the whole image, the CTM uses each clause as a convolution filter.
That is, a clause is evaluated multiple times, once per image patch taking
part in the convolution. The output of a convolution clause is obtained simply
by ORing the outcome of evaluating the clause on each patch:

$\hat{y}=0\leq\sum_{j=1,3,\ldots}^{n-1}\bigvee_{b=1}^{B}\left[\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}^{b}\right]\right]\\\
-\sum_{j=2,4,\ldots}^{n}\bigvee_{b=1}^{B}\left[\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}^{b}\right]\right].$ (2)

Here, $b$ refers to one out of $B$ available image patches (Granmo et al.,
2019). See Appendix A.2 for further details.

###  2.2 Drop Clause

Although there might be an enormous amount of patterns in real-life data, with
a sufficient number of clauses the TM can identify the most important ones.
However, patterns might differ between training and testing data, resulting in
overfitting. We therefore propose a novel regularization method for the TM
called drop clause. This technique is inspired by the dropout method for
neural networks. In drop clause, clauses are removed with a probability $p$ in
each training epoch:

$\hat{y}=0\leq\sum_{j=1,3,\ldots}^{n-1}\pi_{j}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right]\\\
-\sum_{j=2,4,\ldots}^{n}\pi_{j}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right].$ (3)

Above, $\pi_{j}\in\\{0,1\\}$ for clause $j$ is zero with probability $p$ for
each complete epoch. The purpose is to reduce the chance of learning redundant
patterns. Accordingly, the vanilla TM and its drop clause variant are
equivalent if $p=0$.
Drop clause in TM works in a similar way as dropout in neural networks. A
basic TM seeks to minimize prediction error on the training data. Achieving
this, there may still be unused patterns available in the training data. These
patterns can potentially be useful when facing new data, such as test data. By
randomly dropping clauses for complete epochs, we mobilize other clauses to
take over the role of the dropped clauses. Drop clause can be thought of as
having a pool of clauses and selecting a set of clauses with $1-p$ probability
for training every epoch. However, due to this stochastic learning, the
mobilized clauses may solve the task in a different way. Hence, robustness
increases overall when the complete set of clauses are turned on again. The
resulting effects are evaluated experimentally in the next section.
The stochasticity induced by dropping clauses in the TM learning process is in
some senses similar to the stochasticity induced by stochastic gradient
descent (SGD) (Robbins, 2007). In SGD, a mini-batch of training samples is
selected randomly from the training data. While, in drop clause, various sets
of clauses are selected for training with probability $1-p$. The major
difference is that, SGD is stochastic in terms of data sampling during the
learning stage, whereas drop clause is stochastic in terms of sampling the
elements of the model structure (clauses are the elements that form the TM
model). Another difference is that the stochasticity of drop clause can be
adjusted with the drop clause probability hyper-parameter $p$. Note that even
with stochastically and randomly reduced number of clauses, that change ever
training epoch, the TM still retains its convergence properties. Please see
Appendix A.3 for details.

##  3 Experiments and Results

We here investigate the effects drop clause has on the performance of TMs. To
assess the generality of our approach, we test drop clause both on NLP and
image classification. For NLP, we use TM with weighted clauses, and for image
classification, we use the CTM. For evaluation, we compare our approach with
comparable state-of-the-art deep learning models. Since TM is a rule-based
machine learning method, we also cover more standard machine learning
algorithms. The drop clause implementation is written in PyCUDA for parallel
GPU computation. We train our models on 16 NVIDIA Tesla V100 TensorCore GPUs
for the image classification task and on one NVIDIA RTX 3070 8GB GPU for the
NLP tasks.

###  3.1 Natural Language Processing

We explore the performance of drop clause on NLP tasks first. The first
experiments assess how varying the drop clause probability affects
classification accuracy and then compare the best found configuration with
similar machine learning algorithms and state-of-the-art techniques. To this
end, we use $5$ popular standard datasets — IMDb, R8, R52, MR and TREC,
summarized below:

  * •

_IMDb_ consists of $50,000$ movie reviews for binary sentiment analysis, out
of which $25,000$ are used for training and $25,000$ for testing. Here, we use
$10,000$ clauses and set the TM hyperparameters target $T$ to $8,000$ and
specificity $s$ to $2.0$ (see Appendix A.1 for details).

  * •

_Reuters-21578_ contains the text categorization datasets _R8_ and _R52_. R8
is divided into $8$ categories, with $5,485$ training and $2,189$ testing
samples, whereas R52 consists of $52$ categories, divided into $6,532$
training and $2,568$ testing samples. We here employ $3,000$ clauses with
$T=2,000$ and $s=7.0$.

  * •

_MR_ is another movie review dataset for binary sentiment classification,
consisting of $10,662$ samples. We use the train-test split as in (Tang et
al., 2015) and use $5,000$ clauses with $T=4,000$ and $s=6.0$.

  * •

_TREC_ is a question classification dataset that encompasses $6$ categories.
There are a total of $6,000$ samples, $5,500$ for training and $500$ for
testing. Here, we use $5,000$ clauses with $T=4,000$ and $s=2.0$.

Our first step is to compare the difference in performance with respect to
change in drop clause probability, shown in Table 1. The selected drop clause
probabilities are $p\in\left\\{0.1,0.25,0.5,0.75\right\\}$. For IMDb, R8, R52
and MR, the best performance is achieved with $p=0.75$, which is equivalent of
dropping $75\%$ of the total clauses per class, per epoch. As for TREC,
$p=0.5$ works best. As seen, drop clause has significant effect on accuracy,
with average accuracy going up by $4.07\%$ for IMDb, $2.78\%$ for R8, $3.61\%$
for R52, $3.53\%$ for MR and $2.45\%$ for TREC. Additionally, we observe a
substantial reduction in training time proportional to the drop clause ratio.
Inference times on these datasets are less than $2.3ms$ per sample on average
on an NVIDIA RTX 3070 8GB GPU.

Table 1: Effect of Drop Clause on NLP Datasets.

TM $p=0$ $p=.1$ $p=.25$ $p=.5$ $p=.75$ IMDB 87.2 88.3 89.6 90.4 91.27 R8 96.16
97.6 98.1 98.5 98.94 R52 89.14 89.5 90.8 91.5 92.75 MR 75.14 77.25 77.9 78.2
78.67 TREC 88.05 89.8 90.1 90.5 89.9

The TM is a rule-based machine learning algorithm, so we also compare our
proposed TM model with a few traditional machine learning techniques. Table 2
displays the results of our comparison and shows TM’s superior performance
among its class of algorithms222Note that the machine learning methods used
here for comparison have default parameters from sklearn.. We compare our
proposed TM with drop clause against Support Vector Machine (SVM), Random
Forests (RF), K-Nearest Neighbours (K-NN) and XGBoost (XGB). From Table 2, it
is clear that TM with drop clause outperforms other machine learning
algorithms by a wide margin.
We also compare our model with deep learning methods, some of them
representing state-of-the-art. Tables 3 and 4 show the results of our
comparisons. Enhanced with drop clause, the accuracy of TM is comparable not
only to CNNs and LSTMs but also to computationally complex and parametrically
large state-of-the-art models like BERT. On all datasets in Table 3, inclusion
of drop clause propels the performance of the TM to outperform CNN (Kim, 2014)
and bidirectional LSTM with pretrained word embeddings. In fact, on R8 and
R52, drop clause TM is able to achieve better accuracy than BERT (Devlin et
al., 2019) and comes close to its performance on MR. Also, comparing our model
with the state-of-the-art graph convolutional neural network, $S^{2}GC$ (Zhu &
Koniusz, 2020), drop clause TM achieves better performance on R8 and MR, and
comparable performance on R52. Similar results are obtained on the TREC
dataset shown in Table 4. Drop clause TM outperforms a baseline LSTM model as
well as a vanilla Transformer (TF) and Transformer with feature projection
(FP) (Qin et al., 2020).
Even though BERT achieves better performance on TREC dataset, TM has major
advantages over these models concerning computational complexity and
interpretability, which are further enhanced by drop clause (See Section 5).
While it is disputed whether attention is explainable (Jain & Wallace, 2019),
the approach is significantly more complex than our proposed model and
achieves comparable performance. Note that our model only relies on simple
bag-of-words tokens in the target datasets, without considering any additional
pretrained world knowledge, like word2vec, Glove or BERT features. Yet, it
achieves competitive performance compared to deep learning and some state-of-
the-art models.

Table 2: Comparison with Machine Learning methods

TM TM SVM RF K-NN XGB (DC) IMDB 87.2 91.27 83.2 78.5 72.5 84.4 R8 96.16 98.94
84.7 82.4 77.3 85.1 R52 89.14 92.75 71.0 72.5 58.2 75.4 MR 75.14 78.67 52.2
51.7 39.1 56.3 TREC 88.05 90.5 67.5 65.4 56.1 77.6

Table 3: Comparison on IMDb, R8, R52 and MR | TM | CNN | BiLSTM | BERT |  S2GC
---|---|---|---|---|---
| (DC) |  |  |  |
IMDB | 91.27 | 87.9 | 88.9 | 95.4 | -
R8 | 98.94 | 95.71 | 96.31 | 96.02 | 97.4
R52 | 92.75 | 87.59 | 90.54 | 89.66 | 94.5
MR | 78.67 | 77.75 | 77.68 | 79.24 | 76.7
Table 4: Comparison on TREC-6 | TM | LSTM | TF | FP+TF | BERT
---|---|---|---|---|---
| (DC) |  |  |  |
TREC-6 | 90.5 | 87.19 | 87.33 | 89.5 | 95.6

###  3.2 Image Classification

We now turn to image classification, again focusing on how drop clause affects
performance of TM. To this end, we evaluate drop clause on four benchmark
image classification datasets: MNIST, Fashion-MNIST, CIFAR-10 and CIFAR-100.
We binarize the datasets using an adaptive Gaussian thresholding procedure as
proposed in (Granmo et al., 2019). This binarization results in images with
merely $1$ bit per pixel per channel, considerably reducing the memory
overhead. For the task of image classification, we employ the Convolutional TM
(CTM).

  * •

_MNIST_ encompasses $70,000$ $28\times 28$ gray-scale images of hand written
single digits, $60,000$ for training and $10,000$ for testing. Here, we use
$8,000$ clauses with $T=6,400$ and $s=5.0$.

  * •

_Fashion-MNIST_ contains $28\times 28$ gray-scale images from the Zalando
catalogue. For this dataset, we use the same parameters as the MNIST dataset.

  * •

_CIFAR-10 and CIFAR-100_ consist of $50,000$ $32\times 32$ color images of
objects divided into $10$ categories for CIFAR-10 and $100$ for CIFAR-100.
Another $10,000$ images are provided for testing. Here, we make use of
$60,000$ clauses with $T=48,000$ and $s=10.0$.

Again, we explore the effects of four drop clause probability settings,
$p:\left\\{0.1,0.25,0.5,0.75\right\\}$, shown in Table 5. The best performance
is achieved with $p=0.25$ for the MNIST and Fashion-MNIST, while $p=0.5$ gives
the best result for the CIFAR datasets, which is equivalent to dropping a
quarter (or half) of the clauses per training iteration. Notice the
considerable performance increase, especially on the CIFAR datasets, with drop
clause of $p=0.5$. Peak accuracy on MNIST is $99.45\%$ $(\pm 0.25\%)$,
Fashion-MNIST is $92.5\%$ $(\pm 0.25\%)$. CIFAR-10 and CIFAR-100 peak at
$75.1\%$ $(\pm 0.4\%)$ and $45.2\%$ $(\pm 0.2\%)$ respectively, averaged over
$100$ runs333We also tested our model on Kuzushiji-MNIST. Our best model
achieved $97.6\%$ $(\pm 0.2\%)$, averaged over 100 runs, which is close to
ResNet-18’s $97.82\%$. We here used the same hyperparameters as for MNIST..
Apart from the accuracy gain, drop clause with $p=0.5$ reduces training time
by approximately $50\%$, for the CIFAR datasets. For instance, training time
per epoch drops from $61.83s$ to $32.58s$ for CIFAR-10. The inference time for
the drop clause CTM on CIFAR-10 is $1.5ms$ per image on one NVIDIA Tesla V100
GPU, leveraging the computation benefits of binary operations for TM
inference, and no floating point operations.

Table 5: Effect of Drop Clause on Image Classification.

CTM $p=0$ $p=.1$ $p=.25$ $p=.5$ $p=.75$ MNIST 99.3 99.3 99.45 99.35 98.2
F-MNIST 91.5 91.75 92.5 92.25 91.25 CIFAR-10 69.3 70.5 73.2 75.1 72.6
CIFAR-100 35.5 39.5 42.6 45.2 40.8

Table 6 shows the comparison of the drop clause CTM with other popular machine
learning techniques on the image classification problem. As seen, CTM
outperforms the traditional machine learning techniques by a wide margin,
further widened by the introduction of drop clause444Note that the accuracy on
CIFAR-100 is not displayed in Table 6 for other machine learning algorithms as
the accuracy is miniscule.
Table 7 contains a comparison between the drop clause CTM with some related
and state-of-the-art techniques. Binary neural networks can be represented
exactly as a propositional logic expression (Narodytska et al., 2018). As
such, they are particularly comparable to CTM and we therefore also include
results for EEV-BNN (Jia & Rinard, 2020). EEV-BNN is a binary neural network
that has been verified with Boolean satisfiability. Employing EEV-BNN, we use
the MNIST-MLP and Conv-Large BNN architectures from (Jia & Rinard, 2020) for
comparisons. The drop clause CTM significantly outperforms EEV-BNN on MNIST
and CIFAR-10, as shown in Table 7. We also compare our method with a
transformer based model of reduced complexity to make it more comparable to
our model. The Vision Nystromformer (ViN) (Jeevan & Sethi, 2021) is a vision
transformer (ViT) based model that reduces the quadratic computational
complexity of ViT by using the Nystrom methods for approximating self-
attention. It achieves $65.06\%$ accuracy on CIFAR-10 whereas the Hybrid-ViN,
which incorporates rotary positional embedding, obtains slightly better
accuracy as shown in Table 7, comparable to our model.
We also contrast our model against AlexNet with Direct Feedback Alignment
(DFA) (Webster et al., 2021) for parallel backpropagation training, which
makes it comparable to the fast training of TM. The results in Table 7 show
that AlexNet-DFA achieves similar performance on MNIST and Fashion-MNIST,
whereas it is outperformed by drop clause CTM on CIFAR-10. However, there is a
considerable difference on the CIFAR-100 dataset due to larger label space.
Finally, as drop clause is inspired from dropout, we compare our model with
the Maxout network (Goodfellow et al., 2013), which was a natural companion to
dropout. Maxout achieves significantly better performance on the CIFAR
datasets as shown in Table 7. Note that on color images, binarization can lead
to loss of important information especially as we use 1-bit per channel,
compared to 8-bits per channel for lossless color information. Also, as
previously stated, TM possesses computational advantages over these methods
along with interpretability.

Table 6: Comparison on Image Classification with Machine Learning methods

CTM CTM SVM RF K-NN XGB (DC) MNIST 99.3 99.45 93.4 93.8 95.3 96.2 F-MNIST 91.5
92.5 84.6 87.5 85.4 88.4 CIFAR-10 69.3 75.1 37.5 48.7 33.9 47.8 CIFAR-100 35.5
45.2 - - - -

Table 7: Comparison on Image Classification with different SOTA models

CTM EEV Hybrid AlexNet Maxout (DC) -BNN -ViN -DFA MNIST 99.45 98.25 96.4 98.2
99.06 F-MNIST 92.5 - - 91.66 - CIFAR-10 75.1 63.45 75.26 64.7 86.8 CIFAR-100
45.2 - - 52.62 59.52

Another point to note is that, originally, dropout can increase the
performance of basic CNNs by about $3\%$ and $6\%$ on CIFAR-10 and CIFAR-100
respectively (Srivastava et al., 2014). The drop clause method shows promising
results by improving the performance of vanilla CTM by about $6\%$ and $10\%$
on CIFAR-10 and CIFAR-100, respectively.

##  4 Enhanced Interpretability

In this section, we show how drop clause is able to enhance the interpretable
maps produced by TM and CTM for NLP and image classification tasks. We show
interpretable results on the MR dataset at the word-level and on the CIFAR-10
dataset at the pixel-level. Enhancement in interpretability is in terms of
better word representations for NLP tasks and more accurate pixel
representations for objects in images.

###  4.1 Natural Language Sentiment Analysis

We investigate local model interpretability in NLP by using a randomly
selected test example from MR: "A waste of fearless purity in the acting
craft" (additional examples can be found in Appendix C). The example was
selected among the ones that where correctly classified with drop clause and
incorrectly classified without. The purpose is to contrast how drop clause
affects interpretability. Note that for NLP, the majority of the features
appear in negated form. In order to have word-level understanding of the
model, we use a frequency-based interpretation, i.e., we highlight the
features based on how frequently they appear in clauses, as explained in
(Yadav et al., 2021). An arguable unique property of TMs is that the patterns
they produce are both descriptive (frequent) and discriminative. In other
words, each clause captures a full description of the target concept, not
merely the discrimination boundary.
Figure 1(a) highlights the top 100 most frequent features in negated form
(bright color means high frequency), present in the clauses triggered by the
given sample. Three example clauses $C_{0}$, $C_{2}$, and $C_{4}$ are shown
below for the color-coded features. In this case, the prediction is wrong.
More importantly, the literals in the conjunctions do not make sense.
The corresponding result for drop clause is depicted in Figure 1(b). Here, the
$100$ most frequent features in the negated form seem intuitive for predicting
negative sentiment. Features such as "NOT witti (witty)", "NOT grace
(graceful)", "NOT terrif (terrific)", "NOT honest", "NOT cool", or "NOT
intellig (intelligent)" generally mean absence of positive sentiment, which in
this case makes the model draw the correct conclusion (negative sentiment).
Some of the specific patterns that are responsible for predicting the correct
output are $C_{0},C_{2},$ and $C_{4}$, as shown in the figure. Although
randomly chosen, this example is representative for how TM with drop clause is
able to capture a larger variety of correct patterns than what the vanilla TM
is capable of (further exemplified in Appendix C).

(a) Without drop clause

(b) With drop clause $(p=0.75)$

Figure 1: NLP Interpretability of a sample: (a) without and (b) with drop
clause.

###  4.2 Image Classification

In image classification, TM clauses form self-contained patterns by joining
pixels into multi-pixel structures. That is, the image pixels are inputted
directly to the clauses, that are propositional AND-rules. So, Boolean
propositional expressions (clauses) capture patterns in an image which contain
pixels as literals in the clauses, that are comparatively easy for humans to
comprehend (Valiant, 1984).
The CTM forms clauses from the pixels of the square image patches obtained in
the convolution. Accordingly, we extract the top $k$ weighted clauses per
class in patch form. For visualization, we represent the non-negated pixels of
a clause as $1.0$, negated pixels as $-1.0$, and excluded pixels as $0.0$. In
additional to the image content, each clause also encodes positions in the
image where it is valid. If a certain position is invalid, the clause literal
corresponding to the pixel values is treated as $0.0$ to indicate no
activation at that location. The resulting clause masks are applied to the
image and their activation maps are added up to produce a heatmap.
In Figure 2, we compare the heatmaps produced by the vanilla CTM and the CTM
with drop clause (more such comparisons between image heatmaps can be found in
Appendix C). As can be seen from the figure, drop clause is able to capture
the object with slightly more precision. We believe this is because the
remaining clauses are forced to substitute the dropped clauses, learning to
perform their tasks. Due to the stochastic nature of learning, they will,
however, learn to perform the tasks differently than the dropped clauses. As a
result, drop clause reduces redundancy and induces diversity in the learning
of the patterns.
Figure 3 visualizes how the image decomposes into patches and how patterns in
each patch are represented by multiple clauses. The figure shows how patterns
are identified in an image by the clauses in terms of the pixels (literals in
the clause). In this case, each clause is comprised of an input of $64$ pixels
in $8\times 8$ patch form. The clauses are formed using these pixels as
literals. The pixels are simply joined together by logical _NOT_ $(\neg)$ and
_AND_ $(\land)$ operators to form Boolean propositional logic expressions. The
figure further depicts three patches that have been extracted from different
locations in the image. The clause expressions shown in Figure 3 are the ones
that are activated in that particular patch for a particular class (_ship_
class in this case). Since the clauses are logical AND-rules, localized within
the patches, they support pixel-level interpretation. The learning capability
of drop clause TM is evident from this example, that how it is able to capture
such patters from images with binary pixels, with just 1-bit per channel.

(a) Image

(b) TM $(p=0)$

(c) TM $(p=0.5)$

Figure 2: CIFAR-10 Interpretability: (b) without and (c) with DC Figure 3:
CIFAR-10 Pixel-level Interpretability - _Patches of $8\times 8$ are taken at a
time. The three clauses shown per patch are some of the top 100 highest
weighted clauses for the _ship_ class that have maximum activations in that
patch. The pixels shown in the clauses are activated in that patch. Note that,
the clauses are longer than shown here._

##  5 Enhanced Robustness

In this section, we show empirically that introduction of drop clause makes TM
more robust towards input perturbations during testing. We evaluate robustness
on both sentiment analysis and image classification555Note that we do not test
for adversarial robustness. We only test the robustness of our models against
input perturbations and corruptions..

###  5.1 Natural Language Sentiment Analysis

We select the MR dataset to test the robustness of TM on natural language
sentiment analysis. We train our models on the standard training data and
perturb the testing data to evaluate robustness towards out of distribution
changes. We monitor the decrease in testing accuracy with and without
perturbations. During testing, an input instance (sentence) is selected for
perturbation with probability $0.5$. Then, a word is chosen from this sentence
randomly with uniform probability. The selected word is swapped with the most
similar word according to the cosine similarity between their respective Glove
embedding vectors. Swapping with the most similar word results in changing the
binary feature representation by a hamming distance of $2$, while keeping the
meaning and sentiment of the sentence unchanged. The following is an MR
example demonstrating this strategy: _Magnificent drama well worth watching_
$\rightarrow$ _Splendid drama well worth watching_. The word _Magnificent_ is
changed to its synonym _Splendid_. Table 8 shows the comparison between TM and
drop clause TM on MR with and without test data perturbations. The difference
between the test accuracy on the dataset with and without perturbations is
$2.02\%$ and $1.45\%$ for the standard TM and drop clause TM respectively. In
addition, drop clause makes TM more robust compared to BiLSTM, where the
accuracy drops by $1.83\%$. The increase in TM robustness could be due to the
fact that since clauses are stochastically dropped they seem to be less prone
to pick up irrelevant or noisy patterns, making them more robust.

Table 8: Robustness Comparison on MR dataset

TM TM (Drop Clause) BiLSTM MR 75.14 78.67 77.68 MR (perturb) 73.12 77.12 75.85

Table 9: Robustness Comparison on MNIST-C dataset | CTM | CTM (Drop Clause) | BNN
---|---|---|---
MNIST | 99.3 | 99.45 | 98.25
MNIST-C | 88.12 | 91.75 | 85.5

###  5.2 Image Classification

We compare the robustness of TM and drop clause TM using the MNIST-C dataset
(Mu & Gilmer, 2019), which is a _corrupted_ version of MNIST. It consists of
$15$ corruptions such as Gaussian blur, scale, rotate, shear, impulse noise,
canny edges, fog etc. We train our models on the standard MNIST training data
without any augmentations. During testing, we select whether to use non-
corrupted or corrupted test image with probability $0.5$. We then select one
of the $15$ corruptions to apply on the test image with uniform probability.
Drop clause enhances the robustness of CTM, as can be seen in Table 9. There
is a drop of $11.18\%$ for the standard CTM whereas the drop in accuracy is
reduced to $7.7\%$ with drop clause. Also, from Table 9, we observe that both
the TM versions are more robust than binarized neural networks (BNN)666The
MNIST-MLP architecture from (Jia & Rinard, 2020) is used here., whose accuracy
drops drops by $12.75\%$.

##  6 Discussion

To summarize our results, drop clause improves the performance of the TM,
enhancing the advantages TMs have over neural networks and traditional machine
learning techniques when it comes to computational complexity, memory
consumption, training and inference time, and perhaps most importantly,
interpretability. The computational advantages make TMs suitable for federated
learning and deployment on edge devices. On the other hand, the TM still
achieves lower accuracy on the datasets we use here when compared to some deep
neural network models. We conjecture that the accuracy gap could be caused by
the Booleanization information loss, e.g., going from 3x8 bits pixel values to
3 Boolean values (3 bits). Thresholding the 3 color channels separately may
also be sub-optimal because the combinations of the three colour channels
produce different colours and textures. Another challenge arises in NLP tasks.
Here, pretrained models have been dominating, leveraging unlabelled data.
Important models include word2vec, GloVe, BERT, and GPT. TMs require Boolean
input, making it difficult to leverage existing high dimensional embeddings,
impeding performance, with the exception of enhancing the input with GloVe-
derived synonyms (Yadav et al., 2021). Also, the pixel-level interpretability
on image classification can be difficult for humans to interpret as the
Boolean expressions for clauses capturing patterns can be quite long
containing numerous pixels, especially for large images.

##  7 Conclusion

In this paper, we propose _drop clause_ as a technique to improve the
generalization ability of the TM. Drop clause enhances stochasticity during
training, to provide more diverse patterns. As a result, TM performance is
significantly boosted which is empirically shown on a diverse collection of
datasets, both in terms of accuracy and training time. We further show how
drop clause improves the pattern recognition capabilities of TM,
simultaneously improving pattern interpretability. When comparing our model
with state-of-the-art deep learning models, we observe competitive accuracy
levels. Since TM is more akin to traditional machine learning techniques, we
also compare it with a selection of those, reporting superior accuracy results
for the TM. We further showcase pixel-level interpretability on the CIFAR-10
dataset and word-level interpretability on the MR dataset. We finally
establish that drop clause improves the robustness of the TM towards data
corruptions and perturbations during testing.

## References

  * Abeyrathna et al. (2020) Abeyrathna, K. D., Granmo, O.-C., Zhang, X., Jiao, L., and Goodwin, M.  The Regression Tsetlin Machine - A Novel Approach to Interpretable Non-Linear Regression.  _Philosophical Transactions of the Royal Society A_ , 378, 2020.
  * Abeyrathna et al. (2020) Abeyrathna, K. D., Pussewalage, H. S. G., Ranasinghea, S. N., Oleshchuk, V. A., and Granmo, O.-C.  Intrusion Detection with Interpretable Rules Generated Using the Tsetlin Machine.  In _2020 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2020.
  * Abeyrathna et al. (2021) Abeyrathna, K. D., Granmo, O.-C., and Goodwin, M.  Extending the Tsetlin Machine With Integer-Weighted Clauses for Increased Interpretability.  _IEEE Access_ , 9, 2021.
  * Bau et al. (2017) Bau, D., Zhou, B., Khosla, A., Oliva, A., and Torralba, A.  Network dissection: Quantifying interpretability of deep visual representations.  _CoRR_ , abs/1704.05796, 2017.  URL http://arxiv.org/abs/1704.05796.
  * Berge et al. (2019) Berge, G. T., Granmo, O.-C., Tveit, T. O., Goodwin, M., Jiao, L., and Matheussen, B. V.  Using the Tsetlin Machine to Learn Human-Interpretable Rules for High-Accuracy Text Categorization with Medical Applications.  _IEEE Access_ , 7:115134–115146, 2019.  ISSN 2169-3536.  doi: 10.1109/ACCESS.2019.2935416.
  * Devlin et al. (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://www.aclweb.org/anthology/N19-1423.
  * Ghorbani et al. (2019) Ghorbani, A., Abid, A., and Zou, J.  Interpretation of neural networks is fragile.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):3681–3688, Jul. 2019.  doi: 10.1609/aaai.v33i01.33013681.  URL https://ojs.aaai.org/index.php/AAAI/article/view/4252.
  * Goodfellow et al. (2013) Goodfellow, I., Warde-Farley, D., Mirza, M., Courville, A., and Bengio, Y.  Maxout networks.  In Dasgupta, S. and McAllester, D. (eds.), _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pp. 1319–1327, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.  URL https://proceedings.mlr.press/v28/goodfellow13.html.
  * Granmo (2018) Granmo, O.-C.  The Tsetlin Machine - A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic.  _arXiv preprint arXiv:1804.01508_ , 2018.  URL https://arxiv.org/abs/1804.01508.
  * Granmo et al. (2019) Granmo, O.-C., Glimsdal, S., Jiao, L., Goodwin, M., Omlin, C. W., and Berge, G. T.  The Convolutional Tsetlin Machine.  _arXiv preprint arXiv:1905.09688_ , 2019.  URL https://arxiv.org/abs/1905.09688.
  * Jain & Wallace (2019) Jain, S. and Wallace, B. C.  Attention is not Explanation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 3543–3556, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1357.  URL https://www.aclweb.org/anthology/N19-1357.
  * Jeevan & Sethi (2021) Jeevan, P. and Sethi, A.  Vision xformers: Efficient attention for image classification, 2021.
  * Jia & Rinard (2020) Jia, K. and Rinard, M.  Efficient exact verification of binarized neural networks.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1782–1795. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1385974ed5904a438616ff7bdb3f7439-Paper.pdf.
  * Jiao et al. (2021) Jiao, L., Zhang, X., Granmo, O.-C., and Abeyrathna, K. D.  On the Convergence of Tsetlin Machines for the XOR Operator.  _arXiv preprint arXiv:2101.02547_ , 2021.
  * Kim (2014) Kim, Y.  Convolutional neural networks for sentence classification.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pp. 1746–1751, Doha, Qatar, October 2014. Association for Computational Linguistics.  doi: 10.3115/v1/D14-1181.  URL https://aclanthology.org/D14-1181.
  * Lei et al. (2021) Lei, J., Rahman, T., Shafik, R., Wheeldon, A., Yakovlev, A., Granmo, O.-C., Kawsar, F., and Mathur, A.  Low-Power Audio Keyword Spotting Using Tsetlin Machines.  _Journal of Low Power Electronics and Applications_ , 11, 2021.  URL https://www.mdpi.com/2079-9268/11/2/18.
  * Lei et al. (2019) Lei, Z., Yang, Y., Yang, M., Zhao, W., Guo, J., and Liu, Y.  A human-like semantic cognition network for aspect-level sentiment classification.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):6650–6657, Jul. 2019.  doi: 10.1609/aaai.v33i01.33016650.  URL https://ojs.aaai.org/index.php/AAAI/article/view/4635.
  * Liu et al. (2018) Liu, R., Lehman, J., Molino, P., Such, F. P., Frank, E., Sergeev, A., and Yosinski, J.  An intriguing failing of convolutional neural networks and the coordconv solution.  In _Proceedings of the 32Nd International Conference on Neural Information Processing Systems_ , NIPS’18, pp. 9628–9639, 2018.
  * Mu & Gilmer (2019) Mu, N. and Gilmer, J.  MNIST-C: A robustness benchmark for computer vision.  _CoRR_ , abs/1906.02337, 2019.  URL http://arxiv.org/abs/1906.02337.
  * Narodytska et al. (2018) Narodytska, N., Kasiviswanathan, S., Ryzhyk, L., Sagiv, M., and Walsh, T.  Verifying properties of binarized deep neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Nori et al. (2019) Nori, H., Jenkins, S., Koch, P., and Caruana, R.  Interpretml: A unified framework for machine learning interpretability.  _CoRR_ , abs/1909.09223, 2019.  URL http://arxiv.org/abs/1909.09223.
  * Noveck et al. (1991) Noveck, I., Lea, R. B., Davidson, G. M., and O’brien, D.  Human reasoning is both logical and pragmatic.  _Intellectica_ , 11:81–109, 1991.
  * Peters et al. (2018) Peters, M., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., and Zettlemoyer, L.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pp. 2227–2237, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.  doi: 10.18653/v1/N18-1202.  URL https://www.aclweb.org/anthology/N18-1202.
  * Qin et al. (2020) Qin, Q., Hu, W., and Liu, B.  Feature projection for improved text classification.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 8161–8171, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.726.  URL https://aclanthology.org/2020.acl-main.726.
  * Radhakrishnan et al. (2018) Radhakrishnan, A., Durham, C., Soylemezoglu, A., and Uhler, C.  Patchnet: Interpretable neural networks for image classification, 2018\.
  * Robbins (2007) Robbins, H.  A stochastic approximation method.  _Annals of Mathematical Statistics_ , 22:400–407, 2007\.
  * Rudin (2019) Rudin, C.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  _Nature Machine Intelligence_ , 1, 2019.  doi: 10.1038/s42256-019-0048-x.  URL https://doi.org/10.1038/s42256-019-0048-x.
  * Selvaraju et al. (2017) Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , pp. 618–626, 2017.  doi: 10.1109/ICCV.2017.74.
  * Serrano & Smith (2019) Serrano, S. and Smith, N. A.  Is attention interpretable?  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 2931–2951, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1282.  URL https://www.aclweb.org/anthology/P19-1282.
  * Simonyan et al. (2014) Simonyan, K., Vedaldi, A., and Zisserman, A.  Deep inside convolutional networks: Visualising image classification models and saliency maps, 2014.
  * Srivastava et al. (2014) Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15(56):1929–1958, 2014.  URL http://jmlr.org/papers/v15/srivastava14a.html.
  * Tang et al. (2015) Tang, J., Qu, M., and Mei, Q.  PTE: predictive text embedding through large-scale heterogeneous text networks.  _CoRR_ , abs/1508.00200, 2015.  URL http://arxiv.org/abs/1508.00200.
  * Valiant (1984) Valiant, L. G.  A Theory of the Learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Webster et al. (2021) Webster, M. B., Choi, J., and changwook Ahn.  Learning the connections in direct feedback alignment, 2021.  URL https://openreview.net/forum?id=zgGmAx9ZcY.
  * Yadav et al. (2021) Yadav, R. K., Jiao, L., Granmo, O.-C., and Goodwin, M.  Distributed Word Representation in Tsetlin Machine.  _arXiv preprint arXiv:2104.06901_ , 2021.  URL https://arxiv.org/abs/2104.06901.
  * Yadav et al. (2021) Yadav, R. K., Jiao, L., Granmo, O.-C., and Goodwin, M.  Human-Level Interpretable Learning for Aspect-Based Sentiment Analysis.  In _The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)_. AAAI, 2021.
  * Zhang et al. (2018) Zhang, Q., Wu, Y. N., and Zhu, S.-C.  Interpretable convolutional neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 8827–8836, 2018.
  * Zhang et al. (2021) Zhang, X., Jiao, L., Granmo, O.-C., and Goodwin, M.  On the convergence of Tsetlin machines for the identity-and not operators.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.  doi: 10.1109/TPAMI.2021.3085591.
  * Zhu & Koniusz (2020) Zhu, H. and Koniusz, P.  Simple spectral graph convolution.  In _International Conference on Learning Representations_ , 2020.

##  Appendix A Appendix

###  A.1 Tsetlin Machine

Figure 4: A two-action Tsetlin Automaton with $2N$ states.

Figure 5: TM learning dynamics for an XOR-gate training sample, with input
($x_{1}=0,x_{2}=1$) and output target $y=1$.

#### Structure.

A TM in its simplest form takes a feature vector
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{o}]\in\\{0,1\\}^{o}$ of $o$ propositional
values as input and assigns the vector a class $\hat{y}\in\\{0,1\\}$. To
minimize classification error, the TM produces $n$ self-contained patterns. In
brief, the input vector $\mathbf{x}$ provides the literal set
$L=\\{l_{1},l_{2},\ldots,l_{2o}\\}=\\{x_{1},x_{2},\ldots,x_{o},\lnot
x_{1},\lnot x_{2},\ldots,\lnot x_{o}\\}$, consisting of the input features and
their negations. By selecting subsets $L_{j}\subseteq L$ of the literals, the
TM can build arbitrarily complex patterns, ANDing the selected literals to
form conjunctive clauses:

$C_{j}(\mathbf{x})=\bigwedge_{l_{k}\in L_{j}}l_{k}.$ (4)

Above, $j\in\\{1,2,\ldots,n\\}$ refers to a particular clause $C_{j}$ and
$k\in\\{1,2,\ldots,2o\\}$ refers to a particular literal $l_{k}$. As an
example, the clause $C_{j}(\mathbf{x})=x_{1}\land\lnot x_{2}$ consists of the
literals $L_{j}=\\{x_{1},\lnot x_{2}\\}$ and evaluates to $1$ when $x_{1}=1$
and $x_{2}=0$.

The TM assigns one TA per literal $l_{k}$ per clause $C_{j}$ to build the
clauses. The TA assigned to literal $l_{k}$ of clause $C_{j}$ decides whether
$l_{k}$ is _Excluded_ or _Included_ in $C_{j}$. Figure 4 depicts a two-action
TA with $2N$ states. For states $1$ to $N$, the TA performs action _Exclude_
(Action 1), while for states $N+1$ to $2N$ it performs action _Include_
(Action 2). As feedback to the action performed, the environment responds with
either a Reward or a Penalty. If the TA receives a Reward, it moves deeper
into the side of the action. If it receives a Penalty, it moves towards the
middle and eventually switches action.

With $n$ clauses and $2o$ literals, we get $n\times 2o$ TAs. We organize the
states of these in a $n\times 2o$ matrix
$A=[a_{k}^{j}]\in\\{1,2,\ldots,2N\\}^{n\times 2o}$. We will use the function
$g(\cdot)$ to map the automaton state $a_{k}^{j}$ to Action $0$ (_Exclude_)
for states $1$ to $N$ and to Action $1$ (_Include_) for states $N+1$ to $2N$:
$g(a_{k}^{j})=a_{k}^{j}>N$.

We can connect the states $a_{k}^{j}$ of the TAs assigned to clause $C_{j}$
with its composition as follows:

$C_{j}(\mathbf{x})=\bigwedge_{l_{k}\in
L_{j}}l_{k}=\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow l_{k}\right].$
(5)

Here, $l_{k}$ is one of the literals and $a_{k}^{j}$ is the state of its TA in
clause $C_{j}$. The logical _imply_ operator $\Rightarrow$ implements the
_Exclude_ /_Include_ action. That is, the _imply_ operator is always $1$ if
$g(a_{k}^{j})=0$ (_Exclude_), while if $g(a_{k}^{j})=1$ (_Include_) the truth
value is decided by the truth value of the literal.

#### Classification.

Classification is performed as a majority vote. The odd-numbered half of the
clauses vote for class $\hat{y}=0$ and the even-numbered half vote for
$\hat{y}=1$:

$\hat{y}=0\leq\sum_{j=1,3,\ldots}^{n-1}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right]-\sum_{j=2,4,\ldots}^{n}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right].$ (6)

As such, the odd-numbered clauses have positive polarity, while the even-
numbered ones have negative polarity. As an example, consider the input vector
$\mathbf{x}=[0,1]$ in the lower part of Figure 5. The figure depicts two
clauses of positive polarity, $C_{1}(\mathbf{x})=x_{1}\land\lnot x_{2}$ and
$C_{3}(\mathbf{x})=\lnot x_{1}\land\lnot x_{2}$ (the negative polarity clauses
are not shown). Both of the clauses evaluate to zero, leading to class
prediction $\hat{y}=0$.

Input | Clause |  1 |  0
---|---|---|---
Literal | 1 0 | 1 0
Include Literal | P(Reward) |  $\frac{s-1}{s}$ NA | 0 0
P(Inaction) |  $\ \ \frac{1}{s}$ NA |  $\frac{s-1}{s}$ $\frac{s-1}{s}$
| P(Penalty) | 0 NA |  $\ \ \frac{1}{s}$ $\frac{1}{s}$
Exclude Literal | P(Reward) |  0 $\frac{1}{s}$ |  $\ \ \frac{1}{s}$ $\frac{1}{s}$
P(Inaction) |  $\ \ \frac{1}{s}$ $\frac{s-1}{s}$ |  $\frac{s-1}{s}$ $\frac{s-1}{s}$
| P(Penalty) |  $\frac{s-1}{s}$ 0 | 0 0
Table 10: Type I Feedback
Input | Clause |  1 |  0
---|---|---|---
Literal | 1 0 | 1 0
Include Literal | P(Reward) | 0 NA | 0 0
P(Inaction) | 1.0 NA | 1.0 1.0
| P(Penalty) | 0 NA | 0 0
Exclude Literal | P(Reward) | 0 0 | 0 0
P(Inaction) | 1.0 0 | 1.0 1.0
| P(Penalty) | 0 1.0 | 0 0
Table 11: Type II Feedback

#### Learning.

The upper part of Figure 5 illustrates learning. A TM learns online,
processing one training example $(\mathbf{x},y)$ at a time. Based on
$(\mathbf{x},y)$, the TM rewards and penalizes its TAs, which amounts to
incrementing and decrementing their states. There are two kinds of feedback:
Type I Feedback produces frequent patterns and Type II Feedback increases the
discrimination power of the patterns.

Type I feedback is given stochastically to clauses with positive polarity when
$y=1$ and to clauses with negative polarity when $y=0$. Conversely, Type II
Feedback is given stochastically to clauses with positive polarity when $y=0$
and to clauses with negative polarity when $y=1$. The probability of a clause
being updated is based on the vote sum $v$:
$v=\sum_{j=1,3,\ldots}^{n-1}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right]-\sum_{j=2,4,\ldots}^{n}\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}\right]$. The voting error is calculated as:

$\epsilon=\begin{cases}T-v&y=1\\\ T+v&y=0.\end{cases}$ (7)

Here, $T$ is a user-configurable voting margin yielding an ensemble effect.
The probability of updating each clause is
$P(\mathrm{Feedback})=\frac{\epsilon}{2T}$.

After random sampling from $P(\mathrm{Feedback})$ has decided which clauses to
update, the following TA state updates can be formulated as matrix additions,
subdividing Type I Feedback into feedback Type Ia and Type Ib:

$A^{*}_{t+1}=A_{t}+F^{\mathit{II}}+F^{Ia}-F^{Ib}.$ (8)

Here, $A_{t}=[a^{j}_{k}]\in\\{1,2,\ldots,2N\\}^{n\times 2o}$ contains the
states of the TAs at time step $t$ and $A^{*}_{t+1}$ contains the updated
state for time step $t+1$ (before clipping). The matrices
$F^{\mathit{Ia}}\in\\{0,1\\}^{n\times 2o}$ and
$F^{\mathit{Ib}}\in\\{0,1\\}^{n\times 2o}$ contains Type I Feedback. A zero-
element means no feedback and a one-element means feedback. As shown in Table
10, two rules govern Type I feedback:

  * •

Type Ia Feedback is given with probability $\frac{s-1}{s}$ whenever both
clause and literal are $1$-valued.777Note that the probability $\frac{s-1}{s}$
is replaced by $1$ when boosting true positives. It penalizes _Exclude_
actions and rewards _Include_ actions. The purpose is to remember and refine
the patterns manifested in the current input $\mathbf{x}$. This is achieved by
increasing selected TA states. The user-configurable parameter $s$ controls
pattern frequency, i.e., a higher $s$ produces less frequent patterns.

  * •

Type Ib Feedback is given with probability $\frac{1}{s}$ whenever either
clause or literal is $0$-valued. This feedback rewards _Exclude_ actions and
penalizes _Include_ actions to coarsen patterns, combating overfitting. Thus,
the selected TA states are decreased.

The matrix $F^{\mathit{II}}\in\\{0,1\\}^{n\times 2o}$ contains Type II
Feedback to the TAs, given per Table 11.

  * •

Type II Feedback penalizes _Exclude_ actions to make the clauses more
discriminative, combating false positives. That is, if the literal is
$0$-valued and the clause is $1$-valued, TA states below $N+1$ are increased.
Eventually the clause becomes $0$-valued for that particular input, upon
inclusion of the $0$-valued literal.

The final updating step for training example $(\mathbf{x},y)$ is to clip the
state values to make sure that they stay within value $1$ and $2N$:

$A_{t+1}=\mathit{clip}\left(A^{*}_{t+1},1,2N\right).$ (9)

For example, both of the clauses in Figure 5 receives Type I Feedback over
several training examples, making them resemble the input associated with
$y=1$.

(a)

(b)

Figure 6: Example of inference (a) and learning (b) for the Noisy 2D XOR
Problem.

(a)

(b)

Figure 7: (a) Goal state for the Noisy 2D XOR Problem. (b) Illustration of
image, filter and patches.

###  A.2 Convolutional Tsetlin Machine

Consider a set of images $\mathcal{X}=\\{\mathbf{x}_{e}|1\leq e\leq E\\}$,
where $e$ is the index of the images. Each image is of size $d_{x}\times
d_{y}$ and consists of $d_{z}$ binary layers, illustrated in Figure 7b. A
classic TM models such an image with an input vector
$\mathbf{x}=[x_{k}]\in\\{0,1\\}^{d_{x}\times d_{y}\times d_{z}}$ that contains
$d_{x}\times d_{y}\times d_{z}$ input features. Accordingly, each clause is
composed from $d_{x}\times d_{y}\times d_{z}\times 2$ literals.

#### Structure.

The CTM (CTM) (Granmo et al., 2019) performs a convolution over the input
image $\mathbf{x}$, dividing it into patches with spatial dimensions
$d_{w}\times d_{w}$. That is, the input vector
$\mathbf{x}=[x_{k}]\in\\{0,1\\}^{d_{x}\times d_{y}\times d_{z}}$ produces
$B=\left(\left\lceil\frac{d_{x}-d_{w}}{q}\right\rceil+1\right)\times\left(\left\lceil\frac{d_{y}-d_{w}}{q}\right\rceil+1\right)$
patches, with $q$ being the step size of the convolution. For instance, Figure
7b illustrates $B=(6-3+1)\times(6-3+1)=16$ patches of size $3\times 3$,
assuming step size $q=1$.

Each patch $b\in\\{1,2,\ldots,B\\}$, in turn, yields an input vector
$\mathbf{x}^{b}=[x_{k}^{b}]\in\\{0,1\\}^{d_{w}\times d_{w}\times d_{z}}$ with
a corresponding literal vector
$\mathbf{l}^{b}=[l_{k}^{b}]\in\\{0,1\\}^{d_{w}\times d_{w}\times d_{z}\times
2}$. The CTM becomes location aware (Liu et al., 2018) by augmenting each
patch input vector $\mathbf{x}^{b}$ with the coordinates of $\mathbf{x}^{b}$
within $\mathbf{x}$, using threshold-based encoding (Abeyrathna et al., 2020).

#### Classification.

The CTM is based on the classic TM procedure for classification (Eqn. 6).
However, we now have $B$ input vectors $\mathbf{x}^{b}$ per image rather than
a single input vector $\mathbf{x}$. The convolution is performed by evaluating
each clause $C_{j}$ on each input vector $\mathbf{x}^{b}$, i.e., calculating
$\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow l_{k}^{b}\right]$, and then
ORing the evaluations per clause:

$\hat{y}=0\leq\sum_{j=1,3,\ldots}^{n-1}\bigvee_{b=1}^{B}\left[\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}^{b}\right]\right]-\sum_{j=2,4,\ldots}^{n}\bigvee_{b=1}^{B}\left[\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}^{b}\right]\right].$ (10)

Figure 6(a) provides an example where a $3\times 3$ input image produces four
$2\times 2$ patches. The CTM has four clauses of positive polarity and four
clauses of negative polarity. Only one of the clauses of positive polarity
matches. This clause matches the upper left corner of the input image, hence
evaluating to $1$. Accordingly, the net output sum is $+1$, yielding output
$\hat{y}=1$.

#### Learning.

CTM learning leverages the TM learning procedure, per Eqn. 8 and Eqn. 9.
However, when giving Type Ia or Type II Feedback to each clause $C_{j}$, the
CTM does not use the original input vector $\mathbf{x}$. Instead, it randomly
selects one of the patch input vectors $\mathbf{x}^{b}$ that made the clause
evaluate to $1$:

$\mathbf{x}^{b}_{j}=\mathit{RandomChoice}\left(\left\\{\mathbf{x}^{b}\left|\bigwedge_{k=1}^{2o}\left[g(a_{k}^{j})\Rightarrow
l_{k}^{b}\right]=1,1\leq b\leq B\right.\right\\}\right).$ (11)

For Type Ib Feedback, on the other hand, CTM follows the standard updating
scheme.

The reason for randomly selecting a patch input vector $\mathbf{x}^{b}$ is to
have each clause extract a certain sub-pattern, and the randomness of the
uniform distribution statistically spreads the clauses for different sub-
patterns in the target image.

Figure 6(b) demonstrates a learning step. Only a single clause has recognized
the input. Assuming a summation target (margin) of $T=2$ and net clause output
sum $+1$ the probability of giving each clause feedback becomes
$P(Feedback)=\frac{(2-1)}{2\cdot 2}=0.25$. Since the training example is
$y=1$, the positive polarity clauses receives Type I Feedback with probability
$0.25$, while the negative polarity clauses receive Type II feedback again
with probability $0.25$. After several such updates, we have a more balanced
representation of the input patterns in Figure 7(a), with two clauses now
recognizing the input.

###  A.3 Convergence Insights

It is analyzed in (Zhang et al., 2021) and (Jiao et al., 2021) for the
convergence properties of the vanilla TM for 1-bit case and XOR case
respectively. Here we will briefly analyse the impact of the introduced
randomized clause drop on the convergence. For the 1-bit case, the work in
(Zhang et al., 2021) is to study the convergence feature of a TM with only one
clause. When the randomized clause drop proposed is adopted, it will not
influence the conclusions drawn in (Zhang et al., 2021) and the reasons are as
follows. The main difference between the proposed algorithm and the vanilla TM
is that the clause in this work will not be updated upon each given training
sample, but according to a pre-defined probability. In other words, the clause
is updated based on a randomly down-sampled subset as a new training set
compared with the original training data. Given infinite training data and
ideally randomized down-sampling, the statistics of the samples in the subset
is kept the same as the original training data set and the number of training
samples is also sufficient. For this reason, the clause can still observe
sufficient number of training samples and can also observe sufficient
varieties of the training samples. In addition, the other updating rules are
unchanged compared with the vanilla TM. Therefore, all conclusions in (Zhang
et al., 2021) hold for the newly proposed algorithm.

For the XOR case, there are two sub-patterns in the XOR operator and the TM is
proven to be able to converge and learn both sub-patterns when threshold value
$T$ is correctly configured (Jiao et al., 2021). According the the analysis in
the previous paragraph, we understand that the training samples for the new
algorithm is a down-sampled version of the original data set and the
statistics of the samples is kept the same due to the ideal randomness. If the
training samples with only one sub-pattern are given, the randomized down
sampled data, given infinite time horizon, will still offer sufficient samples
with the same probability distribution compared with the original training
set. Therefore, Lemma 1 and Lemma 2 in (Jiao et al., 2021) hold. In fact, when
the training samples with both sub-patterns are given, Lemma 3 and Lemma 4 in
(Jiao et al., 2021) still hold. The reason is that ideal randomly down-
sampling will not make the new training data biased in terms of the sub-
patterns and thus will not change the nature of the recurrence for the
clauses. Clearly, Lemma 5 in (Jiao et al., 2021) is also true because the
newly introduced process will not change the role of $T$. Theorem 2 in (Jiao
et al., 2021) is therefore self-evident. Indeed, the conclusion derived in
(Jiao et al., 2021) is applicable to the algorithm with drop clause.

For the 1-bit case, as the analysis is to study the convergence feature of one
clause, the randomized clause drop will not influence the conclusions drawn in
(Zhang et al., 2021). In this proposed algorithm, the clause will be updated
randomly upon each given training sample. Consider infinite time horizon, the
clause can still observe sufficient number of training samples. In addition,
due to the randomness designed in this algorithm, the clause can also observe
sufficient varieties of the training samples. In short, the clause is given a
randomly down-sampled subset as the new training set from the original
training data. Given infinite training data and ideally randomized down-
sampling, the statistics of the training data set is kept the same and the
number of training samples are sufficient. Therefore, all conclusions in
(Zhang et al., 2021) for the newly proposed algorithm. The main reason is that
the randomized clause drop employed in this paper will only reduce the number
of training samples that is to be observed by the TM. Given the sufficient
randomized

##  Appendix B Related Work

There has been a surge of research in interpretable AI. Most of the studies
focus on making neural networks more interpretable. Currently, state-of-the-
art techniques use visual explanations and gradient interpretability. We
briefly discuss selected related studies in this section. One approach is to
compute the gradients of the class scores for an input image to visualize
which parts of the input image impact the classification (Simonyan et al.,
2014). Another approach to visualize class-specific score maps is introduced
in (Zhang et al., 2018). The technique forces each filter in the top
convolutional layers to learn a class-specific object by adding a modified
mutual information loss. Training is end-to-end by adding the local filter
loss to the task-specific loss. These steps produce a map of interest for the
top convolutional layers. In (Radhakrishnan et al., 2018), the authors propose
a two-stage approach. The first stage learns to estimate the conditional
probability distribution of patches of pixels separately. The second stage, in
turn, averages these estimates to obtain a global assessment. The Grad-CAM
method, proposed in (Selvaraju et al., 2017), has been widely employed to
visualize CNN outputs. Grad-CAM uses the gradients of a target class from the
final convolution layer to produce a coarse localization map. The map
highlights the regions in the image used by the neural network for predicting
the concept. The work in (Bau et al., 2017) analyses how different layers,
training conditions, model architecture, layer width, and accuracy impact
visual interpretability.

NLP model interpretation methods largely visualize attention weights for
words. Example models include BERT and contextualized embedding (Devlin et
al., 2019; Peters et al., 2018), which capture the semantic relatedness among
words using context. However, the weights assigned by the attention vector to
each input do not necessarily provide a faithful explanation of classification
(Serrano & Smith, 2019; Jain & Wallace, 2019). Also, a general
interpretability toolkit called InterpretML was developed (Nori et al., 2019)
which explains linear machine learning algorithms and uses methods such as
LIME to explain black-box models. However, the toolkit only outputs feature
scores.

Overall, state-of-the-art methods use feature importance maps for
interpretation, both for image classification- and NLP models. These maps only
show where the neural network is “looking”. Such an approach is not truly
interpretable because one does not explain why attention is where it is. Many
researchers have attempted to replicate more human-level interpretation
behavior in neural networks (Lei et al., 2019), but have largely failed so
far. In this paper, we improve the performance of the TM by introducing a
novel method called drop clause. We also evaluate its convergence, accuracy,
computation time, and interpretability. Additionally, we show how
interpretable boolean expressions straightforwardly map to classification
decisions, both in NLP and image classification.

##  Appendix C Enhanced Interpretability Examples

(a) TM without drop clause

(b) TM with drop clause $(p=0.75)$

Figure 8: Natural Language Sentiment Analysis Interpretability: Example 1

(a) TM without drop clause

(b) TM with drop clause $(p=0.75)$

Figure 9: Natural Language Sentiment Analysis Interpretability: Example 2

Image | TM Heatmap | TM $(p=0.5)$ Heatmap
---|---|---
|  |
|  |
|  |
|  |
|  |
|  |
|  |
|  |

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

(t)

(u)

(v)

(w)

(x)

Figure 10: CIFAR Heatmaps