Concept Learning: Definition: The problem is to learn a function mapping examples into two classes: positive and negative. We are given a database of examples already classified as positive or negative. Concept learning: the process of inducing a function mapping input examples into a Boolean output.
Examples:
Example: Classifying Mushrooms
Representation of instances:
Features:
Input and Output Spaces:
An example in X is a feature vector X.
Only a small subset of instances is available in the database of examples.
Training Examples:
D : The set of training examples.
D is a set of pairs { (x,c(x)) }, where c is the target concept. c is a subset of the universe of discourse or the set of all possible instances.
Example of D:
((red,small,round,humid,low,smooth), poisonous)
((red,small,elongated,humid,low,smooth), poisonous)
((gray,large,elongated,humid,low,rough), not-poisonous)
((red,small,elongated,humid,high,rough), poisonous)
Hypothesis Representation
Any hypothesis h is a function from X to Y
h: X -> Y
We will explore the space of conjunctions.
Special symbols:
Hypotheses Space:
The space of all hypotheses is represented by H
Let h be a hypothesis in H.
Let X be an example of a mushroom.
if h(X) = 1 then X is poisonous, otherwise X is not-poisonous
Our goal is to find the hypothesis, h*, that is very “close” to target concept c.
A hypothesis is said to “cover” those examples it classifies as positive.
Assumptions: