|
& \textit{false}
\end{array}</math>]]Completeness requires any generated hypothesis ''{{mvar|h}}'' to explain all positive examples <math display="inline">E^+</math>, and consistency forbids generation of any hypothesis ''{{mvar|h}}'' that is inconsistent with the negative examples <math display="inline">E^{-}</math>, both given the background knowledge ''{{mvar|B}}''.<math display="block">\begin{array}{llll}
\text{Completeness:}
& B \cup H
& \models
& E^+
\\
\text{Consistency: }
& B \cup H \cup E^-
& \not\models
& \textit{false}
\end{array}</math>Completeness requires any generated hypothesis ''<span class="texhtml mvar" style="font-style:italic;">h</span>'' to explain all positive examples <math display="inline">E^+</math>, and consistency forbids generation of any hypothesis ''<span class="texhtml mvar" style="font-style:italic;">h</span>'' that is inconsistent with the negative examples <math display="inline">E^{-}</math>, both given the background knowledge ''<span class="texhtml mvar" style="font-style:italic;">B</span>''.
<math display="block">\begin{array}{llll}
\text{Completeness:}
& B \cup H
=== Learning from interpretations ===
In learning from interpretations, the ''positive'' and ''negative'' examples are given as a set of complete or partial [[Herbrand structure|Herbrand structures]], each of which are themselves a finite set of ground literals. Such a structure ''{{mvar|e}}'' is said to be a model of the set of clauses <math display="inline">B \cup H</math> if for any [[Substitution (logic)|substitution]] <math display="inline">\theta</math> and any clause <math display="inline">\mathrm{head} \leftarrow \mathrm{body}</math> in <math display="inline">B \cup H</math> such that <math display="inline">\mathrm{body}\theta \subseteq e</math>, <math>\mathrm{head}\theta \subseteq e</math> also holds. The goal is then to output a hypothesis that is ''complete,'' meaning every positive example is a model of <math display="inline">B \cup H</math>, and ''consistent,'' meaning that no negative example is a model of <math display="inline">B \cup H</math>.<ref name="setting" />
==Example==
[[File:Family relations example for inductive logic programming article.gif|thumb|left|Assumed family relations in section "Example"]]
The following well-known 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.
Plotkin's <ref>{{cite journal|first1=Gordon D.|last1=Plotkin|title=A Note on Inductive Generalization|editor1-first=B.|editor1-last=Meltzer|editor2-first=D.|editor2-last=Michie|journal=Machine Intelligence|volume=5|pages=153–163|year=1970 |isbn= 978-0-444-19688-0}}</ref><ref>{{cite journal|first1=Gordon D.|last1=Plotkin|title=A Further Note on Inductive Generalization|editor1-first=B.|editor1-last=Meltzer|editor2-first=D.|editor2-last=Michie|journal=Machine Intelligence|volume=6|pages=101–124|year=1971 |publisher=Edinburgh University Press |isbn=978-0-85224-195-0}}</ref> "''relative least general generalization (rlgg)''" approach to ''inductive logic programming'' shall be used to obtain a suggestion about how to formally define the daughter relation {{mvar|dau}}.
This approach uses the following steps.
* Relativize 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 the rlgg approach. Ignoring the background knowledge facts, the clause informally 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.
Concerning the [[#Formal definition|above]] requirements, "''Necessity''" was satisfied because the predicate {{mvar|dau}} doesn't appear in the background knowledge, which hence cannot imply any property containing this predicate, such as the positive examples are.
"''Sufficiency''" is satisfied by the computed hypothesis {{mvar|h}}, since it, together with <math>\textit{par}(h,m) \land \textit{fem}(m)</math> from the background knowledge, implies the first positive example <math>\textit{dau}(m,h)</math>, and similarly {{mvar|h}} and <math>\textit{par}(t,e) \land \textit{fem}(e)</math> from the background knowledge implies the second positive example <math>\textit{dau}(e,t)</math>. "''Weak consistency''" is satisfied by {{mvar|h}}, since {{mvar|h}} holds in the (finite) [[Herbrand structure]] described by the background knowledge; similar for "''Strong consistency''".
The common definition of the grandmother relation, viz. <math>\textit{gra}(x,z) \leftarrow \textit{fem}(x) \land \textit{par}(x,y) \land \textit{par}(y,z)</math>, cannot be learned using the above approach, since the variable {{mvar|y}} occurs in the clause body only; the corresponding literals would have been deleted in the 4th step of the approach. To overcome this flaw, that step has to be modified such that it can be parametrized with different ''literal post-selection heuristics''. Historically, the GOLEM implementation is based on the rlgg approach.
== Approaches to ILP ==
| 