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.
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: