Golem (ILP)

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.

[3] Golem takes as input a definite program B as background knowledge together with sets of positive and negative examples, denoted

However, if B is not merely a finite set of ground atoms, then this relative least general generalisation may not exist.

of all ground atoms that can be resolved from B in at most h resolution steps.

[2] 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.

[3] The following example about learning definitions of family relations uses the abbreviations It starts from the background knowledge (cf.

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

The resulting Horn clause is the hypothesis h obtained by Golem.