Knowledge in Learning

Learning from examples starts from almost nothing. A decision-tree learner assumes only a rough form for its hypotheses — some tree over these attributes — plus a mild preference for simplicity, and then searches. Before it can learn anything new it must, in effect, forget everything it knows. That is a strange way for an intelligent agent to operate. A traveler who hears one Brazilian speak Portuguese concludes that Brazilians speak Portuguese, but does not conclude that all Brazilians are named Fernando on learning the speaker's name. The difference is prior knowledge: she already knows that nationality tends to fix language but not personal names.

This lesson studies learning that takes advantage of prior knowledge about the world, usually represented as general first-order logical theories. For the first time we bring knowledge representation and learning together. The benefit is twofold: knowledge makes learning faster (fewer examples suffice), and it makes learning richer (relational hypotheses that no attribute-based method can even express).

A logical formulation of learning

To let knowledge participate, we first rebuild induction inside logic. Each example $X_{i}$ is described by a logical sentence. Attributes become unary predicates, so the first restaurant example (from the decision-tree lesson) reads

A l t er na t e (X_{1}) \land \neg B a r (X_{1}) \land \neg F r i / S a t (X_{1}) \land H u n g r y (X_{1}) \land \dots

Write $D_{i} (X_{i})$ for the whole description of $X_{i}$ . The classification is a literal in the goal predicate: $W i l l W ai t (X_{1})$ or $\neg W i l l W ai t (X_{1})$ . Every hypothesis $h_{j}$ has the form

\forall x G o a l (x) \leftrightarrow C_{j} (x),

where the candidate definition $C_{j} (x)$ is some expression over the attribute predicates. A decision tree is one such sentence. The set of examples a hypothesis predicts positive is its extension; two hypotheses with different extensions are logically inconsistent, because they disagree on at least one example. The hypothesis space $H = {h_{1}, \dots, h_{n}}$ is all the hypotheses the learner will entertain, and the learner believes the disjunction $h_{1} \lor h_{2} \lor \dots \lor h_{n}$ .

An example is inconsistent with a hypothesis in one of two ways. It is a false negative if the hypothesis says negative but the example is positive, and a false positive if the hypothesis says positive but the example is negative. In either case the example and hypothesis are logically inconsistent, so — assuming the example is a correct observation — the hypothesis can be ruled out. Behind that elimination sits the resolution rule: an inconsistent example resolves against a disjunct of the hypothesis space, deleting it. Induction becomes the gradual elimination of hypotheses inconsistent with the data.

Enumerating and resolving over a vast (or infinite) hypothesis space by theorem proving is impractical. Two efficient strategies find consistent hypotheses with much less effort.

Current-best-hypothesis search

Keep a single hypothesis and patch it as examples arrive. When a false negative appears, the hypothesis is too narrow, so we generalize its extension to admit the new positive. When a false positive appears, the hypothesis is too broad, so we specialize its extension to exclude the new negative. A consistent example requires no action.

Current-best-hypothesis search shown as an extension (rectangle) over examples marked

+

and

-

. A false negative (circled

+

outside) forces a generalization that grows the region; a false positive (circled

-

inside) forces a specialization that shrinks it.

Both moves also have a purely logical reading, and that is what lets a program carry them out. If hypothesis $h_{1}$ with definition $C_{1}$ generalizes $h_{2}$ with definition $C_{2}$ , then $\forall x C_{2} (x) \Rightarrow C_{1} (x)$ . So to generalize $h_{2}$ , find a $C_{1}$ logically implied by $C_{2}$ . The simplest way is dropping conditions: if $C_{2} (x)$ is $A l t er na t e (x) \land P a t r o n s (x, S o m e)$ , dropping the first conjunct gives the weaker $C_{1} (x) \equiv P a t r o n s (x, S o m e)$ , which admits more positives. Specialization is the mirror image: add a conjunct, or drop a disjunct.

A worked trace on the restaurant data shows the mechanics. The hypothesis is adjusted example by example:

