Version spaces
4,341 views
61 slides
May 26, 2008
Slide 1 of 61
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
About This Presentation
No description available for this slideshow.
Slide Content
Machine LearningMachine Learning
Version Spaces LearningVersion Spaces Learning
Version Spaces LearningVersion Spaces Learning
22
Neural Net approaches
Symbolic approaches:
version spaces
decision trees
knowledge discovery
data mining
speed up learning
inductive learning
…
Introduction:Introduction:
Very many approaches to machine learning:
Neural Net approaches
Symbolic approaches:
version spaces
decision trees
knowledge discovery
data mining
speed up learning
inductive learning
…
Introduction:Introduction:
Very many approaches to machine learning:
Version SpacesVersion Spaces
A A concept learningconcept learning technique based on technique based on
refining modelsrefining models of the world. of the world.
A A concept learningconcept learning technique based on technique based on
refining modelsrefining models of the world. of the world.
44
Concept LearningConcept Learning
Example:Example:
a student has the following observations about a student has the following observations about
having an allergic reaction after meals:having an allergic reaction after meals:
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
++
--
++
--
--
Concept to learn: under which circumstances do I
get an allergic reaction after meals ??
Concept LearningConcept Learning
Example:Example:
a student has the following observations about a student has the following observations about
having an allergic reaction after meals:having an allergic reaction after meals:
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
++
--
++
--
--
Concept to learn: under which circumstances do I
get an allergic reaction after meals ??
55
In generalIn general
There is a set of all possible events:There is a set of all possible events:
Example:Example:
RestaurantRestaurantMealMeal DayDay Cost Cost
3 X 3 X 7 X 2 = 1263 X 3 X 7 X 2 = 126
Reaction:Reaction: Restaurant X Meal X Day X Cost Restaurant X Meal X Day X Cost --> Bool--> Bool
There is a boolean function (implicitly) defined on
this set.
Example:
Find an inductive ‘guess’ of the concept, thatFind an inductive ‘guess’ of the concept, that
covers all the examplescovers all the examples!!
We have the value of this function for SOME
examples only.
In generalIn general
There is a set of all possible events:There is a set of all possible events:
Example:Example:
RestaurantRestaurantMealMeal DayDay Cost Cost
3 X 3 X 7 X 2 = 1263 X 3 X 7 X 2 = 126
Reaction:Reaction: Restaurant X Meal X Day X Cost Restaurant X Meal X Day X Cost --> Bool--> Bool
There is a boolean function (implicitly) defined on
this set.
Example:
Find an inductive ‘guess’ of the concept, thatFind an inductive ‘guess’ of the concept, that
covers all the examplescovers all the examples!!
We have the value of this function for SOME
examples only.
66
Pictured:Pictured:
Set of all possibleSet of all possible
eventsevents
Given some Given some
examples:examples:
++
++
++
++
--
--
--
--
Find a concept that covers all the positive Find a concept that covers all the positive
examples and none of the negative ones!examples and none of the negative ones!
Pictured:Pictured:
Set of all possibleSet of all possible
eventsevents
Given some Given some
examples:examples:
++
++
++
++
--
--
--
--
Find a concept that covers all the positive Find a concept that covers all the positive
examples and none of the negative ones!examples and none of the negative ones!
77
Non-determinismNon-determinism
Many different ways to solve this!Many different ways to solve this!
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
How to choose ?
Non-determinismNon-determinism
Many different ways to solve this!Many different ways to solve this!
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
How to choose ?
88
An obvious, but bad choice:An obvious, but bad choice:
The concept IS:The concept IS:
Alma 3Alma 3 andand breakfast breakfast andand Friday Friday andand cheap cheap
OROR
Alma 3 Alma 3 andand lunch lunch andand Saturday Saturday andand cheap cheap
Does NOT generalize the examples any !!
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
--
--
--
++
++
An obvious, but bad choice:An obvious, but bad choice:
The concept IS:The concept IS:
Alma 3Alma 3 andand breakfast breakfast andand Friday Friday andand cheap cheap
OROR
Alma 3 Alma 3 andand lunch lunch andand Saturday Saturday andand cheap cheap
Does NOT generalize the examples any !!
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
--
--
--
++
++
99
Pictured:Pictured:
Only the positive examples are positive !Only the positive examples are positive !
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
Pictured:Pictured:
Only the positive examples are positive !Only the positive examples are positive !
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
1010
Equally bad is:Equally bad is:
The concept is anything EXCEPTThe concept is anything EXCEPT::
De Moete De Moete andand lunch lunch andand Friday Friday and and expensiveexpensive
ANDAND
Sedes Sedes andand breakfast breakfast andand Sunday Sunday andand cheap cheap
ANDAND
Alma 3 Alma 3 andand breakfast breakfast and and Sunday Sunday andand expensive expensive
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
++
--
++
--
--
Equally bad is:Equally bad is:
The concept is anything EXCEPTThe concept is anything EXCEPT::
De Moete De Moete andand lunch lunch andand Friday Friday and and expensiveexpensive
ANDAND
Sedes Sedes andand breakfast breakfast andand Sunday Sunday andand cheap cheap
ANDAND
Alma 3 Alma 3 andand breakfast breakfast and and Sunday Sunday andand expensive expensive
RestaurantRestaurantMealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfastFridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfastSundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfastSundaySunday expensiveexpensive NoNo
++
--
++
--
--
1111
Pictured:Pictured:
Everything except the negative examples are Everything except the negative examples are
positive:positive:
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
Pictured:Pictured:
Everything except the negative examples are Everything except the negative examples are
positive:positive:
Set of all possibleSet of all possible
eventsevents
++
++
++
++
--
--
--
--
1212
Solution: Solution:
fix a language of hypotheses:fix a language of hypotheses:
We introduce a fix language of concept We introduce a fix language of concept
descriptions.descriptions.
= hypothesis space= hypothesis space
The concept can only be identified as being one of
the hypotheses in this language
avoids the problem of having ‘useless’ conclusions
forces some generalization/induction to cover more
than just the given examples.
Solution: Solution:
fix a language of hypotheses:fix a language of hypotheses:
We introduce a fix language of concept We introduce a fix language of concept
descriptions.descriptions.
= hypothesis space= hypothesis space
The concept can only be identified as being one of
the hypotheses in this language
avoids the problem of having ‘useless’ conclusions
forces some generalization/induction to cover more
than just the given examples.
1313
most general hypothesis: [ ?, ?, ?, ?]
Reaction - Example:Reaction - Example:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
Every hypothesis is a 4-tuple:
maximally specific: ex.: [ Sedes, lunch, Monday, cheap]
combinations of ? and values are allowed: ex.:
[ De Moete, ?, ?, expensive]
or [ ?, lunch, ?, ?]
One more hypothesis: (bottom = denotes no example)
most general hypothesis: [ ?, ?, ?, ?]
Reaction - Example:Reaction - Example:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
Every hypothesis is a 4-tuple:
maximally specific: ex.: [ Sedes, lunch, Monday, cheap]
combinations of ? and values are allowed: ex.:
[ De Moete, ?, ?, expensive]
or [ ?, lunch, ?, ?]
One more hypothesis: (bottom = denotes no example)
1414
Hypotheses relate to Hypotheses relate to
sets of possible events sets of possible events
EventsEvents
x2x2
x1x1
x1 = x1 =
< < Alma 3, lunch, Monday, expensive>Alma 3, lunch, Monday, expensive>
x2 =x2 =
< Sedes, lunch, Sunday, cheap>< Sedes, lunch, Sunday, cheap>
h1 h1 = [?, lunch, Monday, ?]= [?, lunch, Monday, ?]
h2 h2 = [?, lunch, ?, cheap]= [?, lunch, ?, cheap]
h3 h3 = [?, lunch, ?, ?]= [?, lunch, ?, ?]
GeneralGeneral
SpecificSpecific
HypothesesHypotheses
h2h2
h3h3
h1h1
Hypotheses relate to Hypotheses relate to
sets of possible events sets of possible events
EventsEvents
x2x2
x1x1
x1 = x1 =
< < Alma 3, lunch, Monday, expensive>Alma 3, lunch, Monday, expensive>
x2 =x2 =
< Sedes, lunch, Sunday, cheap>< Sedes, lunch, Sunday, cheap>
h1 h1 = [?, lunch, Monday, ?]= [?, lunch, Monday, ?]
h2 h2 = [?, lunch, ?, cheap]= [?, lunch, ?, cheap]
h3 h3 = [?, lunch, ?, ?]= [?, lunch, ?, ?]
GeneralGeneral
SpecificSpecific
HypothesesHypotheses
h2h2
h3h3
h1h1
1515
Expressive power of this Expressive power of this
hypothesis language:hypothesis language:
Conjunctions of explicit, individual propertiesConjunctions of explicit, individual properties
Examples:
[?, lunch, Monday, ?] : Meal = lunch Day = Monday
[?, lunch, ?, cheap] : Meal = lunch Cost = cheap
[?, lunch, ?, ?] : Meal = lunch
In addition to the 2 special hypotheses:
[ ?, ?, ?, ?] : anything
: nothing
Expressive power of this Expressive power of this
hypothesis language:hypothesis language:
Conjunctions of explicit, individual propertiesConjunctions of explicit, individual properties
Examples:
[?, lunch, Monday, ?] : Meal = lunch Day = Monday
[?, lunch, ?, cheap] : Meal = lunch Cost = cheap
[?, lunch, ?, ?] : Meal = lunch
In addition to the 2 special hypotheses:
[ ?, ?, ?, ?] : anything
: nothing
1616
Other languages of Other languages of
hypotheses are allowedhypotheses are allowed
Example:Example: identify the color of a given sequence of identify the color of a given sequence of
colored objects.colored objects.
the examples:
redred : : ++
purplepurple : : --
blueblue : : ++
any_colorany_color
mono_colormono_color polyo_colorpolyo_color
redred blue blue greengreen orangeorange purplepurple
A useful language of hypotheses:
Other languages of Other languages of
hypotheses are allowedhypotheses are allowed
Example:Example: identify the color of a given sequence of identify the color of a given sequence of
colored objects.colored objects.
the examples:
redred : : ++
purplepurple : : --
blueblue : : ++
any_colorany_color
mono_colormono_color polyo_colorpolyo_color
redred blue blue greengreen orangeorange purplepurple
A useful language of hypotheses:
1717
Important about hypothesis Important about hypothesis
languages:languages:
They should have a specific <-> general ordering.They should have a specific <-> general ordering.
Corresponding to the set-inclusion of the events Corresponding to the set-inclusion of the events
they cover.they cover.
Important about hypothesis Important about hypothesis
languages:languages:
They should have a specific <-> general ordering.They should have a specific <-> general ordering.
Corresponding to the set-inclusion of the events Corresponding to the set-inclusion of the events
they cover.they cover.
1818
Defining Concept Learning:Defining Concept Learning:
Given:Given:
A set A set XX of possible events : of possible events :
Ex.: Eat-events: <Restaurant, Meal, Day, Cost>Ex.: Eat-events: <Restaurant, Meal, Day, Cost>
An (unknown) target function c: X -> {-, +}
Ex.: Reaction: Eat-events -> { -, +}
A language of hypotheses H
Ex.: conjunctions: [ ?, lunch, Monday, ?]
A set of training examples D, with their value under c
Ex.: (<Alma 3, breakfast,Friday,cheap>,+) , …
Find:
A hypothesis h in H such that for all x in D:
x is covered by h c(x) = +
Defining Concept Learning:Defining Concept Learning:
Given:Given:
A set A set XX of possible events : of possible events :
Ex.: Eat-events: <Restaurant, Meal, Day, Cost>Ex.: Eat-events: <Restaurant, Meal, Day, Cost>
An (unknown) target function c: X -> {-, +}
Ex.: Reaction: Eat-events -> { -, +}
A language of hypotheses H
Ex.: conjunctions: [ ?, lunch, Monday, ?]
A set of training examples D, with their value under c
Ex.: (<Alma 3, breakfast,Friday,cheap>,+) , …
Find:
A hypothesis h in H such that for all x in D:
x is covered by h c(x) = +
1919
The inductive learning The inductive learning
hypothesis:hypothesis:
IfIf a hypothesis approximates the target function a hypothesis approximates the target function
well well over a sufficiently large number of examplesover a sufficiently large number of examples,,
thenthen the hypothesis will also approximate the the hypothesis will also approximate the
target function well target function well on other unobserved exampleson other unobserved examples..
The inductive learning The inductive learning
hypothesis:hypothesis:
IfIf a hypothesis approximates the target function a hypothesis approximates the target function
well well over a sufficiently large number of examplesover a sufficiently large number of examples,,
thenthen the hypothesis will also approximate the the hypothesis will also approximate the
target function well target function well on other unobserved exampleson other unobserved examples..
2020
Find-S:Find-S:
a naïve algorithma naïve algorithm
InitializeInitialize: : h := h :=
ForFor each each positivepositive training example training example xx in in DD Do:Do:
IfIf hh does does notnot cover cover xx::
Replace Replace hh by a minimal generalization by a minimal generalization
of of hh that covers that covers xx
ReturnReturn hh
Find-S:Find-S:
a naïve algorithma naïve algorithm
InitializeInitialize: : h := h :=
ForFor each each positivepositive training example training example xx in in DD Do:Do:
IfIf hh does does notnot cover cover xx::
Replace Replace hh by a minimal generalization by a minimal generalization
of of hh that covers that covers xx
ReturnReturn hh
2121
Initially:Initially: h = h =
Reaction example:Reaction example:
Example 1:Example 1:
h = h = [Alma 3,breakfast,Friday,cheap][Alma 3,breakfast,Friday,cheap]
minimal generalizationsminimal generalizations
= the individual events= the individual events
Example 2:Example 2:
h = h = [Alma 3, [Alma 3, ??, , ??,cheap],cheap]
Generalization =Generalization =
replace something by ?replace something by ?
no more positive examples: return no more positive examples: return hh
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
Initially:Initially: h = h =
Reaction example:Reaction example:
Example 1:Example 1:
h = h = [Alma 3,breakfast,Friday,cheap][Alma 3,breakfast,Friday,cheap]
minimal generalizationsminimal generalizations
= the individual events= the individual events
Example 2:Example 2:
h = h = [Alma 3, [Alma 3, ??, , ??,cheap],cheap]
Generalization =Generalization =
replace something by ?replace something by ?
no more positive examples: return no more positive examples: return hh
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
2222
Properties of Find-SProperties of Find-S
BethBeth JoJo AlexAlex
HackerHacker ScientistScientist FootballplayerFootballplayer
HH
Non-deterministicNon-deterministic::
Depending on H, there maybe several minimal Depending on H, there maybe several minimal
generalizations: generalizations:
Beth can be minimally generalized in 2 ways to includeBeth can be minimally generalized in 2 ways to include
a new example Jo.a new example Jo.
Properties of Find-SProperties of Find-S
BethBeth JoJo AlexAlex
HackerHacker ScientistScientist FootballplayerFootballplayer
HH
Non-deterministicNon-deterministic::
Depending on H, there maybe several minimal Depending on H, there maybe several minimal
generalizations: generalizations:
Beth can be minimally generalized in 2 ways to includeBeth can be minimally generalized in 2 ways to include
a new example Jo.a new example Jo.
2323
Properties of Find-S (2)Properties of Find-S (2)
May pick incorrect hypothesis (w.r.t. the negative May pick incorrect hypothesis (w.r.t. the negative
examples):examples):
D :D :BethBeth
AlexAlex
JoJo
++
--
++
BethBeth JoJo AlexAlex
HackerHacker ScientistScientist FootballplayerFootballplayer
HH
Is a wrong solutionIs a wrong solution
Properties of Find-S (2)Properties of Find-S (2)
May pick incorrect hypothesis (w.r.t. the negative May pick incorrect hypothesis (w.r.t. the negative
examples):examples):
D :D :BethBeth
AlexAlex
JoJo
++
--
++
BethBeth JoJo AlexAlex
HackerHacker ScientistScientist FootballplayerFootballplayer
HH
Is a wrong solutionIs a wrong solution
2424
Properties of Find-S (3)Properties of Find-S (3)
Cannot detect inconsistency of the training data:Cannot detect inconsistency of the training data:
D :D :BethBeth
Jo Jo
BethBeth
++
++
--
D :D :BethBeth
Alex Alex
JoJo
++
--
++ JoJo AlexAlex
ScientistScientist
HH
BethBeth
Nor inability of the language H to learn the concept:
Properties of Find-S (3)Properties of Find-S (3)
Cannot detect inconsistency of the training data:Cannot detect inconsistency of the training data:
D :D :BethBeth
Jo Jo
BethBeth
++
++
--
D :D :BethBeth
Alex Alex
JoJo
++
--
++ JoJo AlexAlex
ScientistScientist
HH
BethBeth
Nor inability of the language H to learn the concept:
2525
Nice about Find-S:Nice about Find-S:
It doesn’t have to remember previous examples ! It doesn’t have to remember previous examples !
If If hh already covered the 20 first examples, already covered the 20 first examples,
then then h’h’ will as well will as well
hh
XX HH
If the previous h already covered all previous
examples, then a minimal generalization h’ will too !
h’h’
Nice about Find-S:Nice about Find-S:
It doesn’t have to remember previous examples ! It doesn’t have to remember previous examples !
If If hh already covered the 20 first examples, already covered the 20 first examples,
then then h’h’ will as well will as well
hh
XX HH
If the previous h already covered all previous
examples, then a minimal generalization h’ will too !
h’h’
2626
Dual Find-S:Dual Find-S:
InitializeInitialize: : h := h := [ ?, ?, .., ?][ ?, ?, .., ?]
ForFor each each negativenegative training example training example xx in in DD Do:Do:
IfIf hh does cover does cover xx::
Replace Replace hh by a minimal specialization by a minimal specialization
of of hh that does that does notnot cover cover xx
ReturnReturn hh
Dual Find-S:Dual Find-S:
InitializeInitialize: : h := h := [ ?, ?, .., ?][ ?, ?, .., ?]
ForFor each each negativenegative training example training example xx in in DD Do:Do:
IfIf hh does cover does cover xx::
Replace Replace hh by a minimal specialization by a minimal specialization
of of hh that does that does notnot cover cover xx
ReturnReturn hh
2727
Reaction example:Reaction example:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
Initially:Initially: h = [ ?, ?, ?, ?]h = [ ?, ?, ?, ?]
Example 1:Example 1:
h= [ ?, breakfast, ?, ?]h= [ ?, breakfast, ?, ?]
Example 2:Example 2:
h= [ Alma 3, breakfast, ?, ?]h= [ Alma 3, breakfast, ?, ?]
Example 3:Example 3:
h= [ Alma 3, breakfast, ?, cheap]h= [ Alma 3, breakfast, ?, cheap]
Reaction example:Reaction example:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
Initially:Initially: h = [ ?, ?, ?, ?]h = [ ?, ?, ?, ?]
Example 1:Example 1:
h= [ ?, breakfast, ?, ?]h= [ ?, breakfast, ?, ?]
Example 2:Example 2:
h= [ Alma 3, breakfast, ?, ?]h= [ Alma 3, breakfast, ?, ?]
Example 3:Example 3:
h= [ Alma 3, breakfast, ?, cheap]h= [ Alma 3, breakfast, ?, cheap]
2828
Perform both Find-S and Dual Find-S:
Find-S deals with positive examples
Dual Find-S deals with negative examples
Version Spaces: the idea: Version Spaces: the idea:
BUT:
do NOT select 1 minimal generalization or
specialization at each step,
but keep track of ALL minimal generalizations
or specializations
Perform both Find-S and Dual Find-S:
Find-S deals with positive examples
Dual Find-S deals with negative examples
Version Spaces: the idea: Version Spaces: the idea:
BUT:
do NOT select 1 minimal generalization or
specialization at each step,
but keep track of ALL minimal generalizations
or specializations
2929
Version spaces:Version spaces:
initializationinitialization
The version spaces The version spaces GG and and SS are initialized to be the are initialized to be the
smallest and the largest hypotheses only.smallest and the largest hypotheses only.
G = { [ ?, ?, …, ?] }G = { [ ?, ?, …, ?] }
S = {S = { } }
Version spaces:Version spaces:
initializationinitialization
The version spaces The version spaces GG and and SS are initialized to be the are initialized to be the
smallest and the largest hypotheses only.smallest and the largest hypotheses only.
G = { [ ?, ?, …, ?] }G = { [ ?, ?, …, ?] }
S = {S = { } }
3030
Negative examples:Negative examples:
Replace the top hypothesis by ALL minimal Replace the top hypothesis by ALL minimal
specializations that specializations that DO NOTDO NOT cover the negative cover the negative
example.example.
InvariantInvariant: only the hypotheses : only the hypotheses more specificmore specific than the than the
ones of ones of GG are still possible: are still possible:
they don’t cover the negative examplethey don’t cover the negative example
S = {S = { } }
G = { [ ?, ?, …, ?] }G = { [ ?, ?, …, ?] }
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
Negative examples:Negative examples:
Replace the top hypothesis by ALL minimal Replace the top hypothesis by ALL minimal
specializations that specializations that DO NOTDO NOT cover the negative cover the negative
example.example.
InvariantInvariant: only the hypotheses : only the hypotheses more specificmore specific than the than the
ones of ones of GG are still possible: are still possible:
they don’t cover the negative examplethey don’t cover the negative example
S = {S = { } }
G = { [ ?, ?, …, ?] }G = { [ ?, ?, …, ?] }
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
3131
Positive examples:Positive examples:
Replace the bottom hypothesis by ALL minimal Replace the bottom hypothesis by ALL minimal
generalizations that generalizations that DODO cover the positive example. cover the positive example.
InvariantInvariant: only the hypotheses : only the hypotheses more generalmore general than the than the
ones of ones of SS are still possible: are still possible:
they do cover the positive examplethey do cover the positive example
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
S = {S = { }}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
Positive examples:Positive examples:
Replace the bottom hypothesis by ALL minimal Replace the bottom hypothesis by ALL minimal
generalizations that generalizations that DODO cover the positive example. cover the positive example.
InvariantInvariant: only the hypotheses : only the hypotheses more generalmore general than the than the
ones of ones of SS are still possible: are still possible:
they do cover the positive examplethey do cover the positive example
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
S = {S = { }}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
3232
Later: negative examplesLater: negative examples
Replace the all hypotheses in Replace the all hypotheses in GG that cover a next that cover a next
negative example by ALL minimal specializations negative example by ALL minimal specializations
that that DO NOTDO NOT cover the negative example. cover the negative example.
InvariantInvariant: only the hypotheses : only the hypotheses more specificmore specific than the than the
ones of ones of GG are still possible: are still possible:
they don’t cover the negative examplethey don’t cover the negative example
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
Later: negative examplesLater: negative examples
Replace the all hypotheses in Replace the all hypotheses in GG that cover a next that cover a next
negative example by ALL minimal specializations negative example by ALL minimal specializations
that that DO NOTDO NOT cover the negative example. cover the negative example.
InvariantInvariant: only the hypotheses : only the hypotheses more specificmore specific than the than the
ones of ones of GG are still possible: are still possible:
they don’t cover the negative examplethey don’t cover the negative example
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
G = {h1, h2, …, hn}G = {h1, h2, …, hn}
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
3333
Later: positive examplesLater: positive examples
Replace the all hypotheses in Replace the all hypotheses in SS that do not cover a that do not cover a
next positive example by ALL minimal next positive example by ALL minimal
generalizations that generalizations that DODO cover the example. cover the example.
InvariantInvariant: only the hypotheses : only the hypotheses more generalmore general than the than the
ones of ones of SS are still possible: are still possible:
they do cover the positive examplethey do cover the positive example
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
S = {S = {h11’, h12’, h13’, h2’, …,hm’ h11’, h12’, h13’, h2’, …,hm’ } }
Later: positive examplesLater: positive examples
Replace the all hypotheses in Replace the all hypotheses in SS that do not cover a that do not cover a
next positive example by ALL minimal next positive example by ALL minimal
generalizations that generalizations that DODO cover the example. cover the example.
InvariantInvariant: only the hypotheses : only the hypotheses more generalmore general than the than the
ones of ones of SS are still possible: are still possible:
they do cover the positive examplethey do cover the positive example
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
S = {S = {h11’, h12’, h13’, h2’, …,hm’ h11’, h12’, h13’, h2’, …,hm’ } }
3434
Optimization: negative:Optimization: negative:
Only consider specializations of elements in Only consider specializations of elements in GG that that
are still more general than some specific hypothesis are still more general than some specific hypothesis
(in (in SS))
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
InvariantInvariant: on : on SS used ! used !
… … are more general than ...are more general than ...
Optimization: negative:Optimization: negative:
Only consider specializations of elements in Only consider specializations of elements in GG that that
are still more general than some specific hypothesis are still more general than some specific hypothesis
(in (in SS))
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h2’, …,hm’ h1’, h2’, …,hm’ } }
InvariantInvariant: on : on SS used ! used !
… … are more general than ...are more general than ...
3535
Optimization: positive:Optimization: positive:
Only consider generalizations of elements in Only consider generalizations of elements in SS that that
are still more specific than some general hypothesis are still more specific than some general hypothesis
(in (in GG))
InvariantInvariant: on : on GG used ! used !
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h13’, h2’, …,hm’ h13’, h2’, …,hm’ } }
… … are more specific than ...are more specific than ...
Optimization: positive:Optimization: positive:
Only consider generalizations of elements in Only consider generalizations of elements in SS that that
are still more specific than some general hypothesis are still more specific than some general hypothesis
(in (in GG))
InvariantInvariant: on : on GG used ! used !
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h13’, h2’, …,hm’ h13’, h2’, …,hm’ } }
… … are more specific than ...are more specific than ...
3636
Pruning: negative examples Pruning: negative examples
The new negative example can also be used to prune The new negative example can also be used to prune
all the all the SS - hypotheses that cover the negative - hypotheses that cover the negative
example.example.
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
InvariantInvariant only works for the previous examples, not the last one only works for the previous examples, not the last one
Cover the last negative example!Cover the last negative example!
Pruning: negative examples Pruning: negative examples
The new negative example can also be used to prune The new negative example can also be used to prune
all the all the SS - hypotheses that cover the negative - hypotheses that cover the negative
example.example.
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
InvariantInvariant only works for the previous examples, not the last one only works for the previous examples, not the last one
Cover the last negative example!Cover the last negative example!
3737
Pruning: positive examples Pruning: positive examples
The new positive example can also be used to prune The new positive example can also be used to prune
all the all the GG - hypotheses that do not cover the - hypotheses that do not cover the
positive example.positive example.
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
Don’t cover the last positive exampleDon’t cover the last positive example
Pruning: positive examples Pruning: positive examples
The new positive example can also be used to prune The new positive example can also be used to prune
all the all the GG - hypotheses that do not cover the - hypotheses that do not cover the
positive example.positive example.
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
Don’t cover the last positive exampleDon’t cover the last positive example
3838
Eliminate redundant Eliminate redundant
hypotheseshypotheses
If a hypothesis from If a hypothesis from GG is more specific than is more specific than
another hypothesis from another hypothesis from GG: eliminate it !: eliminate it !
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
More specific than another general hypothesisMore specific than another general hypothesis
Reason:Reason: Invariant acts as a wave frontInvariant acts as a wave front: anything above : anything above GG is not is not
allowed. The most general elements of allowed. The most general elements of GG define the real boundary define the real boundary
Obviously also for Obviously also for SS ! !
Eliminate redundant Eliminate redundant
hypotheseshypotheses
If a hypothesis from If a hypothesis from GG is more specific than is more specific than
another hypothesis from another hypothesis from GG: eliminate it !: eliminate it !
G = {h1, h21, …, hn}G = {h1, h21, …, hn}
S = {S = {h1’, h3’, …,hm’ h1’, h3’, …,hm’ } }
More specific than another general hypothesisMore specific than another general hypothesis
Reason:Reason: Invariant acts as a wave frontInvariant acts as a wave front: anything above : anything above GG is not is not
allowed. The most general elements of allowed. The most general elements of GG define the real boundary define the real boundary
Obviously also for Obviously also for SS ! !
3939
Convergence:Convergence:
Eventually, if Eventually, if GG and and SS MAY get a common element: MAY get a common element:
Version Spaces has Version Spaces has converged to a solutionconverged to a solution..
Remaining examples need to be verified for the Remaining examples need to be verified for the
solutionsolution..
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h13’, h2’, …,hm’ h13’, h2’, …,hm’ } }
Convergence:Convergence:
Eventually, if Eventually, if GG and and SS MAY get a common element: MAY get a common element:
Version Spaces has Version Spaces has converged to a solutionconverged to a solution..
Remaining examples need to be verified for the Remaining examples need to be verified for the
solutionsolution..
G = {h1, h21, h22, …, hn}G = {h1, h21, h22, …, hn}
S = {S = {h13’, h2’, …,hm’ h13’, h2’, …,hm’ } }
4040
Reaction exampleReaction example
Initialization:Initialization:
[ ?, ?, ?, ?][ ?, ?, ?, ?]
MostMost
generalgeneral
MostMost
specificspecific
Reaction exampleReaction example
Initialization:Initialization:
[ ?, ?, ?, ?][ ?, ?, ?, ?]
MostMost
generalgeneral
MostMost
specificspecific
4141
Alma3, breakfast, Friday, cheap: +Alma3, breakfast, Friday, cheap: +
Positive example: minimal generalization ofPositive example: minimal generalization of
[ ?, ?, ?, ?][ ?, ?, ?, ?]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
Alma3, breakfast, Friday, cheap: +Alma3, breakfast, Friday, cheap: +
Positive example: minimal generalization ofPositive example: minimal generalization of
[ ?, ?, ?, ?][ ?, ?, ?, ?]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
4242
DeMoete, lunch, Friday, expensive: -DeMoete, lunch, Friday, expensive: -
Negative example: minimal specialization of Negative example: minimal specialization of [ ?, ?, ?, ?][ ?, ?, ?, ?]
15 possible specializations !! 15 possible specializations !!
[[Alma3Alma3, ?, ?, ?], ?, ?, ?]
[[DeMoeteDeMoete, ?, ?, ?] , ?, ?, ?]
[[SedesSedes, ?, ?, ?], ?, ?, ?]
[?, [?, breakfastbreakfast, ?, ?], ?, ?]
[?, [?, lunchlunch, ?, ?], ?, ?]
[?, [?, dinnerdinner, ?, ?], ?, ?]
[?, ?, [?, ?, MondayMonday, ?], ?]
[?, ?, [?, ?, TuesdayTuesday, ?], ?]
[?, ?, [?, ?, WednesdayWednesday, ?], ?]
[?, ?, [?, ?, ThursdayThursday, ?], ?]
[?, ?, [?, ?, FridayFriday, ?], ?]
[?, ?, [?, ?, SaturdaySaturday, ?], ?]
[?, ?, [?, ?, SundaySunday, ?], ?]
[?, ?, ?, [?, ?, ?, cheapcheap]]
[?, ?, ?, [?, ?, ?, expensiveexpensive]]
Matches the negative exampleMatches the negative exampleXX
XX
XX
XX
Does not generalize the specific modelDoes not generalize the specific model
Specific model:Specific model:
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
XX
XX
XX
XX
XX
XX
XX
XX
Remain !Remain !
DeMoete, lunch, Friday, expensive: -DeMoete, lunch, Friday, expensive: -
Negative example: minimal specialization of Negative example: minimal specialization of [ ?, ?, ?, ?][ ?, ?, ?, ?]
15 possible specializations !! 15 possible specializations !!
[[Alma3Alma3, ?, ?, ?], ?, ?, ?]
[[DeMoeteDeMoete, ?, ?, ?] , ?, ?, ?]
[[SedesSedes, ?, ?, ?], ?, ?, ?]
[?, [?, breakfastbreakfast, ?, ?], ?, ?]
[?, [?, lunchlunch, ?, ?], ?, ?]
[?, [?, dinnerdinner, ?, ?], ?, ?]
[?, ?, [?, ?, MondayMonday, ?], ?]
[?, ?, [?, ?, TuesdayTuesday, ?], ?]
[?, ?, [?, ?, WednesdayWednesday, ?], ?]
[?, ?, [?, ?, ThursdayThursday, ?], ?]
[?, ?, [?, ?, FridayFriday, ?], ?]
[?, ?, [?, ?, SaturdaySaturday, ?], ?]
[?, ?, [?, ?, SundaySunday, ?], ?]
[?, ?, ?, [?, ?, ?, cheapcheap]]
[?, ?, ?, [?, ?, ?, expensiveexpensive]]
Matches the negative exampleMatches the negative exampleXX
XX
XX
XX
Does not generalize the specific modelDoes not generalize the specific model
Specific model:Specific model:
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
XX
XX
XX
XX
XX
XX
XX
XX
Remain !Remain !
4343
Result after example 2:Result after example 2:
[ ?, ?, ?, ?][ ?, ?, ?, ?]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
[[Alma3Alma3, ?, ?, ?], ?, ?, ?][?, [?, breakfastbreakfast, ?, ?], ?, ?][?, ?, ?, [?, ?, ?, cheapcheap]]
Result after example 2:Result after example 2:
[ ?, ?, ?, ?][ ?, ?, ?, ?]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
[[Alma3Alma3, ?, ?, ?], ?, ?, ?][?, [?, breakfastbreakfast, ?, ?], ?, ?][?, ?, ?, [?, ?, ?, cheapcheap]]
4444
Alma3, lunch, Saturday, cheap: +Alma3, lunch, Saturday, cheap: +
Positive example: minimal generalization of Positive example: minimal generalization of [Alma3, [Alma3,
breakfast, Friday, cheap]breakfast, Friday, cheap]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
[Alma3, ?, ?, ?][Alma3, ?, ?, ?][?, breakfast, ?, ?][?, breakfast, ?, ?][?, ?, ?, cheap][?, ?, ?, cheap]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
does not match new exampledoes not match new example
Alma3, lunch, Saturday, cheap: +Alma3, lunch, Saturday, cheap: +
Positive example: minimal generalization of Positive example: minimal generalization of [Alma3, [Alma3,
breakfast, Friday, cheap]breakfast, Friday, cheap]
[Alma3, breakfast, Friday, cheap][Alma3, breakfast, Friday, cheap]
[Alma3, ?, ?, ?][Alma3, ?, ?, ?][?, breakfast, ?, ?][?, breakfast, ?, ?][?, ?, ?, cheap][?, ?, ?, cheap]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
does not match new exampledoes not match new example
4545
Sedes, breakfast, Sunday, cheap: -Sedes, breakfast, Sunday, cheap: -
Negative example: minimal specialization of the Negative example: minimal specialization of the
general models:general models:
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, ?, cheap][?, ?, ?, cheap]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
[[Alma3Alma3, ?, ?, cheap], ?, ?, cheap]
The only specializationThe only specialization
that is introduced is that is introduced is
pruned, because it ispruned, because it is
more specific than more specific than
another general hypothesisanother general hypothesis
Sedes, breakfast, Sunday, cheap: -Sedes, breakfast, Sunday, cheap: -
Negative example: minimal specialization of the Negative example: minimal specialization of the
general models:general models:
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, ?, cheap][?, ?, ?, cheap]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
[[Alma3Alma3, ?, ?, cheap], ?, ?, cheap]
The only specializationThe only specialization
that is introduced is that is introduced is
pruned, because it ispruned, because it is
more specific than more specific than
another general hypothesisanother general hypothesis
4646
Alma 3, breakfast, Sunday, expensive: -Alma 3, breakfast, Sunday, expensive: -
Negative example: minimal specialization of Negative example: minimal specialization of
[Alma3, ?, ?, ?][Alma3, ?, ?, ?]
[Alma3, ?, ?, ?][Alma3, ?, ?, ?]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
[Alma3, ?, ?, [Alma3, ?, ?, cheapcheap]]
Same hypothesis !!!Same hypothesis !!!
Cheap food at Alma3Cheap food at Alma3
produces the allergy !produces the allergy !
Alma 3, breakfast, Sunday, expensive: -Alma 3, breakfast, Sunday, expensive: -
Negative example: minimal specialization of Negative example: minimal specialization of
[Alma3, ?, ?, ?][Alma3, ?, ?, ?]
[Alma3, ?, ?, ?][Alma3, ?, ?, ?]
[Alma3, ? , ? , cheap][Alma3, ? , ? , cheap]
[Alma3, ?, ?, [Alma3, ?, ?, cheapcheap]]
Same hypothesis !!!Same hypothesis !!!
Cheap food at Alma3Cheap food at Alma3
produces the allergy !produces the allergy !
4747
Version Space Algorithm:Version Space Algorithm:
InitiallyInitially: : G := { the hypothesis that covers everything}G := { the hypothesis that covers everything}
S := {S := {}}
For each new For each new positivepositive example: example:
GeneralizeGeneralize all hypotheses in all hypotheses in SS that do not cover the that do not cover the
example yet, but ensure the following:example yet, but ensure the following:
- Only introduce - Only introduce minimal changesminimal changes on the hypotheses. on the hypotheses.
- - EachEach new specific hypothesis is a new specific hypothesis is a specialization ofspecialization of
some general hypothesissome general hypothesis..
- - NoNo new specific hypothesis is a new specific hypothesis is a generalization ofgeneralization of
some other specific hypothesissome other specific hypothesis..
Prune awayPrune away all hypotheses in all hypotheses in GG that do not cover the that do not cover the
example.example.
Version Space Algorithm:Version Space Algorithm:
InitiallyInitially: : G := { the hypothesis that covers everything}G := { the hypothesis that covers everything}
S := {S := {}}
For each new For each new positivepositive example: example:
GeneralizeGeneralize all hypotheses in all hypotheses in SS that do not cover the that do not cover the
example yet, but ensure the following:example yet, but ensure the following:
- Only introduce - Only introduce minimal changesminimal changes on the hypotheses. on the hypotheses.
- - EachEach new specific hypothesis is a new specific hypothesis is a specialization ofspecialization of
some general hypothesissome general hypothesis..
- - NoNo new specific hypothesis is a new specific hypothesis is a generalization ofgeneralization of
some other specific hypothesissome other specific hypothesis..
Prune awayPrune away all hypotheses in all hypotheses in GG that do not cover the that do not cover the
example.example.
4848
Version Space Algorithm (2):Version Space Algorithm (2):
..
..
..
For each new For each new negativenegative example: example:
SpecializeSpecialize all hypotheses in all hypotheses in GG that cover the example, that cover the example,
but ensure the following:but ensure the following:
- Only introduce - Only introduce minimal changesminimal changes on the hypotheses. on the hypotheses.
- - EachEach new general hypothesis is a new general hypothesis is a generalization ofgeneralization of
some specific hypothesissome specific hypothesis..
- - NoNo new general hypothesis is a new general hypothesis is a specialization ofspecialization of
some other general hypothesissome other general hypothesis..
Prune awayPrune away all hypotheses in all hypotheses in SS that cover the example. that cover the example.
Until there are no more examples:Until there are no more examples: report report SS and and GG
OR OR SS or or GG become empty become empty: report failure: report failure
Version Space Algorithm (2):Version Space Algorithm (2):
..
..
..
For each new For each new negativenegative example: example:
SpecializeSpecialize all hypotheses in all hypotheses in GG that cover the example, that cover the example,
but ensure the following:but ensure the following:
- Only introduce - Only introduce minimal changesminimal changes on the hypotheses. on the hypotheses.
- - EachEach new general hypothesis is a new general hypothesis is a generalization ofgeneralization of
some specific hypothesissome specific hypothesis..
- - NoNo new general hypothesis is a new general hypothesis is a specialization ofspecialization of
some other general hypothesissome other general hypothesis..
Prune awayPrune away all hypotheses in all hypotheses in SS that cover the example. that cover the example.
Until there are no more examples:Until there are no more examples: report report SS and and GG
OR OR SS or or GG become empty become empty: report failure: report failure
4949
Properties of VS:Properties of VS:
Symmetry:Symmetry:
positive and negative examples are dealt with in a positive and negative examples are dealt with in a
completely dualcompletely dual way. way.
Does not need to remember previous examples.
Noise:
VS cannot deal with noise !
If a positive example is given to be negative
then VS eliminates the desired hypothesis
from the Version Space G !
Properties of VS:Properties of VS:
Symmetry:Symmetry:
positive and negative examples are dealt with in a positive and negative examples are dealt with in a
completely dualcompletely dual way. way.
Does not need to remember previous examples.
Noise:
VS cannot deal with noise !
If a positive example is given to be negative
then VS eliminates the desired hypothesis
from the Version Space G !
5050
Termination:Termination:
If it terminates because of “no more examples”:If it terminates because of “no more examples”:
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
Then Then all these hypothesesall these hypotheses, and , and all intermediate hypothesesall intermediate hypotheses,,
are still correct descriptions covering the test data.are still correct descriptions covering the test data.
VS makes NO unnecessary choices !VS makes NO unnecessary choices !
Example (spaces on termination):
Termination:Termination:
If it terminates because of “no more examples”:If it terminates because of “no more examples”:
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
Then Then all these hypothesesall these hypotheses, and , and all intermediate hypothesesall intermediate hypotheses,,
are still correct descriptions covering the test data.are still correct descriptions covering the test data.
VS makes NO unnecessary choices !VS makes NO unnecessary choices !
Example (spaces on termination):
5151
Termination (2):Termination (2):
If it terminates because of If it terminates because of SS or or GG being empty: being empty:
Then either:
The data is inconsistent (noise?)
The target concept cannot be represented in the
hypothesis-language H.
[Alma3, breakfast, ?, cheap] [Alma3, breakfast, ?, cheap] [Alma3, lunch, ?, cheap] [Alma3, lunch, ?, cheap]
<Alma3, dinner, Sunday, cheap> <Alma3, dinner, Sunday, cheap> --
<Alma3, breakfast, Sunday, cheap> <Alma3, breakfast, Sunday, cheap> ++
<Alma3, lunch, Sunday, cheap> <Alma3, lunch, Sunday, cheap> ++
Example:
target concept is:
given examples like:
this cannot be learned in our language H.
Termination (2):Termination (2):
If it terminates because of If it terminates because of SS or or GG being empty: being empty:
Then either:
The data is inconsistent (noise?)
The target concept cannot be represented in the
hypothesis-language H.
[Alma3, breakfast, ?, cheap] [Alma3, breakfast, ?, cheap] [Alma3, lunch, ?, cheap] [Alma3, lunch, ?, cheap]
<Alma3, dinner, Sunday, cheap> <Alma3, dinner, Sunday, cheap> --
<Alma3, breakfast, Sunday, cheap> <Alma3, breakfast, Sunday, cheap> ++
<Alma3, lunch, Sunday, cheap> <Alma3, lunch, Sunday, cheap> ++
Example:
target concept is:
given examples like:
this cannot be learned in our language H.
5252
Which example next?Which example next?
VS can decide itself which example would be most VS can decide itself which example would be most
useful next.useful next.
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
It can ‘query’ a user for the most relevant additional
classification !
Example:
<Alma3,lunch,Monday,<Alma3,lunch,Monday,expensiveexpensive>>
classified negative by 3 hypothesesclassified negative by 3 hypotheses
classified positive by 3 hypothesesclassified positive by 3 hypotheses
is the most informative new exampleis the most informative new example
Which example next?Which example next?
VS can decide itself which example would be most VS can decide itself which example would be most
useful next.useful next.
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
It can ‘query’ a user for the most relevant additional
classification !
Example:
<Alma3,lunch,Monday,<Alma3,lunch,Monday,expensiveexpensive>>
classified negative by 3 hypothesesclassified negative by 3 hypotheses
classified positive by 3 hypothesesclassified positive by 3 hypotheses
is the most informative new exampleis the most informative new example
5353
Use of partially learned Use of partially learned
concepts:concepts:
Example:Example: <Alma3,lunch,Monday,cheap><Alma3,lunch,Monday,cheap>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can be classified as positive
is covered by all remaining hypotheses !
it is enough to check that it is covered by the
hypotheses in S ! (all others generalize these)
Use of partially learned Use of partially learned
concepts:concepts:
Example:Example: <Alma3,lunch,Monday,cheap><Alma3,lunch,Monday,cheap>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can be classified as positive
is covered by all remaining hypotheses !
it is enough to check that it is covered by the
hypotheses in S ! (all others generalize these)
5454
Use of partially learned Use of partially learned
concepts (2):concepts (2):
Example:Example: <Sedes,lunch,Sunday,cheap><Sedes,lunch,Sunday,cheap>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can be classified as negative
is not covered by any remaining hypothesis !
it is enough to check that it is not covered by any
hypothesis in G ! (all others specialize these)
Use of partially learned Use of partially learned
concepts (2):concepts (2):
Example:Example: <Sedes,lunch,Sunday,cheap><Sedes,lunch,Sunday,cheap>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can be classified as negative
is not covered by any remaining hypothesis !
it is enough to check that it is not covered by any
hypothesis in G ! (all others specialize these)
5555
Use of partially learned Use of partially learned
concepts (3):concepts (3):
Example:Example: <Alma3,lunch,Monday,expensive><Alma3,lunch,Monday,expensive>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can not be classified
is covered by 3, not covered 3 hypotheses
no conclusionno conclusion
Use of partially learned Use of partially learned
concepts (3):concepts (3):
Example:Example: <Alma3,lunch,Monday,expensive><Alma3,lunch,Monday,expensive>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
can not be classified
is covered by 3, not covered 3 hypotheses
no conclusionno conclusion
5656
Use of partially learned Use of partially learned
concepts (4):concepts (4):
Example:Example: <Sedes,lunch,Monday,expensive><Sedes,lunch,Monday,expensive>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
probably does not belong to the concept : ratio : 1/6probably does not belong to the concept : ratio : 1/6
can only be classified with a certain degree of
precision
is covered by 1, not covered 5 hypotheses
Use of partially learned Use of partially learned
concepts (4):concepts (4):
Example:Example: <Sedes,lunch,Monday,expensive><Sedes,lunch,Monday,expensive>
[Alma3, ?, ?, ?][Alma3, ?, ?, ?] [?, ?, Monday,?][?, ?, Monday,?]
[Alma3, ?, Monday, cheap][Alma3, ?, Monday, cheap]
[Alma3, ?, ?, cheap][Alma3, ?, ?, cheap] [?, ?, Monday, cheap][?, ?, Monday, cheap][Alma3, ?, Monday, ?][Alma3, ?, Monday, ?]
probably does not belong to the concept : ratio : 1/6probably does not belong to the concept : ratio : 1/6
can only be classified with a certain degree of
precision
is covered by 1, not covered 5 hypotheses
5757
The relevance of inductive The relevance of inductive
BIAS: choosing HBIAS: choosing H
Our hypothesis language L fails to learn some Our hypothesis language L fails to learn some
concepts.concepts.
See example :
[Alma3, breakfast, ?, cheap] [Alma3, lunch, ?, cheap]
What about choosing a more expressive language H?
Assume H’:
allows conjunctions (as before)
allows disjunction and negation too !
Example:
–Restaurant = Alma3 ~(Day = Monday)
The relevance of inductive The relevance of inductive
BIAS: choosing HBIAS: choosing H
Our hypothesis language L fails to learn some Our hypothesis language L fails to learn some
concepts.concepts.
See example :
[Alma3, breakfast, ?, cheap] [Alma3, lunch, ?, cheap]
What about choosing a more expressive language H?
Assume H’:
allows conjunctions (as before)
allows disjunction and negation too !
Example:
–Restaurant = Alma3 ~(Day = Monday)
5858
Inductive BIAS (2):Inductive BIAS (2):
This language H’ allows to represent ANY subset of This language H’ allows to represent ANY subset of
the complete set of all events Xthe complete set of all events X
RestaurantRestaurantMealMeal DayDay Cost Cost
3 X 3 X 7 X 2 = 1263 X 3 X 7 X 2 = 126
But X has 126 elements
we can express 2
126
different hypotheses now !
Inductive BIAS (2):Inductive BIAS (2):
This language H’ allows to represent ANY subset of This language H’ allows to represent ANY subset of
the complete set of all events Xthe complete set of all events X
RestaurantRestaurantMealMeal DayDay Cost Cost
3 X 3 X 7 X 2 = 1263 X 3 X 7 X 2 = 126
But X has 126 elements
we can express 2
126
different hypotheses now !
5959
Inductive BIAS (3)Inductive BIAS (3)
Version Spaces using H’:Version Spaces using H’:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
??
{~[DeMoete. Lunch, Friday, expensive] {~[DeMoete. Lunch, Friday, expensive] ~[Sedes, breakfast, Sunday, cheap]} ~[Sedes, breakfast, Sunday, cheap]}
{~[DeMoete. Lunch, Friday, expensive] {~[DeMoete. Lunch, Friday, expensive] ~[Sedes, breakfast, Sunday, cheap] ~[Sedes, breakfast, Sunday, cheap]
~[Alma 3, breakfast, Sunday, expensive]}~[Alma 3, breakfast, Sunday, expensive]}
{~[DeMoete. Lunch, Friday, expensive]}{~[DeMoete. Lunch, Friday, expensive]}
{[Alma 3, breakfast, Friday, cheap]{[Alma 3, breakfast, Friday, cheap] [Alma 3, lunch, Saturday, cheap]} [Alma 3, lunch, Saturday, cheap]}
{[Alma 3, breakfast, Friday, cheap]}{[Alma 3, breakfast, Friday, cheap]}
Inductive BIAS (3)Inductive BIAS (3)
Version Spaces using H’:Version Spaces using H’:
RestaurantRestaurant MealMeal DayDay Cost Cost Reaction Reaction
Alma 3Alma 3 breakfastbreakfast FridayFriday cheapcheap YesYes
De MoeteDe Moete lunchlunch FridayFriday expensiveexpensive NoNo
Alma 3Alma 3 lunchlunch SaturdaySaturday cheapcheap YesYes
SedesSedes breakfastbreakfast SundaySunday cheapcheap NoNo
Alma 3Alma 3 breakfastbreakfast SundaySunday expensiveexpensive NoNo
++
--
++
--
--
??
{~[DeMoete. Lunch, Friday, expensive] {~[DeMoete. Lunch, Friday, expensive] ~[Sedes, breakfast, Sunday, cheap]} ~[Sedes, breakfast, Sunday, cheap]}
{~[DeMoete. Lunch, Friday, expensive] {~[DeMoete. Lunch, Friday, expensive] ~[Sedes, breakfast, Sunday, cheap] ~[Sedes, breakfast, Sunday, cheap]
~[Alma 3, breakfast, Sunday, expensive]}~[Alma 3, breakfast, Sunday, expensive]}
{~[DeMoete. Lunch, Friday, expensive]}{~[DeMoete. Lunch, Friday, expensive]}
{[Alma 3, breakfast, Friday, cheap]{[Alma 3, breakfast, Friday, cheap] [Alma 3, lunch, Saturday, cheap]} [Alma 3, lunch, Saturday, cheap]}
{[Alma 3, breakfast, Friday, cheap]}{[Alma 3, breakfast, Friday, cheap]}
6060
Inductive BIAS (3)Inductive BIAS (3)
Resulting Version Spaces:Resulting Version Spaces:
G = {~[DeMoete. Lunch, Friday, expensive] G = {~[DeMoete. Lunch, Friday, expensive]
~[Sedes, breakfast, Sunday, cheap]~[Sedes, breakfast, Sunday, cheap]
~[Alma 3, breakfast, Sunday, expensive]}~[Alma 3, breakfast, Sunday, expensive]}
S = {[Alma 3, breakfast, Friday, cheap]S = {[Alma 3, breakfast, Friday, cheap]
[Alma 3, lunch, Saturday, cheap]}[Alma 3, lunch, Saturday, cheap]}
We haven’t learned anything
merely restated our positive and negative examples !
In general: in order to be able to learn, we need an
inductive BIAS (= assumption):
Example: “ The desired concept CAN be described
as a conjunction of features “
Inductive BIAS (3)Inductive BIAS (3)
Resulting Version Spaces:Resulting Version Spaces:
G = {~[DeMoete. Lunch, Friday, expensive] G = {~[DeMoete. Lunch, Friday, expensive]
~[Sedes, breakfast, Sunday, cheap]~[Sedes, breakfast, Sunday, cheap]
~[Alma 3, breakfast, Sunday, expensive]}~[Alma 3, breakfast, Sunday, expensive]}
S = {[Alma 3, breakfast, Friday, cheap]S = {[Alma 3, breakfast, Friday, cheap]
[Alma 3, lunch, Saturday, cheap]}[Alma 3, lunch, Saturday, cheap]}
We haven’t learned anything
merely restated our positive and negative examples !
In general: in order to be able to learn, we need an
inductive BIAS (= assumption):
Example: “ The desired concept CAN be described
as a conjunction of features “
6161
Shift of BiasShift of Bias
Practical approach to the Bias problem: Practical approach to the Bias problem:
Start VS with a very weak hypothesis language.
If the concept is learned: o.k.
Else
Refine your language and restart VS
Avoids the choice.
Gives the most general concept that can be learned.
Shift of BiasShift of Bias
Practical approach to the Bias problem: Practical approach to the Bias problem:
Start VS with a very weak hypothesis language.
If the concept is learned: o.k.
Else
Refine your language and restart VS
Avoids the choice.
Gives the most general concept that can be learned.
Tags
Categories
GeneralDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 4,341
- Slides 61
- Age 6400 days
Related Slideshows
22
Pray For The Peace Of Jerusalem and You Will Prosper
RodolfoMoralesMarcuc
32 views
26
Don_t_Waste_Your_Life_God.....powerpoint
chalobrido8
34 views
31
VILLASUR_FACTORS_TO_CONSIDER_IN_PLATING_SALAD_10-13.pdf
JaiJai148317
31 views
14
Fertility awareness methods for women in the society
Isaiah47
30 views
35
Chapter 5 Arithmetic Functions Computer Organisation and Architecture
RitikSharma297999
28 views
5
syakira bhasa inggris (1) (1).pptx.......
ourcommunity56
30 views