Summary Concept Learning and the General-to-Specific Ordering

2 Concept Learning and the General-to-Specific Ordering

I Learning from examples

I General-to-specific ordering over hypotheses

I Version spaces and candidate elimination algorithm

I Picking new examples

I The need for inductive bias

I Note: This is a simple approach assuming no noise and illustrating key concepts.




ICCL
International Center for Computational Logic 1
Algebra, Logic and Formal Methods in Computer Science

,A Concept Learning Task

I Concept Learning is the process of inferring a boolean-valued function
from training examples of its input and output.

I Example: Target concept: “days on which Aldo enjoys his favorite water sport ”.

. Training Examples for EnjoySport:

Sky Temp Humid Wind Water Forecast EnjoySport
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cool Change Yes

. Possible values:

Sky Sunny, Cloudy, Rainy
Temp Warm, Cold
Humid Normal, High
Wind Strong, Weak
Water Warm, Cool
Forecast Same, Change

ICCL
International Center for Computational Logic 2
Algebra, Logic and Formal Methods in Computer Science

,Representing Hypotheses

I Many possible representations.

I Here, h is a conjunction of constraints on attributes.

I Each constraint can be either
. a specific value (e.g., W ater = W arm),
. don’t care (e.g., W ater =?), or
. no value allowed (e.g., W ater = ∅).

I Hypotheses are represented as vectors, e.g.,
Sky AirTemp Humid Wind Water Forecast
hSunny ? ? Strong ? Samei

I Most general hypothesis: h?, ?, ?, ?, ?, ?i.

I Most specific hypothesis: h∅, ∅, ∅, ∅, ∅, ∅i.


ICCL
International Center for Computational Logic 3
Algebra, Logic and Formal Methods in Computer Science

, Prototypical Concept Learning Task

I 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 literals. E.g.,

h?, Cold, High, ?, ?, ?i.

. Training examples D : Positive and negative examples of the target function

hx1, c(x1)i, . . . hxm, c(xm)i.

I Determine: A hypothesis h in H such that h(x) = c(x) for all x in D .

I 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.

ICCL
International Center for Computational Logic 4

Algebra, Logic and Formal Methods in Computer Science