Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic Approach to Concept Learning

2023/10/03 by Mohamed-Bachir Belaid, Belaid, Mohamed-Bachir, Jivitesh Sharma +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Artificial Intelligence (cs.AI) #DNA and Biological Computing #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2310.02005

openalex publication_date 2023/10/03 · openalex created_date 2023/10/05 · openalex updated_date 2026/07/28

Abstract

Tsetlin Machines (TMs) have garnered increasing interest for their ability to learn concepts via propositional formulas and their proven efficiency across various application domains. Despite this, the convergence proof for the TMs, particularly for the AND operator (conjunction of literals), in the generalized case (inputs greater than two bits) remains an open problem. This paper aims to fill this gap by presenting a comprehensive convergence analysis of Tsetlin automaton-based Machine Learning algorithms. We introduce a novel framework, referred to as Probabilistic Concept Learning (PCL), which simplifies the TM structure while incorporating dedicated feedback mechanisms and dedicated inclusion/exclusion probabilities for literals. Given n features, PCL aims to learn a set of conjunction clauses C_i each associated with a distinct inclusion probability p_i. Most importantly, we establish a theoretical proof confirming that, for any clause C_k, PCL converges to a conjunction of literals when 0.5

Related

• On the Convergence of Tsetlin Machines for the AND and the OR Operators
• On the Convergence of Tsetlin Machines for the XOR Operator
• Coalesced Multi-Output Tsetlin Machines with Clause Sharing
• Extending the Tsetlin Machine With Integer-Weighted Clauses for\n Increased Interpretability
• Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size