The Tsetlin Machine outperforms neural networks

https://cair.uia.no/milestones-and-discoveries/the-tsetlin-machine-outperforms-neural-networks/

by beagle3 • 8 years ago

139 20 8 years ago

cair.uia.no

kurthr• 8 years ago

Just go straight to the paper or code... the write-up is almost content free.

Paper: https://arxiv.org/abs/1804.01508

Code: https://github.com/cair/TsetlinMachine

xtacy• 8 years ago

/r/MachineLearning comments on the same paper from April 2018:

https://www.reddit.com/r/MachineLearning/comments/89yp8g/r_t...

wetpaws• 8 years ago

nl• 8 years ago

The paper is actually pretty interesting - it's a pity the headline is misleading.

The Reddit comment[1] is a good summary: More accurately: "The Tsetlin Machine - a new approach to ML - outperforms single layer Neural Networks, SVMs, Random Forests, the Naive Bayes Classifier and Logistic Regression on four carefully selected contrived datasets"

Notably, on their (weird!) "Binary Iris" dataset, the NN appears to be undertrained, and it is unclear what the headline "mean" accuracy figure is actually a mean of.

However, once we get over that, it's quite a different approach, and I can imagine places where it could be useful. Notably, as an anomaly detector it would seem to have interesting properties like interpretable results similar to a random forest.

[1] https://www.reddit.com/r/MachineLearning/comments/89yp8g/r_t...

nestorD3• 8 years ago

They say that their results are interpretable due to being logical formulas but, later, show a toy problem in which their formula has 10000 clauses. By that definition deep-learning is probably interpretable.

However I do think that it is an interesting concept that would probably be worth testing if your inputs and outputs have a natural mapping to booleans.

simonw• 8 years ago

The entire implementation appears to be 300 lines of Cython: https://github.com/cair/TsetlinMachineCython/blob/master/Tse...

nestorD3• 8 years ago

The Tsetlin Machine being a specialized method, it makes sense that it beats neural networks in its domain of predilection (decision from, potentially noisy, binary inputs).

chvid4• 8 years ago

So what is a Tselin machine?

Maybe I am lazy but a don’t see an exact description.

I am assume it is a function that takes an input, a state and produces an output. But what exactly is it?

A neural net is a fairly general construction. Is this not just a nn with a particular activation function, a particular network layout?

shakna• 8 years ago

For a detailed understanding, you need the paper. [0]

But, loosely speaking, it is a classifier that works best with less information, utilising a series of formulas. It only really does bitwise ops for recognition, and is easy to implement and fast.

If I were to describe it in more flowery terms, hashing and finite automata had a baby.

[0] https://arxiv.org/abs/1804.01508

chvid4• 8 years ago

Why can't I just get a reasonable definition of what a Tsetlin machine is?

As far as I can read it a function that takes an input (a vector of real numbers in 0..1 (?)), a state (in form of an integer) and produces an output (in form of something?).

andrewla• 8 years ago

As far as I can tell from looking at the code that implements it, and ignoring the training for the moment, the model itself takes a binary vector, and takes the sum of (the characteristic function of) AND's of elements of that vector, and returns whether the sum exceeds a threshold.

So an example model with an input vector `x` might be

  x[1] & ~x[2] & x[4] + x[2] & x[4] + x[1] & x[3] > 1

EDIT: okay, so that's the effective evaluation model, but for training purposes, it is stored internally as a series of real numbers for each potential coefficient, and if that number exceeds the "number of states", then it is considered active. So the model above in binary form would look like

  +: [1,0,0,1],[0,1,0,1],[1,0,1,0]
  -: [0,1,0,0],[0,0,0,0],[0,0,0,0]

But internally this could be represented (with number_of_states == 6) as

  +: [7.1,5.0,4.0,8.0 ],[3.7,6.1,5.9,7.8],[8.0,3.0,6.5,5.2]

EDIT 2: Each term apparently is assigned a sign flag, and the threshold is 0, so not strictly an increasing sum.

nestorD3• 8 years ago

A Tselin automata returns always true or always false depending on its internal state (wich is basically a counter set during the learning process).

Using one automata per literal per clause you can learn any logical formula in normalized form (the automata tells you if you should include this literal or not). That section made the paper worth reading for me.

A Tselin machine is a refinement of the formula learning algorithm to get better learning properties, once trained you get a (long) formula (not precisely a logical formula since it uses a sum and a threshold instead of OR to improve robustness).

It is important to note that they manipulate boolean inputs and outputs and, thus, it is not a general alternativ for neural network.

alexyak• 8 years ago

The Tsetlin machine is based on Tsetlin’s automata, the so called finite automata with linear tactics. The are basically counters of rewards (up) and penalties (down) with various strategies of integration, proportionization and differentiation. They have minimum necessary for digital emulation of the perception functionality. They str not only due to Tsetlin but also yo Krinsky, Krylov, Varshavsky. Mikhail Tsetlin is the most prominent creator. It’s the work in the USSR in the 60s. So not new but very elegant!

The Tsetlin Machine outperforms neural networks

Related Stories