Golem (ILP) explained

Golem is an inductive logic programming algorithm developed by Stephen Muggleton and Cao Feng in 1990.^[1] It uses the technique of relative least general generalisation proposed by Gordon Plotkin, leading to a bottom-up search through the subsumption lattice.^[2] In 1992, shortly after its introduction, Golem was considered the only inductive logic programming system capable of scaling to tens of thousands of examples.

Description

Golem takes as input a definite program as background knowledge together with sets of positive and negative examples, denoted $E^$ and $E^$ respectively. The overall idea is to construct the least general generalisation of $E^$ with respect to the background knowledge. However, if is not merely a finite set of ground atoms, then this relative least general generalisation may not exist.^[3] Therefore, rather than using directly, Golem uses the set $B^$ of all ground atoms that can be resolved from in at most resolution steps. An additional difficulty is that if $E^$ is non-empty, the least general generalisation of $E^$ may entail a negative example. In this case, Golem generalises different subsets of $E^$ separately to obtain a program of several clauses. Golem also employs some restrictions on the hypothesis space, ensuring that relative least general generalisations are polynomial in the number of training examples. Golem demands that all variables in the head of a clause also appears in a literal of the clause body; that the number of substitutions needed to instantiate existentially quantified variables introduced in a literal is bounded; and that the depth of the chain of substitutions needed to instantiate such a variable is also bounded.^[4]

Example

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

,,,,,,,, and . It starts from the background knowledge (cf. picture)

it{par}(h,m)\landit{par}(h,t)\landit{par}(g,m)\landit{par}(t,e)\landit{par}(n,e)\landit{fem}(h)\landit{fem}(m)\landit{fem}(n)\landit{fem}(e)

,the positive examples

it{dau}(m,h)\landit{dau}(e,t)

,and the trivial propositionto denote the absence of negative examples.

The relative least general generalisation is now computed as follows to obtain a definition of the daughter relation.

Relativise each positive example literal with the complete background knowledge:

\begin{align} it{dau}(m,h)\leftarrowit{par}(h,m)\landit{par}(h,t)\landit{par}(g,m)\landit{par}(t,e)\landit{par}(n,e)\landit{fem}(h)\landit{fem}(m)\landit{fem}(n)\landit{fem}(e)\\ it{dau}(e,t)\leftarrowit{par}(h,m)\landit{par}(h,t)\landit{par}(g,m)\landit{par}(t,e)\landit{par}(n,e)\landit{fem}(h)\landit{fem}(m)\landit{fem}(n)\landit{fem}(e) \end{align}

Convert into clause normal form:

\begin{align} it{dau}(m,h)\lorlnotit{par}(h,m)\lorlnotit{par}(h,t)\lorlnotit{par}(g,m)\lorlnotit{par}(t,e)\lorlnotit{par}(n,e)\lorlnotit{fem}(h)\lorlnotit{fem}(m)\lorlnotit{fem}(n)\lorlnotit{fem}(e)\\ it{dau}(e,t)\lorlnotit{par}(h,m)\lorlnotit{par}(h,t)\lorlnotit{par}(g,m)\lorlnotit{par}(t,e)\lorlnotit{par}(n,e)\lorlnotit{fem}(h)\lorlnotit{fem}(m)\lorlnotit{fem}(n)\lorlnotit{fem}(e) \end{align}

Anti-unify each compatible ^[5] pair ^[6] of literals:

it{dau}(x_me,x_ht)

from

it{dau}(m,h)

and

it{dau}(e,t)

lnotit{par}(x_ht,x_me)

from

lnotit{par}(h,m)

and

lnotit{par}(t,e)

lnotit{fem}(x_me)

from

lnotit{fem}(m)

and

lnotit{fem}(e)

lnotit{par}(g,m)

from

lnotit{par}(g,m)

and

lnotit{par}(g,m)

, similar for all other background-knowledge literals

lnotit{par}(x_gt,x_me)

from

lnotit{par}(g,m)

and

lnotit{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

it{dau}(x_me,x_ht)\lorlnotit{par}(x_ht,x_me)\lorlnotit{fem}(x_me)

remains, together with all ground literals from the background knowledge

Convert clauses back to Horn form:

it{dau}(x_me,x_ht)\leftarrowit{par}(x_ht,x_me)\landit{fem}(x_me)\land(allbackgroundknowledgefacts)

The resulting Horn clause is the hypothesis obtained by Golem. Informally, the clause 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.

Notes and References

Muggleton . Stephen H. . Feng . Cao . 1990 . Arikawa . Setsuo . Goto . Shigeki . Ohsuga . Setsuo . Yokomori . Takashi . Efficient Induction of Logic Programs . Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings . Springer/Ohmsha . 368–381.
Book: Nienhuys-Cheng, Shan-hwei . Foundations of inductive logic programming . Wolf . Ronald de . 1997 . Springer . 978-3-540-62927-6 . Lecture notes in computer science Lecture notes in artificial intelligence . Berlin Heidelberg . 354–358.
Book: Nienhuys-Cheng, Shan-hwei . Foundations of inductive logic programming . Wolf . Ronald de . 1997 . Springer . 978-3-540-62927-6 . Lecture notes in computer science Lecture notes in artificial intelligence . Berlin Heidelberg . 286.
Book: Aha, David W. . Inductive logic programming . . 1992 . Muggleton . Stephen . Stephen Muggleton . London . 247 . Relating relational learning algorithms.
i.e. sharing the same predicate symbol and negated/unnegated status
in general: -tuple when positive example literals are given