Concept Learning (ML)

Concept Learning is inferring a boolean-valued function from training examples of its input and output.
i.e. it is acquring a hypothesis that fits the training data.

• Learning from Examples
• Creating General-to-Specific ordering over hypotheses
• Version spaces and candidate elimination algorithms

Approximation Rule (Most Important Thing in the Course)

When the training data is a reasonable sample representation of the overal data then:

Any hypothesis found to approximate the target function well over a sufficiently large set of training examples will also approximate the target function over other unobserved examples.

If the above is not able to be assumed then be wary of the training data. For instance it might only cover a small subset of the possible cases.

Representing Hypotheses

The hypothesis is a conjunction of constraints on attributes; it is determining which attributes must be a certain value (and what that value is).

Constraints can be:

• A specific value (x = a) // x is important
• Don't care ( x = ?) // x is irrelevant
• No value allowed (x = 0) // x must not figure

Example - EnjoySport

We have a series of attributes that describe the weather conditions. Our goal is to correctly determine whether or not we will EnjoySport in any particular instance (combination of different attribute values).

Attribute	Values
Sky	Sunny, Cloudy, Rainy
AirTemp	Warm, Cold
Humidity	Normal, High
Wind	Strong, Weak
WaterTemp	Warm, Cool
Forecast	Same,Change

Representation

Representation is of the form

(1)

\begin{equation} {attribute_1,attribute_2,attribute_3...,attribute_n} \end{equation}

Where each may be one of the selected values, 0 or ?

e.g. {Cloudy, Cold, ?, Strong, Warm, ?}

The hypothesis will hence be represented as such, with each attribute constrained as required.

Target Function

The Target Function for this example is:
EnjoySport: X -> {0,1}
i.e. the EnjoySport variable (What we are trying to ascertain) takes in X (attributes etc) and outpus either 0 or 1.

Training Examples

The training examples are positive and negative examples of the target function.
E.g. x = {?,warm,?,?,cool,?}, c(x) = false

H: All possible hypotheses
h: Any one hypothesis
c: Target function
D: All training data
d: Any one training example

We have to determine h in H such that h(d) = c(d) for all x in D. i.e. we have to find the target Hypothesis

See Concept Learning As Search