On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators

The Tsetlin Machine (TM) is a recent machine learning algorithm with several distinct properties, such as interpretability, simplicity, and hardware-friendliness. Although numerous empirical evaluations report on its performance, the mathematical analysis of its convergence is still open. In this ar...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2022-10, Vol.44 (10), p.6345-6359
Main Authors: Zhang, Xuan, Jiao, Lei, Granmo, Ole-Christoffer, Goodwin, Morten
Format: Article
Language:English
Subjects:
Algorithms
Basic converters
Computer architecture
Convergence
convergence analysis
Empirical analysis
Learning automata
Machine learning
Mathematical analysis
Operators (mathematics)
Pattern recognition
propositional logic
Task analysis
Training
Training data
Tsetlin automata
tsetlin machine
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Tsetlin Machine (TM) is a recent machine learning algorithm with several distinct properties, such as interpretability, simplicity, and hardware-friendliness. Although numerous empirical evaluations report on its performance, the mathematical analysis of its convergence is still open. In this article, we analyze the convergence of the TM with only one clause involved for classification. More specifically, we examine two basic logical operators, namely, the "IDENTITY"- and "NOT" operators. Our analysis reveals that the TM, with just one clause, can converge correctly to the intended logical operator, learning from training data over an infinite time horizon. Besides, it can capture arbitrarily rare patterns and select the most accurate one when two candidate patterns are incompatible, by configuring a granularity parameter. The analysis of the convergence of the two basic operators lays the foundation for analyzing other logical operators. These analyses altogether, from a mathematical perspective, provide new insights on why TMs have obtained state-of-the-art performance on several pattern recognition problems.
ISSN:0162-8828
2160-9292
1939-3539
DOI:10.1109/TPAMI.2021.3085591