The Convolutional Tsetlin Machine
  Convolutional neural networks (CNNs) have obtained astounding successes for
important pattern recognition tasks, but they suffer from high computational
complexity and the lack of interpretability. The recent Tsetlin Machine (TM)
attempts to address this lack by using easy-to-interpret conjunctive clauses in
propositional logic to solve complex pattern recognition problems. The TM
provides competitive accuracy in several benchmarks, while keeping the
important property of interpretability. It further facilitates hardware-near
implementation since inputs, patterns, and outputs are expressed as bits, while
recognition and learning rely on straightforward bit manipulation. In this
paper, we exploit the TM paradigm by introducing the Convolutional Tsetlin
Machine (CTM), as an interpretable alternative to CNNs. 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. To make
the clauses location-aware, each patch is further augmented with its
coordinates within the image. The output of a convolution clause is obtained
simply by ORing the outcome of evaluating the clause on each patch. In the
learning phase of the TM, clauses that evaluate to 1 are contrasted against the
input. For the CTM, we instead contrast against one of the patches, randomly
selected among the patches that made the clause evaluate to 1. Accordingly, the
standard Type I and Type II feedback of the classic TM can be employed
directly, without further modification. The CTM obtains a peak test accuracy of
99.4% on MNIST, 96.31% on Kuzushiji-MNIST, 91.5% on Fashion-MNIST, and 100.0%
on the 2D Noisy XOR Problem, which is competitive with results reported for
simple 4-layer CNNs, BinaryConnect, Logistic Circuits and an FPGA-accelerated
Binary CNN.
