Shaul Markovitch. Information Filtering: Selection Mechanisms in Learning Systems. PhD Thesis, EECS Department, University of Michigan, 1989.
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.
@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. } }