Golem is an inductive logic programming algorithm developed by

Stephen Muggleton Stephen H. Muggleton FBCS, FIET, FAAAI, FECCAI, FSB, FREng (born 6 December 1959, son of Louis Muggleton) is Professor of Machine Learning and Head of the Computational Bioinformatics Laboratory at Imperial College London.relative least general generalisation proposed by

Gordon Plotkin Gordon David Plotkin, (born 9 September 1946) is a theoretical computer scientist in the School of Informatics at the University of Edinburgh. Plotkin is probably best known for his introduction of structural operational semantics (SOS) and hi ...

, leading to a bottom-up search through the subsumption lattice. 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 Ground may refer to: Geology * Land, the surface of the Earth not covered by water * Soil, a mixture of clay, sand and organic matter present on the surface of the Earth Electricity * Ground (electricity), the reference point in an electrical c ...

atoms Every atom is composed of a nucleus and one or more electrons bound to the nucleus. The nucleus is made of one or more protons and a number of neutrons. Only the most common variety of hydrogen has no neutrons. Every solid, liquid, gas, an ...

, then this relative least general generalisation may not exist. 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.

Example

The following example about learning definitions of family relations uses the abbreviations :, , , , , , , , and . It starts from the background knowledge (cf. picture) :

\textit(h,m) \land \textit(h,t) \land \textit(g,m) \land \textit(t,e) \land \textit(n,e) \land \textit(h) \land \textit(m) \land \textit(n) \land \textit(e)

, the positive examples :

\textit(m,h) \land \textit(e,t)

, and the trivial proposition to 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
\textit(m,h) \leftarrow \textit(h,m) \land \textit(h,t) \land \textit(g,m) \land \textit(t,e) \land \textit(n,e) \land \textit(h) \land \textit(m) \land \textit(n) \land \textit(e) \\
\textit(e,t) \leftarrow \textit(h,m) \land \textit(h,t) \land \textit(g,m) \land \textit(t,e) \land \textit(n,e) \land \textit(h) \land \textit(m) \land \textit(n) \land \textit(e)
\end

, * Convert into

clause normal form In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a ca ...

: *:

\begin
\textit(m,h) \lor \lnot \textit(h,m) \lor \lnot \textit(h,t) \lor \lnot \textit(g,m) \lor \lnot \textit(t,e) \lor \lnot \textit(n,e) \lor \lnot \textit(h) \lor \lnot \textit(m) \lor \lnot \textit(n) \lor \lnot \textit(e) \\
\textit(e,t) \lor \lnot \textit(h,m) \lor \lnot \textit(h,t) \lor \lnot \textit(g,m) \lor \lnot \textit(t,e) \lor \lnot \textit(n,e) \lor \lnot \textit(h) \lor \lnot \textit(m) \lor \lnot \textit(n) \lor \lnot \textit(e)
\end

, * Anti-unify each compatible pair in general: -tuple when positive example literals are given of literals: **

\textit(x_,x_)

from

\textit(m,h)

and

\textit(e,t)

, **

\lnot \textit(x_,x_)

from

\lnot \textit(h,m)

and

\lnot \textit(t,e)

, **

\lnot \textit(x_)

from

\lnot \textit(m)

and

\lnot \textit(e)

, **

\lnot \textit(g,m)

from

\lnot \textit(g,m)

and

\lnot \textit(g,m)

, similar for all other background-knowledge literals **

\lnot \textit(x_,x_)

from

\lnot \textit(g,m)

and

\lnot \textit(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_,x_

, only

\textit(x_,x_) \lor \lnot \textit(x_,x_) \lor \lnot \textit(x_)

remains, together with all ground literals from the background knowledge * Convert clauses back to Horn form: **

\textit(x_,x_) \leftarrow \textit(x_,x_) \land \textit(x_) \land (\text)

The resulting Horn clause is the hypothesis obtained by Golem. Informally, the clause reads "''

x_

is called a daughter of

x_

x_

is the parent of

x_

and

x_

is female''", which is a commonly accepted definition.

References

Inductive logic programming {{Artificial-intelligence-stub