Local Hill-Climbing Algorithm

From GM-RKB
(Redirected from Local Maxima)
Jump to navigation Jump to search

A Local Hill-Climbing Algorithm is a Hill-Climbing Algorithm that only makes local decisions.



References

2009

  • (Kulkarni et al., 2009) ⇒ Sayali Kulkarni, Amit Singh, Ganesh Ramakrishnan, Soumen Chakrabarti. (2009). “Collective Annotation of Wikipedia Entities in Web Text.” In: Proceedings of ACM SIGKDD Conference (KDD-2009). doi:10.1145/1557019.1557073.
    • We investigate practical solutions based on local hill-climbing, rounding integer linear programs, and pre-clustering entities followed by local optimization within clusters. ...
    • Inference is NP-hard. We propose practical and effective heuristics based on local hill-climbing and linear program relaxations. ...
    • We also give a simple local hill-climbing algorithm that is comparable in speed and quality to LP relaxation.

1994

  • (Caruana & Freitag, 1994) ⇒ Rich Caruana, and Dayne Freitag. (1994). “Greedy Attribute Selection.” In: Proceedings of the Eleventh International Conference on Machine Learning
    • ABSTRACT: Many real-world domains bless us with a wealth of attributes to use for learning. This blessing is often a curse: most inductive methods generalize worse given too many attributes than if given a good subset of those attributes. We examine this problem for two learning tasks taken from a calendar scheduling domain. We show that ID3/C4.5 generalizes poorly on these tasks if allowed to use all available attributes. We examine five greedy hillclimbing procedures that search for attribute sets that generalize well with ID3/C4.5. Experiments suggest hillclimbing in attribute space can yield substantial improvements in generalization performance. We present a caching scheme that makes attribute hillclimbing more practical computationally. We also compare the results of hillclimbing in attribute space with FOCUS and RELIEF on the two tasks.

1993