Inductive logic programming

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.

Inductive logic programming is particularly useful in bioinformatics and natural language processing.

History

Building on earlier work on Inductive inference, Gordon Plotkin was the first to formalise induction in a clausal setting around 1970, adopting an approach of generalising from examples. In 1981, Ehud Shapiro introduced several ideas that would shape the field in his new approach of model inference, an algorithm employing refinement and backtracing to search for a complete axiomatisation of given examples. His first implementation was the Model Inference System in 1981: a Prolog program that inductively inferred Horn clause logic programs from positive and negative examples. The term Inductive Logic Programming was first introduced in a paper by Stephen Muggleton in 1990, defined as the intersection of machine learning and logic programming. Muggleton and Wray Buntine introduced predicate invention and inverse resolution in 1988.

Several inductive logic programming systems that proved influential appeared in the early 1990s. FOIL, introduced by Ross Quinlan in 1990 was based on upgrading propositional learning algorithms AQ and ID3. Golem, introduced by Muggleton and Feng in 1990, went back to a restricted form of Plotkin's least generalisation algorithm. The Progol system, introduced by Muggleton in 1995, first implemented inverse entailment, and inspired many later systems. Aleph, a descendant of Progol introduced by Ashwin Srinivasan in 2001, is still one of the most widely used systems as of 2022.

At around the same time, the first practical applications emerged, particularly in bioinformatics, where by 2000 inductive logic programming had been successfully applied to drug design, carcinogenicity and mutagenicity prediction, and elucidation of the structure and function of proteins. Unlike the focus on automatic programming inherent in the early work, these fields used inductive logic programming techniques from a viewpoint of relational data mining. The success of those initial applications and the lack of progress in recovering larger traditional logic programs shaped the focus of the field.

Recently, classical tasks from automated programming have moved back into focus, as the introduction of meta-interpretative learning makes predicate invention and learning recursive programs more feasible. This technique was pioneered with the Metagol system introduced by Muggleton, Dianhuan Lin, Niels Pahlavi and Alireza Tamaddoni-Nezhad in 2014. This allows ILP systems to work with fewer examples, and brought successes in learning string transformation programs, answer set grammars and general algorithms.

Setting

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 B, a logical theory (commonly in the form of clauses used in logic programming), as well as positive and negative examples, denoted ${\textstyle E^{+}}$ and ${\textstyle E^{-}}$ respectively. The output is given as a hypothesis H, 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

As of 2022, 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 ${\textstyle E^{+}}$ and ${\textstyle E^{-}}$ of positive and negated ground literals, respectively. A correct hypothesis H 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 h to explain all positive examples ${\textstyle E^{+}}$, and consistency forbids generation of any hypothesis h that is inconsistent with the negative examples ${\textstyle E^{-}}$, both given the background knowledge B.

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 B does not entail ${\textstyle E^{+}}$, does not impose a restriction on h, 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 ${\textstyle B\land H}$, forbids generation of any hypothesis h that contradicts the background knowledge B. 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.