$X_{1}$ (positive): $A l t er na t e (X_{1})$ holds, so start with $h_{1} : \forall x W i l l W ai t (x) \leftrightarrow A l t er na t e (x)$ .
$X_{2}$ (negative): $h_{1}$ predicts positive — a false positive. Specialize by adding a conjunct: $h_{2} : W i l l W ai t (x) \leftrightarrow A l t er na t e (x) \land P a t r o n s (x, S o m e)$ .
$X_{3}$ (positive): $h_{2}$ predicts negative — a false negative. Generalize by dropping $A l t er na t e$ : $h_{3} : W i l l W ai t (x) \leftrightarrow P a t r o n s (x, S o m e)$ .
$X_{4}$ (positive): false negative again. We cannot drop $P a t r o n s$ (that would readmit $X_{2}$ ), so add a disjunct: $h_{4} : W i l l W ai t (x) \leftrightarrow P a t r o n s (x, S o m e) \lor (P a t r o n s (x, F u l l) \land F r i / S a t (x))$ .

The algorithm is nondeterministic: at each step several generalizations or specializations may apply, and a greedy choice can paint the search into a corner where no local repair restores consistency. Then it must backtrack to an earlier choice point.

Algorithm:

\textsc{Current-Best-Learning}(examples, h)

— maintain and repair one hypothesis

