---
title: Knowledge in Learning
module: Learning
moduleNumber: 5
lessonNumber: 7
order: 507
summary: >
  Pure induction learns a function from labelled examples while knowing almost
  nothing to begin with. This first part brings prior knowledge into the loop by
  recasting learning as logical inference — hypotheses, examples, and classifications
  as sentences. It develops current-best-hypothesis search, the version space and its
  general/specific boundary maintained by candidate elimination, and states the three
  entailment constraints that fix how background knowledge enters. A second part
  builds the three knowledge-based methods those constraints define.
topics: [Learning]
sources:
  - book: AIMA
    ref: "Ch. 19 — Knowledge in Learning; §19.1 A Logical Formulation of Learning; §19.2 Knowledge in Learning"
---

[Learning from examples](/artificial-intelligence/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](/artificial-intelligence/logic-and-planning/first-order-logic).
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](/artificial-intelligence/learning/learning-from-examples))
reads

$$
Alternate(X_1) \wedge \neg Bar(X_1) \wedge \neg Fri/Sat(X_1) \wedge Hungry(X_1) \wedge \ldots
$$

Write $D_i(X_i)$ for the whole description of $X_i$. The classification is a literal
in the goal predicate: $WillWait(X_1)$ or $\neg WillWait(X_1)$. Every hypothesis
$h_j$ has the form

$$
\forall x \;\; Goal(x) \iff 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** $\mathcal{H} = \{h_1, \ldots, h_n\}$ is all the
hypotheses the learner will entertain, and the learner believes the disjunction
$h_1 \vee h_2 \vee \ldots \vee 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.

> **Definition (Consistency).** A hypothesis $h_j$ is consistent with an example
> if it commits neither a false positive nor a false negative on it, and consistent
> with a training set if it is consistent with every example in it. A false positive
> or false negative makes example and hypothesis logically inconsistent, licensing
> the removal of the hypothesis.

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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % (a) consistent
  \begin{scope}
    \draw[black, thick] (0.3,0.3) rectangle (1.9,1.9);
    \node[font=\scriptsize] at (0.7,1.5) {+}; \node[font=\scriptsize] at (1.3,1.4) {+};
    \node[font=\scriptsize] at (0.9,0.9) {+}; \node[font=\scriptsize] at (1.5,0.7) {+};
    \node[font=\scriptsize, red] at (-0.1,2.2) {neg}; \node[font=\scriptsize, red] at (2.5,1.8) {neg};
    \node[font=\scriptsize, red] at (2.4,0.5) {neg}; \node[font=\scriptsize, red] at (0.0,0.3) {neg};
    \node[anchor=north] at (1.1,-0.35) {(a) consistent};
  \end{scope}
  % (b) false negative
  \begin{scope}[xshift=4.6cm]
    \draw[black, thick] (0.3,0.3) rectangle (1.9,1.9);
    \node[font=\scriptsize] at (0.7,1.5) {+}; \node[font=\scriptsize] at (1.3,1.4) {+};
    \node[font=\scriptsize] at (0.9,0.9) {+};
    \node[circle, draw=acc, thick, inner sep=1pt, font=\scriptsize, text=acc] at (2.6,1.1) {+};
    \node[font=\scriptsize, red] at (-0.1,2.2) {neg}; \node[font=\scriptsize, red] at (0.0,0.3) {neg};
    \node[anchor=north] at (1.1,-0.35) {(b) false negative};
  \end{scope}
  % (c) generalized
  \begin{scope}[xshift=9.2cm]
    \draw[acc, thick] (0.3,0.3) -- (0.3,1.9) -- (2.0,1.9) -- (2.0,1.5) -- (2.9,1.5) -- (2.9,0.7) -- (2.0,0.7) -- (2.0,0.3) -- cycle;
    \node[font=\scriptsize] at (0.7,1.5) {+}; \node[font=\scriptsize] at (1.3,1.4) {+};
    \node[font=\scriptsize] at (0.9,0.9) {+}; \node[font=\scriptsize] at (2.5,1.1) {+};
    \node[font=\scriptsize, red] at (-0.1,2.2) {neg}; \node[font=\scriptsize, red] at (0.0,0.3) {neg};
    \node[anchor=north] at (1.3,-0.35) {(c) generalized};
  \end{scope}
\end{tikzpicture}
$$

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 $Alternate(x) \wedge Patrons(x, Some)$, dropping the
first conjunct gives the weaker $C_1(x) \equiv Patrons(x, Some)$, 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): $Alternate(X_1)$ holds, so start with
  $h_1: \forall x\; WillWait(x) \iff Alternate(x)$.
- $X_2$ (negative): $h_1$ predicts positive — a false positive. Specialize by adding
  a conjunct: $h_2: WillWait(x) \iff Alternate(x) \wedge Patrons(x, Some)$.
- $X_3$ (positive): $h_2$ predicts negative — a false negative. Generalize by
  dropping $Alternate$: $h_3: WillWait(x) \iff Patrons(x, Some)$.
