Abstract
We present a connectionist architecture that supports almost instantaneous deductive and abductive reasoning. The deduction algorithm responds in few steps for single rule queries and in general, takes time that is linear with the number of rules in the query. The abduction algorithm produces an explanation in few steps and the best explanation in time linear with the size of the assumption set. The size of the network is polynomially related to the size of other representations of the domain, and may even be smaller. We base our connectionist model on Valiant's Neuroidal model and make minimal assumptions about the computing elements, which are assumed to be classical threshold elements with states. Within this model, we develop a reasoning framework that utilizes a model-based approach to reasoning. We interpret the connectionist architecture as encoding examples of the domain we reason about and show how to perform various reasoning tasks with this interpretation. We then show that the representations used can be acquired efficiently from interactions with the environment and discuss how this learning process influences the reasoning performance of the network.
Introduction
Traditional Artificial Intelligence has long relied on the "Knowledge-Base + Inference Engine" paradigm. In this view, knowledge is stored as logical formulas, and an engine is used to "prove" new facts. However, this approach faces two major hurdles: computational intractability and the connectionist gap. General logical inference is NP-hard, making it too slow for the "reflexive" reasoning humans perform in daily life, such as language understanding. Furthermore, while neural networks excel at learning from data, they have historically struggled to represent and apply the rigid rules of logic.
This paper addresses these issues by proposing a shift in perspective: reasoning with examples rather than abstract symbolic rules. Instead of storing a rule like "If it rains, the grass is wet," the system stores "snapshots" or models of the world where both conditions are true. This shifts the computational burden from complex theorem proving to simple model evaluation, bridging the gap between learning from the environment and efficient common-sense inference.
The Connectionist Architecture
The framework is built upon Valiant’s Neuroidal model, a programmable framework of threshold elements (nodes) that can change states and weights. The architecture is organized into a multi-layer network designed to facilitate rapid inference.
As illustrated in Figure 1, the bottom layer represents literals (variables and their negations). The middle layer consists of "example nodes," each representing a specific observed model or snapshot of the world. The top layer contains target nodes that signal the final inference.
Two primary algorithms drive the network:
- AlgD (Deduction Algorithm): A 5-step process utilizing "weight flips." It prompts the network with the antecedent of a query to activate relevant example nodes, then checks if the consequent holds across those active nodes.
- Abduction: The network utilizes backward connections and relay nodes (seen in the lower left of Figure 1) to find the best "explanation" for an observation in constant time.
Theoretical Foundations and Learning
Instead of a Boolean formula $f$, the knowledge base is a set of models $\Gamma$ (satisfying assignments). To check if a query $\alpha$ is true, the system simply checks if $\alpha$ holds in all stored models in $\Gamma$. This approach treats reasoning as evaluation rather than search. If the system possesses the right examples, reasoning becomes a parallel check across those examples.
The paper introduces the concept of "Fair Queries" ($Q_c$), proving that it is not necessary to store every possible model of the world. If enough examples are sampled from an arbitrary but fixed probability distribution $D$ over the environment, the network will be correct on queries that appear frequently or are clearly true/false with very high probability. This makes learning and reasoning a seamless process: "learning" is simply the memorization of representative examples into the network.
Results and Performance
The proposed architecture demonstrates significant advantages in both speed and efficiency:
- Speed: Deduction for a single rule takes exactly 5 computational steps. For queries involving multiple rules, the time remains linear relative to the number of rules, independent of the total size of the knowledge base.
- Efficiency: The network size is polynomially related to traditional representations like DNF formulas and is often significantly smaller.
- Provable Correctness: Theorem 3 in the paper proves that if the network stores a specific set of "characteristic models," it is guaranteed to perform correct deduction for a wide class of common queries, including Horn and log-nCNF functions.
Conclusion and Future Work
While this framework provides a robust foundation for reflexive reasoning, several challenges remain. The current model is limited to propositional logic and does not yet handle first-order logic or complex relational data. Additionally, while the paper discusses "local" networks, the interaction of thousands of such networks in a brain-scale system requires further study. Future work will also need to address reasoning with incomplete information and the jump from Boolean variables to the nuances of natural language syntax and semantics.
Summary updated