Inductive logic programming

The background knowledge is given as a logic theory B, commonly in the form of Horn clauses used in logic programming. The positive and negative examples are given as a conjunction ${\displaystyle E^{+}}$ and ${\displaystyle E^{-}}$ of unnegated and negated ground literals, respectively. A correct hypothesis h is a logic proposition satisfying the following requirements.[9]

${\displaystyle {\begin{array}{llll}{\text{Necessity:}}&B&\not \models &E^{+}\\{\text{Sufficiency:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Weak consistency:}}&B\land h&\not \models &{\textit {false}}\\{\text{Strong consistency:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}}$

"Necessity" does not impose a restriction on h, but forbids any generation of a hypothesis as long as the positive facts are explainable without it. "Sufficiency" requires any generated hypothesis h to explain all positive examples ${\displaystyle E^{+}}$. "Weak consistency" forbids generation of any hypothesis h that contradicts the background knowledge B. "Strong consistency" also forbids generation of any hypothesis h that is inconsistent with the negative examples ${\displaystyle E^{-}}$, given the background knowledge B; it implies "Weak consistency"; if no negative examples are given, both requirements coincide. Džeroski [10] requires only "Sufficiency" (called "Completeness" there) and "Strong consistency".

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)

${\displaystyle {\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

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

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

Plotkin's [11][12] "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:

  ${\displaystyle {\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:

  ${\displaystyle {\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 [13] pair [14] of literals:
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})}$ from ${\displaystyle {\textit {dau}}(m,h)}$ and ${\displaystyle {\textit {dau}}(e,t)}$,
  • ${\displaystyle \lnot {\textit {par}}(x_{ht},x_{me})}$ from ${\displaystyle \lnot {\textit {par}}(h,m)}$ and ${\displaystyle \lnot {\textit {par}}(t,e)}$,
  • ${\displaystyle \lnot {\textit {fem}}(x_{me})}$ from ${\displaystyle \lnot {\textit {fem}}(m)}$ and ${\displaystyle \lnot {\textit {fem}}(e)}$,
  • ${\displaystyle \lnot {\textit {par}}(g,m)}$ from ${\displaystyle \lnot {\textit {par}}(g,m)}$ and ${\displaystyle \lnot {\textit {par}}(g,m)}$, similar for all other background-knowledge literals
  • ${\displaystyle \lnot {\textit {par}}(x_{gt},x_{me})}$ from ${\displaystyle \lnot {\textit {par}}(g,m)}$ and ${\displaystyle \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 ${\displaystyle x_{me},x_{ht}}$, only ${\displaystyle {\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:
  • ${\displaystyle {\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 "${\displaystyle x_{me}}$ is called a daughter of ${\displaystyle x_{ht}}$ if ${\displaystyle x_{ht}}$ is the parent of ${\displaystyle x_{me}}$ and ${\displaystyle 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 ${\displaystyle {\textit {par}}(h,m)\land {\textit {fem}}(m)}$ from the background knowledge, implies the first positive example ${\displaystyle {\textit {dau}}(m,h)}$, and similarly h and ${\displaystyle {\textit {par}}(t,e)\land {\textit {fem}}(e)}$ from the background knowledge implies the second positive example ${\displaystyle {\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. ${\displaystyle {\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 is a program that takes as an input logic theories ${\displaystyle B,E^{+},E^{-}}$ and outputs a correct hypothesis H wrt theories ${\displaystyle B,E^{+},E^{-}}$ An algorithm of an ILP system consists 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 iff for any input logic theories ${\displaystyle B,E^{+},E^{-}}$ any correct hypothesis H wrt to these input theories can be found with its hypothesis search procedure.

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