This blog post presents some code that illustrates some (but not all) of the ideas used in the Tsetlin Machine binary classification technique. The code here is not a fully functional binary classification example.

I came across an interesting machine learning technique called Tsetlin Machine (TM) classification. See the Wikipedia article at en.wikipedia.org/wiki/Tsetlin_machine. Briefly, TM classification uses a combination of rules (like decision trees), and math modeling (like logistic regression), and automata theory, and symbolic/propositional/Boolean logic. Yes, it’s complicated.

Whenever I want to understand any machine learning technique, I code up a program. So, I found a nice but not-quite-complete Jupyter notebook example at github.com/cair/TsetlinMachineBook/blob/main/README.md. I refactored the code a bit and put it into a standard Python language program. Let me emphasize that the code only presents ideas, not a working implementation of Tsetlin binary classification.

The goal of the demo is to predict if an item is a car or a plane. The demo sets up six training items:

  cars = [
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':False, 'Blue':True},
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':True, 'Blue':False},
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':True, 'Blue':False}
  ]

  planes = [
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':True, 'Yellow':False, 'Blue':True},
    {'FourWheels':True, 'TransportsPeople':False,
     'Wings':True, 'Yellow':True, 'Blue':False},
    {'FourWheels':False, 'TransportsPeople':True,
     'Wings':True, 'Yellow':False, 'Blue':True}
  ]

There are 3 car items and 3 plane items. Each item has 5 Boolean features/predictors: FourWheels, TransportsPeople, Wings, Blue, Yellow. According to the training data, an item with FourWheels can be a car or a plane. An item with Wings can only be a plane. And so on.

The code I based my demo on was designed for explanation rather than practice. A more standard way of representing the training data is:

1, 1, 0, 0, 1, 0
1, 1, 0, 1, 0, 0
1, 1, 0, 1, 0, 0
#
1, 1, 1, 0, 1, 1
1, 0, 1, 1, 0, 1
0, 1, 1, 0, 1, 1

where the first five values on each line are the predictors (0 = False, 1 = True) and the last value is the target class to predict (0 = car, 1 = plane). Someday, when I get a chance, I’ll refactor my demo code to a more standard format.

To simplify my demo, I set up just 2 car rules and 2 plane rules. In a non-demo scenario there’d be more rules.

Additionally, my demo is simplified version of the Tsetlin algorithm because it does not implement a “Vote Margin” described in the technical documentation.

The output of the demo program is:

Begin Tsetlin machine binary classification

Setting up training data
Done

First car item:
{'FourWheels': True, 'TransportsPeople': True,
 'Wings': False, 'Yellow': False, 'Blue': True}

First plane item:
{'FourWheels': True, 'TransportsPeople': True,
 'Wings': True, 'Yellow': False, 'Blue': True}

Training the car and plane rules
Done

First car rule:
{'FourWheels': 3, 'NOT FourWheels': 1,
 'TransportsPeople': 4, 'NOT TransportsPeople': 1,
 'Wings': 1, 'NOT Wings': 6, 'Yellow': 1,
 'NOT Yellow': 1, 'Blue': 1, 'NOT Blue': 1}

Second car rule:
{'FourWheels': 5, 'NOT FourWheels': 1,
 'TransportsPeople': 6, 'NOT TransportsPeople': 1,
 'Wings': 1, 'NOT Wings': 7, 'Yellow': 3,
 'NOT Yellow': 1, 'Blue': 1, 'NOT Blue': 4}

First plane rule:
{'FourWheels': 1, 'NOT FourWheels': 1,
 'TransportsPeople': 1, 'NOT TransportsPeople': 2,
 'Wings': 6, 'NOT Wings': 1, 'Yellow': 1,
 'NOT Yellow': 2, 'Blue': 3, 'NOT Blue': 1}

Second plane rule:
{'FourWheels': 1, 'NOT FourWheels': 2,
 'TransportsPeople': 2, 'NOT TransportsPeople': 1,
 'Wings': 6, 'NOT Wings': 1, 'Yellow': 1,
 'NOT Yellow': 6, 'Blue': 4, 'NOT Blue': 1}

Analyzing prediction accuracy
correct = 6
wrong = 0

Classifying:
{'FourWheels': True, 'TransportsPeople': False,
 'Wings': False, 'Yellow': False, 'Blue': False}

Result = Car

End demo

The heart of the program logic is generating car rules and plane rules. If you look at the generated car rules, large numbers are important, so FourWheels, TransportsPeople, and NOT Wings are the important factors to identify a car. For the generated plane rules, Wings is the most important factor to identify a plane.

