1996

Efficient \($\Theta$\)-Subsumption Based on Graph Algorithms. Scheffer, Tobias; Herbrich, Ralf; Wysotzki, Fritz (1996). (Vol. 1314) 212–228.
[ Abstract ] [ BibTeX ] [ URL ]
 
The \($\theta$\)-subsumption problem is crucial to the efficiency of ILP learning systems. We discuss two \($\theta$\)-subsumption algorithms based on strategies for preselecting suitable matching literals. The class of clauses, for which subsumption becomes polynomial, is a superset of the deterministic clauses. We further map the general problem of \($\theta$\)-subsumption to a certain problem of finding a clique of fixed size in a graph, and in return show that a specialization of the pruning strategy of the Carraghan and Pardalos clique algorithm provides a dramatic reduction of the subsumption search space. We also present empirical results for the mesh design data set.
@inproceedings{scheffer1996efficient, abstract = {The $\theta$-subsumption problem is crucial to the efficiency of ILP learning systems. We discuss two $\theta$-subsumption algorithms based on strategies for preselecting suitable matching literals. The class of clauses, for which subsumption becomes polynomial, is a superset of the deterministic clauses. We further map the general problem of $\theta$-subsumption to a certain problem of finding a clique of fixed size in a graph, and in return show that a specialization of the pruning strategy of the Carraghan and Pardalos clique algorithm provides a dramatic reduction of the subsumption search space. We also present empirical results for the mesh design data set.}, author = {Scheffer, Tobias and Herbrich, Ralf and Wysotzki, Fritz}, booktitle = {Lecture Notes in Artifical Intelligence: 6th International Workshop on Inductive Logic Programming,}, keywords = {imported ralf.herbrich}, pages = {212–228}, title = {Efficient $\Theta$-Subsumption Based on Graph Algorithms}, volume = 1314, year = 1996 }