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

• URL: http://arxiv.org/abs/2007.14268v3
• Date: Mon, 11 Oct 2021 15:56:24 GMT
• Title: On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators
• Authors: Xuan Zhang, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin
• Abstract summary: We analyze the convergence of the Tsetlin Machine with only one clause involved for classification. Our analysis reveals that the TM, with just one clause, can converge correctly to the intended logical operator. The analysis of the convergence of the two basic operators lays the foundation for analyzing other logical operators.
• Score: 14.186377732379045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning [55.52872152909785]
  Chain-of-thought (CoT) via prompting is the de facto method for eliciting reasoning capabilities from large language models (LLMs) We show that CoT gives strong performance benefits primarily on tasks involving math or logic, with much smaller gains on other types of tasks.
  arXiv  Detail & Related papers  (2024-09-18T17:55:00Z)
• MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning [63.80739044622555]
  We introduce MuSR, a dataset for evaluating language models on soft reasoning tasks specified in a natural language narrative. This dataset has two crucial features. First, it is created through a novel neurosymbolic synthetic-to-natural generation algorithm. Second, our dataset instances are free text narratives corresponding to real-world domains of reasoning.
  arXiv  Detail & Related papers  (2023-10-24T17:59:20Z)
• In-Context Convergence of Transformers [63.04956160537308]
  We study the learning dynamics of a one-layer transformer with softmax attention trained via gradient descent. For data with imbalanced features, we show that the learning dynamics take a stage-wise convergence process.
  arXiv  Detail & Related papers  (2023-10-08T17:55:33Z)
• Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic Approach to Concept Learning [20.519261060300302]
  This paper presents 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. We establish a theoretical proof confirming that, for any clause $C_k$, PCL converges to a conjunction of literals when $0.5p_k1$.
  arXiv  Detail & Related papers  (2023-10-03T12:21:41Z)
• The Transformation Logics [58.35574640378678]
  We introduce a new family of temporal logics designed to balance the trade-off between expressivity and complexity. Key feature is the possibility of defining operators of a new kind that we call transformation operators. We show them to yield logics capable of creating hierarchies of increasing expressivity and complexity.
  arXiv  Detail & Related papers  (2023-04-19T13:24:04Z)
• On the Equivalence of the Weighted Tsetlin Machine and the Perceptron [12.48513712803069]
  Tsetlin Machine (TM) has been gaining popularity as an inherently interpretable machine leaning method. Although possessing favorable properties, TM has not been the go-to method for AI applications.
  arXiv  Detail & Related papers  (2022-12-27T22:38:59Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  We propose MURMUR, a neuro-symbolic modular approach to text generation from semi-structured data with multi-step reasoning. We conduct experiments on two data-to-text generation tasks like WebNLG and LogicNLG.
  arXiv  Detail & Related papers  (2022-12-16T17:36:23Z)
• On the Convergence of Tsetlin Machines for the AND and the OR Operators [18.937937844147644]
  The Tsetlin Machine (TM) is a novel machine-learning algorithm based on propositional logic. In this article, we analyze the convergence when input training samples follow AND and OR operators respectively.
  arXiv  Detail & Related papers  (2021-09-17T13:53:26Z)
• On the Convergence of Tsetlin Machines for the XOR Operator [16.85020149902772]
  The Tsetlin Machine (TM) is a novel machine learning algorithm with several distinct properties. We analyze the convergence of the TM when input is non-linearly related to output by the XOR-operator.
  arXiv  Detail & Related papers  (2021-01-07T14:13:41Z)
• Closed-Form Expressions for Global and Local Interpretation of Tsetlin Machines with Applications to Explaining High-Dimensional Data [7.05622249909585]
  We propose closed-form expressions for understanding why a TM model makes a specific prediction (local interpretability) We also introduce expressions for measuring the importance of feature value ranges for continuous features. For both classification and regression, our evaluation show correspondence with SHAP as well as competitive prediction accuracy in comparison with XGBoost, Explainable Boosting Machines, and Neural Additive Models.
  arXiv  Detail & Related papers  (2020-07-27T21:47:24Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  We study the task of logical generalization using graph neural networks (GNNs) Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training.
  arXiv  Detail & Related papers  (2020-03-14T05:45:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.