Information Filtering: Selection Mechanisms in Learning Systems
Shaul Markovitch. Information Filtering: Selection Mechanisms in Learning Systems. PhD Thesis, EECS Department, University of Michigan, 1989.
Abstract
Traditionally knowledge was considered as beneficial to the performance of problem solvers. Recent studies indicate that knowledge acquisition is not necessarily a monotonic process, and that sometimes additional knowledge leads to deterioration in system performance. This thesis studies the problem of harmful knowledge in learning systems, defines a unifying framework to deal with the problem, and tests the framework in the context of a useful learning system. Knowledge is harmful if the problem solver's performance would be improved by removing it. The information filtering model is proposed as a unifying framework for reducing or eliminating harmfulness of knowledge. The framework identifies five logical types of selection processes (filters) that can be incorporated into learning systems in order to reduce harmful knowledge: selective experience, attention, acquisition, retention and utilization. The framework is implemented and tested within the context of LASSY, a learning system that improves the performance of a PROLOG interpreter by utilizing acquired domain specific knowledge. LASSY incorporates two primary learning mechanisms: one deductive and the other inductive. The deductive mechanism is a lemma learner which uses theorems proved in the past as shortcuts for future proving. The inductive mechanism is a module that acquires average costs and number of solutions for various calling patterns that are used for reordering subgoals in rule bodies. LASSY incorporates all five types of selection mechanisms. The two novel ones are an experience filter which uses a model of the task domain to generate training problems that are likely to generate relevant knowledge and utilization filter which is used for filtering out the usage of lemmas in branches of the search tree which have high probability of failing. The system's performance was improved by a factor of two when using the lemma learner and its filters. The subgoal reordering improved the system performance by a factor of 23. When combined, the system's performance was improved by a factor of 36. It is concluded that it is not beneficial to be greedy, even for knowledge, and that being selective by inserting information filters can reduce the harmfulness of knowledge in learning systems.
Keywords: Utility Problem, Selective Learning, Active Learning, Lemma Learning
Secondary Keywords:
Online version:
Bibtex entry:
@phdthesis{Markovitch:1989:IFS,
Author = {Shaul Markovitch},
Title = {Information Filtering: Selection Mechanisms in Learning Systems},
Year = {1989},
School = {EECS Department, University of Michigan},
Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-thesis.pdf},
Keywords = {Utility Problem, Selective Learning, Active Learning, Lemma Learning},
Secondary-keywords = {Learning to Order, Information Filtering, Forgetting, Selective Utilization, Deductive Learning, Explanation-Based Learning},
Abstract = {
Traditionally knowledge was considered as beneficial to the
performance of problem solvers. Recent studies indicate that
knowledge acquisition is not necessarily a monotonic process, and
that sometimes additional knowledge leads to deterioration in
system performance. This thesis studies the problem of harmful
knowledge in learning systems, defines a unifying framework to
deal with the problem, and tests the framework in the context of a
useful learning system. Knowledge is harmful if the problem
solver's performance would be improved by removing it. The
information filtering model is proposed as a unifying framework
for reducing or eliminating harmfulness of knowledge. The
framework identifies five logical types of selection processes
(filters) that can be incorporated into learning systems in order
to reduce harmful knowledge: selective experience, attention,
acquisition, retention and utilization. The framework is
implemented and tested within the context of LASSY, a learning
system that improves the performance of a PROLOG interpreter by
utilizing acquired domain specific knowledge. LASSY incorporates
two primary learning mechanisms: one deductive and the other
inductive. The deductive mechanism is a lemma learner which uses
theorems proved in the past as shortcuts for future proving. The
inductive mechanism is a module that acquires average costs and
number of solutions for various calling patterns that are used for
reordering subgoals in rule bodies. LASSY incorporates all five
types of selection mechanisms. The two novel ones are an
experience filter which uses a model of the task domain to
generate training problems that are likely to generate relevant
knowledge and utilization filter which is used for filtering out
the usage of lemmas in branches of the search tree which have high
probability of failing. The system's performance was improved by a
factor of two when using the lemma learner and its filters. The
subgoal reordering improved the system performance by a factor of
23. When combined, the system's performance was improved by a
factor of 36. It is concluded that it is not beneficial to be
greedy, even for knowledge, and that being selective by inserting
information filters can reduce the harmfulness of knowledge in
learning systems.
}
}