Machine Learning

  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 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) The LIST-THEN-ELIMINATION algorithm The LIST-THEN-ELIMINATE algorithm first initializes the version space to contain all hypotheses in H and then eliminates any hypothesis found inconsistent with any training example . ___________________________________________________________________________ 1. VersionSpace c a list containing every hypothesis in H 2. For each training example , (x, c(x)) remove from VersionSpace any hypothesis h for which h