Learning Investment Functions for Controlling the Utility of Control Knowledge
Oleg Ledeniov and Shaul Markovitch. Learning Investment Functions for Controlling the Utility of Control Knowledge. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, 463-468 Madison, Wisconsin, 1998.
Abstract
The utility problem occurs when the cost of the acquired knowledge outweighs its benefits. 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 costs 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. In this work we deal with a control mechanism that carries very high cost regardless of the particular knowledge acquired. We propose to use in such cases explicit reasoning about the economy of the control process. The solution includes three steps. First, the control procedure must be converted to anytime procedure. Second, a resource-investment function should be acquired to learn the expected return in speedup time for additional control time. Third, the function is used to determine a stopping condition for the anytime procedure. We have implemented this framework within the context of a program for speeding up logic inference by subgoal ordering. The control procedure utilizes the acquired control knowledge to find efficient subgoal ordering. The cost of ordering, however, may outweigh its benefit. Resource investment functions are used to cut-off ordering when the future net return is estimated to be negative.
Keywords: Speedup Learning, Utility Problem, Resource-Bounded Reasoning
Secondary Keywords:
Online version:
Bibtex entry:
@inproceedings{Ledeniov:1998:LIF,
Author = {Oleg Ledeniov and Shaul Markovitch},
Title = {Learning Investment Functions for Controlling the Utility of Control Knowledge},
Year = {1998},
Booktitle = {Proceedings of the Fifteenth National Conference on Artificial Intelligence},
Pages = {463--468},
Address = {Madison, Wisconsin},
Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Ledeniov-Markovitch-aaai1998.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 benefits. 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 costs 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. In this work we deal with a
control mechanism that carries very high cost regardless of the
particular knowledge acquired. We propose to use in such cases
explicit reasoning about the economy of the control process. The
solution includes three steps. First, the control procedure must
be converted to anytime procedure. Second, a resource-investment
function should be acquired to learn the expected return in
speedup time for additional control time. Third, the function is
used to determine a stopping condition for the anytime procedure.
We have implemented this framework within the context of a program
for speeding up logic inference by subgoal ordering. The control
procedure utilizes the acquired control knowledge to find
efficient subgoal ordering. The cost of ordering, however, may
outweigh its benefit. Resource investment functions are used to
cut-off ordering when the future net return is estimated to be
negative.
}
}