Accession Number : ADA293105

Title :   Production Matching for Large Learning Systems.

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Doorenbos, Robert B.

PDF Url : ADA293105

Report Date : 31 JAN 1995

Pagination or Media Count : 208

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.

Descriptors :   *PRODUCTION, *LEARNING MACHINES, *MATCHING, ALGORITHMS, METHODOLOGY, TEST BEDS, THESES, PROBLEM SOLVING, COSTS, SCALE, ARTIFICIAL INTELLIGENCE, LEARNING.

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE