Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Marta Arias , Roni Khardon , Jérôme Maloberti, Learning Horn Expressions with LOGAN-H, The Journal of Machine Learning Research, 8, p.549-587, 5/1/2007
• 2: Attilio Giordana , Lorenza Saitta, Phase Transitions in Relational Learning, Machine Learning, v.41 n.2, p.217-251, November 2000 [doi>10.1023/A:1007620705405]
• 3: Carla P. Gomes , Cèsar Fernández , Bart Selman , Christian Bessière, Statistical Regimes Across Constrainedness Regions, Constraints, v.10 n.4, p.317-337, October 2005 [doi>10.1007/s10601-005-2807-z]
• 4: Carla P. Gomes , Bart Selman , Nuno Crato , Henry Kautz, Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, Journal of Automated Reasoning, v.24 n.1-2, p.67-100, February 2000 [doi>10.1023/A:1006314320276]
• 5: Kuželka, O., & ŽŽelezný, F. (2009). A restarted strategy for efficient subsumption testing. Fundamenta Informaticae, spec. issue on multi-relational data mining. (Accepted).
• 6: Jérôme Maloberti , Michèle Sebag, Fast Theta-Subsumption with Constraint Satisfaction Algorithms, Machine Learning, v.55 n.2, p.137-174, May 2004 [doi>10.1023/B:MACH.0000023150.80092.40]
• 7: Sebag, M., & Rouveirol, C. (1997). Tractable induction and classification in first-order logic via stochastic matching. IJCAI97 (pp. 888--893). Morgan Kaufmann.
• 8: Ashwin Srinivasan , S. H. Muggleton , M. J. E. Sternberg , R. D. King, Theories for mutagenicity: a study in first-order and feature-based induction, Artificial Intelligence, v.85 n.1-2, p.277-299, Aug. 1996 [doi>10.1016/0004-3702(95)00122-0]
• 9: Filip Železný , Ashwin Srinivasan , C. David Page, Jr., Randomised restarted search in ILP, Machine Learning, v.64 n.1-3, p.183-208, September 2006 [doi>10.1007/s10994-006-7733-9]
• 10: Žáková, M., Železný, F., Garcia-Sedano, J., Tissot, C. M., Lavrač, N., Křemen, P., & Molina, J. (2007). Relational data mining applied to virtual engineering of product designs. ILP06 (pp. 439--453). Springer.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming; Uncertainty, "fuzzy," and probabilistic reasoning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Theory