Loyr4VYJp0qNpL7_D8_mIr-4WOM9iob_fOqK6K7tv3MygBUbad5AsCiY4BioGij4fg9V3GxT1S4LdmXEcxScFA

A Framework for Set-Oriented Computation in Inductive Logic Programming and its Application




1 views

Unformatted text preview:

A Framework for Set-Oriented Computation in Inductive Logic Programming and its Application in Generalizing Inverse Entailment⋆ He´ctor Corrada Bravo1, David Page2,1, Raghu Ramakrishnan1, Jude Shavlik1,2, and Vitor Santos Costa2,3 1 Department of Computer Sciences 2 Department of Biostatistics and Medical Informatics University of Wisconsin-Madison, USA 3 COPPE/Sistemas UFRJ, Brasil {hcorrada,raghu,shavlik}@cs.wisc.edu {page,vitor}@biostat.wisc.edu Abstract. We propose a new approach to Inductive Logic Programming that systematically exploits caching and offers a number of advantages over current systems. It avoids redundant computation, is more amenable to the use of set-oriented generation and evaluation of hypotheses, and allows relational DBMS technology to be more easily applied to ILP systems. Further, our approach opens up new avenues such as proba- bilistically scoring rules during search and the generation of probabilistic rules. As a first example of the benefits of our ILP framework, we pro- pose a scheme for defining the hypothesis search space through Inverse Entailment using multiple example seeds. 1 Introduction The goal of Inductive Logic Programming (ILP) [1] is to autonomously learn first-order logic programs that model relational data. However, the current ap- proach to ILP has limitations in its scalability and computational efficiency. Recent efforts extend ideas from relational database query optimization to this setting [2–6]. Along the same line, we present a new formulation of ILP that systematically exploits caching to achieve greater efficiency and flexibility, and present theoretical results that characterize it. The fundamental building blocks for our approach are a new data structure and an extension operation for hypotheses that expose and exploit opportunities for caching the results of previous computation. This provides an immediate benefit by avoiding the redundant computation pervasive in the standard ILP search and score paradigm. Further, the extension operation is formulated as a set-oriented computational strategy defined in terms of (extended) relational ⋆ Work was supported by Air Force Grant F30602-01-2-0571, DARPA ISTO Grant HR0011-04-0007 and a Ford Fellowship from the National Academy of Sciences. database operations, facilitating the use of relational query-processing techniques in ILP systems. Extensional representations of hypotheses are treated as first-class objects. Consequently, statistics derived from these objects are easily maintained, and can be used to define alternatives to guide the search process in ILP. For example, probabilistic methods for search [7, 3, 4, 8, 9] can directly use statistics derived from our new data structure for representing hypotheses. Additionally, statistics derived from an extensional representation of hy- potheses offer new avenues for learning a class of rules richer class than Horn clauses. For example, rules containing statements about aggregates [10], and rules containing probabilistic statements, such as statements about missing val- ues [11], can be generated. While these extensions are beyond the scope of this paper, we investigate a scheme for restricting the hypothesis search space using Inverse Entailment based on a set of multiple seed examples. Our algorithm for Generalized Inverse Entailment offers flexibility and robustness in hypothesis space restriction, including alternative seed-coverage measures (which we study in this paper) and cost-based measures that can be readily obtained from ...





Loading Unlocking...

Login

Join to view A Framework for Set-Oriented Computation in Inductive Logic Programming and its Application and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?

Sign Up

Join to view A Framework for Set-Oriented Computation in Inductive Logic Programming and its Application and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?