Concept Learning Space of Versions of Concepts LearnedA Concept Learning TaskFIND-S Algorithm : Finding a Maximally Specific HypothesisHypothesis found by FIND-SVersion Space and the Candidate Elimination AlgorithmRepresentationConsistent Hypothesis: DefinitionVersion Space: DefinitionThe LIST-THEN-ELIMINATE AlgorithmThe LIST-THEN-ELIMINATE AlgorithmA More Compact Representation for Version SpacesVersion Space with General (G) and Specific (S) Boundary SetsGeneral BoundarySpecific BoundaryVersion Space TheoremThe CANDIDATE-ELIMINATION AlgorithmCANDIDATE-ELIMINATION AlgorithmAn Illustrative ExampleCANDIDATE-ELIMINATION Trace (Samples 1 and 2)Samples 1 and 2 force S boundary to become more general. They have no effect onCANDIDATE-ELIMINATION Trace (Sample 3)Negative example forces G2 to be specialized to G3CANDIDATE-ELIMINATION Trace (Sample 4)Positive sample generalizes S boundaryFinal Version Space for EnjoySportResult of Candidate Elimination AlgorithmRemarks on Version Spaces and CANDIDATE-ELIMINATIONWill CANDIDATE-ELIMINATION Algorithm Converge to the Correct Hypothesis?What Training Example Should the Learner Request Next?Training Example Requested by LearnerOptimal query strategyHow Can Partially Learned Concepts Be Used?New Instances To Be ClassifiedInductive BiasA Biased Hypothesis SpaceAn Unbiased LearnerAn Unbiased LearnerTruth Table(s) for 3 binary variablesConjunctive concepts for 3 binary variablesAn Unbiased learnerAn Unbiased LearnerUnbiased Learner is Too LimitedThe Futility of Bias-Free LearningInductive Bias of a LearnerInductive Bias DefinitionCANDIDATE-ELIMINATION Algorithm inductive biasModeling Inductive Systems by Equivalent Deductive SystemsThree Learners :weakest to strongest biasSummarySummary, continuedSummary, continued1Concept Learning Space of Versions of Concepts Learned2A Concept Learning TaskExample Sky AirTemp Humidity Wind Water Forecast EnjoySport1 Sunny Warm Normal Strong Warm Same Yes2 Sunny Warm High Strong Warm Same Yes3 Rainy Cold High Strong Warm Change No4 Sunny Warm High Strong Cool Change YesTable 2.1 Target concept: “Days on which Aldo enjoys his favorite water sport” Task is to learn to predict value of EnjoySport from three positive examples, one negative example3FIND-S Algorithm : Finding a Maximally Specific Hypothesis• Initialize h to the most specific hypothesis in H• For each positive training instance x• For each attribute constraint aiin h• If the constraint aiis satisfied by x• Then do nothing• Else replace ai in h by the next more general constraint that is satisfied by x• Output hypothesis h• Note: Find-S ignores negative training instances• Since negative instances will be classified as negative by hypothesis anyhow, as long as samples are not inconsistent4Hypothesis found by FIND-S h <--<Sunny,Warm,?,Strong,?,?> There are other hypotheses consistent with the data, e.g., <Sunny,?,?,Strong,?,?>Example Sky AirTemp Humidity Wind Water Forecast EnjoySport1 Sunny Warm Normal Strong Warm Same Yes2 Sunny Warm High Strong Warm Same Yes3 Rainy Cold High Strong Warm Change No4 Sunny Warm High Strong Cool Change Yes5Hypothesis Space Search Performed by FIND-S +:positive instance-: negative instance6Version Space and the Candidate Elimination Algorithm Find-S algorithm outputs a hypothesis that is consistent with the training samples Candidate -Elimination algorithm outputs all hypotheses consistent with the training samples7Representation The CANDIDATE-ELIMINATION algorithm finds all describable hypotheses that are consistent with the observed training examples.8Consistent Hypothesis: Definition  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. A hypothesis is consistent with the training samples if it correctly classifies the samples)()())(,(),( xcxhDxcxDhConsistent =∈∀≡9Version Space: Definition The subset of all hypotheses consistent with the training examples  Definition: The version space, VS H,D, w.r.t. hypotheses H and examples D, is a subset of hypotheses from Hconsistent with the examples{}),(|,DhConsistentHhVSDH∈≡10The LIST-THEN-ELIMINATEAlgorithm 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.11The LIST-THEN-ELIMINATEAlgorithm•VersionSpace ← a list containing every hypothesis in H•For each training example, <x,c(x)>•remove from VersionSpace any hypothesis h for which h(x)≠c(x).•Output the list of hypotheses in VersionSpace.•Requires exhaustively enumerating all hypotheses in H -- unrealistic for all but most trivial hypothesis spaces12A More Compact Representation for Version Spaces The CANDIDATE-ELIMINATION algorithm  same principle as LIST-THEN-ELIMINATEalgorithm employs a more compact representation of the version space than does the LIST-THEN-ELIMINATE algorithm version space is represented by its most general and least general members13Version Space with General (G) and Specific (S) Boundary Sets14General BoundaryDefinition: The general boundary G, with respect to hypothesis space H and training data D, is the set of maximally general members of H consistent with D.{})]},())[((),(| DgConsistentggHgDgConsistentHgGg′∧>′∈′¬∃∧∈≡15Specific BoundaryDefinition: The specific boundary S, with respect to hypothesis space H and training data D, is the set of minimally general (i.e., maximally specific) members of H consistent with D.{})]},())[((),(| DsConsistentssHsDsConsistentHsSg′∧′>∈′¬∃∧∈≡16Version Space TheoremVersion space consists of hypotheses contained in S, plus those contained in G and those in-betweenTheorem: Let X be an arbitrary set of instances, and let H be a set of boolean-valued hypotheses defined over X. Let c : X → {0,1} be an arbitrary target concept defined over X, and let D be an arbitrary set of training examples {〈x,c(x)〉}. For all X, H, c, and D such that S and G are well defined,)})()((|{,shgGgSsHhVSggDH≥≥∈∃∈∃∈=17The CANDIDATE-ELIMINATION Algorithm The CANDIDATE-ELIMINATION algorithm computes the version space containing all hypotheses from H that are consistent with an observed sequence of training examples.18CANDIDATE-ELIMINATION AlgorithmInitialize G to the set of maximally general hypotheses in HInitialize S to the set of maximally