Content deleted Content added
→Example: Remove the very detailed example of one specific method for now. |
→Bottom-up search: Merge content from Inverse resolution to here for now. Should the article get too long or more content be added to this subsection, one could of course split it out again, as it is clearly a notable topic. |
||
Line 34:
& \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
Line 78 ⟶ 91:
Relative least general generalisations are the foundation of the bottom-up system [[Golem (ILP)|Golem]].<ref name=":12">{{Cite book |last1=Nienhuys-Cheng |first1=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Spinger |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |___location=Berlin Heidelberg |pages=354–358}}</ref><ref>{{Cite journal |last1=Muggleton |first1=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>
==== Inverse resolution ====
Inverse resolution is an [[inductive reasoning]] technique that involves [[wiktionary:invert|inverting]] the [[Resolution (logic)|resolution operator]].
Inverse resolution takes information about the [[Resolvent (logic)|resolvent]] of a resolution step to compute possible resolving clauses. Two types of inverse resolution operator are in use in [[inductive logic programming]]: V-operators and W-operators. A V-operator takes clauses <math display="inline">R</math> and <math display="inline">C_1</math>as input and returns a clause <math display="inline">C_2</math> such that <math display="inline">R</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math>. A W-operator takes two clauses <math display="inline">R_1</math> and <math display="inline">R_2</math> and returns thre clauses <math display="inline">C_1</math>, <math display="inline">C_2</math> and <math display="inline">C_3</math> such that <math display="inline">R_1</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math> and <math display="inline">R_2</math> is the resolvent of <math display="inline">C_2</math> and <math display="inline">C_3</math>.<ref name="invres">{{Cite book |last1=Nienhuys-Cheng |first1=Shan-hwei |title=Foundations of inductive logic programming |last2=Wolf |first2=Ronald de |date=1997 |publisher=Spinger |isbn=978-3-540-62927-6 |series=Lecture notes in computer science Lecture notes in artificial intelligence |___location=Berlin Heidelberg |page=197}}</ref>
Inverse resolution was first introduced by [[Stephen Muggleton]] and Wray Buntine in 1988 for use in the inductive logic programming system Cigol.<ref>{{cite book |last1=Muggleton |first1=S.H. |url= |title=Proceedings of the 5th International Conference on Machine Learning |last2=Buntine |first2=W. |date=1988 |isbn=978-0-934613-64-4 |pages=339–352 |chapter=Machine invention of first-order predicate by inverting resolution |doi=10.1016/B978-0-934613-64-4.50040-2}}</ref> By 1993, this spawned a surge of research into inverse resolution operators and their properties.<ref name="invres" />
=== Top-down search ===
| |||