PALO: A Probabilistic Hill-Climbing Algorithm
- Russ Greiner, Dept of Computing Science; PI of AICML
Many learning systems search through a space of possible performance elements, seeking an element whose expected utility, over the distribution of problems, is high. As the task of finding the globally optimal element is usually intractable, many practical learning systems use hill-climbing to find a local optimum. Unfortunately, even this is problematic as the underlying distribution of problems, required to determine an element's expected utility and hence essential for comparing different elements, is typically unknown. This paper addresses the task of approximating this hill-climbing search when the utility function can only be estimated by sampling. We present an algorithm that returns an element that is, with provably high probability, essentially a local optimum. We then demonstrate the generality of this algorithm by sketching three meaningful applications, that respectively find an element whose efficiency, accuracy or completeness is nearly optimal. These results suggest approaches to solving the utility problem from explanation-based learning, the multiple extension problem from nonmonotonic reasoning and the tractability/completeness tradeoff problem from knowledge representation.
Citation
R. Greiner. "PALO: A Probabilistic Hill-Climbing Algorithm". Artificial Intelligence (AIJ), 84(1-2), pp 177--204, July 1996.| Keywords: | PALO, hill climbing, machine learning |
| Category: | In Journal |
BibTeX
@article{Greiner:AIJ96,
author = {Russ Greiner},
title = {PALO: A Probabilistic Hill-Climbing Algorithm},
Volume = "84",
Number = "1-2",
Pages = {177--204},
journal = {Artificial Intelligence (AIJ)},
year = 1996,
}Last Updated: April 24, 2007Submitted by Russ Greiner
