@PHDTHESIS{Doo95,
author = {Doorenbos, Robert B.},
title = {Production Matching for Large Learning Systems},
school = {Carnegie Mellon University},
year = {1995},
address = {Pittsburgh, PA},
abstract = {One of the central results on AI research in the 1970's was that to
achieve good performance, AI 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 emph{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,00 rules.
We show that with the best existing match algorithms, the match cost
increase 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, 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.},
keywords = {Artificial Intelligence sep Large-Scale Production Systems sep Machine
Learning sep Production Match sep Soar},
}
@ARTICLE{For82,
author = {Forgy, Charles L.},
title = {Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match
Problem},
journal = {Artificial Intelligence},
year = {1982},
volume = {19},
pages = {17--37},
number = {1},
abstract = {The Rete Match Algorithm is an efficient method for comparing a large
collection of patterns to a large collection of objects. It finds
all the objects that match each pattern. The algorithm was developed
for use in production system interpreters, and it has been used for
systems containing from a few hundred to more than a thousand pattern
and objects. This article presents the algorithm in detail. It explains
the basic concepts of the algorithm, it describes pattern and object
representations that are appropriate for the algorithm, and it describes
the operations performed by the pattern matcher.},
}