PowerPoint Presentation
Version Spaces
Learning by Recording Cases
Incremental Concept Learning
Version Spaces
Classification
Learning
Lesson Preview
Definition
Abstract version spaces
Algorithm for version spaces
Identification trees
Brick
Brick
Brick
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
touches
touches
supports
supports
Brick
Brick
Brick
left-of
New Concept
touches
touches
must-
support
must-
support
must-
support
must-
support
Current Concept
Background Knowledge
Brick
or
Wedge
Brick
Brick
left-of
touches
touches
Block
Brick
Wedge
is-a
is-a
Current Concept
Block
Brick
Brick
left-of
touches
touches
must-
support
must-
support
must-
support
must-
support
Incremental Concept Learning
Specific
General
Incremental Concept Learning
Example #1: Positive
Specific
General
Incremental Concept Learning
Example #1: Positive
Specific
General
Incremental Concept Learning
Example #2: Negative
Specific
General
Incremental Concept Learning
Example #2: Negative
Specific
General
Incremental Concept Learning
Example #3: Negative
Specific
General
Incremental Concept Learning
Example #3: Negative
Specific
General
Incremental Concept Learning
Example #4: Positive
Specific
General
Incremental Concept Learning
Example #4: Positive
Specific
General
Incremental Concept Learning
Example #5: Negative
Specific
General
Incremental Concept Learning
Example #5: Negative
Specific
General
Incremental Concept Learning
Example #6: Negative
Specific
General
Incremental Concept Learning
Example #6: Negative
Specific
General
Incremental Concept Learning
Specific
General
Specific
General
Version Spaces
Version Spaces
Example #1: Positive
Specific
General
Version Spaces
Example #1: Positive
Specific
General
Version Spaces
Example #2: Negative
Specific
General
Version Spaces
Example #2: Negative
Specific
General
Version Spaces
Example #3: Negative
Specific
General
Version Spaces
Example #3: Negative
Specific
General
Version Spaces
Example #4: Positive
Specific
General
Version Spaces
Example #4: Positive
Specific
General
Version Spaces
Example #5: Negative
Specific
General
Version Spaces
Example #5: Negative
Specific
General
Version Spaces
Example #6: Negative
Specific
General
Version Spaces
Example #6: Negative
Specific
General
Version Spaces
Specific
General
Incremental Concept Learning
Given new example:
Is this an example of the concept?
Generalize the
specific model
Specialize the
general model
Yes
No
Most general model
(matches everything)
Most specific model
(matches one thing)
Specific
General
Positive samples generalize specific descriptions
Negative samples specialize general descriptions
Specific
General
Positive samples prune specific descriptions
Negative samples prune general descriptions
Specific
General
Positive and negative samples force models to converge
Specific
General
NumberRestaurantMealDayCostAllergic Reaction?
Visit1SamsBreakfastFridayCheapYes
Visit2KimsLunchFridayExpensiveNo
Visit3SamsLunchSaturdayCheapYes
Visit4BobsBreakfastSundayCheapNo
Visit5SamsBreakfastSundayExpensiveNo
Visit1
restaurant : Sams
meal : breakfast
day : Friday
cost : cheap
Visit1
restaurant : Sams
meal : breakfast
day : Friday
cost : cheap
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Specific
General
Visit2
restaurant : Kims
meal : lunch
day : Friday
cost : expensive
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Specific
General
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kims
meal : lunch
day : Friday
cost : expensive
[any]
Breakfast
[any]
[any]
Specific
General
Sams
[any]
[any]
[any]
[any]
[any]
[any]
cheap
[any]
[any]
Friday
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kims
meal : lunch
day : Friday
cost : expensive
Specific
General
[any]
[any]
[any]
cheap
[any]
[any]
Friday
[any]
[any]
Breakfast
[any]
[any]
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kims
meal : lunch
day : Friday
cost : expensive
Specific
General
[any]
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sams
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sams
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sams
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sams
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bobs
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bobs
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bobs
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bobs
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bobs
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sams
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sams
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
[any]
[any]
cheap
Sams
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sams
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sams
[any]
[any]
cheap
Sams
[any]
[any]
[any]
Sams
[any]
[any]
cheap
Same!
Algorithm for Version Spaces
For each example:
If the example is positive:
Generalize all specific models to include it
Prune away general models that cannot include it
If the example is negative:
Specialize all general models to include it
Prune away specific models that cannot include it
Prune away any models subsumed by other models
NumberMealMealDayCostVeganReaction?
Visit1KimsBreakfastFridayCheapNoYes
Visit2KimsLunchFridayCheapNoYes
Visit3SamsLunchSaturdayCheapNoNo
Visit4KimsBreakfastSundayCheapYesNo
Visit5SamsBreakfastSundayExpensiveYesNo
Visit6KimsLunchSaturdayCheapNoYes
Visit7KimsLunchMondayExpensiveNoNo
Kims
[any]
[any]
Cheap
[any]
[any]
[any]
[any]
[any]
[any]
[any]
Lunch
Friday
[any]
No
Kims
Lunch
Friday
Cheap
No
Kims
[any]
[any]
Cheap
No
[any]
[any]
[any]
Cheap
No
What model did you converge on?
Visit1
restaurant : Kimsmeal : Breakfastday : Friday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
What would the initial general and specific models be?
Visit2
restaurant : Kimsmeal : Lunchday : Friday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Based on this example, would we generalize or specialize?
Generalize Specialize
Visit2
restaurant : Kimsmeal : Lunchday : Friday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
After generalizing, what will the general model be?
Kims
[any]
Friday
Cheap
no
Visit3
restaurant : Samsmeal : Lunchday : Saturday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kims
[any]
Friday
Cheap
no
Based on this example, would we generalize or specialize?
Generalize Specialize
Visit3
restaurant : Samsmeal : Lunchday : Saturday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kims
[any]
Friday
Cheap
no
How many potential general models will we have after specializing based on this case and pruning?
3
Visit3
restaurant : Samsmeal : Lunchday : Saturday
cost : Cheapvegan : no
Kims
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kims
[any]
Friday
Cheap
no
[any]
[any]
Friday
[any]
[any]
Kims
[any]
[any]
[any]
[any]
[any]
Breakfast
[any]
[any]
[any]
NumberMealMealDayCostVeganReaction?
Visit1KimsBreakfastFridayCheapNoYes
Visit2KimsLunchFridayCheapNoYes
Visit3SamsLunchSaturdayCheapNoNo
Visit4KimsBreakfastSundayCheapYesNo
Visit5SamsBreakfastSundayExpensiveYesNo
Visit6KimsLunchSaturdayCheapNoYes
Visit7KimsLunchMondayExpensiveNoNo
Kims
[any]
[any]
Cheap
[any]
[any]
[any]
[any]
[any]
[any]
[any]
Lunch
Friday
[any]
No
Kims
Lunch
Friday
Cheap
No
Kims
[any]
[any]
Cheap
No
[any]
[any]
[any]
Cheap
No
What model did you converge on?
Is the origin
North of 5N?
East of 5E?
East of 5E?
B
C
D
Yes
No
Yes
Yes
No
No
East of 3E?
Yes
No
Y
East of 2E?
X
A
Y
0E1E2E3E4E5E6E7E8E9E10E
0N1N2N3N4N5N6N7N8N9N10N
C
D
X
A
Yes
No
B
NumberRestaurantMealDayCostAllergic Reaction?
Visit1SamsBreakfastFridayCheapYes
Visit2KimsLunchFridayExpensiveNo
Visit3SamsLunchSaturdayCheapYes
Visit4BobsBreakfastSundayCheapNo
Visit5SamsBreakfastSundayExpensiveNo
NumberRestaurantMealDayCostAllergic Reaction?
Visit1SamsBreakfastFridayCheapYes
Visit2KimsLunchFridayExpensiveNo
Visit3SamsLunchSaturdayCheapYes
Visit4BobsBreakfastSundayCheapNo
Visit5SamsBreakfastSundayExpensiveNo
Visit1
Visit3
Visit5
Restaurant
Kims
Bobs
Sams
Visit2
Visit4
NumberRestaurantMealDayCostAllergic Reaction?
Visit1SamsBreakfastFridayCheapYes
Visit2KimsLunchFridayExpensiveNo
Visit3SamsLunchSaturdayCheapYes
Visit4BobsBreakfastSundayCheapNo
Visit5SamsBreakfastSundayExpensiveNo
Restaurant
Kims
Bobs
Sams
Visit2
Visit4
Visit1
Visit3
Visit5
Cost
Cheap
Expensive
NameHairHeightAgeLotionBurn?
SarahBlondeAverage20sNoYes
DanaBlondeTall30sYesNo
AlexBrownShort30sYesNo
AnnieBlondeShort30sNoYes
EmilyRedAverage40sYesYes
PeteBrownTall40sNoNo
JohnBrownAverage40sNoNo
KatieBlondeShort20sYesNo
JoshRedShort20sNoYes
Red
Blonde
Brown
Emily
Josh
Yes
No
Alex
Pete
John
Yes
No
Dana
Katie
Annie
Sarah
Hair Color
Lotion
Lotion
Yes
Pete
John
Lotion
No
Red
Blonde
Brown
Hair Color
Emily
Annie
Sarah
Red
Blonde
Brown
Hair Color
Alex
Dana
Katie
Josh
Red
Blonde
Brown
Hair Color
Emily
Josh
Lotion
Lotion
Yes
No
Alex
Pete
John
Yes
No
Dana
Katie
Annie
Sarah
John
Emily
Dana
Pete
Alex
Short
Average
Tall
Blonde
Red
Brown
20s
30s
40s
Blonde
Red
Brown
20s
30s
40s
Katie
Annie
Sarah
Red
Blonde
Brown
Emily
Josh
Yes
No
Alex
Pete
John
Yes
No
Dana
Katie
Annie
Sarah
Hair Color
Lotion
Lotion
Height
Hair Color
Hair Color
Age
Age
Assignment
How would you use version spaces to design an agent that could answer Ravens progressive matrices?
To recap
Definition of version spaces
Algorithm for version spaces
Complex problems with version spaces
Limitations and questions
Identification trees
/docProps/thumbnail.jpeg
Reviews
There are no reviews yet.