- $X_4$ (positive): false negative again. We cannot drop $Patrons$ (that would
  readmit $X_2$), so add a disjunct:
  $h_4: WillWait(x) \iff Patrons(x, Some) \vee (Patrons(x, Full) \wedge Fri/Sat(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
caption: $\textsc{Current-Best-Learning}(examples, h)$ — maintain and repair one hypothesis
input: a set of $examples$, a current hypothesis $h$
if $examples$ is empty then
  return $h$
$e \gets$ first of $examples$
if $e$ is consistent with $h$ then
  return $\textsc{Current-Best-Learning}(rest(examples), h)$
else if $e$ is a false positive for $h$ then
  for each $h'$ in specializations of $h$ consistent with $examples$ seen so far do
    $h'' \gets \textsc{Current-Best-Learning}(rest(examples), h')$
    if $h'' \ne fail$ then return $h''$
else if $e$ is a false negative for $h$ then
  for each $h'$ in generalizations of $h$ consistent with $examples$ seen so far do
    $h'' \gets \textsc{Current-Best-Learning}(rest(examples), h')$
    if $h'' \ne fail$ then return $h''$
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 \vee \ldots \vee h_n$, the surviving set — assuming the true
hypothesis is in $\mathcal{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**.

> **Definition (Version space).** The set of all hypotheses consistent with the
> examples seen so far. It is incremental: a new example can only shrink it, and old
> examples never need re-examination, since every surviving hypothesis already
> agrees with them.

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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % top inconsistent band
  \fill[black] (-1.2,3.0) -- (5.2,3.0) -- (4.2,2.4) -- (-0.2,2.4) -- cycle;
  \node[font=\scriptsize] at (2.0,2.75) {this region all inconsistent};
  % G-set box
  \draw[black, thick] (-0.2,1.7) rectangle (4.2,2.35);
  \node[font=\scriptsize] at (0.3,2.0) {G1}; \node[font=\scriptsize] at (1.3,2.0) {G2};
  \node[font=\scriptsize] at (2.3,2.0) {G3}; \node[font=\scriptsize] at (3.1,2.0) {...};
  \node[font=\scriptsize] at (3.8,2.0) {Gm};
  % S-set box
  \draw[black, thick] (0.6,-0.35) rectangle (3.4,0.3);
  \node[font=\scriptsize] at (1.0,-0.05) {S1}; \node[font=\scriptsize] at (1.8,-0.05) {S2};
  \node[font=\scriptsize] at (2.4,-0.05) {...}; \node[font=\scriptsize] at (3.0,-0.05) {Sn};
  % bottom inconsistent band
  \fill[black] (-0.2,-0.7) -- (4.2,-0.7) -- (5.2,-1.3) -- (-1.2,-1.3) -- cycle;
  \node[font=\scriptsize] at (2.0,-1.0) {this region all inconsistent};
  % connecting lattice (schematic)
  \foreach \gx in {0.3,1.3,2.3,3.8} {
    \draw[black] (\gx,1.7) -- ($ (\gx,1.7)!0.5!(2.0,0.6) $);
  }
  \foreach \sx in {1.0,1.8,3.0} {
    \draw[black] (\sx,0.3) -- ($ (\sx,0.3)!0.5!(2.0,1.3) $);
  }
  % more/less general axis
  \draw[->, acc, thick] (5.6,0.4) -- (5.6,2.1); \node[acc, anchor=west, font=\scriptsize] at (5.6,2.1) {more general};
  \draw[->, acc, thick] (5.6,0.4) -- (5.6,-1.3); \node[acc, anchor=west, font=\scriptsize] at (5.6,-1.3) {more specialized};
\end{tikzpicture}
$$

The initial version space represents every hypothesis: set the G-set to $True$
(everything is positive) and the S-set to $False$ (nothing is). The
$\textsc{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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=42mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (fps) at (0,3.0) {false positive for S-member:\\too general, delete it};
  \node[box] (fns) at (0,1.5) {false negative for S-member:\\too narrow, generalize it};
  \node[box] (fpg) at (0,0.0) {false positive for G-member:\\too general, specialize it};
  \node[box] (fng) at (0,-1.5) {false negative for G-member:\\too narrow, delete it};
  \node[box, draw=acc, text=acc, minimum width=28mm] (out) at (6.0,0.75) {tighter\\version space};
  \draw[->, red, thick] (fps.east) -- (out.west);
  \draw[->, acc, thick] (fns.east) -- (out.west);
  \draw[->, acc, thick] (fpg.east) -- (out.west);
  \draw[->, red, thick] (fng.east) -- (out.west);
\end{tikzpicture}
$$

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,
$Size \in \{small, large\}$ and $Color \in \{red, blue\}$, 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 $\langle \emptyset,
\emptyset \rangle$ (matches nothing) and the most general is $\langle ?, ?
\rangle$ (matches everything). Initialize $S = \{\langle \emptyset, \emptyset
\rangle\}$ and $G = \{\langle ?, ? \rangle\}$.

- **Example 1: $\langle small, red \rangle$, positive.** A positive example is a
  false negative for the too-specific $S$, so generalize $S$ minimally to cover it:
  $S = \{\langle small, red \rangle\}$. $G$ already covers it, so $G$ is unchanged.
- **Example 2: $\langle large, red \rangle$, positive.** Again a false negative for
  $S$. The minimal generalization of $\langle small, red \rangle$ that admits a
  large object drops the $Size$ constraint: $S = \{\langle ?, red \rangle\}$. $G$
  still covers it.
- **Example 3: $\langle small, blue \rangle$, negative.** This is a false positive
  for $G = \langle ?, ? \rangle$, which is too general. Specialize $G$ to exclude the
  blue negative while staying more general than $S = \langle ?, red \rangle$. Adding
  $Color = red$ works; adding $Size = large$ does _not_, because $\langle large, ?
  \rangle$ is not more general than $\langle ?, red \rangle$. So $G = \{\langle ?,
  red \rangle\}$.

Now $S$ and $G$ coincide at $\langle ?, red \rangle$: 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 $\langle ?, ? \rangle$, matching
$G$, and the concept would have been "anything" — the boundaries always squeeze
toward each other from opposite sides.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  h/.style={draw, minimum width=20mm, minimum height=6mm, font=\scriptsize, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % G side descending on the left
  \node[h] (g0) at (0,3.4) {G: (?, ?)};
  \node[h, draw=acc, text=acc] (g1) at (0,0.6) {G: (?, red)};
  \draw[->, acc, thick] (g0) -- (g1) node[midway, right, font=\scriptsize] {ex3 neg};
  % S side ascending on the right
  \node[h] (s0) at (5,-1.0) {S: (none)};
  \node[h] (s1) at (5,0.4) {S: (small, red)};
  \node[h, draw=acc, text=acc] (s2) at (5,1.8) {S: (?, red)};
  \draw[->, acc, thick] (s0) -- (s1) node[midway, right, font=\scriptsize] {ex1 pos};
  \draw[->, acc, thick] (s1) -- (s2) node[midway, right, font=\scriptsize] {ex2 pos};
  % meet
  \draw[acc, dashed, thick] (g1) -- (s2) node[midway, fill=white, inner sep=1.5pt, font=\scriptsize] {G = S: one concept};
\end{tikzpicture}
$$

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 $Descriptions$ be the conjunction of all
example descriptions and $Classifications$ the conjunction of all their goal literals.
A $Hypothesis$ that "explains the observations" must satisfy the **entailment
constraint** (with $\models$ read "logically entails"):

$$
Hypothesis \wedge Descriptions \models Classifications.
$$

Pure inductive learning solves this for $Hypothesis$, drawn from a fixed hypothesis
space. Add $Background$ 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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (bg) at (2.4,2.0) {prior\\knowledge};
  \node[box, ellipse, minimum width=30mm, draw=acc, text=acc] (learn) at (2.4,0) {knowledge-based\\inductive learning};
  \node[box] (hyp) at (6.2,0) {hypotheses};
  \node[font=\scriptsize, anchor=east] at (-0.3,0) {observations};
  \node[font=\scriptsize, anchor=west] at (8.1,0) {predictions};
  \draw[->, black, thick] (-0.3,0.0) -- (learn.west);
  \draw[->, acc, thick] (learn.east) -- (hyp.west);
  \draw[->, black, thick] (hyp.east) -- (8.1,0.0);
  \draw[->, black, thick] (hyp.north) |- (bg.east);
  \draw[->, black, thick] (bg.south) -- (learn.north);
\end{tikzpicture}
$$

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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  row/.style={draw, minimum width=32mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[row] (ebl) at (0,2.4) {EBL\\(explanation-based)};
  \node[row] (rbl) at (0,0.8) {RBL\\(relevance-based)};
  \node[row, draw=acc, text=acc] (kbil) at (0,-0.8) {KBIL\\(knowledge-based induction)};
  \node[anchor=west, font=\scriptsize] at (2.4,2.4) {background alone entails the hypothesis};
  \node[anchor=west, font=\scriptsize] at (2.4,0.8) {relevance + data entail it deductively};
  \node[anchor=west, font=\scriptsize] at (2.4,-0.8) {background + new hypothesis explain the data};
  \draw[->, acc, thick] (0,1.85) -- (0,1.35);
  \draw[->, acc, thick] (0,0.25) -- (0,-0.25);
  \node[rotate=90, font=\scriptsize, anchor=south] at (-2.1,0.8) {hypothesis grows};
  \draw[->, acc, thick] (-1.9,-0.8) -- (-1.9,2.4);
\end{tikzpicture}
$$

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](/artificial-intelligence/learning/knowledge-based-learning-methods).