Controlled Utilization of Control Knowledge for Speeding up Logic Inference

Oleg Ledeniov and Shaul Markovitch. Controlled Utilization of Control Knowledge for Speeding up Logic Inference. Technical Report CIS9812, Technion, 1998.

Abstract

The utility problem occurs when the cost of the acquired knowledge outweighs its benefit. When the learner acquires control knowledge for speeding up a problem solver, the benefit is the speedup gained due to the better control, and the cost is the added time required by the control procedure due to the added knowledge. Previous work in this area was mainly concerned with the cost of matching control rules. The solutions to this kind of utility problem involved some kind of selection mechanism to reduce the number of control rules (or, generally, they involved filtering of control knowledge). In this work we consider a control mechanism that carries very high cost regardless of the particular knowledge acquired, therefore filtering of control knowledge does not reduce the execution time. We propose to use in such cases explicit reasoning about the economy of the control process. A 'control of control' module supervises the work of the control procedure, invoking and stopping it selectively. For its decisions, this module needs some ``control of control'' knowledge, which can be learned from experience. We have implemented this framework within the context of a program for speeding up logic inference by subgoal ordering. We conducted a series of experiments that showed the usefulness of the proposed framework.

Keywords: Speedup Learning, Utility Problem, Resource-Bounded Reasoning

Secondary Keywords:

Online version:

Bibtex entry:

 @techreport{Ledeniov:1998:CUC,
  Author = {Oleg Ledeniov and Shaul Markovitch},
  Title = {Controlled Utilization of Control Knowledge for Speeding up Logic Inference},
  Year = {1998},
  Number = {CIS9812},
  Type = {Technical Report},
  Institution = {Technion},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Ledeniov-Markovitch-CIS9812.pdf},
  Keywords = {Speedup Learning, Utility Problem, Resource-Bounded Reasoning},
  Secondary-keywords = {Anytime Algorithms, Logic Programming, Learning to Order},
  Abstract = {
    The utility problem occurs when the cost of the acquired knowledge
    outweighs its benefit. When the learner acquires control knowledge
    for speeding up a problem solver, the benefit is the speedup
    gained due to the better control, and the cost is the added time
    required by the control procedure due to the added knowledge.
    Previous work in this area was mainly concerned with the cost of
    matching control rules. The solutions to this kind of utility
    problem involved some kind of selection mechanism to reduce the
    number of control rules (or, generally, they involved filtering of
    control knowledge). In this work we consider a control mechanism
    that carries very high cost regardless of the particular knowledge
    acquired, therefore filtering of control knowledge does not reduce
    the execution time. We propose to use in such cases explicit
    reasoning about the economy of the control process. A 'control of
    control' module supervises the work of the control procedure,
    invoking and stopping it selectively. For its decisions, this
    module needs some ``control of control'' knowledge, which can be
    learned from experience. We have implemented this framework within
    the context of a program for speeding up logic inference by
    subgoal ordering. We conducted a series of experiments that showed
    the usefulness of the proposed framework.
  }

  }