Combining Left and Right Unlinking for Matching a Large Number of Learned Rules

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Enabling Technologies

In systems which learn a large number of rules (productions), it is important to match the rules efficiently, in order to avoid the machine learning utility problem. So we need match algorithms that scale well with the number of productions in the system. (Doorenbos 1993) introduced right unlinking as a way to improve the scalability of the Rete match algorithm. This paper introduces a symmetric optimization, left unlinking, and demonstrates that it makes Rete scale well on an even larger class of systems. Unfortunately, when left and right unlinking are combined in the same system, they can interfere with each other. We give a particular way to combine them which we prove minimizes this interference, and analyze the worst-case remaining interference. Finally, we present empirical results showing that the interference is very small in practice, and that the combination of left and right unlinking allows five of our seven testbed systems to learn over 100,000 rules without incurring a significant increase in match cost.