---
title: Inductive logic programming
slug: inductive-logic-programming
qid: 
snapshot: enwiki-001369278663
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1369278663
tags: [109366651, 109366652, 129826521, 22903403, 22985424, 23603337, 24623845, 26220375, 48128016, 64158044]
---

# Inductive logic programming

> [!note] Provenance
> Snapshot `enwiki-001369278663` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1369278663> · Licensed CC BY-SA 4.0

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical (i.e. suggesting a theory to explain observed facts) rather than mathematical (i.e. proving a property for all members of a well-ordered set) induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples. * Schema: positive examples + negative examples + background knowledge ⇒ hypothesis. Bioinformatics and drug design have been highlighted as a principal application area of inductive logic programming techniques.

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical (i.e. suggesting a theory to explain observed facts) rather than mathematical (i.e. proving a property for all members of a well-ordered set) induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples. Schema: positive examples + negative examples + background knowledge ⇒ hypothesis. Bioinformatics and drug design have been highlighted as a principal application area of inductive logic programming techniques. Inductive logic programming has adopted several different learning settings, the most common of which are learning from entailment and learning from interpretations. In both cases, the input is provided in the form of background knowledge , a logical theory (commonly in the form of clauses used in logic programming), as well as positive and negative examples, denoted E^+ and E^{-} respectively. The output is given as a hypothesis , itself a logical theory that typically consists of one or more clauses. The two settings differ in the format of examples presented. , learning from entailment is by far the most popular setting for inductive logic programming. In this setting, the positive and negative examples are given as finite sets E^+ and E^{-} of positive and negated ground literals, respectively. A correct hypothesis is a set of clauses satisfying the following requirements, where the turnstile symbol \models stands for logical entailment: \begin{array}{llll} \text{Completeness:} & B \cup H & \models & E^+ \\ \text{Consistency: } & B \cup H \cup E^- & \not\models & \textit{false} \end{array} Completeness requires any generated hypothesis to explain all positive examples E^+ , and consistency forbids generation of any hypothesis that is inconsistent with the negative examples E^{-} , both given the background knowledge . In Muggleton's setting of concept learning, "completeness" is referred to as "sufficiency", and "consistency" as "strong consistency". Two further conditions are added: "Necessity", which postulates that does not entail E^+ , does not impose a restriction on , but forbids any generation of a hypothesis as long as the positive facts are explainable without it. "Weak consistency", which states that no contradiction can be derived from B\land H , forbids generation of any hypothesis that contradicts the background knowledge . Weak consistency is implied by strong consistency; if no negative examples are given, both requirements coincide. Weak consistency is particularly important in the case of noisy data, where completeness and strong consistency cannot be guaranteed. In learning from interpretations, the positive and negative examples are given as a set of complete or partial Herbrand structures, each of which are themselves a finite set of ground literals. Such a structure is said to be a model of the set of clauses B \cup H if for any substitution \theta and any clause \mathrm{head} \leftarrow \mathrm{body} in B \cup H such that \mathrm{body}\theta \subseteq e , \mathrm{head}\theta \subseteq e also holds. The goal is then to output a hypothesis that is complete, meaning every positive example is a model of B \cup H , and consistent, meaning that no negative example is a model of B \cup H . Search-based systems exploit that the space of possible clauses forms a complete lattice under the subsumption relation, where one clause C_1 subsumes another clause C_2 if there is a substitution \theta such that C_1\theta , the result of applying \theta to C_1 , is a subset of C_2 . This lattice can be traversed either bottom-up or top-down. A least general generalisation algorithm takes as input two clauses C_1 and C_2 and outputs the least general generalisation of C_1 and C_2 , that is, a clause C that subsumes C_1 and C_2 , and that is subsumed by every other clause that subsumes C_1 and C_2 . The least general generalisation can be computed by first computing all selections from C_1 and C_2 , which are pairs of literals (L,M) \in (C_1 \times 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 is a finite set of ground literals, then the negation of is itself a clause. In this case, a relative least general generalisation can be computed by disjoining the negation of with both C_1 and C_2 and then computing their least general generalisation as before. Relative least general generalisations are the foundation of the bottom-up system Golem. Inverse resolution takes information about the resolvent of a resolution step to compute possible resolving clauses. Two types of inverse resolution operator are in use in inductive logic programming: V-operators and W-operators. A V-operator takes clauses R and C_1 as input and returns a clause C_2 such that R is the resolvent of C_1 and C_2 . A W-operator takes two clauses R_1 and R_2 and returns three clauses C_1 , C_2 and C_3 such that R_1 is the resolvent of C_1 and C_2 and R_2 is the resolvent of C_2 and C_3 . Inverse resolution was first introduced by Stephen Muggleton and Wray Buntine in 1988 for use in the inductive logic programming system Cigol. By 1993, this spawned a surge of research into inverse resolution operators and their properties. a set of positive and negative examples E^{+} and E^{-} the goal of probabilistic inductive logic programming is to find a probabilistic logic program H such that the probability of positive examples according to {H \cup B} is maximized and the probability of negative examples is minimized. This problem has two variants: parameter learning and structure learning. In the former, one is given the structure (the clauses) of and the goal is to infer the probabilities annotations of the given clauses, while in the latter the goal is to infer both the structure and the probability parameters of . Just as in classical inductive logic programming, the examples can be given as examples or as (partial) interpretations. ==See also== Commonsense reasoning Formal concept analysis Inductive reasoning Inductive programming Inductive probability Statistical relational learning Version space learning ==Further reading== Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html
