6. A CONCEPT LEARNING TASK
Consider the example task of learning the target concept "Days on
which Aldo enjoys his favourite water sport”
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 |
Table: Positive and negative training examples for the
target concept EnjoySport.
The task is to learn
to predict the value of EnjoySport for an arbitrary day, based on the
values of its other
attributes?
What hypothesis
representation is provided to the learner?
·
Let’s consider a
simple representation in which each hypothesis consists of a conjunction of
constraints on the instance attributes.
·
Let each hypothesis
be a vector of six constraints, specifying the values of the six attributes Sky,
AirTemp, Humidity, Wind, Water, and Forecast.
For each attribute, the hypothesis will either
·
Indicate by a
"?' that any value is acceptable for this attribute,
·
Specify a single
required value (e.g., Warm) for the attribute, or
·
Indicate by a
"Φ" that no value is acceptable
If some instance x satisfies all the constraints of hypothesis h, then h
classifies x as a positive
example (h(x) = 1).
The hypothesis that PERSON enjoys his favorite sport only on cold days
with high humidity
is represented by the expression
(?, Cold, High, ?, ?, ?)
The most general hypothesis-that every day is a positive example-is
represented by
(?, ?, ?, ?, ?, ?)
The most specific possible hypothesis-that no day is a positive example-is
represented by
(Φ, Φ, Φ, Φ, Φ, Φ)
Notation
·
The set of items over
which the concept is defined is called the set of instances, which is denoted
by X.
Example: X
is the set of all possible days, each represented by the attributes: Sky,
AirTemp,
Humidity, Wind, Water, and Forecast
·
The concept or
function to be learned is called the target concept, which is denoted by c. c
can be any Boolean valued function defined over the instances X
c: X→ {O, 1}
Example: The
target concept corresponds to the value of the attribute EnjoySport
(i.e., c(x) = 1 if EnjoySport = Yes, and c(x) = 0 if EnjoySport = No).
·
Instances for which
c(x) = 1 are called positive examples, or members of the target concept.
·
Instances for which
c(x) = 0 are called negative examples, or non-members of the target
·
concept.
·
The ordered pair (x,
c(x)) to describe the training example consisting of the instance x and its
target concept value c(x).
·
D to denote the set
of available training examples
The symbol H to denote the set of all possible hypotheses that the learner
may consider regarding the identity of the target concept. Each hypothesis h in
H represents a Boolean valued
function defined over X
h: X→{O, 1}
The goal of the learner is to find a hypothesis h such that h(x) = c(x)
for all x in X.
___________________________________________________________________________
Ø Given:
·
Instances X: Possible days, each described by the attributes
o
Sky (with possible
values Sunny, Cloudy, and Rainy),
o
AirTemp (with values
Warm and Cold),
o
Humidity (with values
Normal and High),
o
Wind (with values
Strong and Weak),
o
Water (with values
Warm and Cool),
o
Forecast (with values
Same and Change).
Hypotheses H:
Each hypothesis is described by a conjunction of constraints on the
attributes Sky, AirTemp, Humidity, Wind, Water, and
Forecast. The constraints may be "?" (any value is acceptable , “Φ”
(no value e is acceptable , or a specific value.
· Target concept c: EnjoySport : X → {0, l}
· Training examples D: Positive and negative examples of
the target function
Determine:
· A hypothesis h in H such that h(x) = c(x) for all x in X.
-----------------------------------------------------------------------------------------------------------------
Table: The EnjoySport
concept learning task.
The inductive learning hypothesis
Any hypothesis found to approximate the target function well over a
sufficiently large set of training examples will also approximate the target
function well over other unobserved examples.