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 ${\textstyle C_{1}}$ subsumes another clause ${\textstyle C_{2}}$ if there is a substitution ${\textstyle \theta }$ such that ${\textstyle C_{1}\theta }$, the result of applying ${\textstyle \theta }$ to ${\textstyle C_{1}}$, is a subset of ${\textstyle C_{2}}$. 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. 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 ${\textstyle C_{1}}$ and ${\textstyle C_{2}}$ and outputs the least general generalisation of ${\textstyle C_{1}}$ and ${\textstyle C_{2}}$, that is, a clause ${\textstyle C}$ that subsumes ${\textstyle C_{1}}$ and ${\textstyle C_{2}}$, and that is subsumed by every other clause that subsumes ${\textstyle C_{1}}$ and ${\textstyle C_{2}}$. The least general generalisation can be computed by first computing all selections from ${\textstyle C}$ and ${\textstyle D}$, which are pairs of literals $(L,M)\in (C_{1},C_{2})$ 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.

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 ${\textstyle C_{1}}$ and ${\textstyle C_{2}}$ and then computing their least general generalisation as before.

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

 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.