Oversearching and Layered Search in Empirical Learning

When learning classifiers, more extensive search for rules is shown to lead to lower predictive accuracy on many of the real-world domains investigated. This counter-intuitive result is particularly relevant to recent systematic search methods that use risk-free pruning to achieve the same outcome as exhaustive search. We propose an iterated search method that commences with greedy search, extending its scope at each iteration until a stopping criterion is satisfied. This layered search is often found to produce theories that are more accurate than those obtained with either greedy search or moderately extensive beam search. 1 Introduction Mitchell [1982] observes that the generalization implicit in learning from examples can be viewed as a search over the space of possible theories. From this perspective, most machine learning methods carry out a series of local searches in the vicinity of the current theory, selecting at each step the most promising improvement. Covering algorithms ..