Abstract: This paper presents a novel approach to bridging symbolic logic programming and connectionist models by extending Prolog with "net-clauses." By treating variables as communication channels and clauses as processing units, the framework enables efficient, parallel-like graph matching and constraint satisfaction, particularly for 3D polyhedra recognition.
Introduction
In the late 1980s, Artificial Intelligence was characterized by a divide between Symbolic AI (e.g., Prolog), which excels at logic and state-space searching, and Connectionism (neural networks), which is adept at distributed processing and pattern recognition. While Prolog is powerful, it struggles with graph isomorphism—the task of determining if two graphs are structurally identical. Traditional list-based graph matching in Prolog is inefficient due to its reliance on backtracking, leading to combinatorial explosions. Zdravko I. Markov proposes a framework to perform these matches simultaneously and efficiently by re-envisioning Prolog's execution model.
The Net-Clause Formalism
The author introduces three major shifts in Prolog usage to create a logic-connectionist hybrid:
- Attributed Graph Representation: Edges are represented with attributes such as slope and length. Prolog’s unification mechanism handles equality and inequality constraints automatically through shared variables.
- Net-Clauses: This syntactic extension allows clauses to share variables across the database, transforming the database into an interconnected network of nodes.
- The
activate(N)Predicate: This "engine" replaces standard top-down execution. It triggers clause bodies based on the number of instantiated variables in their "head." This data-driven approach simulates a parallel execution environment. - Inhibitory Links: Using
~Xnotation, the system can model inhibitory signals. If variableXis instantiated, the link acts as a "stop" signal, mimicking biological neural logic.
Key Insights and Ideas
The framework's most striking innovation is the reinterpretation of variables as wires. Instead of mere placeholders, variables serve as channels for information transfer between network components.
As shown in Figure 1, this architecture allows for simultaneous matching. An input pattern (e.g., edges from an image) can be matched against multiple object classes—such as squares, rhombuses, or parallelograms—at once. Furthermore, by adjusting the threshold N in activate(N), the system supports "fuzzy matching," which is essential for computer vision where data might be missing or noisy.
Results and Discussion
The framework was implemented in an experimental version of Prolog, demonstrating both qualitative success and improved efficiency. The system successfully distinguished between similar geometric classes by propagating constraints through the network. By utilizing the activation rule, the system avoids the pitfalls of standard backtracking order, ensuring only "useful" clauses are executed. Although running on sequential hardware, the multi-pass scanning of the net-clause database effectively simulates a parallel computational model.
Limitations and Future Work
While promising, the current implementation faces overhead challenges when ignoring standard clause functors. Future work aims to allow connections to perform more complex calculations during unification, such as solving equations. Additionally, the author suggests developing learning procedures so the network can automatically acquire the structure of new objects, moving closer to the capabilities of true neural networks.
Summary updated