Abstract
Tsetlin Machines (TMs) are a pattern recognition approach that uses finite state machines for learning and propositional logic to represent patterns. In addition to being natively interpretable, they have provided competitive accuracy for various tasks. In this paper, we increase the computing power of TMs by proposing a first-order logic-based framework with Herbrand semantics. The resulting TM is relational and can take advantage of logical structures appearing in natural language, to learn rules that represent how actions and consequences are related in the real world. The outcome is a logic program of Horn clauses, bringing in a structured view of unstructured data. In closed-domain question-answering, the first-order representation produces 10x more compact KBs, along with an increase in answering accuracy from 94.83% to 99.48%. The approach is further robust towards erroneous, missing, and superfluous information, distilling the aspects of a text that are important for real-world understanding.
Introduction
While Deep Learning dominates Natural Language Processing (NLP), it often acts as a "black box," making it difficult to explain why a model reached a specific answer. Tsetlin Machines (TMs) emerged as a logic-based, interpretable alternative that uses simple bitwise operations to learn patterns. However, standard TMs are limited by propositional logic, treating every entity (e.g., "Bob," "Alice") as a unique, fixed feature. This creates two major hurdles: a lack of generalization across different entities and exploding complexity as the number of unique names and locations grows. This paper introduces the Relational Tsetlin Machine (RTM), which moves from propositional logic to first-order logic to learn universal rules like "If Person X moves to Location Y, then Person X is at Location Y."
Methods
The core innovation of the RTM is the shift to First-Order Logic using Herbrand semantics. The process involves several key steps to transform unstructured text into a structured logic program:
- Entity Generalization: Instead of learning rules about specific constants, the RTM replaces them with variables ($Z_1, Z_2, \dots$). This allows the machine to learn the structure of an action rather than the specific actors.
- Horn Clauses: The RTM produces logic programs consisting of Horn clauses (e.g., $B_0 \leftarrow B_1, B_2$). This turns a paragraph into a mini-database of rules.
- Convolutional Permutations: Since there are many ways to map variables to constants, the RTM uses a convolutional operator to evaluate all possible permutations of variable assignments, using Tsetlin Automata to decide which mappings are valid.
Results and Discussion
The authors evaluated the RTM using bAbI-style QA tasks and a handcrafted "Parentage" dataset. The model demonstrated significant improvements in both performance and efficiency.
- Accuracy and Compactness: In closed-domain question answering, the RTM improved accuracy from 94.83% to 99.48%. Furthermore, the use of first-order rules led to a 10x reduction in the size of the Knowledge Base compared to propositional versions.
- Generalization: By using variables, the RTM can answer questions about entities it has never seen before. If it learns the rule for "moving," it can apply it to any subject encountered in a test set.
- Robustness to Noise: TMs are inherently fault-tolerant. Even with 10% noise injected into the training data, the RTM maintained a 95.08% accuracy, demonstrating its ability to distill the "essence" of a text despite errors.
Conclusion
The Relational Tsetlin Machine provides a powerful, interpretable framework for natural language understanding by bridging the gap between symbolic logic and pattern recognition. While currently focused on non-recursive clauses in closed domains, future work will explore adding recursion to achieve Turing-completeness and scaling the approach to massive, open-domain corpora.
Summary updated