Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

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 h1 is a more general hypothesis than hypothesis h2 if h2 implies h1. In this case, h2 is a more specific hypothesis than h1. Any hypothesis is both more general than itself and more specific than itself.

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 H that is consistent with the examples.

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 H and examples E, can be derived from its general boundary and specific boundary. In particular, the version space is the set of h∈H such that h is more general than an element of S and more specific than an element of G.