TL;DR
This paper introduces TREAT, a novel match algorithm for AI production systems that significantly outperforms the widely-used RETE algorithm in terms of computational efficiency. By employing a "conflict-set support" strategy, TREAT reduces the number of comparisons needed for variable binding, leading to substantial speedups, especially in systems with frequent WM updates.
What Problem Does This Paper Address?
AI production systems, the backbone of many expert systems, rely on a repetitive cycle of matching rules against a working memory (WM), selecting a rule to fire, and executing its actions. The "match" phase, where rules are compared against the WM, is notoriously computationally expensive, often consuming up to 90% of the system's execution time. The dominant algorithm for this task, RETE, uses a sophisticated network to maintain state and incrementally compute matches. However, RETE's state-saving mechanism, "condition-element support," has been conjectured to be more costly than the comparisons it aims to avoid. This paper investigates this conjecture by proposing and evaluating TREAT, an alternative match algorithm that leverages "conflict-set support" to optimize the match phase, particularly in scenarios with changing WM.
Methods
TREAT introduces a new state-saving mechanism called "conflict-set support." Unlike RETE, which maintains detailed state about individual condition elements (memory support and condition relationship), TREAT primarily focuses on maintaining the conflict set itself across cycles. This allows TREAT to efficiently handle WM updates:
- Additions: New WM elements are used as "seeds" to initiate a constrained search for new instantiations, focusing only on rules that could be affected by the new data.
- Deletions: Instead of recomputing large parts of the network, TREAT directly examines the conflict set and removes instantiations that contain the deleted WM element.
TREAT also incorporates "condition membership" (tracking the number of WM elements matching a condition) and "memory support" (alpha-memories) similar to RETE, but it avoids the complex "condition relationship" state that RETE maintains. The paper also discusses join optimizations for TREAT, particularly "seed-ordering," which prioritizes processing newly added WM elements.
Datasets
The paper evaluates TREAT on five different OPS5 production system programs:
- MAB: The "Monkeys and Bananas" program.
- Waltz: A constraint propagation system.
- Mapper: A program for navigating Manhattan's public transportation system, notable for its very large WM (1124 elements).
- Mud: A system for analyzing oil well castings.
- Mesgen: A natural-language program that converts financial data into text.
These programs were chosen to represent a variety of system characteristics. The evaluation was performed using OPS5 interpreters, with a RETE-based interpreter from Carnegie Mellon University and TREAT-based interpreters developed at Columbia University.
Key Insights and Ideas
- Conflict-Set Support is Powerful: The core insight is that maintaining the conflict set directly and using WM changes as seeds for search can be more efficient than RETE's complex network for state management, especially when WM changes are frequent.
- Challenging the RETE Paradigm: The paper directly challenges the long-held assumption that RETE's comprehensive state-saving is always optimal, providing empirical evidence that simpler approaches can be superior.
- Deletions are a TREAT Strength: TREAT's direct handling of deletions in the conflict set proves significantly more efficient than RETE's need to potentially recompute and unwind its network.
- Seed-Ordering Optimization: The "seed-ordering" heuristic for join optimization in TREAT is crucial for achieving its best performance, demonstrating the importance of how search is guided.
Key Results
The empirical study comparing TREAT and RETE on five OPS5 programs yielded significant results:
- Overall Speedup: TREAT consistently outperformed RETE.
- Variable Binding Comparisons: TREAT required fewer comparisons for variable binding than RETE in all five programs.
- Substantial Speedups: In two instances, TREAT required less than half the comparisons of RETE.
- Optimization Impact: TREAT with "seed-ordering" optimization consistently outperformed RETE, even on a sequential computer.
- Sharing's Limited Impact: The study found that sharing network structures in RETE did not significantly contribute to performance in the variable binding phase.
- No Beta-Memories: The paper highlights that TREAT's lack of beta-memories (a key component of RETE) does not hinder its performance in the tested scenarios.
Limitations and Future Work
- Negated Condition Elements: The paper mentions that handling negated condition elements slightly complicates TREAT, but it is addressed in the abstract algorithm and detailed in other works by the authors.
- Parallelism: While the paper notes that RETE's network structure is not advantageous in parallel environments due to contention, it doesn't deeply explore TREAT's parallel performance beyond mentioning its potential benefits.
- Generalizability: The study focused on OPS5. While the authors suggest TREAT's join optimizations could make it effective for other production system languages, further validation on different platforms and languages would be beneficial.
- Future Work: The authors imply that further exploration of join optimizations and the application of TREAT to parallel architectures are promising directions. The paper also suggests that the efficiency gains observed support the conjecture that condition-element support in RETE may not always be worthwhile.
Summary updated