Matching 100,045 Learned Rules

AAAI 1993

TL;DR

This paper tackles the challenge of efficiently matching a massive number of rules (over 100,000) in AI production systems, a scenario common in machine learning and cognitive modeling. The authors demonstrate that standard Rete and Treat algorithms struggle to scale with rule count, but introduce a novel "right unlinking" optimization that significantly improves performance, making large-scale rule learning more feasible.

What Problem Does This Paper Address?

Modern AI systems, particularly those that learn from experience (like machine learning systems) or aim to model human cognition, can accumulate an enormous number of rules or "productions." This paper focuses on the critical problem of matching – determining which of these rules should be activated given the current state of the system's "working memory." The core challenge is that as the number of rules grows, the computational cost of matching can increase dramatically, leading to the "utility problem" in machine learning: learned rules might slow down the system more than they speed it up. Previous research on smaller systems suggested that matching algorithms like Rete and Treat scale well, but this paper investigates much larger systems and finds this assumption breaks down.

Methods

The authors evaluate the performance of two standard matching algorithms: Rete (Forgy, 1982) and Treat (Miranker, 1990). Rete uses a dataflow network to represent rule conditions, with alpha and beta parts for testing working memory elements and joining partial matches, respectively. Treat is a similar algorithm that doesn't explicitly build the network but still performs the same logical operations.

The key novel contribution is the "right unlinking" optimization for the Rete algorithm. This optimization addresses the slowdown caused by "right activations" of join nodes in the Rete network. When a working memory element is added, it can trigger a right activation of a join node. If the join node's associated "beta memory" (which stores partial matches) is empty, this activation is essentially a "null right activation" and does no useful work. Right unlinking works by maintaining a count of items in beta memories. If a beta memory becomes empty, the corresponding join node is temporarily "unlinked" from its alpha memory, preventing future null right activations. Conversely, if a beta memory becomes non-empty, the join node is relinked.

Datasets

The paper does not use traditional "datasets" in the sense of static data for training. Instead, it evaluates its algorithms on four large-scale production systems that learn rules dynamically:

  • Dispatcher-Soar: A message dispatcher system that learns ~114,000 rules.
  • Assembler-Soar: A cognitive model of assembling circuit boards, learning ~35,000 rules.
  • Memory1 & Memory2: Two "artificial" systems built for the experiments, learning ~102,000 and ~60,000 rules respectively, designed to mimic aspects of the other systems.

These systems were run on problem generators to create sequences of problems, allowing them to learn and grow their rule bases.

Key Insights and Ideas

  • Standard Rete and Treat Don't Scale: Contrary to expectations from smaller systems, the performance of standard Rete and Treat algorithms degrades significantly as the number of rules increases beyond tens of thousands.
  • Affect Set Size is Crucial: The "affect set size" (the number of rules affected by a change in working memory) is not small and constant as previously thought for systems that use extensive problem-space search. In these large learning systems, the affect set size grows linearly with the number of rules.
  • Sharing is More Important Than Expected: While sharing of network nodes in the Rete algorithm has been considered less critical in smaller systems, it becomes vital for performance in large systems, especially for nodes higher up in the Rete network.
  • Null Right Activations are a Major Bottleneck: The primary cause of slowdown in the Dispatcher and Memory1 systems was identified as an increasing number of "null right activations" in the Rete network, which do no useful work but consume CPU cycles.
  • Right Unlinking is Highly Effective: The proposed "right unlinking" optimization dramatically reduces the impact of null right activations, leading to substantial speedups, particularly in systems with very large rule bases.

Key Results

  • The standard Rete algorithm showed a substantial increase in match cost as the number of rules grew, with systems learning over 100,000 rules experiencing significant performance degradation.
  • The average affect set size in these large learning systems grew linearly with the number of rules, reaching up to ~10,000 productions affected per cycle in some cases.
  • Sharing of Rete network nodes provided significant token reduction (up to 2-3 orders of magnitude in Dispatcher and Memory1) as rule count increased.
  • The right unlinking optimization resulted in speedup factors of 40-50 for the Dispatcher and Memory1 systems when they reached ~100,000 rules, effectively eliminating the slowdown observed with standard Rete.
  • For Assembler and Memory2 systems, right unlinking provided smaller speedups (2-3x), indicating other sources of slowdown (left activations and beta memory activations) were also contributing.

Limitations and Future Work

  • Limitations: The paper acknowledges that while right unlinking is effective, it only addresses one source of slowdown (right activations). Other sources, like left activations and beta memory activations, still contribute to performance degradation in some systems (Assembler and Memory2). The authors also note that measuring performance solely by CPU time can be implementation-dependent, though they used the same implementation for comparisons.
  • Future Work: The authors suggest further work is needed to develop and evaluate optimizations for left activations and beta memory activations. They also propose exploring hybrid approaches combining Rete and Treat, or developing optimizations analogous to right unlinking for Treat, to address the remaining slowdowns. Understanding the precise reasons for the differing effectiveness of sharing across systems (Dispatcher/Memory1 vs. Assembler/Memory2) is also an area for further investigation.

Summary updated

BibTeX
@inproceedings{1993matching,
  title = {{Matching 100,045 Learned Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure