On the Convergence of Tsetlin Machines for the XOR Operator

Area of Science:

• Machine Learning
• Pattern Recognition
• Theoretical Computer Science

Background:

• The Tsetlin Machine (TM) is a novel machine learning algorithm known for transparent inference and hardware-near learning.
• Empirical studies highlight TM's performance, but mathematical analysis of its properties remains limited.

Purpose of the Study:

• To mathematically analyze the convergence properties of the Tsetlin Machine.
• To investigate TM's ability to learn non-linear relationships, specifically the XOR function.
• To understand the role of the hyper-parameter T in clause construction and pattern recognition.

Main Methods:

• Mathematical analysis of Tsetlin Machine convergence.
• Focus on non-linear input-output relationships using the XOR operator.
• Investigation of TM's learning dynamics over an infinite time horizon.

Main Results:

• The Tsetlin Machine, with two conjunctive clauses, converges almost surely to reproducing the XOR function.
• The hyper-parameter T guides clause construction to effectively capture distinct data sub-patterns.
• The analysis provides a foundation for studying more complex logical expressions with TMs.

Conclusions:

• Mathematical analysis confirms TM's capability to learn complex non-linear functions like XOR.
• The hyper-parameter T plays a crucial role in TM's efficient pattern recognition.
• This work offers theoretical insights into the state-of-the-art performance of Tsetlin Machines.