OFAI

Technical Reports - Query Results

Your query term was 'number = 2002-28'
1 report found
OFAI-TR-2002-28 ( 218kB PDF file)

A Pathology of Bottom-Up Hill-Climbing in Inductive Rule Learning

Johannes Fürnkranz

In this paper, we close the gap between the simple and straight-forward implementations of top-down hill-climbing that can be found in the literature, and the comparably complex strategies for greedy bottom-up generalization. Our main result is that the simple bottom-up counterpart of the top-down hill-climbing algorithm is unable to learn in domains with comparably dispersed examples. In particular, we show that greedy generalization from a seed example is impossible if it differs from its nearest neighbor in more than one attribute value. We also perform an empirical study of the how frequent this case is in popular benchmark datasets, and present average-case and worst-case results for binary domains.

Keywords: Rule Learning, Hill-Climbing

Citation: Fürnkranz J.: A Pathology of Bottom-Up Hill-Climbing in Inductive Rule Learning. In Proceedings of the 13th International Conference on Algorithmic Learning Theory (ALT-02), Lübeck, Germany. Springer-Verlag 2002.