A Clustering and Demotion Based Algorithm for Inductive Learning of Default Theories
This work addresses the need for more efficient and interpretable inductive logic programming systems, though it is incremental as it builds on existing methods like FOLD and FOIL.
The paper tackles the problem of inducing nonmonotonic logic programs from examples by proposing Kmeans-FOLD, which improves upon the FOLD algorithm using clustering and demotion strategies, resulting in more concise programs and significant improvements for datasets with multiple clusters.
We present a clustering- and demotion-based algorithm called Kmeans-FOLD to induce nonmonotonic logic programs from positive and negative examples. Our algorithm improves upon-and is inspired by-the FOLD algorithm. The FOLD algorithm itself is an improvement over the FOIL algorithm. Our algorithm generates a more concise logic program compared to the FOLD algorithm. Our algorithm uses the K-means based clustering method to cluster the input positive samples before applying the FOLD algorithm. Positive examples that are covered by the partially learned program in intermediate steps are not discarded as in the FOLD algorithm, rather they are demoted, i.e., their weights are reduced in subsequent iterations of the algorithm. Our experiments on the UCI dataset show that a combination of K-Means clustering and our demotion strategy produces significant improvement for datasets with more than one cluster of positive examples. The resulting induced program is also more concise and therefore easier to understand compared to the FOLD and ALEPH systems, two state of the art inductive logic programming (ILP) systems.