Concept Learning and Version Spaces in Machine Learning
undefined
M
A
C
H
I
N
E
L
E
A
R
N
I
N
G
L
E
C
T
U
R
E
2
C
O
N
C
E
P
T
L
E
A
R
N
I
N
G
A
N
D
V
E
R
S
I
O
N
S
P
A
C
E
S
B
a
s
e
d
o
n
C
h
a
p
t
e
r
2
o
f
M
i
t
c
h
e
l
l
’
s
b
o
o
k
1
OUTLINE
•
C
o
n
c
e
p
t
L
e
a
r
n
i
n
g
f
r
o
m
e
x
a
m
p
l
e
s
•
H
y
p
o
t
h
e
s
i
s
r
e
p
r
e
s
e
n
t
a
t
i
o
n
•
G
e
n
e
r
a
l
-
t
o
s
p
e
c
i
f
i
c
o
r
d
e
r
i
n
g
o
f
h
y
p
o
t
h
e
s
e
s
•
t
h
e
F
i
n
d
-
S
a
l
g
o
r
i
t
h
m
2
WHAT IS A CONCEPT?
3
•
Assume a given domain, e.g. objects, animals, etc.
•
A
C
o
n
c
e
p
t
i
s
a
s
u
b
s
e
t
o
f
t
h
e
d
o
m
a
i
n
,
e
.
g
.
b
i
r
d
s
⊆
a
n
i
m
a
l
s
•
Generally we can’t look at all objects in the domain
WHAT IS A CONCEPT?
4
•
A
C
o
n
c
e
p
t
c
o
u
l
d
b
e
d
e
f
i
n
e
d
a
s
a
B
o
o
l
e
a
n
-
v
a
l
u
e
d
f
u
n
c
t
i
o
n
C
d
e
f
i
n
e
d
o
v
e
r
t
h
e
l
a
r
g
e
r
s
e
t
•
E
x
a
m
p
l
e
:
a
f
u
n
c
t
i
o
n
d
e
f
i
n
e
d
o
v
e
r
a
l
l
a
n
i
m
a
l
s
w
h
o
s
e
v
a
l
u
e
i
s
t
r
u
e
f
o
r
b
i
r
d
s
a
n
d
f
a
l
s
e
f
o
r
e
v
e
r
y
o
t
h
e
r
a
n
i
m
a
l
.
•
c(bird) = true
•
c(cat) = false
•
c(car) = false
•
c(pigeon) = true
WHAT IS CONCEPT LEARNING?
5
•
G
i
v
e
n
a
s
e
t
o
f
e
x
a
m
p
l
e
s
l
a
b
e
l
e
d
a
s
m
e
m
b
e
r
s
(
p
o
s
i
t
i
v
e
)
o
r
n
o
n
-
m
e
m
b
e
r
s
(
n
e
g
a
t
i
v
e
)
o
f
a
c
o
n
c
e
p
t
:
•
Infer
the general definition of this concept
•
Approximate
c
from
training examples:
•
Infer the
best
concept-description from the set of all
possible hypotheses
EXAMPLE OF A CONCEPT
LEARNING TASK
•
C
o
n
c
e
p
t
:
G
o
o
d
d
a
y
s
o
n
w
h
i
c
h
m
y
f
r
i
e
n
d
e
n
j
o
y
s
w
a
t
e
r
s
p
o
r
t
(values: Yes, No)
•
T
a
s
k
:
p
r
e
d
i
c
t
t
h
e
v
a
l
u
e
o
f
”
E
n
j
o
y
S
p
o
r
t
”
f
o
r
a
n
a
r
b
i
t
r
a
r
y
d
a
y
b
a
s
e
d
o
n
t
h
e
v
a
l
u
e
s
o
f
t
h
e
o
t
h
e
r
a
t
t
r
i
b
u
t
e
s
•
R
e
s
u
l
t
:
c
l
a
s
s
i
f
i
e
r
f
o
r
d
a
y
s
6
REPRESENTING HYPOTHESES
•
Many possible hypothesis (h) representations
•
The simplest h could be represented as a conjunction of
constraints over the instance attributes
•
Each constraint can be:
•
a specific value (e.g., Water = Warm)
•
?: don’t care/any value (e.g., Water=?)
•
no value allowed (e.g., Water=Ø)
•
E
x
a
m
p
l
e
:
h
y
p
o
t
h
e
s
i
s
h
S
k
y
T
e
m
p
H
u
m
i
d
W
i
n
d
W
a
t
e
r
F
o
r
e
c
a
s
t
< Sunny ? ? Strong ? Same >
•
We say h(x)=1 for a day x, if x satisfies the description
7
MOST
GENERAL/SPECIFIC
HYPOTHESIS
every day is a positive example
No day is a positive example
8
PROTOTYPICAL CONCEPT LEARNING TASK
•
G
I
V
E
N
:
•
Instances X: Possible days, each described by the attributes
sky, AirTemp, Humidity, Wind, Water, Forecast
•
Target function c: EnjoySport: X
{0,1}•
Hypotheses H: Conjunctions of constraints on attributes
<?, Cold, High, ?, ?, ?>
•
Training examples D: positive and negative examples of the target
function
<x1,c(x1)>,<x2,c(x2)>,
…,
<xn, c(xn)>
•
D
E
T
E
R
M
I
N
E
:
•
A
h
y
p
o
t
h
e
s
i
s
h
i
n
H
w
i
t
h
h
(
x
)
=
c
(
x
)
f
o
r
a
l
l
x
i
n
D
9
THE INDUCTIVE LEARNING
HYPOTHESIS
•
Any hypothesis found to approximate the target
function well over the training examples, will also
approximate the target function well over the
unobserved examples.
Tom Mitchell
•
Assumptions for Inductive Learning Algorithms:
•
The training sample represents the population
•
The input attributes permit discrimination
10
10
NUMBER OF INSTANCES,
CONCEPTS, HYPOTHESES
11
11
L
e
a
r
n
i
n
g
c
a
n
b
e
v
i
e
w
e
d
a
s
a
t
a
s
k
o
f
s
e
a
r
c
h
i
n
g
a
l
a
r
g
e
s
p
a
c
e
•
Sky: Sunny, Cloudy, Rainy
•
AirTemp: Warm, Cold
•
Humidity: Normal, High
•
Wind: Strong, Weak
•
Water: Warm, Cold
•
Forecast: Same, Change
#distinct instances : 3*2*2*2*2*2 = 96
#distinct concepts : 2
96
#syntactically distinct hypotheses : 5*4*4*4*4*4=5120 (general and
specific cases are added)
#semantically distinct hypotheses : 1+4*3*3*3*3*3=973
CONCEPT LEARNING AS
SEARCH
•
L
e
a
r
n
i
n
g
c
a
n
b
e
v
i
e
w
e
d
a
s
a
t
a
s
k
o
f
s
e
a
r
c
h
i
n
g
a
l
a
r
g
e
s
p
a
c
e
•
Different learning algorithms search this space in different
ways!
12
12
GENERAL-TO-SPECIFIC
ORDERING OF HYPOTHESIS
•
M
a
n
y
a
l
g
o
r
i
t
h
m
s
r
e
l
y
o
n
o
r
d
e
r
i
n
g
o
f
h
y
p
o
t
h
e
s
i
s
•
Consider two hypotheses:
•
h1
=(Sunny, ?, ?, Strong, ?,?)
•
h2
= (Sunny, ?,?,?,?,?)
h2
imposes fewer constraints than
h1
: it
classifies more
instances x as positive h(x)=1
h2
is more general than
h1
!
•
How to formalize this?
13
13
GENERAL-TO-SPECIFIC
ORDERING OF HYPOTHESIS
•
M
a
n
y
a
l
g
o
r
i
t
h
m
s
r
e
l
y
o
n
o
r
d
e
r
i
n
g
o
f
h
y
p
o
t
h
e
s
i
s
•
Consider two hypotheses:
•
h1
=(Sunny, ?, ?, Strong, ?,?)
•
h2
= (Sunny, ?,?,?,?,?)
h2
imposes fewer constraints than
h1
: it
classifies more instances x
as positive h(x)=1
h2
is more general than
h1
!
•
How to formalize this?
•
h2
is more general than
h1
iff
h2(x)=1
h1(x)=1
•
We note it
h2 ≥g h1
14
14
INSTANCE, HYPOTHESES, AND
MORE-GENERAL
15
15
The
≥g
relation is important as it provides a structure
over the hypothesis space.
x
1
=< Sunny,Warm,High,Strong,Cool,Same>
x
2
=< Sunny,Warm,High,Light,Warm,Same>
h
2
=< Sunny,?,?,?,?,?>
h
3
=< Sunny,?,?,?,Cool,?>
h
1
=< Sunny,?,?,Strong,?,?>
16
16
FIND-S ALGORITHM
I
n
i
t
i
a
l
i
z
e
h
t
o
t
h
e
m
o
s
t
s
p
e
c
i
f
i
c
h
y
p
o
t
h
e
s
i
s
i
n
H
:
F
o
r
e
a
c
h
p
o
s
i
t
i
v
e
t
r
a
i
n
i
n
g
i
n
s
t
a
n
c
e
x
:
F
o
r
e
a
c
h
a
t
t
r
i
b
u
t
e
c
o
n
s
t
r
a
i
n
t
a
i
i
n
h
:
I
f
t
h
e
c
o
n
s
t
r
a
i
n
t
i
s
n
o
t
s
a
t
i
s
f
i
e
d
b
y
x
T
h
e
n
r
e
p
l
a
c
e
a
i
b
y
t
h
e
n
e
x
t
m
o
r
e
g
e
n
e
r
a
l
c
o
n
s
t
r
a
i
n
t
s
a
t
i
s
f
i
e
d
b
y
x
O
u
t
p
u
t
h
y
p
o
t
h
e
s
i
s
h
FIND-S
h
= <
,
,
,
,
,
>
h
= <
Sunny, Warm, Normal, Strong, Warm, Same>
h
= <
Sunny, Warm, ? , Strong, Warm, Same>
h
= <
Sunny, Warm, ? , Strong, ? , ? >
17
17
FIND-S
h
= <
Sunny, Warm, ? , Strong, ? , ? >
Prediction
18
18
In the field of machine learning, concept learning involves inferring general definitions of concepts from labeled examples. This process aims to approximate the best concept description from a set of possible hypotheses. The concept learning approach is illustrated through examples, such as predicting whether a day is suitable for water sports based on various attributes. Hypotheses are represented as conjunctions of constraints over instance attributes, allowing classification based on given criteria.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
MACHINE LEARNING MACHINE LEARNING LECTURE 2 LECTURE 2 CONCEPT LEARNING AND VERSION SPACES CONCEPT LEARNING AND VERSION SPACES Based on Chapter 2 of Mitchell s book 1
OUTLINE Concept Learning from examples Hypothesis representation General-to specific ordering of hypotheses the Find-S algorithm 2
WHAT IS A CONCEPT? Assume a given domain, e.g. objects, animals, etc. A Concept is a subset of the domain, e.g. birds animals Birds Things Animals Cars Generally we can t look at all objects in the domain 3
WHAT IS A CONCEPT? A Concept could be defined as a Boolean-valued function C defined over the larger set Example: a function defined over all animals whose value is true for birds and false for every other animal. c(bird) = true c(cat) = false c(car) = false c(pigeon) = true 4
WHAT IS CONCEPT LEARNING? Given a set of examples labeled as members (positive) or non-members (negative) of a concept: Infer the general definition of this concept Approximate c from training examples: Infer the best concept-description from the set of all possible hypotheses 5
EXAMPLE OF A CONCEPT LEARNING TASK Concept: Good days on which my friend enjoys water sport (values: Yes, No) Task: predict the value of Enjoy Sport for an arbitrary day based on the values of the other attributes Result: classifier for days attributes Sky Temp Humid Wind Water Forecast Enjoy Sport instance Sunny Sunny Rainy Sunny Warm Warm Cold Warm Normal High High High Strong Strong Strong Strong Warm Warm Warm Cool Same Same Change Change Yes Yes No Yes 6
REPRESENTING HYPOTHESES Many possible hypothesis (h) representations The simplest h could be represented as a conjunction of constraints over the instance attributes Each constraint can be: a specific value (e.g., Water = Warm) ?: don t care/any value (e.g., Water=?) no value allowed (e.g., Water= ) Example: hypothesis h Sky Temp Humid Wind Water Forecast < Sunny ? ? Strong ? Same > We say h(x)=1 for a day x, if x satisfies the description 7
MOST GENERAL/SPECIFIC HYPOTHESIS every day is a positive example No day is a positive example 8
PROTOTYPICAL CONCEPT LEARNING TASK GIVEN: Instances X: Possible days, each described by the attributes sky, AirTemp, Humidity, Wind, Water, Forecast Target function c: EnjoySport: X {0,1} Hypotheses H: Conjunctions of constraints on attributes <?, Cold, High, ?, ?, ?> Training examples D: positive and negative examples of the target function <x1,c(x1)>,<x2,c(x2)>, ,<xn, c(xn)> DETERMINE: A hypothesis h in H with h(x)=c(x) for all x in D 9
THE INDUCTIVE LEARNING HYPOTHESIS Any hypothesis found to approximate the target function well over the training examples, will also approximate the target function well over the unobserved examples. Tom Mitchell Assumptions for Inductive Learning Algorithms: The training sample represents the population The input attributes permit discrimination 10
NUMBER OF INSTANCES, CONCEPTS, HYPOTHESES Learning can be viewed as a task of searching a large space Sky: Sunny, Cloudy, Rainy AirTemp: Warm, Cold Humidity: Normal, High Wind: Strong, Weak Water: Warm, Cold Forecast: Same, Change #distinct instances : 3*2*2*2*2*2 = 96 #distinct concepts : 296 #syntactically distinct hypotheses : 5*4*4*4*4*4=5120 (general and specific cases are added) #semantically distinct hypotheses : 1+4*3*3*3*3*3=973 11
CONCEPT LEARNING AS SEARCH Learning can be viewed as a task of searching a large space Different learning algorithms search this space in different ways! 12
GENERAL-TO-SPECIFIC ORDERING OF HYPOTHESIS Many algorithms rely on ordering of hypothesis Consider two hypotheses: h1=(Sunny, ?, ?, Strong, ?,?) h2= (Sunny, ?,?,?,?,?) h2 imposes fewer constraints than h1: it classifies more instances x as positive h(x)=1 h2 is more general than h1! How to formalize this? 13
GENERAL-TO-SPECIFIC ORDERING OF HYPOTHESIS Many algorithms rely on ordering of hypothesis Consider two hypotheses: h1=(Sunny, ?, ?, Strong, ?,?) h2= (Sunny, ?,?,?,?,?) h2 imposes fewer constraints than h1: it classifies more instances x as positive h(x)=1 h2 is more general than h1! How to formalize this? h2 is more general than h1 iff h2(x)=1 h1(x)=1 We note it h2 g h1 14
INSTANCE, HYPOTHESES, AND MORE-GENERAL Instances Hypotheses specific x1 h1 h3 h2 h1 h2 h3 h2 x2 general x1=< Sunny,Warm,High,Strong,Cool,Same> h1=< Sunny,?,?,Strong,?,?> x2=< Sunny,Warm,High,Light,Warm,Same> h2=< Sunny,?,?,?,?,?> h3=< Sunny,?,?,?,Cool,?> 15 The g relation is important as it provides a structure over the hypothesis space.
FIND-S ALGORITHM Initialize h to the most specific hypothesis in H: For each positive training instance x: For each attribute constraint ai in h: If the constraint is not satisfied by x Then replace ai by the next more general constraint satisfied by x Output hypothesis h 16
FIND-S Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Warm Same Yes 2 Sunny Warm High Strong Warm Same Yes 3 Rainy Cold High Strong Warm Change No 4 Sunny Warm High Strong Cool Change Yes h = < , , , , , > h = <Sunny, Warm, Normal, Strong, Warm, Same> h = <Sunny, Warm, ? , Strong, Warm, Same> h = <Sunny, Warm, ? , Strong, ? , ? > 17
FIND-S Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Warm Same Yes 2 Sunny Warm High Strong Warm Same Yes 3 Rainy Cold High Strong Warm Change No 4 Sunny Warm High Strong Cool Change Yes h = <Sunny, Warm, ? , Strong, ? , ? > Prediction 5 Rainy Cold High Strong Warm Change No No 6 Sunny Warm Normal Strong Warm Same Yes Yes 7 Sunny Warm Low Strong Cool Same Yes Yes 18
