Production Matching for Large Learning Systems.
Abstract
One of the central results of AI research in the 1970's was that to achieve good performance, Al systems must have large amounts of knowledge. Machine learning techniques have been developed to automatically acquire knowledge, often in the form of if-then rules (productions). Unfortunately, this often leads to a utility problem - the "learning" ends up causing an overall slowdown in the system. This is because the more rules a system has, the longer it takes to match them against the current situation in order to determine which ones are applicable. To address this problem, this thesis is aimed at enabling the scaling up of the number of rules in production systems. We examine a diverse set of testbed systems, each of which learns at least 100,000 rules. We show that with the best existing match algorithms, the match cost increases linearly in the number of rules in these systems. This is inadequate for large learning systems, because it leads to a utility problem. We then examine the causes of this linear increase, and develop techniques which eliminate the major causes. The end result is an improved match algorithm, Rete/UL, which is a general extension of the existing state-of-the- art Rete match algorithm. Rete/UL's performance scales well on a significantly broader class of systems than existing match algorithms. The use of Rete/UL rather than Rete significantly reduces or eliminates the utility problem in all the testbed systems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 31, 1995
- Accession Number
- ADA293105
Entities
People
- Robert B. Doorenbos
Organizations
- Carnegie Mellon University