1
input: a set of $examples$ , a current hypothesis $h$
2
if $examples$ is empty then
3
return $h$
4
$e \gets$ first of $examples$
5
if $e$ is consistent with $h$ then
6
return $\textsc{Current-Best-Learning}(rest(examples), h)$
7
else if $e$ is a false positive for $h$ then
8
for each $h'$ in specializations of $h$ consistent with $examples$ seen so far do
9
$h'' \gets \textsc{Current-Best-Learning}(rest(examples), h')$
10
if $h'' \ne fail$ then return $h''$
11
else if $e$ is a false negative for $h$ then
12
for each $h'$ in generalizations of $h$ consistent with $examples$ seen so far do
13
$h'' \gets \textsc{Current-Best-Learning}(rest(examples), h')$
14
if $h'' \ne fail$ then return $h''$
15
return $fail$

Two costs bite as data grows: every repair rechecks all previous examples, and the backtracking search can wander through a doubly-exponential hypothesis space.

Least-commitment search and the version space

Backtracking arises because current-best-hypothesis commits to one guess too soon. The least-commitment alternative keeps all hypotheses consistent with the data so far, never choosing among them. As inconsistent hypotheses are pruned from the disjunction $h_{1} \lor \dots \lor h_{n}$ , the surviving set — assuming the true hypothesis is in $H$ — still contains the right answer, because only incorrect hypotheses were removed. This surviving set is the version space, and the algorithm that maintains it is candidate elimination.

The version space can be astronomically large, so we never list it. Instead we exploit the generalization ordering, just as one represents all reals in $[1, 2]$ by the two endpoints. The version space is bounded by two boundary sets: the G-set, its most general members, and the S-set, its most specific members. Everything between the two boundaries is guaranteed consistent.

The version space bounded by a most-general G-set and a most-specific S-set. Every hypothesis between the two boundaries is consistent; the shaded regions above

G

and below

S

are all inconsistent.

The initial version space represents every hypothesis: set the G-set to $T r u e$ (everything is positive) and the S-set to $F a l se$ (nothing is). The $Version-Space-Update$ step retains only hypotheses consistent with each new example $e$ ; the boundaries are moved by four cases, one per boundary member $S_{i}$ or $G_{i}$ that the new example makes inconsistent:

False positive for $S_{i}$ : $S_{i}$ is too general, and by definition has no consistent specialization, so remove it from the S-set.
False negative for $S_{i}$ : $S_{i}$ is too specific; replace it by its immediate generalizations that are still more specific than some member of $G$ .
False positive for $G_{i}$ : $G_{i}$ is too general; replace it by its immediate specializations that are still more general than some member of $S$ .
False negative for $G_{i}$ : $G_{i}$ is too specific, has no consistent generalization, so remove it from the G-set.

The candidate-elimination update. A new example may be a false positive or false negative for a boundary member; each of the four cases either deletes it or replaces it by immediate neighbors that stay inside the opposite boundary.

The process runs until one of three things happens: exactly one hypothesis remains (return it); the version space collapses — S or G becomes empty, meaning no consistent hypothesis exists, the analogue of the decision-tree learner's failure; or examples run out with several hypotheses left, in which case the version space represents a disjunction and a new example is classified by majority vote of the survivors when they disagree.

A worked candidate-elimination trace

Track the two boundaries through a worked run. Objects have two attributes, $S i z e \in {s ma l l, l a r g e}$ and $C o l or \in {r e d, b l u e}$ , and a hypothesis is a conjunction of attribute constraints, each either a fixed value or a wildcard ? that matches anything. The most specific hypothesis is $⟨ \emptyset, \emptyset ⟩$ (matches nothing) and the most general is $⟨ ?, ?⟩$ (matches everything). Initialize $S = {⟨ \emptyset, \emptyset ⟩}$ and $G = {⟨ ?, ?⟩}$ .

Example 1: $⟨ s ma l l, r e d ⟩$ , positive. A positive example is a false negative for the too-specific $S$ , so generalize $S$ minimally to cover it: $S = {⟨ s ma l l, r e d ⟩}$ . $G$ already covers it, so $G$ is unchanged.
Example 2: $⟨ l a r g e, r e d ⟩$ , positive. Again a false negative for $S$ . The minimal generalization of $⟨ s ma l l, r e d ⟩$ that admits a large object drops the $S i z e$ constraint: $S = {⟨ ?, r e d ⟩}$ . $G$ still covers it.
Example 3: $⟨ s ma l l, b l u e ⟩$ , negative. This is a false positive for $G = ⟨ ?, ?⟩$ , which is too general. Specialize $G$ to exclude the blue negative while staying more general than $S = ⟨ ?, r e d ⟩$ . Adding $C o l or = r e d$ works; adding $S i z e = l a r g e$ does not, because $⟨ l a r g e, ?⟩$ is not more general than $⟨ ?, r e d ⟩$ . So $G = {⟨ ?, r e d ⟩}$ .

Now $S$ and $G$ coincide at $⟨ ?, r e d ⟩$ : the version space has collapsed to a single hypothesis, the concept is red things, learned from three examples without ever enumerating the hypothesis space. Had the third example been positive instead, $S$ would have generalized to $⟨ ?, ?⟩$ , matching $G$ , and the concept would have been anything — the boundaries always squeeze toward each other from opposite sides.

The candidate-elimination trace. S climbs from the empty concept up to (?, red) as positives arrive; G descends from (?, ?) down to (?, red) when the blue negative arrives. The boundaries meet, collapsing the version space to one concept.

Version-space learning is fragile in practice. With noise or too few attributes for exact classification the space always collapses. If unlimited disjunction is allowed, the S-set degenerates to a single hypothesis — the disjunction of all positive descriptions — and the G-set to the negation of all negative descriptions, so nothing is really generalized. And for some hypothesis spaces the boundary sets grow exponentially in the number of attributes. Still, the pure version-space method produced the first genuinely novel scientific knowledge generated by a program, in the Meta-DENDRAL system, which learned mass-spectrometry rules worth publishing.

How prior knowledge changes learning

To bring knowledge in, name the pieces. Let $D escr i pt i o n s$ be the conjunction of all example descriptions and $C l a ss i f i c a t i o n s$ the conjunction of all their goal literals. A $H y p o t h es i s$ that explains the observations must satisfy the entailment constraint (with $⊨$ read logically entails):

H y p o t h es i s \land D escr i pt i o n s ⊨ C l a ss i f i c a t i o n s .

Pure inductive learning solves this for $H y p o t h es i s$ , drawn from a fixed hypothesis space. Add $B a c k g r o u n d$ knowledge and the setting changes: the agent already knows something and is trying to learn more. Learning becomes cumulative — the agent's stock of background knowledge grows over its lifetime, and each new episode both uses and adds to it.

Cumulative, knowledge-based inductive learning. Observations and the current background knowledge feed the learner, which outputs hypotheses that both drive predictions and are folded back into the background knowledge.

Prior knowledge shows up in three distinct roles, each a different entailment constraint. The traveler generalizes about language from one Brazilian; the caveman watching Zog toast a lizard on a stick generalizes a principle of painless cooking from one demonstration; the medical student infers a drug's effect from one consultation. These are not pure induction — the background knowledge does real work, and the shape of that work differs.

Three ways prior knowledge enters learning, ordered by how much the hypothesis contributes. In EBL the background alone entails the hypothesis; in RBL relevance plus data entail it deductively; in KBIL the hypothesis is genuinely new, and background plus hypothesis together explain the data.

Each of the three roles corresponds to a distinct learning method with its own algorithm. Explanation-based learning turns background knowledge into speed, relevance-based learning turns determinations into a smaller search, and inductive logic programming learns genuinely new first-order theories. Those three methods continue in Knowledge-Based Learning: EBL, Relevance, and ILP.