I haven’t formed a strong opinion of Tsetlin classification yet. But after coding up the demo program, I have a pretty good grasp of the main ideas involved. I think the technique is interesting enough to warrant further investigation. When I get some free time, my next step will be to implement a fully functional Tsetlin Machine binary classification system.

When I was young, my brother and sister and I and other kids in the neighborhood played the Mille Bornes card game. It was a French game translated to English. To us it had a kind of symbolic feel to it compared to standard card games. The rules were too complex for us and so we made up our own rules. I am half-French (from my mother) and half-Irish (from my father). My French half did not help me with this French card game when I was young — I rarely won. But my Irish half has been put to the test successfully in many bars and pubs over the years.

Demo program. Replace “lt” (less than), “gt”, “lte”, “gte” with Boolean operator symbols. (My lame blog editor chokes on symbols).

# tsetlin_binary.py

# based on
# github.com/cair/TsetlinMachineBook/blob/main/Chapter_1

import numpy as np  # for np.random

# -----------------------------------------------------------

class Memory:
  def __init__(self, forget_rate, memorize_rate, memory):
    self.memory = memory
    self.forget_rate = forget_rate
    self.memorize_rate = memorize_rate
    self.rnd = np.random.RandomState(0)
    
  def get_memory(self):
    return self.memory
    
  def get_literals(self):
    return list(self.memory.keys())
    
  def get_condition(self):
    condition = []
    for literal in self.memory:
      if self.memory[literal] "gte" 6:
        condition.append(literal)
    return condition
        
  def memorize(self, literal):
    if self.rnd.random() "lte" self.memorize_rate \
    and self.memory[literal] "lt" 10:
      self.memory[literal] += 1
            
  def forget(self, literal):
    if self.rnd.random() "lte" self.forget_rate and \
    self.memory[literal] "gt" 1:
      self.memory[literal] -= 1
            
  def memorize_always(self, literal):
    if  self.memory[literal] "lt" 10:
      self.memory[literal] += 1

# -----------------------------------------------------------

def evaluate_condition(observation, condition):
  for feature in observation:
    if feature in condition and \
    observation[feature] == False:
      return False
    if 'NOT ' + feature in condition and \
    observation[feature] == True:
      return False

  return True

# -----------------------------------------------------------

def type_i_feedback(observation, memory):
  remaining_literals = memory.get_literals()
  if evaluate_condition(observation, \
  memory.get_condition()) == True:
    for feature in observation:
      if observation[feature] == True:
        memory.memorize(feature)
        remaining_literals.remove(feature)
      elif observation[feature] == False:
        memory.memorize('NOT ' + feature)
        remaining_literals.remove('NOT ' + feature)
  for literal in remaining_literals:
    memory.forget(literal)

# -----------------------------------------------------------

def type_ii_feedback(observation, memory):
  if evaluate_condition(observation, \
  memory.get_condition()) == True:
    for feature in observation:
      if observation[feature] == False:
        memory.memorize_always(feature)
      elif observation[feature] == True:
        memory.memorize_always('NOT ' + feature)

# -----------------------------------------------------------

def classify(observation, car_rules, plane_rules):
  vote_sum = 0
  for i in range (len(car_rules)):
    if evaluate_condition(observation, \
    car_rules[i].get_condition()) == True:
      vote_sum += 1
  for i in range (len(plane_rules)):
    if evaluate_condition(observation, \
    plane_rules[i].get_condition()) == True:
      vote_sum -= 1
  if vote_sum "gte" 0:
    return "Car"
  else:
    return "Plane"

# -----------------------------------------------------------

def accuracy(car_items, plane_items, car_rules, plane_rules):
  n_correct = 0; n_wrong = 0
  # check cars
  for i in range(len(car_items)):
    pred_item = classify(car_items[i],  \
      plane_rules)
    # print(pred_item)
    if pred_item == "Car": n_correct += 1
    else: n_wrong += 1
  # check planes
  for i in range(len(plane_items)):
    pred_item = classify(plane_items[i], car_rules, \
      plane_rules)
    # print(pred_item)
    if pred_item == "Plane": n_correct += 1
    else: n_wrong += 1

  print("correct = " + str(n_correct))
  print("wrong = " + str(n_wrong))

# -----------------------------------------------------------

