TY  - RPRT
ID  - jf:TUD-KE-2008-02
T1  - A Re-Evaluation of the Over-Searching Phenomenon in Inductive Rule Learning
A1  - Janssen, Frederik
A1  - Fürnkranz, Johannes
Y1  - 2008
IS  - TUD-KE-2008-02
T2  - TU Darmstadt, Knowledge Engineering Group
UR  - /publications/reports/tud-ke-2008-02.pdf
N2  - Most commonly used inductive rule learning algorithms employ a hill-climbing search,
whereas local pattern discovery algorithms employ exhaustive search. In this paper, we
evaluate the spectrum of different search strategies to see whether separate-and-conquer
rule learning algorithms are able to gain performance in terms of predictive accuracy or
theory size by using more powerful search strategies like beam search or exhaustive search.
Unlike previous results that demonstrated that rule learning algorithms suffer from oversearching, our work pays particular attention to the connection between the search heuristic and the search strategy, and we show that for some rule evaluation functions, complex search algorithms will consistently improve results without suffering from the over-searching phenomenon. In particular, we will see that this is typically the case for heuristics which perform bad in a hill-climbing search. We interpret this as evidence that commonly used rule learning heuristics mix two different aspects: a rule evaluation metric that measures the predictive quality of a rule, and a search heuristic that captures the potential of a candidate rule to be refined into highly predictive rule. For effective exhaustive search,
these two aspects need to be clearly separated.
ER  -