Version Space Problem 1
Taken From: http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/vspace/3_vspace.html

Reference: E. Rich, K. Knight, "Artificial Intelligence", McGraw Hill, Second Edition.
http://www.cc.gatech.edu/classes/cs3361_97_winter/learning.txt

Problem 1: Learning the concept of "Japanese Economy Car"

Features: ( Country of Origin, Manufacturer, Color, Decade, Type )

Origin Manufacturer Color Decade Type Example Type
Japan Honda Blue 1980 Economy Positive
Japan Toyota Green 1970 Sports Negative
Japan Toyota Blue 1990 Economy Positive
USA Chrysler Red 1980 Economy Negative
Japan Honda White 1980 Economy Positive

Solution:

1. Positive Example: (Japan, Honda, Blue, 1980, Economy)

Initialize G to a singleton set that includes everything.
Initialize S to a singleton set that includes the first positive example. 		G = { (?, ?, ?, ?, ?) }
S = { (Japan, Honda, Blue, 1980, Economy) }

 

These models represent the most general and the most specific heuristics one might learn.
The actual heuristic to be learned, "Japanese Economy Car", probably lies between them somewhere within the version space.

2. Negative Example: (Japan, Toyota, Green, 1970, Sports)

Specialize G to exclude the negative example.
G =
 
 
 		 { (?, Honda, ?, ?, ?),
(?, ?, Blue, ?, ?),
(?, ?, ?, 1980, ?),
(?, ?, ?, ?, Economy) }
S = { (Japan, Honda, Blue, 1980, Economy) }

 

Refinement occurs by generalizing S or specializing G, until the heuristic hopefully converges to one that works well.

3. Positive Example: (Japan, Toyota, Blue, 1990, Economy)

Prune G to exclude descriptions inconsistent with the positive example.
Generalize S to include the positive example.
G =
 		 { (?, ?, Blue, ?, ?),
(?, ?, ?, ?, Economy) }
S = { (Japan, ?, Blue, ?, Economy) }

 

4. Negative Example: (USA, Chrysler, Red, 1980, Economy)

Specialize G to exclude the negative example (but stay consistent with S)
G =
 		 { (?, ?, Blue, ?, ?),
(Japan, ?, ?, ?, Economy) }
S = { (Japan, ?, Blue, ?, Economy) }

 

5. Positive Example: (Japan, Honda, White, 1980, Economy)

Prune G to exclude descriptions inconsistent with positive example.
Generalize S to include positive example. 		G = { (Japan, ?, ?, ?, Economy) }
S = { (Japan, ?, ?, ?, Economy) }

 

G and S are singleton sets and S = G.
Converged.
No more data, so algorithm stops.