Home | Publications | CS Home

Utilization Filtering: a Method for Reducing the Inherent Harmfulness of Deductively Learned Knowledge

---

Shaul Markovitch and Paul Scott. Utilization Filtering: a Method for Reducing the Inherent Harmfulness of Deductively Learned Knowledge. In Proceedings of The Eleventh International Joint Conference for Artificial Intelligence, 738-743 Detroit, Michigan, 1989.

---

Abstract

This paper highlights a phenomenon that causes deductively learned knowledge to be harmful when used for problem solving. The problem occurs when deductive problem solvers encounter a failure branch of the search tree. The backtracking mechanism of such problem solvers will force the program to traverse the whole subtree thus visiting many nodes twice - once by using the deductively learned rule and once by using the rules that generated the learned rule in the first place. We suggest an approach called utilization filtering to solve that problem. Learners that use this approach submit to the problem solver a filter function together with the knowledge that was acquired. The function decides for each problem whether to use the learned knowledge and what part of it to use. We have tested the idea in the context of a lemma learning system, where the filter uses the probability of a subgoal failing to decide whether to turn lemma usage off. Experiments show an improvement of performance by a factor of 3.

---

Keywords: Utility Problem, Lemma Learning, Selective Learning, Speedup Learning

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @inproceedings{Markovitch:1989:UFM,
  Author = {Shaul Markovitch and Paul Scott},
  Title = {Utilization Filtering: a Method for Reducing the Inherent Harmfulness of Deductively Learned Knowledge},
  Year = {1989},
  Booktitle = {Proceedings of The Eleventh International Joint Conference for Artificial Intelligence},
  Pages = {738--743},
  Address = {Detroit, Michigan},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Scott-ijcai1989.pdf},
  Keywords = {Utility Problem, Lemma Learning, Selective Learning, Speedup Learning},
  Secondary-keywords = {Deductive Learning, Utilization Filtering, Explanation-Based Learning, Information Filtering},
  Abstract = {
    This paper highlights a phenomenon that causes deductively learned
    knowledge to be harmful when used for problem solving. The problem
    occurs when deductive problem solvers encounter a failure branch
    of the search tree. The backtracking mechanism of such problem
    solvers will force the program to traverse the whole subtree thus
    visiting many nodes twice - once by using the deductively learned
    rule and once by using the rules that generated the learned rule
    in the first place. We suggest an approach called utilization
    filtering to solve that problem. Learners that use this approach
    submit to the problem solver a filter function together with the
    knowledge that was acquired. The function decides for each problem
    whether to use the learned knowledge and what part of it to use.
    We have tested the idea in the context of a lemma learning system,
    where the filter uses the probability of a subgoal failing to
    decide whether to turn lemma usage off. Experiments show an
    improvement of performance by a factor of 3.
  }

  }