A Pathology of Bottom-up Hill-Climbing in Inductive Rule Learning
Abstract
In this paper, we close the gap between the simple and straight-forwardimplemen tations of top-down hill-climbing that can be foundin the literature, andthe rather complex strategies for greedy bottom-up generalization. Our main result is that the simple bottom-up counterpart to the top-down hill-climbing algorithm is unable to learn in domains with dispersed examples. In particular, we show that guided greedy generalization is impossible if the seed example differs in more than one attribute value from its nearest neighbor. We also perform an empirical study of the commonness of this problem is in popular benchmark datasets, andpresen t average-case andw orst-case results for the probability of drawing a pathological seed example in binary domains.
Cite
Text
Fürnkranz. "A Pathology of Bottom-up Hill-Climbing in Inductive Rule Learning." International Conference on Algorithmic Learning Theory, 2002. doi:10.1007/3-540-36169-3_22Markdown
[Fürnkranz. "A Pathology of Bottom-up Hill-Climbing in Inductive Rule Learning." International Conference on Algorithmic Learning Theory, 2002.](https://mlanthology.org/alt/2002/furnkranz2002alt-pathology/) doi:10.1007/3-540-36169-3_22BibTeX
@inproceedings{furnkranz2002alt-pathology,
title = {{A Pathology of Bottom-up Hill-Climbing in Inductive Rule Learning}},
author = {Fürnkranz, Johannes},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2002},
pages = {263-277},
doi = {10.1007/3-540-36169-3_22},
url = {https://mlanthology.org/alt/2002/furnkranz2002alt-pathology/}
}