Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

### 7.7.1 Version-Space Learning

Rather than enumerating all of the hypotheses, the subset of * H* consistent with the examples can
be found more efficiently by imposing some structure on the hypothesis
space.

Hypothesis *h _{1}* is a

**more general hypothesis**than hypothesis

*h*if

_{2}*h*implies

_{2}*h*. In this case,

_{1}*h*is a

_{2}**more specific hypothesis**than

*h*. Any hypothesis is both more general than itself and more specific than itself.

_{1}**Example 7.26:**The hypothesis

*¬academic ∧music*is more specific than

*music*and is also more specific than

*¬academic*. Thus,

*music*is more general than

*¬academic ∧music*. The most general hypothesis is

*true*. The most specific hypothesis is

*false*.

The "more general than" relation forms a partial ordering over the hypothesis space. The version-space algorithm that follows exploits this partial ordering to search for hypotheses that are consistent with the training examples.

Given hypothesis space * H* and examples

*E*, the

**version space**is the subset of

*that is consistent with the examples.*

**H**The **general boundary** of a version space, *G*, is the set of
maximally general members of the version space (i.e., those members
of the version space such that no other element of the version
space is more general). The **specific boundary** of a
version space, *S*, is the set of maximally specific members of the version
space.

These concepts are useful because the general boundary and the specific boundary completely determine the version space:

**Proposition 7.1:**The version space, given hypothesis space

*and examples*

**H***E*, can be derived from its general boundary and specific boundary. In particular, the version space is the set of

*h∈*such that

**H***h*is more general than an element of

*S*and more specific than an element of

*G*.