Concept Learning

This talk is based on

Tom M. Mitchell. Machine Learning. [1] McGraw Hill. 1997. Chapter 2.
and his slides [2].

Most learning problems require the learner to learn a categorization.
For example
- Which one of these pictures represents the letter A?
- Which one of these pictures shows Elvis Presley?
- Which move will lead to an eventual win in the game?
- Which one of these credit records has suffered from credit fraud?
- Which genes are responsible for higher brain function disorder?
Concept learning is inferring a boolean-valued function from training examples of its input.

Want to learn "on which days does Al enjoy his favorite sport"?
Represent days using a set of attributes. Assume no noise in examples.
We are given positive and negative examples of the target function $c(x)$:

Example	Sky	Temp	Humidity	Wind	Water	Forecast	Enjoy Sport?
1	Sunny	Warm	Normal	Strong	Warm	Same	Yes
2	Sunny	Warm	High	String	Warm	Same	Yes
3	Rainy	Cold	High	Strong	Warm	Change	Yes
4	Sunny	Warm	High	Strong	Cool	Change	Yes

The hypothesis representation uses either a value, a ?, or a ∅, for each specific attribute: \[\langle?, Cold, High, ?, ?, ?\rangle\]
GOAL: find $h \in H$ such that $h(x)=c(x)$.

With $n$ attributes, each with 3 values, we have that \[|H| = 3^n\]
We assume that one of those hypothesis will match the target function $c(x)$.
Furthermore, all we know about $c(x)$ is given by the examples we have seen. We must assume that the future examples will resemble past ones.
The inductive learning hypothesis states that 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.
Why should this be true? Its not true for the stock market, or is it?

Concept learning can be viewed as search through $H$.
Since we chose the hypothesis representation we also chose $H$, so we must be careful.
Some of these hypothesis might not be semantically distinct even if they are syntactically distinct.
In our representation, all hypothesis with any ∅ attributes are the same.

In any concept learning problem the hypothesis can be ordered in a general-to-specific ordering.
By using this ordering we can exhaustively search even infinite spaces without having to enumerate every hypothesis.
For example, \[h_1 = \langle Sunny, ?, ?, Strong, ?, ?\rangle\] is more specific than \[h_2 = \langle Sunny, ?, ?, ?, ?, ?\rangle\]
Or, $h_2$ is more general than $h_1$.
Any example that is classified as positive by $h_1$ will also be classified as positive by $h_2$.
If $h_j$ and $h_k$ are boolean-valued functions defined over X then $h_j$ is more general than or equal to $h_k$ (written $h_j \geq_g h_k$) if and only if \[ \forall_{x \in X}[(h_k(x)=1) \rightarrow (h_j(x)=1)]\]

This box represents the set of all instances X. Each point is an instance.
The circles are hypothesis. The points inside a circle correspond to the instances that hypothesis classifies as positive.
$x_1 = \langle Sunny, Warm, High, Strong, Cool, Same\rangle$
$x_2 = \langle Sunny, Warm, High, Light, Warm, Same\rangle$
The second box represents an ordered set of all the possible hypothesis.
The ones higher up are more specific, the lower more general.
There top will contain the hypothesis that classifies all examples as negative while the bottom with the hypothesis that classifies every example as positive.
$h_1 = \langle Sunny, ?, ?, Strong, ?, ?\rangle$
$h_2 = \langle Sunny, ?, ?, ?, ?, ?\rangle$
$h_3 = \langle Sunny, ?, ?, ?, Cool, ?\rangle$

Initialize $h$ to the most specific hypothesis in $H$
For each positive training instance $x$
- For each attribute constraint $a_{i}$ in $h$:
  - If the constraint $a_{i}$ in $h$ is satisfied by $x$ Then do nothing
  - Else replace $a_{i}$ in $h$ by the next more general constraint that is satisfied by $x$
Output hypothesis $h$

Guaranteed to output the most specific hypothesis within $H$ that is consistent with the positive training examples.
Notice that negative examples are ignored.

