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?
Visit1Sam’sBreakfastFridayCheapYes
Visit2Kim’sLunchFridayExpensiveNo
Visit3Sam’sLunchSaturdayCheapYes
Visit4Bob’sBreakfastSundayCheapNo
Visit5Sam’sBreakfastSundayExpensiveNo
Visit1
restaurant : Sam’s
meal : breakfast
day : Friday
cost : cheap
Visit1
restaurant : Sam’s
meal : breakfast
day : Friday
cost : cheap
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Specific
General
Visit2
restaurant : Kim’s
meal : lunch
day : Friday
cost : expensive
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Specific
General
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kim’s
meal : lunch
day : Friday
cost : expensive
[any]
Breakfast
[any]
[any]
Specific
General
Sam’s
[any]
[any]
[any]
[any]
[any]
[any]
cheap
[any]
[any]
Friday
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kim’s
meal : lunch
day : Friday
cost : expensive
Specific
General
[any]
[any]
[any]
cheap
[any]
[any]
Friday
[any]
[any]
Breakfast
[any]
[any]
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit2
restaurant : Kim’s
meal : lunch
day : Friday
cost : expensive
Specific
General
[any]
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sam’s
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sam’s
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sam’s
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
[any]
Breakfast
[any]
[any]
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit3
restaurant : Sam’s
meal : lunch
day : Saturday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bob’s
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bob’s
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bob’s
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bob’s
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
[any]
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit4
restaurant : Bob’s
meal : Breakfast
day : Sunday
cost : cheap
Specific
General
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sam’s
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sam’s
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
[any]
[any]
cheap
Sam’s
breakfast
Friday
cheap
[any]
[any]
[any]
[any]
Visit5
restaurant : Sam’s
meal : Breakfast
day : Sunday
cost : expensive
Specific
General
Sam’s
[any]
[any]
cheap
Sam’s
[any]
[any]
[any]
Sam’s
[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?
Visit1Kim’sBreakfastFridayCheapNoYes
Visit2Kim’sLunchFridayCheapNoYes
Visit3Sam’sLunchSaturdayCheapNoNo
Visit4Kim’sBreakfastSundayCheapYesNo
Visit5Sam’sBreakfastSundayExpensiveYesNo
Visit6Kim’sLunchSaturdayCheapNoYes
Visit7Kim’sLunchMondayExpensiveNoNo
Kim’s
[any]
[any]
Cheap
[any]
[any]
[any]
[any]
[any]
[any]
[any]
Lunch
Friday
[any]
No
Kim’s
Lunch
Friday
Cheap
No
Kim’s
[any]
[any]
Cheap
No
[any]
[any]
[any]
Cheap
No
What model did you converge on?
Visit1
restaurant : Kim’smeal : Breakfastday : Friday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
What would the initial general and specific models be?
Visit2
restaurant : Kim’smeal : Lunchday : Friday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Based on this example, would we generalize or specialize?
ο Generalize ο Specialize
Visit2
restaurant : Kim’smeal : Lunchday : Friday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
After generalizing, what will the general model be?
Kim’s
[any]
Friday
Cheap
no
Visit3
restaurant : Sam’smeal : Lunchday : Saturday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kim’s
[any]
Friday
Cheap
no
Based on this example, would we generalize or specialize?
ο Generalize ο Specialize
Visit3
restaurant : Sam’smeal : Lunchday : Saturday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kim’s
[any]
Friday
Cheap
no
How many potential general models will we have after specializing based on this case and pruning?
3
Visit3
restaurant : Sam’smeal : Lunchday : Saturday
cost : Cheapvegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
Kim’s
[any]
Friday
Cheap
no
[any]
[any]
Friday
[any]
[any]
Kim’s
[any]
[any]
[any]
[any]
[any]
Breakfast
[any]
[any]
[any]
NumberMealMealDayCostVeganReaction?
Visit1Kim’sBreakfastFridayCheapNoYes
Visit2Kim’sLunchFridayCheapNoYes
Visit3Sam’sLunchSaturdayCheapNoNo
Visit4Kim’sBreakfastSundayCheapYesNo
Visit5Sam’sBreakfastSundayExpensiveYesNo
Visit6Kim’sLunchSaturdayCheapNoYes
Visit7Kim’sLunchMondayExpensiveNoNo
Kim’s
[any]
[any]
Cheap
[any]
[any]
[any]
[any]
[any]
[any]
[any]
Lunch
Friday
[any]
No
Kim’s
Lunch
Friday
Cheap
No
Kim’s
[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?
Visit1Sam’sBreakfastFridayCheapYes
Visit2Kim’sLunchFridayExpensiveNo
Visit3Sam’sLunchSaturdayCheapYes
Visit4Bob’sBreakfastSundayCheapNo
Visit5Sam’sBreakfastSundayExpensiveNo
NumberRestaurantMealDayCostAllergic Reaction?
Visit1Sam’sBreakfastFridayCheapYes
Visit2Kim’sLunchFridayExpensiveNo
Visit3Sam’sLunchSaturdayCheapYes
Visit4Bob’sBreakfastSundayCheapNo
Visit5Sam’sBreakfastSundayExpensiveNo
✓Visit1
✓Visit3
× Visit5
Restaurant
Kim’s
Bob’s
Sam’s
× Visit2
× Visit4
NumberRestaurantMealDayCostAllergic Reaction?
Visit1Sam’sBreakfastFridayCheapYes
Visit2Kim’sLunchFridayExpensiveNo
Visit3Sam’sLunchSaturdayCheapYes
Visit4Bob’sBreakfastSundayCheapNo
Visit5Sam’sBreakfastSundayExpensiveNo
Restaurant
Kim’s
Bob’s
Sam’s
× 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 Raven’s 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.