CONCEPT LEARNING AS SEARCH

 

CONCEPT LEARNING AS SEARCH

·       Concept learning can be viewed as

·       the task of searching through a large space of hypotheses implicitly defined by the hypothesis representation.

·       The goal of this search is to

·       find the hypothesis that best fits the training examples.

Example:

•        Consider the instances X and hypotheses H in the EnjoySport learning task.

•        The attribute

•        Sky has three possible values, and

•        AirTemp, Humidity, Wind, Water, Forecast each have two possible values,

•        the instance space X contains

•        exactly 3*2*2*2*2*2 = 96 distinct instances

•        5*4*4*4*4*4 = 5120 syntactically distinct hypotheses within H.

•        Every hypothesis containing one or more "Φ" symbols represents the empty set of instances; that is, it classifies every instance as negative.

•        1 + (4*3*3*3*3*3) = 973 Semantically distinct hypotheses.

A CONCEPT LEARNING TASK – Instance Space

Hypothesis Space

ü  Similarly there are 5 * 4 * 4 * 4 * 4 * 4 = 5120 syntactically distinct hypotheses within H.

ü  Notice, however, that every hypothesis containing one or more "ø" symbols represents the empty set of instances; that is, it classifies every instance as negative.

ü  Therefore, the number of semantically distinct hypotheses is only 1 + (4 *3 * 3 * 3 * 3 * 3) = 973.

ü  Our EnjoySport example is a very simple learning task, with a relatively small, finite hypothesis space.

General-to-Specific Ordering of Hypotheses

•        To illustrate the general-to-specific ordering, consider the two hypotheses

h1 = (Sunny, ?, ?, Strong, ?, ?)

h2 = (Sunny, ?, ?, ?, ?, ?)

•        Now consider the sets of instances that are classified positive by h1 and by h2. Because h2 imposes fewer constraints on the instance, it classifies more instances as positive.

•        In fact, any instance classified positive by h1 will also be classified positive by h2. Therefore, we say that h2 is more general than h1.

 

More General Than hypothesis

 

·       In the figure,

ü  the box on the left represents the set X of all instances,

ü  the box on the right the set H of all hypotheses.

·       Each hypothesis corresponds to some subset of X

ü  – the subset of instances that it classifies positive.

·       The arrows connecting hypotheses represent

ü   the more - general -than relation,

ü  with the arrow pointing toward the less general hypothesis.

·       Note the subset of instances characterized by

ü     h2 subsumes the subset characterized by h1,

ü     hence  h2 is more - general– than h1.

A CONCEPT LEARNING TASK

 

A CONCEPT LEARNING TASK

•        Consider the example task of learning the target concept "Days on which Tom enjoys his favourite water sport”

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

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

Concept Learning Task: Notation

Ø  Given:

·       Instances X: Possible days, each described by the attributes

ü  Sky (with possible values Sunny, Cloudy, and Rainy),

ü  AirTemp (with values Warm and Cold),

ü  Humidity (with values Normal and High),

ü  Wind (with values Strong and Weak),

ü  Water (with values Warm and Cool),

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