DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Combining Left and Right Unlinking for Matching a Large Number of Learned Rules
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 -- if the learned rules slow down the matcher, the learning can slow the whole system down to a crawl. So we need match algorithms that scale well with the number of productions in the system. Right unlinking was introduced as a way to improve the scalability of the Rete match algorithm. In this paper we build on this idea, introducing a symmetric optimization, left unlinking, and demonstrating 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 the 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.
APPROVED FOR PUBLIC RELEASE