Accession Number:

ADA278979

Title:

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

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Doorenbos, Robert B.

Report Date:

1994-04-04

Pagination or Media Count:

18.0

Abstract:

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.

Descriptors:

• *RULE BASED SYSTEMS
• *ARTIFICIAL INTELLIGENCE
• ALGORITHMS
• EXPERIMENTAL DATA
• KNOWLEDGE BASED SYSTEMS
• MATCHING
• OPTIMIZATION
• COMPUTER COMMUNICATIONS
• LEARNING MACHINES

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE