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
Number Restaurant Meal Day Cost Allergic Reaction?
Visit1 Sam’s Breakfast Friday Cheap Yes
Visit2 Kim’s Lunch Friday Expensive No
Visit3 Sam’s Lunch Saturday Cheap Yes
Visit4 Bob’s Breakfast Sunday Cheap No
Visit5 Sam’s Breakfast Sunday Expensive No
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
Number Meal Meal Day Cost Vegan Reaction?
Visit1 Kim’s Breakfast Friday Cheap No Yes
Visit2 Kim’s Lunch Friday Cheap No Yes
Visit3 Sam’s Lunch Saturday Cheap No No
Visit4 Kim’s Breakfast Sunday Cheap Yes No
Visit5 Sam’s Breakfast Sunday Expensive Yes No
Visit6 Kim’s Lunch Saturday Cheap No Yes
Visit7 Kim’s Lunch Monday Expensive No No
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’s meal : Breakfast day : Friday
cost : Cheap vegan : no
Kim’s
Breakfast
Friday
Cheap
no
[any]
[any]
[any]
[any]
[any]
What would the initial general and specific models be?
Visit2
restaurant : Kim’s meal : Lunch day : Friday
cost : Cheap vegan : 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’s meal : Lunch day : Friday
cost : Cheap vegan : 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’s meal : Lunch day : Saturday
cost : Cheap vegan : 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’s meal : Lunch day : Saturday
cost : Cheap vegan : 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’s meal : Lunch day : Saturday
cost : Cheap vegan : 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]
Number Meal Meal Day Cost Vegan Reaction?
Visit1 Kim’s Breakfast Friday Cheap No Yes
Visit2 Kim’s Lunch Friday Cheap No Yes
Visit3 Sam’s Lunch Saturday Cheap No No
Visit4 Kim’s Breakfast Sunday Cheap Yes No
Visit5 Sam’s Breakfast Sunday Expensive Yes No
Visit6 Kim’s Lunch Saturday Cheap No Yes
Visit7 Kim’s Lunch Monday Expensive No No
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
0E 1E 2E 3E 4E 5E 6E 7E 8E 9E 10E
0N 1N 2N 3N 4N 5N 6N 7N 8N 9N 10N
C
D
X
A
Yes
No
B
Number Restaurant Meal Day Cost Allergic Reaction?
Visit1 Sam’s Breakfast Friday Cheap Yes
Visit2 Kim’s Lunch Friday Expensive No
Visit3 Sam’s Lunch Saturday Cheap Yes
Visit4 Bob’s Breakfast Sunday Cheap No
Visit5 Sam’s Breakfast Sunday Expensive No
Number Restaurant Meal Day Cost Allergic Reaction?
Visit1 Sam’s Breakfast Friday Cheap Yes
Visit2 Kim’s Lunch Friday Expensive No
Visit3 Sam’s Lunch Saturday Cheap Yes
Visit4 Bob’s Breakfast Sunday Cheap No
Visit5 Sam’s Breakfast Sunday Expensive No
✓Visit1
✓Visit3
× Visit5
Restaurant
Kim’s
Bob’s
Sam’s
× Visit2
× Visit4
Number Restaurant Meal Day Cost Allergic Reaction?
Visit1 Sam’s Breakfast Friday Cheap Yes
Visit2 Kim’s Lunch Friday Expensive No
Visit3 Sam’s Lunch Saturday Cheap Yes
Visit4 Bob’s Breakfast Sunday Cheap No
Visit5 Sam’s Breakfast Sunday Expensive No
Restaurant
Kim’s
Bob’s
Sam’s
× Visit2
× Visit4
✓Visit1
✓Visit3
× Visit5
Cost
Cheap
Expensive
Name Hair Height Age Lotion Burn?
Sarah Blonde Average 20s No Yes
Dana Blonde Tall 30s Yes No
Alex Brown Short 30s Yes No
Annie Blonde Short 30s No Yes
Emily Red Average 40s Yes Yes
Pete Brown Tall 40s No No
John Brown Average 40s No No
Katie Blonde Short 20s Yes No
Josh Red Short 20s No Yes
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