Unformatted text preview:

1CS 5751 Machine LearningChapter 2 Concept Learning 1Concept Learning• Learning from examples• General-to-specific ordering over hypotheses• Version Spaces and candidate elimination algorithm• Picking new examples• The need for inductive biasCS 5751 Machine LearningChapter 2 Concept Learning 2Some Examples for SmileyFacesEyes FcolorNose Hair?Head Smile?CS 5751 Machine LearningChapter 2 Concept Learning 3Features from Computer ViewPurpleGreenGreenYellowYellow YesYes YesYesYesYesNoNoNoYesRoundRoundRoundSquareRoundSquareRoundSquareSquareRoundEyes FcolorNose Hair?Head Smile?TriangleSquareTriangleSquareTriangleCS 5751 Machine LearningChapter 2 Concept Learning 4Representing HypothesesMany possible representations for hypotheses hIdea: h as conjunctions of constraints on featuresEach constraint can be:– a specific value (e.g., Nose = Square)– don’t care (e.g., Eyes = ?)– no value allowed (e.g., Water=Ø)For example,Eyes Nose Head Fcolor Hair?<Round, ?, Round, ?, No>?CS 5751 Machine LearningChapter 2 Concept Learning 5Prototypical Concept Learning TaskGiven:– Instances X: Faces, each described by the attributes Eyes, Nose, Head, Fcolor, and Hair?– Target function c: Smile? : X -> { no, yes }– Hypotheses H: Conjunctions of literals such as<?,Square,Square,Yellow,?>– Training examples D: Positive and negative examples of the target functionDetermine: a hypothesis h in H such that h(x)=c(x)for all x in D.><><>< )(,,...,)(,,)(,2211 mmxcxxcxxcxCS 5751 Machine LearningChapter 2 Concept Learning 6Inductive Learning HypothesisAny hypothesis found to approximate the target function well over a sufficiently large set of training examples will also approximate the target function well over other unobserved examples.• What are the implications?• Is this reasonable?• What (if any) are our alternatives?• What about concept drift (what if our views/tastes change over time)?2CS 5751 Machine LearningChapter 2 Concept Learning 7Instances, Hypotheses, and More-General-ThanInstances XHypotheses Hx1=<Round,Square,Square,Purple,Yes>SpecificGeneralx2=<Round,Square,Round,Green,Yes>h1=<Round,?,Square,?,?>h3=<Round,?,?,?,?>h2=<Round,?,?,?,Yes>h3h1h2CS 5751 Machine LearningChapter 2 Concept Learning 8Find-S Algorithm1. Initialize h to the most specific hypothesis in H2. For each positive training instance xFor each attribute constraint aiin hIF the constraint aiin h is satisfied by x THEN do nothingELSE replace aiin h by next more general constraint satisfied by x3. Output hypothesis hCS 5751 Machine LearningChapter 2 Concept Learning 9Hypothesis Space Search by Find-Sh3,4Instances XHypotheses HSpecificGeneralh1,2h1=<Round,Triangle,Round,Purple,Yes>x1=<Round,Triangle,Round,Purple,Yes> +x2=<Square,Square,Square,Green,Yes> -x5=<Square,Square,Round,Yellow,Yes> +x4=<Round,Triangle,Round,Green,No> -x3=<Square,Triangle,Round,Yellow,Yes> +h2=<Round,Triangle,Round,Purple,Yes>h3=<?,Triangle,Round,?,Yes>h4=<?,Triangle,Round,?,Yes>h5=<?,?,Round,?,Yes>h0=<φ,φ,φ,φ,φ>h0x1x4x2x5x3h5CS 5751 Machine LearningChapter 2 Concept Learning 10Complaints about Find-S• Cannot tell whether it has learned concept• Cannot tell when training data inconsistent• Picks a maximally specific h (why?)• Depending on H, there might be several!• How do we fix this?CS 5751 Machine LearningChapter 2 Concept Learning 11The List-Then-Eliminate Algorithm1. Set VersionSpace equal to a list containing every hypothesis in H2. For each training example, <x,c(x)>remove from VersionSpace any hypothesis h for which h(x) != c(x)3. Output the list of hypotheses in VersionSpace• But is listing all hypotheses reasonable?• How many different hypotheses in our simple problem?– How many not involving “?” terms?CS 5751 Machine LearningChapter 2 Concept Learning 12Version SpacesA 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 in D.The version space, VSH,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.)()( ) )(,(),( xcxhDxcxDhConsistent=∈><∀≡)},( | {,DhConsistentHhVSDH∈≡3CS 5751 Machine LearningChapter 2 Concept Learning 13Example Version SpaceS: { <?,Triangle,Round,?,Yes> }G: { <?,?,Round,?,?> <?,Triangle,?,?,?> }<?,?,Round,?,Yes> <?,Triangle,?,?,Yes><?,Triangle,Round,?,?>CS 5751 Machine LearningChapter 2 Concept Learning 14Representing Version SpacesThe General boundary, G, of version space VSH,Dis the set of its maximally general members.The Specific boundary, S, of version space VSH,Dis the set of its maximally specific members.Every member of the version space lies between these boundariesyxyxshgGgSsHhVSDH toequalor general more is means where)} )( )( (| {,≥≥≥∈∃∈∃∈=CS 5751 Machine LearningChapter 2 Concept Learning 15Candidate Elimination AlgorithmG = maximally general hypotheses in HS = maximally specific hypotheses in HFor each training example d, doIf d is a positive exampleRemove from G any hypothesis that does not include dFor each hypothesis s in S that does not include dRemove s from SAdd to S all minimal generalizations h of s such that1. h includes d, and2. Some member of G is more general than hRemove from S any hypothesis that is more generalthan another hypothesis in SCS 5751 Machine LearningChapter 2 Concept Learning 16Candidate Elimination Algorithm (cont)For each training example d, do (cont)If d is a negative exampleRemove from S any hypothesis that does include dFor each hypothesis g in G that does include dRemove g from GAdd to G all minimal generalizations h of g such that1. h does not include d, and2. Some member of S is more specific than hRemove from G any hypothesis that is less generalthan another hypothesis in GIf G or S ever becomes empty, data not consistent (with H)CS 5751 Machine LearningChapter 2 Concept Learning 17Example TraceS0: { <Ø,Ø,Ø,Ø,Ø> }G0: { <?,?,?,?,?> }X1=<R,T,R,P,Y> +S1: { <R,T,R,P,Y> }G1X2=<S,S,S,G,Y> -G2: { <R,?,?,?,?>, <?,T,?,?,?>, <?,?,R,?,?>, <?,?,?,P,?> }S2X3=<S,T,R,Y,Y> +S3: { <?,T,R,?,Y> }G3X4=<R,T,R,G,N> -G4: { <?,T,?,?,Y>, <?,?,R,?,Y> }S4X5=<S,S,R,Y,Y> +S5: { <?,?,R,?,Y> }G5CS 5751 Machine LearningChapter 2 Concept Learning 18What Training Example Next?S: { <?,Triangle,Round,?,Yes> }G: { <?,?,Round,?,?> <?,Triangle,?,?,?> }<?,?,Round,?,Yes> <?,Triangle,?,?,Yes><?,Triangle,Round,?,?>4CS 5751


View Full Document

U of M CS 5751 - Concept Learning

Download Concept Learning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Concept Learning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concept Learning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?