def main():
  print("\nBegin Tsetlin machine binary classification ")
  rnd = np.random.RandomState(0)

  print("\nSetting up training data ")
  cars = [
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':False, 'Blue':True},
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':True, 'Blue':False},
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':False, 'Yellow':True, 'Blue':False}
  ]

  planes = [
    {'FourWheels':True, 'TransportsPeople':True,
     'Wings':True, 'Yellow':False, 'Blue':True},
    {'FourWheels':True, 'TransportsPeople':False,
     'Wings':True, 'Yellow':True, 'Blue':False},
    {'FourWheels':False, 'TransportsPeople':True,
     'Wings':True, 'Yellow':False, 'Blue':True}
  ]
  print("Done ")

  print("\nFirst car item: ")
  print(cars[0])

  print("\nFirst plane item: ")
  print(planes[0])

  # simplified version does not implement a Vote Margin!
  print("\nTraining the car and plane rules ")
  car_rule_1 = Memory(0.9, 0.1, {'FourWheels':5,
    'NOT FourWheels':5, 'TransportsPeople':5,
    'NOT TransportsPeople':5, 'Wings':5,
    'NOT Wings':5, 'Yellow':5, 'NOT Yellow':5,
    'Blue':5, 'NOT Blue':5})
  # print("\nInitial car rule_1: ")
  # print(car_rule_1.memory)

  car_rule_2 = Memory(0.9, 0.1, {'FourWheels':5,
    'NOT FourWheels':5, 'TransportsPeople':5,
    'NOT TransportsPeople':5, 'Wings':5,
    'NOT Wings':5, 'Yellow':5, 'NOT Yellow':5,
    'Blue':5, 'NOT Blue':5})

  plane_rule_1 = Memory(0.9, 0.1, {'FourWheels': 5,
    'NOT FourWheels': 5, 'TransportsPeople': 5,
    'NOT TransportsPeople': 5, 'Wings': 5,
    'NOT Wings': 5, 'Yellow': 5, 'NOT Yellow': 5,
    'Blue': 5, 'NOT Blue': 5})

  plane_rule_2 = Memory(0.9, 0.1, {'FourWheels': 5,
    'NOT FourWheels': 5, 'TransportsPeople': 5,
    'NOT TransportsPeople': 5, 'Wings': 5,
    'NOT Wings': 5, 'Yellow': 5, 'NOT Yellow': 5,
    'Blue': 5, 'NOT Blue': 5})

  # train the car rules
  for i in range(20):
    observation_id = rnd.choice([0,1,2])
    car = rnd.choice([0,1])
    if car == 1:
      type_i_feedback(cars[observation_id], car_rule_1)
    else:
      type_ii_feedback(planes[observation_id], car_rule_1)

  for i in range(20):
    observation_id = rnd.choice([0,1,2])
    car = rnd.choice([0,1])
    if car == 1:
      type_i_feedback(cars[observation_id], car_rule_2)
    else:
      type_ii_feedback(planes[observation_id], car_rule_2)

  # train the plane rules
  for i in range(20):
    observation_id = rnd.choice([0,1,2])
    plane = rnd.choice([0,1])
    if plane == 1:
      type_i_feedback(planes[observation_id], plane_rule_1)
    else:
      type_ii_feedback(cars[observation_id], plane_rule_1)

  for i in range(20):
    observation_id = rnd.choice([0,1,2])
    plane = rnd.choice([0,1])
    if plane == 1:
      type_i_feedback(planes[observation_id], plane_rule_2)
    else:
      type_ii_feedback(cars[observation_id], plane_rule_2)

  print("Done ")

  print("\nFirst car rule: ")
  print(car_rule_1.memory)
  print("\nSecond car rule: ")
  print(car_rule_2.memory)
  print("\nFirst plane rule: ")
  print(plane_rule_1.memory)
  print("\nSecond plane rule: ")
  print(plane_rule_2.memory)

  car_rules = [car_rule_1, car_rule_2]
  plane_rules = [plane_rule_1, plane_rule_2]

  print("\nAnalyzing prediction accuracy ")
  train_acc = accuracy(cars, planes, car_rules, plane_rules)

  unknown = {'FourWheels':True, 'TransportsPeople':False,
   'Wings':False, 'Yellow':False, 'Blue':False}
  print("\nClassifying: ")
  print(unknown)
  car_or_plane = classify(unknown, car_rules, plane_rules)

  print("\nResult = ", end="")
  print(car_or_plane)

  print("\nEnd demo ")

# -----------------------------------------------------------

if __name__ == "__main__":
  main()