User:Felix QW/Inductive logic programming

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}$.

Approaches to ILP

Bottom-Up search

• Sketches of Golem and the Model Inference System
• Inverse resolution
• Least general generalisations

Top-down search

• Sketch of Progol/Aleph
• Beam search

Metainterpretative learning

• Metarules
• Constraint-based learning

Common issues

• Language bias
• Scoring functions
• Predicate invention
• Learning recursive programs