Ex.	Sky	Temp	Humid	Wind	Water	Forecast	Enjoy Sport?	Hypothesis
0								$\langle$ ∅, ∅, ∅,∅,∅,∅ $\rangle$
1	Sunny	Warm	Normal	Strong	Warm	Same	Yes	$\langle Sunny, Warm, Normal, Strong, Warm, Same \rangle$
2	Sunny	Warm	High	String	Warm	Same	Yes	$\langle Sunny, Warm, ?, Strong, Warm, Same \rangle$
3	Rainy	Cold	High	Strong	Warm	Change	No	$\langle Sunny, Warm, ?, Strong, Warm, Same \rangle$
4	Sunny	Warm	High	Strong	Cool	Change	Yes	$\langle Sunny, Warm, ?, Strong, ?, ? \rangle$

Can't tell whether it has learned concept
Can't tell when training data inconsistent. Does not work well with noisy data.
Picks a maximally specific $h$ (why?)
Depending on $H$, there might be several!

We will try to output a description of the set of all hypothesis consistent with the set of training examples.
A hypothesis $h$ is consistent with a set of training examples $D$ of target concept $c$ if and only if $h(x)=c(x)$ for each training example $\langle x, c(x) \rangle$ in $D$. \[Consistent(h,D) \equiv \forall_{\langle x, c(x) \rangle \in D} h(x)=c(x) \]
Notice how an example $x$ satisfies $h$ when $h(x)=1$, while it is consistent with $h$ if $h(x)=c(x)$.
The version space, denoted $VS_{H,D}$ with respect to $H$ and $D$, is the subset of hypothesis from $H$ consistent with the training examples in D. \[VS_{H,D} \equiv \{h \in H\,|\, Consistent(h,D)\}\]

$VersionSpace \leftarrow$ a list containing every hypothesis in $H$
For each training example, $\langle x, c(x) \rangle$
- remove from $VersionSpace$ any hypothesis $h$ for which $h(x) \neq c(x)$
Output the list of hypotheses in $VersionSpace$

It requires exhaustively enumeration of all hypothesis in $H$ (huge!).

The version space is represented by its most general and most specific member sets(those in boxes).
The general can be thought of as large circles which surround the specific.

