[BibTeX] [RIS]
A Re-Evaluation of the Over-Searching Phenomenon in Inductive Rule Learning
Type of publication: Techreport
Citation: jf:TUD-KE-2008-02
Number: TUD-KE-2008-02
Year: 2008
Institution: TU Darmstadt, Knowledge Engineering Group
URL: http://www.ke.informatik.tu-darmstadt.de/publications/reports/tud-ke-2008-02.pdf
Abstract: 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 diff erent 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 suff er 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 suff ering 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 diff erent 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.
Authors Janssen, Frederik
F├╝rnkranz, Johannes
  • tud-ke-2008-02.pdf