Knowledge-Based Learning: EBL, Relevance, and ILP

This builds on 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

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.

Taking the leaves of the generalized tree as the rule body and the variabilized goal as the head produces

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:

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,

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

read nationality determines language. Determinations sanction a deductive form of learning: with the observations, they entail a new general rule.

The entailment constraints for relevance-based learning (RBL) are

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})$.

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.

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 $\left(\genfrac{}{}{0ex}{}{n}{p}\right)=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 $\text{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.

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,

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

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(⟨Mum,Charles⟩)$; 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)\leftrightarrow [Mother(x,y)\vee Father(x,y)]$, the $Grandparent$ definition collapses to $Grandparent(x,y)\leftrightarrow [\exists zParent(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 $⟨George,Anne⟩$ and $388$ negative pairs. FOIL builds Horn clauses with $Grandfather(x,y)$ as head, starting from the empty body

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

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.

$\text{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 $\text{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.

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

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.

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.¹ 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.² 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.³ 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.⁴ Cropper and Dumančić's survey Inductive Logic Programming at 30 (2022) is the current map of the field.⁵

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.⁶ 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, 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.