Bounding the cost of learned rules

Jihie Kim, Paul S. Rosenbloom

Research output: Contribution to journalArticlepeer-review

Abstract

In this article we approach one key aspect of the utility problem in explanation-based learning (EBL) - the expensive-rule problem - as an avoidable defect in the learning procedure. In particular, we examine the relationship between the cost of solving a problem without learning versus the cost of using a learned rule to provide the same solution, and refer to a learned rule as expensive if its use is more costly than the original problem solving from which it was learned. The key idea we explore is that expensiveness is inadvertently and unnecessarily introduced into learned rules by the learning algorithms themselves. This becomes a particularly powerful idea when combined with an analysis tool which identifies these hidden sources of expensiveness, and modifications of the learning algorithms which eliminate them. The result is learning algorithms for which the cost of learned rules is bounded by the cost of the problem solving that they replace.

Original languageEnglish
Pages (from-to)43-80
Number of pages38
JournalArtificial Intelligence
Volume120
Issue number1
DOIs
StatePublished - Jun 2000

Fingerprint

Dive into the research topics of 'Bounding the cost of learned rules'. Together they form a unique fingerprint.

Cite this