Showing posts with label hypothesis. Show all posts
Showing posts with label hypothesis. Show all posts

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.




About Machine Learning

Welcome! Your Hub for AI, Machine Learning, and Emerging Technologies In today’s rapidly evolving tech landscape, staying updated with the ...