Not Logged In

Probabilistic Hill-Climbing

Many learning tasks involve searching through a discrete space of performance elements, seeking an element whose future utility is expected to be high. As the task of finding the global optimum is often intractable, many practical learning systems use sim­ ple forms of hill­climbing to find a locally optimal element. However, hill­climbing can be complicated by the fact that the utility value of a performance element can depend on the distribution of problems, which typically is unknown. This paper formulates the problem of performing hill­climbing search in settings where the required utility values can only be estimated on the basis of their performance on random test cases. We present and prove correct an algorithm that returns a performance element that is arbitrarily close to a local optimum with arbitrarily high probability.

Citation

W. Cohen, R. Greiner, D. Schuurmans. "Probabilistic Hill-Climbing". Computational Learning Theory and Natural Learning Systems, (Edition II), MIT Press, pp 171--181, January 1992.

Keywords: probabilistic, machine learning, PALO, hill-climbing
Category: In Workshop

BibTeX

@misc{Cohen+al:CLNL92,
  author = {William W. Cohen and Russ Greiner and Dale Schuurmans},
  title = {Probabilistic Hill-Climbing},
  Publisher = {MIT Press},
  Edition = "II",
  Pages = {171--181},
  booktitle = {Computational Learning Theory and Natural Learning Systems},
  year = 1992,
}

Last Updated: May 12, 2007
Submitted by Russ Greiner

University of Alberta Logo AICML Logo