Fast Estimation of First-Order Clause Coverage Through Randomization and Maximum Likelihood
Abstract
In inductive logic programming, θ-subsumption is a widely used coverage test. Unfortunately, testing θ-subsumption is NP-complete, which represents a crucial efficiency bottleneck for many relational learners. In this paper, we present a probabilistic estimator of clause coverage, based on a randomized restarted search strategy. Under a distribution assumption, our algorithm can estimate clause coverage without having to decide subsumption for all examples. We implement this algorithm in program ReCovEr. On generated graph data and real-world datasets, we show that ReCovEr provides reasonably accurate estimates while achieving dramatic runtimes improvements compared to a state-of-the-art algorithm.
Cite
Text
Kuzelka and Zelezný. "Fast Estimation of First-Order Clause Coverage Through Randomization and Maximum Likelihood." International Conference on Machine Learning, 2008. doi:10.1145/1390156.1390220Markdown
[Kuzelka and Zelezný. "Fast Estimation of First-Order Clause Coverage Through Randomization and Maximum Likelihood." International Conference on Machine Learning, 2008.](https://mlanthology.org/icml/2008/kuzelka2008icml-fast/) doi:10.1145/1390156.1390220BibTeX
@inproceedings{kuzelka2008icml-fast,
title = {{Fast Estimation of First-Order Clause Coverage Through Randomization and Maximum Likelihood}},
author = {Kuzelka, Ondrej and Zelezný, Filip},
booktitle = {International Conference on Machine Learning},
year = {2008},
pages = {504-511},
doi = {10.1145/1390156.1390220},
url = {https://mlanthology.org/icml/2008/kuzelka2008icml-fast/}
}