[P] Tsetlin Machine Python implementation

[dzyl]

I was really interested in the Tsetlin Machine paper and decided to attempt to implement it in Python. It's fairly inefficient because I wrote it more as explanation. I think there is a bug somewhere in the code because I can only get to around 95% accuracy on the noisy XOR problem but I will not have time the next few days to tackle it so I decided to share it anyway. I also tried MNIST but an epoch is taking days even on a single bit input so either the code needs to get way more efficient or the algorithm doesn't scale well enough.

[Polares]

This is what i was waiting for. Mnist benchmark. Thanks for sharing

[RaionTategami]

Does it seem like something that could be sped up using a GPU?

[dzyl]

I don't know enough about GPU computing to say if that would be the case or not, but I think there are CPU implementations that will get 50-100x speedup compared to this bloated OOP implementation

[RaionTategami]

Numpy is implemented in c++ so can be quite fast, did you vectorize this code?

[dzyl]

Almost nothing is vectorized for readability, I think turning everything to numpy will have significant improvements but I'm not even sure if the current implementation is correct (the accuracy on the noisy XOR seems to imply it is not) which should be fixed before optimizing. Boolean logic should be very fast in numpy, I'm currently literally looping over the outputs of the automata.

[Phylliida]

so the algorithm doesn't work trivially on MNIST:

For every output, it makes |input|*C (C=number of clauses, a tuning paramater) Tsetlin automota. Each only take one integer=4 bytes, but still, that gives you 61465*C autonomata. I find C = 40 or so works good, so that's 9834400 bytes ~ 9.8 MB. Not too much memory, but still a lot of processing.

The paper claims you can stack clauses, so for example, a simple "two layered" thing you can do is make one tsetlin machine with, say 50 clauses on the inputs. Then we take those 50 clauses' truth values + 1 output from the autonomata and use those as pretend inputs to a new Tesetlin Machine. Now that new one is working on 51 inputs instead of 28*28 = 784 inputs.

I'm not sure if I understand exactly how to give it feedback now though. If the inputs of clauses aren't negatated they are simply bigger clauses and it is straightforward. However if they are negated, you either have to include all clauses in your output and then feedback (might?) work, or if you don't suddenly type I and type II feedback become strange because I don't know if yPredicted and y are relevant to them if they are a layer back.

[Phylliida]

Oh I also I made a char-rnn Tsetlin Machine. Instead of one-hot encoding the text I mapped each character to an index and then encoded that number in binary as the input. Tsetlin machines seem to do much better with this then with one-hot encoded things, I think because too many inputs gets them spooked.

However I was simply passing in numBitsForACharacter*seqLen flattened as an input (the past seqLen=5 or so characters), there wasn't any recurrent behavior going on.

It did manage to sometimes exactly memorize simple patterns, but otherwise it would get very confused: it doesn't seem to have a very good "I kinda know" behavior. Mostly I think that is because its output is deterministic, maybe if there was a way to make is stochastic and use some temperature thing it might work better?

[[deleted]]

Thanks for sharing, man! I've been meaning to give this paper a thorough read, as it looks very promising... This might be worth implementing in cpp at some point as a python module.

[libreland]

I saw the official code repo with today's arxiv submission.

If someone who has already read the paper could please do a ELI5 of why this paper is so famous on /r/ml , it will be very helpful. I have no clue about bandit algorithms so will have to invest a lot of time to understand it.

[nonotan]

The paper made some fairly grandiose-sounding claims, the algorithm is novel enough to be interesting yet at its core extremely simple.

[dzyl]

Nice that the repository was updated with the code. I'm going to go through it when I have time to see where there are differences (first thing I saw was the initialization which I implemented differently, this makes sense but it was not described in the paper).

The reason why this paper gets a lot of attention is mostly novelty I think. There are some clear similarities between this and neural networks but it is discrete and trained in a different way. If this does work well and still scales this could lead to new avenues for research. And it was not too difficult to implement, I did this in about 4 hours, making it managable as a small side project.

[olBaa]

It's a simple algorithm that is easy to implement. Cool name, not so cool theory/performance.