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