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: | /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. |
| Keywords: | |
| Authors | |
|
Attachments
|
|
|
|
|
Topics
|
|
|
|