The general boundary, $G$, of version space $VS_{H,D}$ is the set of its maximally general members of $H$ consistent with $D$ \[ G \equiv \{ g \in H \,|\, Consistent(g,D) \wedge (\not \exists_{g' \in H} (g' >_{g} g \wedge Consistent(g',D)))\} \]
The specific boundary S, of version space $VS_{H,D}$ is the set of its maximally specific members of $H$ consistent with $D$: \[ S \equiv \{ s \in H \,|\, Consistent(s,D) \wedge (\not \exists_{s' \in H} (s >_{g} s' \wedge Consistent(s',D)))\} \]
Every member of the version space lies between these boundaries \[VS_{H,D} = \{h \in H\,|\, \exists_{s \in S} \exists_{g \in G} g \geq h \geq s\}\]

$G \leftarrow$ maximally general hypotheses in $H$
$S \leftarrow$ maximally specific hypotheses in $H$
For each training example $d$, do
1. If $d$ is a positive example then:
  1. Remove from $G$ any hypothesis inconsistent with $d$
  2. For each hypothesis $s$ in $S$ that is not consistent with $d$
  3. Remove $s$ from $S$
  4. Add to $S$ all minimal generalizations $h$ of $s$ such that $h$ is consistent with $d$, and some member of $G$ is more general than $h$
  5. Remove from $S$ any hypothesis that is more general than another hypothesis in $S$
2. else if $d$ is a negative example:
  1. Remove from $S$ any hypothesis inconsistent with $d$
  2. For each hypothesis $g$ in $G$ that is not consistent with $d$
    1. Remove $g$ from $G$
    2. Add to $G$ all minimal specializations $h$ of $g$ such that $h$ is consistent with $d$, and some member of $S$ is more specific than $h$.
    3. Remove from $G$ any hypothesis that is less general than another hypothesis in $G$

$\langle Sunny, Warm, Normal, Strong, Warm, Same \rangle, EnjoySport = yes$
$\langle Sunny, Warm, High, Strong, Warm, Same \rangle, EnjoySport = yes$
$\langle Rainy, Cold, High, Strong, Warm, Change \rangle, EnjoySport = no$
$\langle Sunny, Warm, High, Strong, Cool, Change \rangle, EnjoySport = yes$

$S_0: \{\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset\}$

$S_1: \{ \langle Sunny, Warm, Normal, Strong, Warm, Same \rangle \}$

$S_2$, $S_3$ $: \{ \langle Sunny, Warm, ?, Strong, Warm, Same \rangle \}$

$S_4: \{ \langle Sunny, Warm, ?, Strong, ?, ? \rangle \}$

$G_4: \{\langle Sunny, ?, ?, ?, ?, ? \rangle, \langle ?, Warm, ?, ?, ?, ? \rangle \}$

$G_3: \{\langle Sunny, ?, ?, ?, ?, ? \rangle, \langle ?, Warm, ?, ?, ?, ? \rangle, \langle ?, ?, ?, ?, ?, Same \rangle\}$

$G_0$, $G_1$, $G_2$$: \{\langle ?, ?, ?, ?, ?, ? \rangle \}$

It will converge towards the hypothesis that correctly describes the target concept given that
- there are no errors in the training examples,
- there is some hypothesis H that correctly describes the target concept.
If there are errors, $S$ and $G$ will eventually converge to an empty version space.
For best performance, the next example should satisfy exactly half the hypotheses in the current version space (twenty questions).
Partially learned concepts can still be used (i.e., before converging to a single hypothesis)
- If all the hypotheses classify an instance as positive or negative then we can safely classify it as such.
- If there is a discrepancy then we could let the majority win. The vote could be viewed as a confidence measure.

How would these examples be classified by the partially learned concept to the right?
$\langle Sunny, Warm, Normal, Strong, Cool, Change \rangle$-Positive, since every hypothesis classifies it as positive.
$\langle Rainy, Cool, Normal, Light, Warm, Same \rangle$-Negative, everyone says so
$\langle Sunny, Warm, Normal, Light, Warm, Same \rangle$-Unknown, half say yes, half say no
$\langle Sunny, Cold, Normal, Strong, Warm, Same \rangle$-Negative by 4, positive by 2. Negative.

Given the following examples:
$\langle Sunny, Warm, Normal, Strong, Cool, Change \rangle$, yes
$\langle Cloudy, Warm, Normal, Light, Warm, Same \rangle$, yes
$\langle Rainy, Warm, Normal, Light, Warm, Same \rangle$, no
There is no hypothesis in our space that can represent this concept. The closest we can come is \[ \langle ?, Warm, Normal, Light, Warm, Same \rangle$
So, it is a biased learner

We could define an unbiased hypothesis space by allowing arbitrary conjunctions, disjunctions, and negations.
The number of possible hypothesis (ignoring semantic repetition) is $2^{|X|}$.
The Candidate-Elimination algorithm, if applied to this hypothesis space, will be unable to generalize beyond the observed examples!
So, in order to learn the concept we would need to present every single example.
If we use a partially-learned concept, then exactly half of the hypotheses will vote positive and half negative for every unseen example.

A learner that makes no a priori assumptions regarding the identity of the target concept has no rational basis for classifying any unseen instances.
So, what is the inductive bias?
Given an algorithm $L$ and a set of training instances $D_c = \{\langle x,c(x) \rangle\}$, let $L(x_i,D_c)$ be the classification given to $x_i$ by $L$ after training on $D_c$. The inductive bias of $L$ is any minimal set of assertions $B$ for any target concept $c$ and examples $D$ s.t. \[\forall_{x_i \in X} B \wedge D_c \wedge x_i \entails L(x_i, D_c) \]
For example, the inductive bias of the Candidate-Elimination algorithm (with voting) is the assumption that the target concept is contained in the hypothesis space.
That is, if we make that assumption then the classification follows logically (by deduction).

Concept learning as search through $H$
General-to-specific ordering over $H$
Version space candidate elimination algorithm
$S$ and $G$ boundaries characterize learner's uncertainty
Learner can generate useful queries
Inductive leaps possible only if learner is biased
Inductive learners can be modeled by equivalent deductive systems

Concept Learning

1 Introduction

2 Learning Task

2.1 Inductive Learning Hypothesis

3 Concept Learning as Search

3.1 Ordering of Hypotheses

3.2 Ordering Space

4 Find-S Algorithm

4.1 Find-S Example

4.2 Find-S Problems

5 Version Spaces

5.1 List-Then-Eliminate Algorithm

5.2 Example of Representing Version Spaces

5.3 Version Space Representation

5.4 Candidate Elimination Algorithm

5.5 Candidate-Elimination Example

5.6 Candidate-Elimination Summary

5.7 Partial Classification Example

6 Inductive Bias

6.1 Unbiased Learner

6.2 Futility of Bias-Free Learning

7 Summary

URLs