PowerPoint Presentation
Incremental Concept Learning
Learning by Recording Cases
Incremental Concept Learning
Version Spaces
Classification
Learning
Lesson Preview
Purpose of incremental concept learning
Variabilization
Specialization
Generalization
Heuristics for specialization and generalization
This is a foo.
This is not a foo.
This is a foo.
Is this a foo?
ο Yes
ο No
Is this a foo?
ο Yes
ο No
Is this a foo?
ο Yes
ο No
Is this a foo?
ο Yes
ο No
Is this a foo?
ο Yes
ο No
Incremental Concept Learning
Given new example:
Is this an example of the concept?
Does it fit the current definition of the concept?
Does it fit the current definition of the concept?
Do nothing
Generalize
Specialize
Do nothing
Yes
No
Yes
No
Yes
No
An Arch
Brick
A
Brick B
Brick
C
Brick
D
supports
supports
left-of
supports
An Arch
Brick
Brick
Brick
Brick
supports
supports
left-of
supports
Brick
Brick
Brick
supports
supports
left-of
An Arch
Current Concept
An Arch
Brick
Brick
Brick
Brick
supports
supports
left-of
supports
Brick
Brick
Brick
supports
supports
left-of
Current Concept
An Arch
Brick
Brick
Brick
Brick
supports
supports
left-of
supports
Brick
Brick
Brick
supports
supports
left-of
New Concept
Brick
Brick
Brick
supports
supports
left-of
Current Concept
An Arch
Brick
Brick
Brick
Brick
supports
supports
left-of
supports
Brick
Brick
Brick
supports
supports
left-of
“drop-link” heuristic
Brick
Brick
Brick
supports
supports
left-of
New Concept
Brick
Brick
Brick
supports
supports
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
Brick
Brick
Brick
supports
supports
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
Brick
Brick
Brick
supports
supports
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
Brick
Brick
Brick
must-
support
left-of
New Concept
must-
support
Brick
Brick
Brick
supports
supports
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
Brick
Brick
Brick
must-
support
left-of
New Concept
must-
support
“require-link” heuristic
Brick
Brick
Brick
left-of
Not an Arch
touches
touches
supports
supports
Brick
Brick
Brick
left-of
Current Concept
Brick
Brick
Brick
left-of
Not an Arch
touches
touches
supports
supports
must-
support
must-
support
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
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
“forbid-link” heuristic
Wedge
Brick
Brick
left-of
An Arch
supports
supports
Current Concept
An Arch
Brick
Brick
Brick
left-of
¬touches
¬touches
Wedge
Brick
Brick
supports
supports
left-of
must-
support
must-
support
Current Concept
An Arch
Brick
Brick
Brick
left-of
¬touches
¬touches
Wedge
Brick
Brick
supports
supports
left-of
Brick
or
Wedge
Brick
Brick
left-of
¬touches
¬touches
must-
support
must-
support
must-
support
must-
support
New Concept
Current Concept
An Arch
Brick
Brick
Brick
left-of
¬touches
¬touches
Wedge
Brick
Brick
supports
supports
left-of
Brick
or
Wedge
Brick
Brick
left-of
¬touches
¬touches
must-
support
must-
support
must-
support
must-
support
“enlarge-set” heuristic
New Concept
Current Concept
Background Knowledge
Brick
or
Wedge
Brick
Brick
left-of
¬touches
¬touches
Block
Brick
Wedge
is-a
is-a
must-
support
must-
support
Current Concept
Brick
or
Wedge
Brick
Brick
left-of
¬touches
¬touches
Block
Brick
Wedge
is-a
is-a
Block
Brick
Brick
left-of
¬touches
¬touches
must-
support
must-
support
must-
support
must-
support
New Concept
Background Knowledge
Current Concept
Brick
or
Wedge
Brick
Brick
left-of
¬touches
¬touches
Block
Brick
Wedge
is-a
is-a
Block
Brick
Brick
left-of
¬touches
¬touches
must-
support
must-
support
must-
support
must-
support
“climb-tree” heuristic
New Concept
Background Knowledge
Heuristics for Specializing and Generalizing
require-link: link must be present to be a positive example of the concept
forbid-link: link must be absent to be a positive example of the concept
drop-link: link is not necessary to be a positive example of the concept
enlarge-set: multiple objects or links may fit one role in the concept
climb-tree: generalize over multiple objects in the same role based on knowledge
close-interval: expand range of values to be a positive example of the concept
This is a foo.
Current Concept
Variabalize this concept on the right.
Brick
Brick
Brick
Brick
This is a foo.
Variabalize this concept on the right.
Current Concept
Brick
Brick
Brick
Brick
This is a foo.
Write the connections for this concept on the right.
supports
supports
supports
supports
Current Concept
This is not a foo.
Modify the concept on the right to specialize based on this example.
Brick
Brick
Brick
Brick
supports
supports
supports
supports
¬touches
¬touches
Current Concept
Brick
Brick
Brick
Brick
supports
supports
supports
supports
¬touches
¬touches
This is a foo.
Modify the concept on the right to generalize based on this example.
Current Concept
Brick
Brick or Cylinder
Brick or Cylinder
Brick
supports
supports
supports
supports
¬touches
¬touches
This is a foo.
Modify the concept on the right to generalize based on this example.
Current Concept
Background Knowledge
Block
Brick
Cylinder
is-a
is-a
Brick
Brick or Cylinder
Brick or Cylinder
Brick
supports
supports
supports
supports
¬touches
¬touches
Modify the concept on the right to generalize based on this knowledge.
Current Concept
Background Knowledge
Block
Brick
Cylinder
is-a
is-a
Brick
Block
Block
Brick
supports
supports
supports
supports
¬touches
¬touches
Modify the concept on the right to generalize based on this knowledge.
Current Concept
Current Concept
Brick
Block
Block
Brick
supports
supports
supports
supports
¬touches
¬touches
This is not a foo.
Modify the concept on the right to specialize based on this example.
Final Concept
Brick
Block
Block
Brick
supports
supports
supports
supports
¬touches
¬touches
Assignment
How would you use incremental concept learning to design an agent that could answer Raven’s progressive matrices?
To recap…
Purpose of incremental concept learning
Variabilization
Specialization
Generalization
Heuristics for specialization and generalization
/docProps/thumbnail.jpeg