Research map / Learning theory and algorithms / Prediction and decision losses

Generalized Convergence Analysis of Tsetlin Automaton Based Algorithms: A Probabilistic Approach to Concept Learning

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Probabilistic Concept Learning (PCL), a simplified Tsetlin-automaton variant with per-clause inclusion probabilities, and proves it converges to a target conjunction of literals for 0.5 < p < 1 on a single clause.

Problem

Convergence of Tsetlin Machine learning for conjunctions (AND) of literals in the generalized case with more than two input bits remains an open problem.

Approach

Replaces TM feedback with clause-independent feedback tables where each literal's Tsetlin automaton is updated independently using a per-clause inclusion probability p_i, disables the inaction transition, enabling a per-literal probabilistic convergence proof.

Key results

• Theorem 1 proves PCL with one clause almost surely converges to the target conjunction for 0.5 < p < 1; experiments show near 100% success for p=0.75 at n=8 after about 1000 epochs.
• On binary IRIS with 10 clauses, PCL reaches about 92.4% average accuracy versus 95.0% for TM (300 clauses) and 95.5% for RF.
• For n=4, success drops to near zero for p<0.5 and fails to converge at p=1.0.

Measured effects reported in the paper

Surprising findings

• At p=1.0 the success rate diminishes, indicating non-convergence despite the theorem's bound being strict at 1.
• For larger n (11 and 12), PCL with fixed p=0.95 learns more conjunctions on average than the vanilla TM with s=1.0 when trained on the full truth table.

Limitations

• Proof covers only a single clause and does not imply convergence of the original Tsetlin Machine.
• Requires binarized inputs and does not natively support multiclass problems.
• Accuracy on IRIS lags state-of-the-art classifiers.

Experimental setup

Datasets: synthetic boolean conjunction targets (n up to 12) IRIS (binarized to 16 features)

Benchmarks: binary IRIS synthetic conjunction learning (n=2 to 12)

Metrics: convergence success rate out of 100 target conjunctions classification accuracy

Baselines: Tsetlin Machine (TM-a) Tsetlin Machine (TM-b) Naive Bayes Logistic Regression 1-layer NN SVM DT RF KNN

Builds on: Tsetlin Machine Tsetlin automaton

Closest papers by meaning

• Convergence Analysis of Tsetlin Machines under Noise-Free and Noisy Training Conditions: from $2$ Bits to $k$ Bits (ICLR 2026 · similarity 0.88)
• A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models (NeurIPS 2024 · similarity 0.84)
• On the Hardness of Probabilistic Neurosymbolic Learning (ICML 2024 · similarity 0.84)
• Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo (ICLR 2025 · similarity 0.84)
• A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.84)
• Selection, Reflection and Self-Refinement: Revisit Reasoning Tasks via a Causal Lens (ICLR 2026 · similarity 0.83)