Concept Learning

This talk is based on

1 Introduction

2 Learning Task

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

2.1 Inductive Learning Hypothesis

3 Concept Learning as Search

3.1 Ordering of Hypotheses

3.2 Ordering Space

General To Specific

4 Find-S Algorithm

  1. Initialize $h$ to the most specific hypothesis in $H$
  2. 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$
  3. Output hypothesis $h$

4.1 Find-S Example

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$
finds

4.2 Find-S Problems

5 Version Spaces

5.1 List-Then-Eliminate Algorithm

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

5.2 Example of Representing Version Spaces

Version Space

5.3 Version Space Representation

5.4 Candidate Elimination Algorithm

  1. $G \leftarrow$ maximally general hypotheses in $H$
  2. $S \leftarrow$ maximally specific hypotheses in $H$
  3. 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$

5.5 Candidate-Elimination Example

  1. $\langle Sunny, Warm, Normal, Strong, Warm, Same \rangle, EnjoySport = yes$
  2. $\langle Sunny, Warm, High, Strong, Warm, Same \rangle, EnjoySport = yes$
  3. $\langle Rainy, Cold, High, Strong, Warm, Change \rangle, EnjoySport = no$
  4. $\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 \}$

5.6 Candidate-Elimination Summary

5.7 Partial Classification Example

Version Space

6 Inductive Bias

6.1 Unbiased Learner

6.2 Futility of Bias-Free Learning

7 Summary

URLs

  1. Machine Learning book at Amazon, http://www.amazon.com/exec/obidos/ASIN/0070428077/multiagentcom/
  2. Slides by Tom Mitchell on Machine Learning, http://www-2.cs.cmu.edu/~tom/mlbook-chapter-slides.html

This talk available at http://jmvidal.cse.sc.edu/talks/conceptlearning/
Copyright © 2009 José M. Vidal . All rights reserved.

21 January 2003, 10:52AM