Local Hill-Climbing Algorithm

References

(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.

(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.

(Gent & Walsh, 1993) ⇒ Gent, I.P. and Walsh, T. (1993). “Towards an Understanding of Hill-Climbing Procedures for SAT.” In: Proceedings of AAAI Conference (AAAI 1993)