Outline read Chapter 2 suggested exercises 2 2 2 3 2 4 2 6 Learning from examples General to speci c ordering over hypotheses Version spaces and candidate elimination algorithm Picking new examples The need for inductive bias Note simple approach assuming no noise illustrates key concepts 22 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Training Examples for EnjoySport Sky Sunny Sunny Rainy Sunny Temp Warm Warm Cold Warm Humid Normal High High High Wind Strong Strong Strong Strong Water Warm Warm Warm Cool Forecst EnjoySpt Same Yes Same Yes Change No Change Yes What is the general concept 23 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Representing Hypotheses Many possible representations Here h is conjunction of constraints on attributes Each constraint can be a spec c value e g Water Warm don t care e g Water no value allowed e g Water For example Sky AirTemp Humid Wind Water Forecst hSunny Strong Samei 24 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Prototypical Concept Learning Task Given Instances X Possible days each described by the attributes Sky AirTemp Humidity Wind Water Forecast Target function c EnjoySport X f0 1g Hypotheses H Conjunctions of literals E g h Cold High i Training examples D Positive and negative examples of the target function hx1 c x1 i hxm c xm i Determine A hypothesis h in H such that h x c x for all x in D 25 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 The inductive learning hypothesis Any hypothesis found to approximate the target function well over a su ciently large set of training examples will also approximate the target function well over other unobserved examples 26 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Instance Hypotheses and MoreGeneral Than Instances X Hypotheses H Specific h 1 x1 x h h 2 3 2 General 27 x1 Sunny Warm High Strong Cool Same h 1 Sunny Strong x Sunny Warm High Light Warm Same 2 h Sunny 2 h Sunny Cool 3 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Find S Algorithm 1 Initialize h to the most speci c hypothesis in H 2 For each positive training instance x For each attribute constraint ai in h If the constraint ai in h is satis ed by x Then do nothing Else replace ai in h by the next more general constraint that is satis ed by x 3 Output hypothesis h 28 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Hypothesis Space Search by Find S Instances X Hypotheses H h0 x3 h1 x 1 h 2 3 x 2 x4 h x 1 Sunny Warm Normal Strong Warm Same x 2 Sunny Warm High Strong Warm Same x 3 Rainy Cold High Strong Warm Change x Sunny Warm High Strong Cool Change 4 29 Specific lecture slides for textbook 4 General h 0 h1 Sunny Warm Normal Strong Warm Sam h2 Sunny Warm Strong Warm Same h Sunny Warm Strong Warm Same 3 h Sunny Warm Strong 4 Machine Learning T Mitchell McGraw Hill 1997 Complaints about Find S Can t tell whether it has learned concept Can t tell when training data inconsistent Picks a maximally speci c h why Depending on H there might be several 30 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Version Spaces A hypothesis h is consistent with a set of training examples D of target concept c if and only if h x c x for each training example hx c x i in D Consistent h D 8hx c x i 2 D h x c x The version space V SH D with respect to hypothesis space H and training examples D is the subset of hypotheses from H consistent with all training examples in D V SH D fh 2 H jConsistent h D g 31 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 The List Then Eliminate Algorithm 1 V ersionSpace a list containing every hypothesis in H 2 For each training example hx c x i remove from V ersionSpace any hypothesis h for which h x 6 c x 3 Output the list of hypotheses in V ersionSpace 32 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Example Version Space S Sunny Warm Strong Sunny Strong G 33 Sunny Warm Warm Strong Sunny Warm lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Representing Version Spaces The General boundary G of version space V SH D is the set of its maximally general members The Speci c boundary S of version space V SH D is the set of its maximally speci c members Every member of the version space lies between these boundaries V SH D fh 2 H j 9s 2 S 9g 2 G g h s g where x y means x is more general or equal to y 34 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Candidate Elimination Algorithm G maximally general hypotheses in H S maximally speci c hypotheses in H For each training example d do If d is a positive example Remove from G any hypothesis inconsistent with d For each hypothesis s in S that is not consistent with d Remove s from S Add to S all minimal generalizations h of s such that 1 h is consistent with d and 2 some member of G is more general than h Remove from S any hypothesis that is more general than another hypothesis in S If d is a negative example 35 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Remove from S any hypothesis inconsistent with d For each hypothesis g in G that is not consistent with d Remove g from G Add to G all minimal specializations h of g such that 1 h is consistent with d and 2 some member of S is more speci c than h Remove from G any hypothesis that is less general than another hypothesis in G 36 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 Example Trace S 0 G 0 37 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 What Next Training Example S Sunny Warm Strong Sunny Strong G 38 Sunny Warm Warm Strong Sunny Warm lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 How Should These Be Classi ed S Sunny Warm Strong Sunny Strong G Warm Strong Sunny Warm hSunny Warm Normal Strong Cool Changei hRainy hSunny 39 Sunny Warm Cool Normal Light Warm Samei Warm Normal Light Warm Samei lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 What Justi es this Inductive Leap hSunny Warm Normal Strong Cool Changei hSunny Warm Normal Light Warm Samei S hSunny Warm Normal i Why believe we can classify the unseen hSunny Warm Normal Strong Warm Samei 40 lecture slides for textbook Machine Learning T Mitchell McGraw Hill 1997 An UNBiased Learner Idea Choose …