Learning from interpretations

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 e is said to be a model of the set of clauses ${\textstyle B\cup H}$ if for any substitution ${\textstyle \theta }$ and any clause ${\textstyle \mathrm {head} \leftarrow \mathrm {body} }$ in ${\textstyle B\cup H}$ such that ${\textstyle \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 ${\textstyle B\cup H}$, and consistent, meaning that no negative example is a model of ${\textstyle B\cup H}$.

Example

Assumed family relations in section "Example"

The following well-known example about learning definitions of family relations uses the abbreviations

par: parent, fem: female, dau: daughter, g: George, h: Helen, m: Mary, t: Tom, n: Nancy, and e: Eve.

It starts from the background knowledge (cf. picture)

${\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)$,

the positive examples

${\textit {dau}}(m,h)\land {\textit {dau}}(e,t)$,

and the trivial proposition true to denote the absence of negative examples.

Plotkin's "relative least general generalization (rlgg)" approach to inductive logic programming shall be used to obtain a suggestion about how to formally define the daughter relation dau.

This approach uses the following steps.

• Relativize each positive example literal with the complete background knowledge:

  ${\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}$,

• Convert into clause normal form:

  ${\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}$,

• Anti-unify each compatible pair of literals:
  • ${\textit {dau}}(x_{me},x_{ht})$ from ${\textit {dau}}(m,h)$ and ${\textit {dau}}(e,t)$,
  • $\lnot {\textit {par}}(x_{ht},x_{me})$ from $\lnot {\textit {par}}(h,m)$ and $\lnot {\textit {par}}(t,e)$,
  • $\lnot {\textit {fem}}(x_{me})$ from $\lnot {\textit {fem}}(m)$ and $\lnot {\textit {fem}}(e)$,
  • $\lnot {\textit {par}}(g,m)$ from $\lnot {\textit {par}}(g,m)$ and $\lnot {\textit {par}}(g,m)$, similar for all other background-knowledge literals
  • $\lnot {\textit {par}}(x_{gt},x_{me})$ from $\lnot {\textit {par}}(g,m)$ and $\lnot {\textit {par}}(t,e)$, and many more negated literals
• Delete all negated literals containing variables that don't occur in a positive literal:
  • after deleting all negated literals containing other variables than $x_{me},x_{ht}$, only ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ remains, together with all ground literals from the background knowledge
• Convert clauses back to Horn form:
  • ${\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})$

The resulting Horn clause is the hypothesis h obtained by the rlgg approach. Ignoring the background knowledge facts, the clause informally reads "$x_{me}$ is called a daughter of $x_{ht}$ if $x_{ht}$ is the parent of $x_{me}$ and $x_{me}$ is female", which is a commonly accepted definition.

Concerning the above requirements, "Necessity" was satisfied because the predicate dau doesn't appear in the background knowledge, which hence cannot imply any property containing this predicate, such as the positive examples are. "Sufficiency" is satisfied by the computed hypothesis h, since it, together with ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ from the background knowledge, implies the first positive example ${\textit {dau}}(m,h)$, and similarly h and ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ from the background knowledge implies the second positive example ${\textit {dau}}(e,t)$. "Weak consistency" is satisfied by h, since h holds in the (finite) Herbrand structure described by the background knowledge; similar for "Strong consistency".

The common definition of the grandmother relation, viz. ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$, cannot be learned using the above approach, since the variable y occurs in the clause body only; the corresponding literals would have been deleted in the 4th step of the approach. To overcome this flaw, that step has to be modified such that it can be parametrized with different literal post-selection heuristics. Historically, the GOLEM implementation is based on the rlgg approach.

Inductive Logic Programming system

An inductive logic programming system is a program that takes as an input logic theories $B,E^{+},E^{-}$ and outputs a correct hypothesis H with respect to theories $B,E^{+},E^{-}$. Search-based ILP systems consist of two parts: hypothesis search and hypothesis selection. First a hypothesis is searched with an inductive logic programming procedure, then a subset of the found hypotheses (in most systems one hypothesis) is chosen by a selection algorithm. A selection algorithm scores each of the found hypotheses and returns the ones with the highest score. An example of score function include minimal compression length where a hypothesis with a lowest Kolmogorov complexity has the highest score and is returned. An ILP system is complete if and only if for any input logic theories $B,E^{+},E^{-}$ any correct hypothesis H with respect to these input theories can be found with its hypothesis search procedure.

Hypothesis search

The ILP systems Progol, Hail and Imparo find a hypothesis H using the principle of the inverse entailment for theories B, E, H: $B\land H\models E\iff B\land \neg E\models \neg H$. First they construct an intermediate theory F called a bridge theory satisfying the conditions $B\land \neg E\models F$ and $F\models \neg H$. Then as $H\models \neg F$, they generalize the negation of the bridge theory F with anti-entailment. However, the operation of anti-entailment is computationally more expensive since it is highly nondeterministic. Therefore, an alternative hypothesis search can be conducted using the operation of the inverse subsumption (anti-subsumption) instead which is less non-deterministic than anti-entailment.

Questions of completeness of a hypothesis search procedure of specific ILP system arise. For example, Progol's hypothesis search procedure based on the inverse entailment inference rule is not complete by Yamamoto's example. On the other hand, Imparo is complete by both anti-entailment procedure and its extended inverse subsumption procedure.

