User:Felix QW/Inductive logic programming
Approaches to ILP
Inductive logic programming systems can be roughly divided into two classes, search-based and meta-interpretative systems.
Search-based systems exploit that the space of possible clauses forms a complete lattice under the subsumption relation, where one clause subsumes another clause if there is a substitution such that , the result of applying to , is a subset of . This lattice can be traversed either bottom-up or top-down.
Bottom-up search
Bottom-up methods to search the subsumption lattice have been investigated since Plotkin's first work on formalising induction in clausal logic in 1970.[1][2] Techniques used include least general generalisation, based on anti-unification, and inverse resolution, based on inverting the resolution inference rule.
Least general generalisations
A least general generalisation algorithm takes as input two clauses and and outputs the least general generalisation of and , that is, a clause that subsumes and , and that is subsumed by every other clause that subsumes and . The least general generalisation can be computed by first computing all selections from and , which are pairs of literals sharing the same predicate symbol and negated/unnegated status. Then, the least general generalisation is obtained as the disjunction of the least general generalisations of the individual selections, which can be obtained by first-order syntactical anti-unification.[3]
To account for background knowledge, inductive logic programming systems employ relative least general generalisations, which are defined in terms of subsumption relative to a background theory. In general, such relative least general generalisations are not guaranteed to exist; however, if the background theory B is a finite set of ground literals, then the negation of B is itself a clause. In this case, a relative least general generalisation can be computed by disjoining the negation of B with both and and then computing their least general generalisation as before.[4]
Relative least general generalisations are the foundation of the bottom-up system Golem.
Inverse resolution
Merge ART. here for now.
Top-down search
- Sketch of Progol/Aleph/FOIL and the Model Inference System
Metainterpretative learning
- Metarules
- Constraint-based learning
Common issues
- Language bias
- Scoring functions
- Predicate invention
- Learning recursive programs
Applications
- Bioinformatics
- Other areas
References
- ^ Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Foundations of inductive logic programming. Lecture notes in computer science Lecture notes in artificial intelligence. Berlin Heidelberg: Spinger. pp. 174–177. ISBN 978-3-540-62927-6.
- ^ Plotkin, G.D. (1970). Automatic Methods of Inductive Inference (PDF) (PhD). University of Edinburgh. hdl:1842/6656.
- ^ Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Foundations of inductive logic programming. Lecture notes in computer science Lecture notes in artificial intelligence. Berlin Heidelberg: Spinger. p. 255. ISBN 978-3-540-62927-6.
- ^ Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Foundations of inductive logic programming. Lecture notes in computer science Lecture notes in artificial intelligence. Berlin Heidelberg: Spinger. p. 286. ISBN 978-3-540-62927-6.
This article incorporates text from a free content work. Licensed under CC-BY 4.0 (license statement/permission). Text taken from A History of Probabilistic Inductive Logic Programming, Fabrizio Riguzzi, Elena Bellodi and Riccardo Zese, Frontiers Media.