A Statistical Approach to Solving the EBL Utility Problem
Full Text:
utility.ps 
Many "learning from experience" systems use information extracted from problem solving experiences to modify a performance element PE, forming a new one PE' that can solve these and similar problems more efficiently. However, as transformations that improve performance on one set of problems can degrade performance on other sets, the new PE' is not always better than the original PE; this depends on the distribution of problems. We therefore seek the the performance element whose expected performance, over this distribution, is optimal. Unfortunately, the actual distribution, which is needed to determine which element is optimal, is usually not known. Moreover, the task of finding the optimal element, even knowing the distribution, is intractable for most interesting spaces of elements. This paper presents a method, PALO, that side-steps these problems by using a set of samples to estimate the unknown distribution, and by using a set of transformations to hill-climb to a local optimum: Given any parameters $epsilon, delta > 0$, PALO produces an element PE' whose expected performance is, with probability $geq 1-delta$, within $epsilon$ of a local optimum. This process is based on a mathematically rigorous form of utility analysis: in particular, it uses statistical techniques to determine whether the result of a proposed transformation will be better than the original system. We also present an efficient way of implementing this learning system in the context of a general class of performance elements; and include empirical evidence that this approach can work effectively.
Citation
R. Greiner,
I. Jurisica.
"A Statistical Approach to Solving the EBL Utility Problem".
National Conference on Artificial Intelligence (AAAI), July 1992.
| Keywords: |
statistical, utility problem, EBL, machine learning, PALO, empirical |
| Category: |
In Conference |
BibTeX
@incollection{Greiner+Jurisica:AAAI92,
author = {Russ Greiner and Igor Jurisica},
title = {A Statistical Approach to Solving the EBL Utility Problem},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 1992,
}Last Updated: April 24, 2007
Submitted by Russ Greiner 
