VERSION SPACES AND THE CANDIDATE-ELIMINATION ALGORITHM

The key idea in the CANDIDATE-ELIMINATION algorithm is to output a description of the set of all hypotheses consistent with the training examples

 Representation

 Definition: consistent- A hypothesis h is consistent with a set of training examples D if and only if h(x) = c(x) for each example (x, c(x)) in D.

Consistent (h, D) º (" áx, c(x)ñ Î D) h(x) = c(x)) 

Note difference between definitions of consistent and satisfies

• An example x is said to satisfy hypothesis h when h(x) = 1, regardless of whether x is a positive or negative example of the target concept.
• An example x is said to consistent with hypothesis h iff h(x) = c(x)

 Definition: version space- The version space, denoted V SH, D with respect to hypothesis space

H and training examples D, is the subset of hypotheses from H consistent with the training examples in D

V SH, D  º{h Î H | Consistent (h, D)}