Golem is an inductive logic programming algorithm developed by Stephen Muggleton and Cao Feng in 1990. It uses the technique of relative least general generalisation proposed by Gordon Plotkin, 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.
Therefore, rather than using directly, Golem uses the set <math display="inline">B^{h}</math> of all ground atoms that can be resolved from in at most resolution steps. An additional difficulty is that if <math display="inline">E^{-}</math> is non-empty, the least general generalisation of <math display="inline">E^{+}</math> may entail a negative example. In this case, Golem generalises different subsets of <math display="inline">E^{+}</math> separately to obtain a program of several clauses.
Example
thumb|left|Assumed family relations
The following example about learning definitions of family relations uses the abbreviations
:, , , , , , , , and .
It starts from the background knowledge (cf. picture)
:<math>\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)</math>,
the positive examples
:<math>\textit{dau}(m,h) \land \textit{dau}(e,t)</math>,
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:
- :<math>\begin{align}
\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{align}</math>,
- Convert into clause normal form:
- :<math>\begin{align}
\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{align}</math>,
- Anti-unify each compatible pair of literals:
- <math>\textit{dau}(x_{me},x_{ht})</math> from <math>\textit{dau}(m,h)</math> and <math>\textit{dau}(e,t)</math>,
- <math>\lnot \textit{par}(x_{ht},x_{me})</math> from <math>\lnot \textit{par}(h,m)</math> and <math>\lnot \textit{par}(t,e)</math>,
- <math>\lnot \textit{fem}(x_{me})</math> from <math>\lnot \textit{fem}(m)</math> and <math>\lnot \textit{fem}(e)</math>,
- <math>\lnot \textit{par}(g,m)</math> from <math>\lnot \textit{par}(g,m)</math> and <math>\lnot \textit{par}(g,m)</math>, similar for all other background-knowledge literals
- <math>\lnot \textit{par}(x_{gt},x_{me})</math> from <math>\lnot \textit{par}(g,m)</math> and <math>\lnot \textit{par}(t,e)</math>, 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 <math>x_{me},x_{ht}</math>, only <math>\textit{dau}(x_{me},x_{ht}) \lor \lnot \textit{par}(x_{ht},x_{me}) \lor \lnot \textit{fem}(x_{me})</math> remains, together with all ground literals from the background knowledge
- Convert clauses back to Horn form:
- <math>\textit{dau}(x_{me},x_{ht}) \leftarrow \textit{par}(x_{ht},x_{me}) \land \textit{fem}(x_{me}) \land (\text{all background knowledge facts})</math>
The resulting Horn clause is the hypothesis obtained by Golem. Informally, the clause reads "<math>x_{me}</math> is called a daughter of <math>x_{ht}</math> if <math>x_{ht}</math> is the parent of <math>x_{me}</math> and <math>x_{me}</math> is female", which is a commonly accepted definition.