Editing Golem (ILP)

{{Short description|Inductive logic programming algorithm}}
'''Golem''' is an [[inductive logic programming]] algorithm developed by [[Stephen Muggleton]] and Cao Feng in 1990.<ref>{{Cite journal |last=Muggleton |first=Stephen H. |last2=Feng |first2=Cao |date=1990 |editor-last=Arikawa |editor-first=Setsuo |editor2-last=Goto |editor2-first=Shigeki |editor3-last=Ohsuga |editor3-first=Setsuo |editor4-last=Yokomori |editor4-first=Takashi |title=Efficient Induction of Logic Programs |url=https://dblp.org/rec/conf/alt/MuggletonF90.bib |journal=Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings |publisher=Springer/Ohmsha |pages=368–381}}</ref> It uses the technique of [[Inductive logic programming#Least general generalisation|relative least general generalisation]] proposed by [[Gordon Plotkin]], leading to a bottom-up search through the [[theta-subsumption|subsumption lattice]].<ref name=":0">{{Cite book |last=Nienhuys-Cheng |first=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Springer |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |location=Berlin Heidelberg |pages=354–358}}</ref> In 1992, shortly after its introduction, Golem was considered the only inductive logic programming system capable of scaling to tens of thousands of examples.<ref name=":1" /> 

== Description ==
Golem takes as input a [[Definite clause|definite program]] {{Mvar|B}} as background knowledge together with sets of positive and negative examples, denoted <math display="inline">E^{+}</math> and <math display="inline">E^{-}</math> respectively. The overall idea is to construct the least general generalisation of <math display="inline">E^{+}</math> with respect to the background knowledge. However, if {{Mvar|B}} is not merely a finite set of [[Ground expression|ground]] [[Atomic formula|atoms]], then this relative least general generalisation may not exist.<ref>{{Cite book |last=Nienhuys-Cheng |first=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Springer |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |location=Berlin Heidelberg |page=286}}</ref>
Therefore, rather than using {{Mvar|B}} directly, Golem uses the set <math display="inline">B^{h}</math> of all ground atoms that can be [[Resolution (logic)|resolved]] from  {{Mvar|B}} in at most {{Mvar|h}} 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.<ref name=":0" /> 
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.<ref name=":1">{{Cite book |last=Aha |first=David W. |title=Inductive logic programming |publisher=[[Academic Press]] |year=1992 |editor-last=Muggleton |editor-first=Stephen |editor-link=Stephen Muggleton |location=London |pages=247 |chapter=Relating relational learning algorithms}}</ref> 

==Example==
[[File:Family relations example for inductive logic programming article.gif|thumb|left|Assumed family relations]]
The following example about learning definitions of family relations uses the abbreviations 
:{{math|''par'': ''parent''}}, {{math|''fem'': ''female''}}, {{math|''dau'': ''daughter''}}, {{math|''g'': ''George''}}, {{math|''h'': ''Helen''}}, {{math|''m'': ''Mary''}}, {{math|''t'': ''Tom''}}, {{math|''n'': ''Nancy''}}, and {{math|''e'': ''Eve''}}. 
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
{{mvar|true}}
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-unification (computer science)|Anti-unify]] each compatible <ref>i.e. sharing the same predicate symbol and negated/unnegated status</ref> pair <ref>in general: {{mvar|n}}-tuple when {{mvar|n}} positive example literals are given</ref> 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 {{mvar|h}} 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.

== References ==
{{Reflist}}{{DEFAULTSORT:Golem (Ilp)}}
[[Category:Inductive logic programming]]

{{Artificial-intelligence-stub}}