TsetlinMachine
Code and datasets for the Tsetlin Machine
Install / Use
/learn @cair/TsetlinMachineREADME
Tsetlin Machine
Code and datasets for the Tsetlin Machine. Implements the Tsetlin Machine from https://arxiv.org/abs/1804.01508, including the multiclass version. The Tsetlin Machine solves complex pattern recognition problems with easy-to-interpret propositional formulas, composed by a collective of Tsetlin Automata.
<p align="center"> <img width="75%" src="https://github.com/olegranmo/blob/blob/master/Tsetlin_Machine_Example_Configuration_Full.png"> </p>Contents
- Basics
- Noisy XOR Demo
- Requirements
- Other Implementations
- Other Architectures
- Hardware
- Books
- Conferences
- Videos
- Tutorials
- Acknowledgements
- Tsetlin Machine Papers
- Licence
Basics
Classification
<p align="left"> A basic Tsetlin Machine takes a vector <img src="http://latex.codecogs.com/svg.latex?X%3D%5Bx_1%2C%5Cldots%2Cx_o%5D" border="0" valign="middle"/> of Boolean features as input, to be classified into one of two classes, <img src="http://latex.codecogs.com/svg.latex?y=0" border="0" valign="middle"/> or <img src="http://latex.codecogs.com/svg.latex?y=1" border="0" valign="middle"/>. Together with their negated counterparts, <img src="http://latex.codecogs.com/svg.latex?\bar{x}_k = {\lnot} {x}_k = 1-x_k" border="0" valign="middle"/>, the features form a literal set <img src="http://latex.codecogs.com/svg.latex?L = \{x_1,\ldots,x_o,\bar{x}_1,\ldots,\bar{x}_o\}" border="0" valign="middle"/>. </p> <p align="left"> A Tsetlin Machine pattern is formulated as a conjunctive clause <img src="http://latex.codecogs.com/svg.latex?C_j" border="0" valign="middle"/>, formed by ANDing a subset <img src="http://latex.codecogs.com/svg.latex?L_j {\subseteq} L" border="0" valign="middle"/> of the literal set: </p> <p align="center"> <img src="http://latex.codecogs.com/svg.latex?C_j (X)=\bigwedge_{{{l}} {\in} L_j} l = \prod_{{{l}} {\in} L_j} l" border="0" valign="middle"/>. </p> <p align="left"> For example, the clause <img src="http://latex.codecogs.com/svg.latex?C_j(X)=x_1\land{\lnot}x_2=x_1 \bar{x}_2" border="0" valign="middle"/> consists of the literals <img src="http://latex.codecogs.com/svg.latex?L_j = \{x_1,\bar{x}_2\}" border="0" valign="middle"/> and outputs <img src="http://latex.codecogs.com/svg.latex?1" border="0" valign="middle"/> iff <img src="http://latex.codecogs.com/svg.latex?x_1 = 1" border="0" valign="middle"/> and <img src="http://latex.codecogs.com/svg.latex?x_2 = 0" border="0" valign="middle"/>. </p> <p align="left"> The number of clauses employed is a user-configurable parameter <img src="http://latex.codecogs.com/svg.latex?n" border="0"/>. Half of the clauses are assigned positive polarity. The other half is assigned negative polarity. The clause outputs, in turn, are combined into a classification decision through summation and thresholding using the unit step function <img src="http://latex.codecogs.com/svg.latex?{u(v) = 1 ~\mathbf{if}~ v \ge 0 ~\mathbf{else}~ 0}" border="0" valign="middle"/>: </p> <p align="center"> <img src="http://latex.codecogs.com/svg.latex?\hat{y} = u\left(\sum_{j=1}^{n/2} C_j^+(X) - \sum_{j=1}^{n/2} C_j^-(X)\right)" border="0" valign="middle"/>. </p> <p align="left"> In other words, classification is based on a majority vote, with the positive clauses voting for <img src="http://latex.codecogs.com/svg.latex?y=1" border="0" valign="middle"/> and the negative for <img src="http://latex.codecogs.com/svg.latex?y=0" border="0" valign="middle"/>. The classifier <p align="center"> <img src="http://latex.codecogs.com/svg.latex?\hat{y} = u\left(x_1 \bar{x}_2 + \bar{x}_1 x_2 - x_1 x_2 - \bar{x}_1 \bar{x}_2\right)" border="0" valign="middle"/>, </p> for instance, captures the XOR-relation. </p>Learning
<p align="left"> A clause <img src="http://latex.codecogs.com/svg.latex?C_j(X)" border="0" valign="middle"/> is composed by a team of Tsetlin Automata, each Tsetlin Automaton deciding to <i>Include</i> or <i>Exclude</i> a specific literal <img src="http://latex.codecogs.com/svg.latex?l_k" border="0" valign="middle"/> in the clause (see figure above). Learning which literals to include is based on reinforcement: Type I feedback produces frequent patterns, while Type II feedback increases the discrimination power of the patterns. </p> <p align="left"> A Tsetlin Machine learns on-line, processing one training example <img src="http://latex.codecogs.com/svg.latex?{(X, y)}" border="0" valign="middle"/> at a time. </p> <p align="center"> <img width="52%" src="https://github.com/olegranmo/blob/blob/master/Type_I_Feedback.png"> </p> <p align="left"> <b>Type I feedback</b> is given stochastically to clauses with positive polarity when <img src="http://latex.codecogs.com/svg.latex?y=1" border="0" valign="middle"/> and to clauses with negative polarity when <img src="http://latex.codecogs.com/svg.latex?y=0" border="0" valign="middle"/>. An afflicted clause, in turn, reinforces each of its Tsetlin Automata based on: (i) the clause output <img src="http://latex.codecogs.com/svg.latex?C_j(X)" border="0" valign="middle"/>; (ii) the action of the targeted Tsetlin Automaton - <i>Include</i> or <i>Exclude</i>; and (iii) the value of the literal <img src="http://latex.codecogs.com/svg.latex?l_k" border="0" valign="middle"/> assigned to the automaton. As shown in Table 1, two rules govern Type I feedback, given independently to each Tsetlin Automaton of the clause: </p>- <i>Include</i> is rewarded and <i>Exclude</i> is penalized with probability <img src="http://latex.codecogs.com/svg.latex?\frac{s-1}{s}" border="0" valign="middle"/> whenever <img src="http://latex.codecogs.com/svg.latex?C_j(X)=1" border="0" valign="middle"/> <b>and</b> <img src="http://latex.codecogs.com/svg.latex?{l_k=1}" border="0" valign="middle"/>. This reinforcement is strong (triggers with high probability) and makes the clause remember and refine the pattern it recognizes in <img src="http://latex.codecogs.com/svg.latex?X" border="0" valign="middle"/>.
- <i>Include</i> is penalized and <i>Exclude</i> is rewarded with probability <img src="http://latex.codecogs.com/svg.latex?\frac{1}{s}" border="0" valign="middle"/> if <img src="http://latex.codecogs.com/svg.latex?C_j(X)=0" border="0" valign="middle"/> <b>or</b> <img src="http://latex.codecogs.com/svg.latex?{l_k}=0" border="0" valign="middle"/>. This reinforcement is weak (triggers with low probability) and coarsens infrequent patterns, making them frequent.
