Covering vs. Divide-and-Conquer for Top-Down Induction of Logic Programs

Abstract

Covering and divide-and-conquer are two wellestablished search techniques for top-down induction of propositional theories. However, for top-down induction of logic programs, only covering has been formalized and used extensively. In this work, the divide-and-conquer technique is formalized as well and compared to the covering technique in a logic programming framework. Covering works by repeatedly specializing an overly general hypothesis, on each iteration focusing on finding a clause with a high coverage of positive examples. Divide-and-conquer works by specializing an overly general hypothesis once, focusing on discriminating positive from negative examples. Experimental results are presented demonstrating that there are cases when more accurate hypotheses can be found by divideand-conquer than by covering. Moreover, since covering considers the same alternatives repeatedly it tends to be less efficient than divideand-conquer, which never considers the same alternative twice. On the other hand, covering searches a larger hypothesis space, which may result in that more compact hypotheses are found by this technique than by divide-andconquer. Furthermore, divide-and-conquer is, in contrast to covering, not applicable to learning recursive definitions,