Implementations

• 1BC and 1BC2: first-order naive Bayesian classifiers:
• ACE (A Combined Engine)
• Aleph
• Atom Archived 2014-03-26 at the Wayback Machine
• Claudien
• DL-Learner
• DMax
• FastLAS (Fast Learning from Answer Sets)
• FOIL (First Order Inductive Learner)
• Golem
• ILASP (Inductive Learning of Answer Set Programs)
• Imparo
• Inthelex (INcremental THEory Learner from EXamples) Archived 2011-11-28 at the Wayback Machine
• Lime
• Metagol
• Mio
• MIS (Model Inference System) by Ehud Shapiro
• PROGOL
• RSD
• Warmr (now included in ACE)
• ProGolem

Probabilistic inductive logic programming

Probabilistic inductive logic programming adapts the setting of inductive logic programming to learning probabilistic logic programs. It can be considered as statistical relational learning within the formalism of probabilistic logic programming.

Given

1. background knowledge as a probabilistic logic program B, and
2. a set of positive and negative examples ${\textstyle E^{+}}$ and ${\textstyle E^{-}}$

the goal of probabilistic inductive logic programming is to find a probabilistic logic program ${\textstyle H}$ such that the probability of positive examples according to ${\textstyle {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 first, one is given the structure (the clauses) of H and the goal is to infer the probabilities annotations of the given clauses, while in the second the goal was to infer both the structure and the probability parameters of H. Just as in classical inductive logic programming, the examples can be given as examples or as (partial) interpretations.

Parameter Learning

Parameter learning for languages following the distribution semantics has been performed by using an expectation-maximisation algorithm or by gradient descent. An expectation-maximisation algorithm consists of a cycle in which the steps of expectation and maximization are repeatedly performed. In the expectation step, the distribution of the hidden variables is computed according to the current values of the probability parameters, while in the maximisation step, the new values of the parameters are computed. Gradient descent methods compute the gradient of the target function and iteratively modify the parameters moving in the direction of the gradient.

Structure Learning

Structure learning was pioneered by Daphne Koller and Avi Pfeffer in 1997, where the authors learn the structure of first-order rules with associated probabilistic uncertainty parameters. Their approach involves generating the underlying graphical model in a preliminary step and then applying expectation-maximisation.

In 2008, De Raedt et al. presented an algorithm for performing theory compression on ProbLog programs, where theory compression means removing as many clauses as possible from the theory in order to maximize the probability. No new clause can be added to the theory.

In the same year, Meert, W. et al. introduced a method for learning parameters and structure of ground probabilistic logic programs by considering the Bayesian networks equivalent to them and applying techniques for learning Bayesian networks.

ProbFOIL, introduced by De Raedt and Ingo Thon in 2010, combined the inductive logic programming system FOIL with ProbLog. Logical rules are learned from probabilistic data in the sense that both the examples themselves and their classifications can be probabilistic. The set of rules has to allow to predict the probability of the examples from their description. In this setting, the parameters (the probability values) are fixed and the structure has to be learned.

In 2011, Elena Bellodi and Fabrizio Riguzzi introduced SLIPCASE, which performs a beam search among probabilistic logic programs by iteratively refining probabilistic theories and optimizing the parameters of each theory using expectation-maximisation. Its extension SLIPCOVER, proposed in 2014, uses bottom clauses generated as in Progol to guide the refinement process, thus reducing the number of revisions and exploring more effectively the search space. Moreover, SLIPCOVER separates the search for promising clauses from that of the theory: the space of clauses is explored with a beam search, while the space of theories is searched greedily.

See also

• Commonsense reasoning
• Formal concept analysis
• Inductive reasoning
• Inductive programming
• Inductive probability
• Statistical relational learning
• Version space learning

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.

Further reading

• Muggleton, S.; De Raedt, L. (1994). "Inductive Logic Programming: Theory and methods". The Journal of Logic Programming. 19–20: 629–679. doi:10.1016/0743-1066(94)90035-3.
• Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 978-0-13-457870-5. Archived from the original on 2004-09-06. Retrieved 2004-09-22.
• Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html Archived 2014-03-26 at the Wayback Machine