Tsetlin Machine for Logical Learning and Reasoning With Graphs

License Maintenance

"The Tsetlin machine is a new universal artificial intelligence (AI) method that learns simple logical rules to understand complex things, similar to how an infant uses logic to learn about the world. Being logical, the rules become understandable to humans. Yet, unlike all other intrinsically explainable techniques, Tsetlin machines are drop-in replacements for neural networks by supporting classification, convolution, regression, reinforcement learning, auto-encoding, language models, and natural language processing. They are further ideally suited for cutting-edge hardware solutions of low cost, enabling nanoscale intelligence, ultralow energy consumption, energy harvesting, unrivaled inference speed, and competitive accuracy."

This project implements the Graph Tsetlin Machine.

Features
Installation
Tutorial
Demos
Example Use Case
Graph Tsetlin Machine Basics
Paper
CUDA Configurations
Roadmap
Licence

Features

Processes directed and labeled multigraphs
Vector symbolic node properties and edge types
Nested (deep) clauses
Arbitrarily sized inputs
Incorporates Vanilla, Multiclass, Convolutional, and Coalesced Tsetlin Machines
Rewritten faster CUDA kernels

Installation

pip3 install graphtsetlinmachine

python ./setup.py sdist
pip3 install dist/GraphTsetlinMachine-0.3.4.tar.gz

Tutorial

In this tutorial, you create graphs for the Noisy XOR problem and then train and test the Graph Tsetlin Machine on these.

Noisy XOR gives four kinds of graphs, shown below:

Observe how each node has one of two properties: A or B. If both of the graph's nodes have the same property, the graph is given the class label $Y=0$. Otherwise, it is given the class label $Y=1$.

The task of the Graph Tsetlin Machine is to assign the correct class label to each graph when the labels used for training are noisy.

Initialization

Start by creating the training graphs using the Graphs construct:

graphs_train = Graphs(
    10000,
    symbols = ['A', 'B'],
    hypervector_size = 32,
    hypervector_bits = 2
)

You initialize the graphs as follows:

Number of Graphs. The first number sets how many graphs you are going to create. Here, you prepare for creating 10,000 graphs.
Symbols. Next, you find the symbols A and B. You use these symbols to assign properties to the nodes of the graphs. You can define as many symbols as you like. For the Noisy XOR problem, you only need two.
Vector Symbolic Representation (Hypervectors). You also decide how large hypervectors you would like to use to store the symbols. Larger hypervectors room more symbols. Since you only have two symbols, set the size to 32. Finally, you decide how many bits to use for representing each symbol. Use 2 bits for this tutorial. You then get 32*31/2 = 496 unique bit pairs - plenty of space for two symbols!
Generation and Compilation. The generation and compilation of hypervectors happen automatically during initialization, using sparse distributed codes.

Adding Nodes

The next step is to set how many nodes you want in each of the 10,000 graphs you are building. For the Noisy XOR problem, each graph has two nodes:

for graph_id in range(10000):
    graphs_train.set_number_of_graph_nodes(graph_id, 2)

After doing that, you prepare for adding the nodes:

graphs_train.prepare_node_configuration()

You add the two nodes to the graphs as follows, giving them one outgoing edge each:

for graph_id in range(10000):
   number_of_outgoing_edges = 1
   graphs_train.add_graph_node(graph_id, 'Node 1', number_of_outgoing_edges)
   graphs_train.add_graph_node(graph_id, 'Node 2', number_of_outgoing_edges)

Adding Edges

You are now ready to prepare for adding edges:

graphs_train.prepare_edge_configuration()

Next, you connect the two nodes of each graph:

for graph_id in range(10000):
    edge_type = "Plain"
    graphs_train.add_graph_node_edge(graph_id, 'Node 1', 'Node 2', edge_type)
    graphs_train.add_graph_node_edge(graph_id, 'Node 2', 'Node 1', edge_type)

You need two edges because you build directed graphs, and with two edges you cover both directions. Use only one edge type, named Plain.

Adding Properties and Class Labels

In the last step, you randomly assign property A or B to each node.

Y_train = np.empty(10000, dtype=np.uint32)
for graph_id in range(10000):
    x1 = random.choice(['A', 'B'])
    x2 = random.choice(['A', 'B'])

    graphs_train.add_graph_node_property(graph_id, 'Node 1', x1)
    graphs_train.add_graph_node_property(graph_id, 'Node 2', x2)

Based on this assignment, you set the class label of the graph. If both nodes get the same property, the class label is 0. Otherwise, it is 1.

    if x1 == x2:
        Y_train[graph_id] = 0
    else:
        Y_train[graph_id] = 1

The class label is finally randomly inverted to introduce noise.

    if np.random.rand() <= 0.01:
        Y_train[graph_id] = 1 - Y_train[graph_id]

Execution

Running the program, you should get the following output:

python3 ./examples/NoisyXORDemo.py 
Creating training data
Creating testing data
Initialization of sparse structure.
0 99.15 100.00 5.40 0.88
1 99.15 100.00 1.54 0.88
2 99.15 100.00 1.55 0.88
3 99.15 100.00 1.52 0.88
4 99.15 100.00 1.53 0.88
5 99.15 100.00 1.52 0.88
...

See the Noisy XOR Demo in the example folder for further details.

Demos

Vanilla MNIST

The Graph Tsetlin Machine supports rich data (images, video, text, spectrograms, sound, etc.). One can, for example, add an entire image to a graph node, illustrated for MNIST images below:

Here, you define an image by adding its white pixels as properties to the node. Each white pixel in the grid of 28x28 pixels gets its own symbol Wx,y.

Note that with only a single node, you obtain a Coalesced Vanilla Tsetlin Machine. See the Vanilla MNIST Demo in the example folder for further details.

Convolutional MNIST

By using many nodes to capture rich data, you can exploit inherent structure in the data. Below, each MNIST image is broken down into a grid of 19x19 image patches. A patch then contains 10x10 pixels:

Again, white pixel symbols Wx,y define the image content. Additionally, this example use a node's location inside the image to enhance the representation. You do this by introducing row Ry and column Cx symbols.

These symbols allow the Graph Tsetlin Machine to learn and reason about pixel patterns as well as their location inside the image.

Without adding any edges, the result is a Coalesced Convolutional Tsetlin Machine. See the Convolutional MNIST Demo in the example folder for further details.

Sequence Classification

The above two examples did not require edges. Here is an example where the edges are essential.

The task is to decide how many 'A's occur in sequence. The 'A's can appear at any time, preceded and followed by spaces. The below graphs model the task:

From the perspective of a single node, the three classes Y=0 (one 'A'), Y=1 (two 'A's), and Y=2 (three 'A's) all look the same. Each node only sees an 'A' or a space. By considering the nodes to its $Left$ and to its $Right$, however, a node can start gathering information about how many 'A's appear in the sequence.

Remark. Notice the two types of edges: $Left$ and $Right$. With only a single edge type, a node would not be able distinguish between an 'A' to its left and an 'A' to its right, making the task more difficult. Hence, using two types of edges is beneficial.

See the Sequence Classification Demo in the example folder for further details.

Noisy XOR With MNIST Images

This example increases the challenge of the Noisy XOR problem by using images of handwritten '0's and '1's instead of the symbols $\

GraphTsetlinMachine

Install / Use

README