--- title: "Knowledge-Based Learning: EBL, Relevance, and ILP" module: Learning moduleNumber: 5 lessonNumber: 8 order: 508 summary: > Once learning is cast as logical inference, three methods follow from the three ways prior knowledge can enter. Explanation-based learning generalizes a single example by explaining it with the domain theory, gaining speed but nothing new. Relevance-based learning uses determinations to shrink the hypothesis space and converge from fewer examples. Inductive logic programming learns genuinely new first-order rules — top-down with FOIL, bottom-up by inverting resolution, even inventing new predicates — and connects to modern statistical relational and neuro-symbolic learning. topics: [Learning] sources: - book: AIMA ref: "§19.3 Explanation-Based Learning; §19.4 Learning Using Relevance Information; §19.5 Inductive Logic Programming" --- This builds on [Knowledge in Learning](/artificial-intelligence/learning/knowledge-in-learning), which recast induction inside logic — examples, hypotheses, and classifications as sentences — developed the version space and candidate elimination, and set out the three entailment constraints by which prior knowledge enters. Each constraint names a method, and this part develops all three, in order of how much the hypothesis itself contributes. ## Explanation-based learning **Explanation-based learning** (EBL) extracts a general rule from a single observation by _explaining_ it with the domain theory and then generalizing the explanation. Its entailment constraints are $$ Hypothesis \wedge Descriptions \models Classifications, \qquad Background \models Hypothesis. $$ The second line says the hypothesis _follows logically_ from the background knowledge. So EBL does not learn anything factually new — the agent could already have derived the example, given unlimited computation. What it gains is _speed_: it converts slow, first-principles reasoning into fast, special-purpose rules, generalizing memoization from single input-output pairs to whole classes of cases. The mechanism is: construct a proof (an "explanation") that the goal predicate holds of the example using the background rules, then determine the class of cases for which the same proof structure works, and turn that into a rule. Consider simplifying $1 \times (0 + X)$ with a small knowledge base of rewrite rules such as $Rewrite(1 \times u, u)$, $Rewrite(0 + u, u)$, and $Primitive(u) \Rightarrow Simplify(u, u)$. EBL builds _two_ proof trees at once: the concrete proof for the example, and a **variabilized** proof in which the example's constants are replaced by variables. The two proofs take exactly the same inference steps; the variabilized proof records which bindings each rule application forces. $$ % caption: An EBL explanation tree for simplifying $1 \times (0 + X)$. Each node is a % subgoal discharged by a rule application; the leaves that survive variabilization % become the body of the extracted rule, whose head is the top goal. \begin{tikzpicture}[>=stealth, font=\scriptsize, n/.style={draw, minimum width=26mm, minimum height=7mm, align=center, font=\scriptsize}, leaf/.style={draw, minimum width=26mm, minimum height=7mm, align=center, font=\scriptsize, fill=black!5}] \definecolor{acc}{HTML}{2348F2} \node[n, draw=acc, text=acc] (top) at (0,5.4) {Simplify(1x(0+X), w)}; \node[leaf] (rw1) at (-3.2,4.0) {Rewrite(1x(0+X), v)}; \node[n] (s1) at (1.0,4.0) {Simplify(0+X, w)}; \node[leaf] (rw2) at (-2.2,2.6) {Rewrite(0+X, vp)}; \node[n] (s2) at (2.4,2.6) {Simplify(X, w)}; \node[n] (p1) at (2.4,1.2) {Primitive(X)}; \node[leaf] (au) at (2.4,-0.2) {ArithmeticUnknown(X)}; \draw[->] (top) -- (rw1); \draw[->] (top) -- (s1); \draw[->] (s1) -- (rw2); \draw[->] (s1) -- (s2); \draw[->] (s2) -- (p1); \draw[->] (p1) -- (au); \end{tikzpicture} $$ Taking the leaves of the generalized tree as the rule body and the variabilized goal as the head produces $$ Rewrite(1 \times (0 + z), 0 + z) \wedge Rewrite(0 + z, z) \wedge ArithmeticUnknown(z) \;\Rightarrow\; Simplify(1 \times (0 + z), z). $$ The first two conditions are true regardless of $z$, so they can be **dropped**, leaving the compact rule $ArithmeticUnknown(z) \Rightarrow Simplify(1 \times (0 + z), z)$. We cannot drop the last condition: if $z$ were $2 \times 3$, the correct simplification of $1 \times (0 + (2 \times 3))$ would be $6$, not $2 \times 3$. To recap: > **Algorithm (Explanation-based learning).** Given an example, (1) construct a proof > that the goal predicate applies, using the background knowledge; (2) in parallel, > build a generalized proof for the variabilized goal with the same inference steps; > (3) form a rule whose body is the leaves of the proof tree and whose head is the > variabilized goal, after applying the bindings the generalized proof forces; (4) > drop any body conditions that hold regardless of the goal's variables. ### Choosing which rule, and whether it helps A generalized proof tree yields _many_ rules — a rule can be read off any partial subtree. Pruning higher in the tree gives more general rules that cover more cases but require more inference to apply. Which to keep is a question of **efficiency**, and it cuts both ways: - Adding rules raises the **branching factor** in the search space: the inference engine must consider each new rule even where it does not help. - Derived rules must repay that cost with real speedups on the cases they cover, mostly by avoiding dead-end branches and shortening proofs. - More general rules apply to more cases, but the cost of any subgoal depends on what other rules are present, so the analysis is a genuine optimization problem. A common discipline is to insist on the **operationality** of each subgoal: a subgoal is operational if it is "easy" to solve. Pruning a branch as soon as an operational subgoal is reached keeps that subgoal as a conjunct of the new rule. Operationality trades off against generality — easier subgoals usually cover fewer cases — and there is rarely a clean line between operational and not. The practical resolution is empirical: add several candidate rules, keep the ones that actually speed things up on the distribution of problems the system faces. This is the same distributional assumption used in PAC-learning: by generalizing from past problems, EBL makes the knowledge base faster for the kind of problems expected in future. ## Learning using relevance information The traveler's inference about Brazilian language uses a different kind of knowledge: not a full theory that entails the conclusion, but a statement of _relevance_ — nationality determines language. In first-order logic, $$ Nationality(x, n) \wedge Nationality(y, n) \wedge Language(x, l) \;\Rightarrow\; Language(y, l). $$ Given this and the observation that Fernando is Brazilian and speaks Portuguese, it follows that $Nationality(x, Brazil) \Rightarrow Language(x, Portuguese)$. Sentences of this form express a strict relevance: given nationality, language is fixed. They are **functional dependencies**, or **determinations**, written with Davies's notation $$ Nationality(x, n) \succ Language(x, l), $$ read "nationality determines language." Determinations sanction a deductive form of learning: with the observations, they entail a new general rule. > **Definition (Determination).** A relation $P \succ Q$ between predicates asserting > that once the $P$-values are fixed, the $Q$-value is fixed: any two objects agreeing > on $P$ must agree on $Q$. Equivalently, $Q$ is a function of $P$. The entailment constraints for **relevance-based learning** (RBL) are $$ Hypothesis \wedge Descriptions \models Classifications, \qquad Background \wedge Descriptions \wedge Classifications \models Hypothesis. $$ RBL uses the content of the observations, but the hypothesis it produces goes no further than the logical content of background plus data — it is deductive and cannot by itself invent new knowledge from scratch. ### Determinations shrink the hypothesis space Determinations do not predict language for _all_ nationalities from one example; their effect is to _limit the space of hypotheses the learner must consider_. In predicting conductance one need attend only to material and temperature — mass, ownership, day of the week, and the current president are irrelevant. A determination $Material(x, m) \wedge Temperature(x, t) \succ Conductance(x, \rho)$ specifies a _sufficient basis vocabulary_: the correct definition of conductance is expressible using only the predicates on the left-hand side. This is a dramatic reduction. With $n$ Boolean features and no restrictions, $|\mathcal{H}| = O(2^{2^n})$ and the number of examples needed to converge is $O(2^n)$. A determination with $d$ predicates on its left cuts the requirement to $O(2^d)$ — a reduction of $O(2^{n-d})$. $$ % caption: A determination collapses the hypothesis space. Without relevance, % $n$ features yield a doubly-exponential space needing $O(2^n)$ examples; a % determination naming $d < n$ relevant features leaves only $O(2^d)$, so far % fewer examples converge. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % big oval: full space \draw[black, thick] (0,1.4) ellipse (3.4 and 1.8); \node[font=\scriptsize, anchor=south] at (0,3.05) {all hypotheses over $n$ features}; \node[font=\scriptsize] at (-1.7,1.4) {needs $O(2^n)$ ex.}; % small oval: restricted \draw[acc, thick] (0.8,1.0) ellipse (1.5 and 0.9); \node[font=\scriptsize, acc] at (0.8,1.4) {relevant $d$}; \node[font=\scriptsize, acc] at (0.8,0.75) {$O(2^d)$ ex.}; % determination label \node[font=\scriptsize, anchor=north, align=center] at (0,-0.9) {determination names $d < n$\\relevant features}; \draw[->, acc, thick] (0.8,-0.55) -- (0.8,0.1); \end{tikzpicture} $$ ### Learning the determinations Relevance itself has to be learned. A determination $P \succ Q$ is consistent with a set of examples if every pair of examples agreeing on the left-hand predicates also agrees on the goal. We want a _minimal_ consistent determination — the smallest set of relevant attributes. Search subsets of the attributes in increasing size, testing each for consistency, and return the first that passes. ```algorithm caption: $\textsc{Minimal-Consistent-Det}(E, A)$ — find a smallest relevant attribute set input: examples $E$; attribute set $A$ of size $n$ for $i = 0$ to $n$ do for each subset $A_i$ of $A$ of size $i$ do if $\textsc{Consistent-Det?}(A_i, E)$ then return $A_i$ ``` ```algorithm caption: $\textsc{Consistent-Det?}(A, E)$ — does attribute set $A$ determine the goal on $E$? input: attribute set $A$; examples $E$ $H \gets$ empty hash table for each example $e$ in $E$ do if some stored example has the same $A$-values as $e$ but a different class then return $false$ store the class of $e$ in $H$, keyed by $e$'s values for $A$ return $true$ ``` On six conductance measurements over samples of copper and lead, the minimal consistent determination is $Material \wedge Temperature \succ Conductance$. There is a larger, non-minimal one — $Mass \wedge Size \wedge Temperature \succ Conductance$ — consistent only because no two materials in the small sample share a density; a larger sample would eliminate it. If the smallest determination has $p$ of $n$ attributes, the search reaches it only after examining $\binom{n}{p} = O(n^p)$ subsets, so the method is exponential in $p$ and the underlying problem is NP-complete; in practice $p$ is small because most domains have local structure. Combining $\textsc{Minimal-Consistent-Det}$ with decision-tree learning gives **RBDTL**: first find a minimal relevant attribute set, then grow a tree using only those attributes. RBDTL learns and uses relevance to shrink its hypothesis space, so it converges faster than a plain decision-tree learner whenever the target depends on only a few of the available attributes. $$ % caption: Learning-curve sketch: on a target that depends on only a few of many % attributes, RBDTL (relevance-restricted) reaches high test accuracy with far fewer % examples than plain decision-tree learning (DTL), which must sift all attributes. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, black] (0,0) -- (6.2,0) node[anchor=north, font=\scriptsize] {training set size}; \draw[->, black] (0,0) -- (0,3.6); \node[font=\scriptsize, rotate=90] at (-1.05,1.8) {test accuracy}; \node[font=\scriptsize, anchor=east] at (-0.22,2.9) {1.0}; \node[font=\scriptsize, anchor=east] at (-0.22,1.25) {0.5}; \draw[black] (-0.1,2.9) -- (0.1,2.9); \draw[black] (-0.1,1.25) -- (0.1,1.25); % RBDTL: rises fast, plateaus high \draw[acc, very thick] (0,1.15) .. controls (1.0,2.7) and (2.0,2.9) .. (5.8,2.9); \node[acc, anchor=west, font=\scriptsize] at (5.85,2.9) {RBDTL}; % DTL: rises slowly \draw[red, thick, dashed] (0,1.1) .. controls (2.2,1.6) and (4.0,2.1) .. (5.8,2.4); \node[red, anchor=west, font=\scriptsize] at (5.85,2.4) {DTL}; \end{tikzpicture} $$ Relevance information is one instance of **declarative bias**: prior knowledge that picks out the appropriate hypothesis space to search within. Determinations are only one form — the next section handles knowledge expressed as arbitrary first-order theories. ## Inductive logic programming **Inductive logic programming** (ILP) unites induction with first-order representations, learning hypotheses expressed as logic programs. It solves the general **knowledge-based inductive learning** (KBIL) constraint, $$ Background \wedge Hypothesis \wedge Descriptions \models Classifications, $$ for the unknown $Hypothesis$, given background knowledge and examples. ILP matters for three reasons. It gives complete algorithms for inducing general first-order theories, so it works in domains where attribute-based methods cannot — protein-fold prediction, say, where the structure is a web of _relationships_ between substructures, not a bag of attributes on one object. And its hypotheses are human-readable logic, so biologists can scrutinize and criticize the rules a system like PROGOL learns, letting ILP participate in the scientific cycle in a way black-box classifiers cannot. For example, learn family relations from a family tree described by $Mother$, $Father$, $Married$ relations and $Male$, $Female$ properties. To learn $Grandparent$, $Classifications$ contains the $20 \times 20 = 400$ conjuncts $Grandparent(Mum, Charles)$, $\neg Grandparent(Mum, Harry)$, and so on. With empty background knowledge, one solution is the unwieldy disjunction $$ Grandparent(x, y) \iff [\exists z\; Mother(x, z) \wedge Mother(z, y)] \vee [\exists z\; Mother(x, z) \wedge Father(z, y)] \vee \ldots $$ An attribute-based learner gets nowhere here. To express $Grandparent$ as an attribute it would have to make _pairs_ of people into objects and invent grotesque attributes like $FirstElementIsMotherOfElizabeth(\langle Mum, Charles \rangle)$; the resulting definition is a giant disjunction of specific cases that does not generalize at all. _Attribute-based learning algorithms are incapable of learning relational predicates._ This is the central advantage of ILP. Background knowledge helps dramatically. If $Background$ includes $Parent(x, y) \iff [Mother(x, y) \vee Father(x, y)]$, the $Grandparent$ definition collapses to $Grandparent(x, y) \iff [\exists z\; Parent(x, z) \wedge Parent(z, y)]$ — a small hypothesis instead of a four-way disjunction. Reducing the hypothesis size is exactly reducing the effort to find it. ### Top-down learning: FOIL The first ILP approach generalizes decision-tree learning: start with a very general rule and specialize it until it fits, but with first-order literals instead of attributes and a set of clauses instead of a tree. FOIL is the classic program. Learning $Grandfather(x, y)$, there are $12$ positive example pairs like $\langle George, Anne \rangle$ and $388$ negative pairs. FOIL builds Horn clauses with $Grandfather(x, y)$ as head, starting from the empty body $$ \Rightarrow Grandfather(x, y), $$ which calls _everything_ positive and so must be specialized by adding body literals. Of the candidate additions, $Parent(x, z) \Rightarrow Grandfather(x, y)$ and $Father(x, z) \Rightarrow Grandfather(x, y)$ both keep all positives, but the $Father$ version rules out more negatives (it excludes mothers), so it is preferred. Adding $Parent(z, y)$ next yields $$ Father(x, z) \wedge Parent(z, y) \Rightarrow Grandfather(x, y), $$ which classifies every example correctly. The general solution is a set of Horn clauses, each covering some positives, together covering all positives, and none covering a negative. ```algorithm caption: $\textsc{Foil}(examples, target)$ — top-down induction of first-order Horn clauses input: a set of $examples$; a goal literal $target$ $clauses \gets$ empty while $examples$ contains positive examples do $clause \gets \textsc{New-Clause}(examples, target)$ remove positive examples covered by $clause$ from $examples$ add $clause$ to $clauses$ return $clauses$ ``` ```algorithm caption: $\textsc{New-Clause}(examples, target)$ — grow one clause, literal by literal input: a set of $examples$; a goal literal $target$ $clause \gets$ a clause with $target$ as head and an empty body $ext \gets examples$ while $ext$ contains negative examples do $l \gets \textsc{Choose-Literal}(\textsc{New-Literals}(clause), ext)$ append $l$ to the body of $clause$ $ext \gets$ examples formed by extending each of $ext$ with values for $l$'s new variables return $clause$ ``` $\textsc{New-Literals}$ constructs every "useful" literal that can be added. There are three kinds: literals using any predicate (including the goal predicate, which lets FOIL learn _recursive_ definitions), with the restriction that each new literal share at least one variable with an earlier literal or the head; equality and inequality literals such as $z \ne x$; and arithmetic comparisons like $x > y$ for continuous variables. The branching factor is large, so type information prunes it, and $\textsc{Choose-Literal}$ uses an information-gain heuristic to pick among candidates. An Ockham's-razor test discards any clause longer than the positive examples it explains, avoiding overcomplex clauses that merely fit noise. ### Bottom-up learning: inverse resolution The second ILP approach inverts deduction. If $Background \wedge Hypothesis \wedge Descriptions \models Classifications$, then by the completeness of resolution there is a resolution proof of each classification — so running the proof _backward_ can recover a $Hypothesis$ that makes it go through. **Inverse resolution** does exactly this: an ordinary resolution step takes clauses $C_1$ and $C_2$ and produces resolvent $C$; an inverse step takes $C$ and one of the clauses and _generates_ the missing clause. $$ % caption: An inverse-resolution trace for the positive example % Grandparent(George, Anne). Starting from the empty clause and the negated goal at % the bottom, each upward step inverts a resolution: it takes the current clause and % a known clause on the right, and hypothesizes the clause above. \begin{tikzpicture}[>=stealth, font=\scriptsize, h/.style={draw, fill=black!7, minimum height=7mm, align=center, font=\scriptsize, inner sep=3pt}, k/.style={draw, minimum height=7mm, align=center, font=\scriptsize, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} \node[h] (c1) at (0,4.6) {not Parent(x,z) or not Parent(z,y) or Grandparent(x,y)}; \node[k] (k1) at (7.2,4.6) {Parent(George, Elizabeth)}; \node[h] (c2) at (0.3,2.9) {not Parent(Elizabeth,y) or Grandparent(George,y)}; \node[k] (k2) at (7.2,2.9) {Parent(Elizabeth, Anne)}; \node[h] (c3) at (0.6,1.3) {Grandparent(George, Anne)}; \node[k] (k3) at (7.2,1.3) {not Grandparent(George, Anne)}; \node[draw, minimum size=4mm] (empty) at (3.6,0.0) {}; \node[font=\scriptsize, anchor=west] at (1.15,2.1) {[x/George, z/Elizabeth]}; \node[font=\scriptsize, anchor=east] at (0.05,0.65) {[y/Anne]}; \draw[->, acc, thick] (k1.west) -- (c1.east); \draw[->, acc, thick] (c2.north) -- (c1.south); \draw[->, acc, thick] (k2.west) -- (c2.east); \draw[->, acc, thick] (c3.north) -- (c2.south); \draw[->, acc, thick] (k3.west) -- (c3.east); \draw[->, acc, thick] (empty.north) -- (c3.south); \end{tikzpicture} $$ Reading the trace upward from the empty clause: the negated goal $\neg Grandparent(George, Anne)$ and the empty clause invert to give $Grandparent(George, Anne)$; resolving that against $Parent(Elizabeth, Anne)$ inverts to $\neg Parent(Elizabeth, y) \vee Grandparent(George, y)$; and one more inverse step against $Parent(George, Elizabeth)$ yields the hypothesis $$ Parent(x, z) \wedge Parent(z, y) \;\Rightarrow\; Grandparent(x, y). $$ Inverse resolution is a search: for any $C$ there can be infinitely many pairs $C_1, C_2$ that resolve to it, and the participating clauses may come from the background, the descriptions, the negated classifications, or previously hypothesized clauses — a large branching factor. Implemented systems tame it by generating only the most specific clauses, restricting to **linear resolution**, restricting the language (PROGOL uses Horn clauses with **inverse entailment**, rewriting the constraint to $Background \wedge Descriptions \wedge \neg Classifications \models \neg Hypothesis$), or replacing theorem proving with model checking. ### Inventing new predicates Inverse resolution has a capability no attribute-based or top-down method matches: it can **invent new predicates**. When an inverse step hypothesizes two clauses $C_1$ and $C_2$ from a single clause $C$, resolution eliminates a literal the two share — and that literal can contain a predicate that appears nowhere in $C$. Working backward, the system is free to _generate_ a new predicate to reconstruct the missing literal. $$ % caption: An inverse-resolution step that invents a predicate P. Splitting the lower % clause into two hypothesized parents forces a shared literal in a new predicate P; % later steps constrain P by Mother(x,y) => P(x,y) and Father(x,y) => P(x,y), so P % turns out to be Parent. \begin{tikzpicture}[>=stealth, font=\scriptsize, h/.style={draw, fill=black!7, minimum height=7mm, align=center, font=\scriptsize, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} \node[h] (l) at (-2.7,2.3) {not Father(x,y) or P(x,y)}; \node[h] (r) at (3.0,2.3) {not P(George,y) or Ancestor(George,y)}; \node[h] (bot) at (0.2,0.4) {Father(George,y) or Ancestor(George,y)}; \node[font=\scriptsize, anchor=west] at (-0.6,1.35) {[x/George]}; \draw[->, acc, thick] (bot.north) -- (l.south); \draw[->, acc, thick] (bot.north) -- (r.south); \end{tikzpicture} $$ Here a new predicate $P$ is generated while learning $Ancestor$. Later inverse steps might add $Mother(x, y) \Rightarrow P(x, y)$ and $Father(x, y) \Rightarrow P(x, y)$, which together identify $P$ as exactly the $Parent$ relation. Algorithms that generate new predicates perform **constructive induction**, one of the hardest problems in machine learning and a necessary part of genuine cumulative learning. New terms have driven major scientific advances — Galileo's acceleration, Joule's thermal energy — because a well-chosen new entity lets a whole body of observations be explained by a simpler theory. An inverse-resolution system that inverts a complete resolution strategy is, in principle, a complete algorithm for learning first-order theories: given trajectories of falling bodies and suitable background mathematics, it could in principle infer the law of gravity. What is missing is not expressive power but the heuristics to search the enormous space efficiently. ## Modern ILP and statistical relational learning FOIL and inverse resolution are the classical ILP of this lesson; the field has moved on in three directions the textbook predates, all still trading in human-readable relational hypotheses. **Combining logic with probability.** The sharpest limitation of pure ILP is brittleness — one noisy example can force a wrong specialization or collapse a version space. **Statistical relational learning** fixes this by attaching probabilities to first-order rules. **Markov logic networks** (Richardson and Domingos, 2006) weight each first-order clause and treat the set as a template for a Markov random field, so a rule can be usually-but-not-always true; learning fits both the clauses and their weights.[^srl-mln] **ProbLog** (De Raedt, Kimmig, and Toivonen, 2007) does the same for logic programs, annotating each fact and rule with a probability and computing the probability of a query by summing over proofs.[^srl-problog] These systems keep the relational expressiveness that defeats attribute-based methods while gaining the noise tolerance that made naive Bayes and EM practical. **Modern rule learners.** The successors to FOIL and PROGOL search smarter and learn harder programs. **Metagol** (Muggleton, Lin, and Tamaddoni-Nezhad, 2015) does _meta-interpretive learning_: it learns recursive logic programs and invents auxiliary predicates by instantiating higher-order metarules, making predicate invention systematic rather than incidental.[^ilp-metagol] **Popper** (Cropper and Morel, 2021) recasts ILP as a constraint-satisfaction search: it generates a candidate program, tests it, and on failure derives _constraints_ that prune every program with the same flaw, an approach called learning from failures that scales to programs earlier systems could not find.[^ilp-popper] Cropper and Dumančić's survey "Inductive Logic Programming at 30" (2022) is the current map of the field.[^ilp-survey] **Neuro-symbolic learning.** A parallel line makes rule induction differentiable so it can be trained by gradient descent alongside neural networks. **∂ILP** (Evans and Grefenstette, 2018) represents rules as soft, continuously-weighted choices and learns them end-to-end, tolerating noisy and ambiguous data that break discrete ILP.[^ns-dilp] This connects the relational learning of this lesson to the deep-learning methods of the sibling subject: the goal is a system that learns _representations_ from raw data the way a network does, yet outputs _explanations_ a scientist can read, the way ILP does. The through-line from Meta-DENDRAL to Popper is unchanged: prior knowledge, expressed as logic, lets a learner state and find relational theories that no bag-of-attributes method can even represent — and the modern work is mostly about doing that search faster and under noise. ## Where this leaves us Every method here obeys one of three entailment constraints, and they line up by how much the hypothesis contributes. EBL requires $Background \models Hypothesis$: nothing factually new, only speed. RBL requires $Background \wedge Descriptions \wedge Classifications \models Hypothesis$: deductive generalization licensed by relevance, again nothing beyond the logical closure of what is known. KBIL, and ILP as its main realization, drops both restrictions — the hypothesis is genuinely new, and $Background \wedge Hypothesis \wedge Descriptions \models Classifications$ lets background knowledge shrink the search while first-order syntax lets the learner state relational hypotheses that attribute-based methods cannot represent. The two themes hold throughout. Knowledge makes learning _faster_: it prunes otherwise consistent hypotheses (version spaces, determinations), shortens the hypotheses needed to explain the data (EBL, background clauses in ILP), and narrows the space to search (relevance, declarative bias). And knowledge makes learning _richer_: first-order background and hypotheses reach relational concepts — $Grandparent$, protein folds, $Ancestor$ — and inverse resolution can even invent the new predicates a good theory needs. This same use of prior structure carries into [reinforcement learning](/artificial-intelligence/learning/reinforcement-learning), where an agent must learn from its own experience of acting rather than from labelled examples, and where prior knowledge again decides how quickly that experience pays off. [^srl-mln]: Richardson, M., and Domingos, P. (2006), "Markov Logic Networks," _Machine Learning_ 62: 107–136 — weighted first-order clauses defining a Markov random field, giving relational models that tolerate exceptions and noise. [^srl-problog]: De Raedt, L., Kimmig, A., and Toivonen, H. (2007), "ProbLog: A Probabilistic Prolog and Its Application in Link Discovery," _IJCAI_ — probabilistic logic programs where facts and rules carry probabilities and query probability is computed over proofs. [^ilp-metagol]: Muggleton, S. H., Lin, D., and Tamaddoni-Nezhad, A. (2015), "Meta-interpretive learning of higher-order dyadic datalog," _Machine Learning_ 100: 49–73 — learning recursive programs and inventing predicates via higher-order metarules. [^ilp-popper]: Cropper, A., and Morel, R. (2021), "Learning programs by learning from failures," _Machine Learning_ 110: 801–856 — the Popper system, casting ILP as constraint-based search that prunes flawed programs from failures. [^ilp-survey]: Cropper, A., and Dumančić, S. (2022), "Inductive Logic Programming at 30: A New Introduction," _Journal of Artificial Intelligence Research_ 74: 765–850 — a survey of the modern field. [^ns-dilp]: Evans, R., and Grefenstette, E. (2018), "Learning Explanatory Rules from Noisy Data," _Journal of Artificial Intelligence Research_ 61: 1–64 — differentiable ILP (∂ILP), learning soft-weighted rules end-to-end by gradient descent under noise.