Machine Learning - Spring 2004
==============================
Lab experiments 5
-----------------
Program: search.pl
Data: animals.pl, loandata.pl
-----------------------------
?- ['c:/prolog/search'].
?- ['c:/prolog/animals'].
?- lrn.
Generalizing: example(1, mammal, [has_covering=hair, milk=t, homeothermic=t, habitat=land, eggs=f, gills=f])
Hypothesis found: [eggs=f]
Covered examples: [1, 2, 4]
Generalizing: example(3, mammal, [has_covering=hair, milk=t, homeothermic=t, habitat=sea, eggs=t, gills=f])
*** Removing: [eggs=f]-[1, 2, 4]
Hypothesis found: [milk=t]
Covered examples: [1, 2, 3, 4]
Generalizing: example(5, fish, [has_covering=scales, milk=f, homeothermic=f, habitat=sea, eggs=t, gills=t])
Hypothesis found: [gills=t]
Covered examples: [5]
Generalizing: example(6, reptile, [has_covering=scales, milk=f, homeothermic=f, habitat=land, eggs=t, gills=f])
Hypothesis found: [has_covering=scales, gills=f]
Covered examples: [6, 7]
Generalizing: example(8, bird, [has_covering=feathers, milk=f, homeothermic=t, habitat=air, eggs=t, gills=f])
Hypothesis found: [has_covering=feathers]
Covered examples: [8, 9]
Generalizing: example(10, amphibian, [has_covering=none, milk=f, homeothermic=f, habitat=land, eggs=t, gills=f])
Hypothesis found: [has_covering=none, eggs=t]
Covered examples: [10]
NOTE that the hypothesis [milk=t] is more general than (semantically covers) [eggs=f].
Note also that the coverage shown for each hypothesis is based on the whole set of examples.
Although after creating the first hypothesis [eggs=f] there is only one example left
uncovered (3), the coverage of [milk=t] is [1, 2, 3, 4]. This allows to remove the
hypotheses covered by other hypotheses, while they are being generated (the message
*** Removing: [eggs=f]-[1, 2, 4] indicates this).
The final set of hypotheses (rules) can be seen by using "listing":
?- listing(if).
if[milk=t]then mammal.
if[gills=t]then fish.
if[has_covering=scales, gills=f]then reptile.
if[has_covering=feathers]then bird.
if[has_covering=none, eggs=t]then amphibian.
The above experiment suggests that if [milk=t] is generated first the other hypothesis
for mammals will never by tried. We can achieve this by putting example 3 (the one whose
generalization resulted in [milk=t]) first in the data file. The result of this experiment
(mammals odered as [3, 1, 2, 4]) is shown below.
?- lrn.
Generalizing: example(3, mammal, [has_covering=hair, milk=t, homeothermic=t, habitat=sea, eggs=t, gills=f])
Hypothesis found: [milk=t]
Covered examples: [3, 1, 2, 4]
Generalizing: example(5, fish, [has_covering=scales, milk=f, homeothermic=f, habitat=sea, eggs=t, gills=t])
Hypothesis found: [gills=t]
Covered examples: [5]
Generalizing: example(6, reptile, [has_covering=scales, milk=f, homeothermic=f, habitat=land, eggs=t, gills=f])
Hypothesis found: [has_covering=scales, gills=f]
Covered examples: [6, 7]
Generalizing: example(8, bird, [has_covering=feathers, milk=f, homeothermic=t, habitat=air, eggs=t, gills=f])
Hypothesis found: [has_covering=feathers]
Covered examples: [8, 9]
Generalizing: example(10, amphibian, [has_covering=none, milk=f, homeothermic=f, habitat=land, eggs=t, gills=f])
Hypothesis found: [has_covering=none, eggs=t]
Covered examples: [10]
The next two runs of the algorithm on the loandata further illustrate the effect
of reordering examples.
?- ['c:/prolog/loandata']. % Example order: 1,2,3,4,5,6,7,8,9,10,11,12
?- lrn.
Generalizing: example(1, approve, [emp=yes, buy=comp, sex=f, married=no])
Hypothesis found: [emp=yes, buy=comp]
Covered examples: [1, 3, 6, 7, 8, 9, 10]
Generalizing: example(2, reject, [emp=no, buy=comp, sex=f, married=yes])
Hypothesis found: [emp=no]
Covered examples: [2, 11, 12]
Generalizing: example(4, approve, [emp=yes, buy=car, sex=f, married=yes])
Hypothesis found: [emp=yes, married=yes]
Covered examples: [4, 6, 9, 10]
Generalizing: example(5, reject, [emp=yes, buy=car, sex=f, married=no])
Hypothesis found: [buy=car, married=no]
Covered examples: [5]
?- ['c:/prolog/loandata']. % Example order: 3,1,2,4,5,6,7,8,9,10,11,12
?- lrn.
Generalizing: example(3, approve, [emp=yes, buy=comp, sex=m, married=no])
Hypothesis found: [emp=yes, sex=m]
Covered examples: [3, 8, 9, 10]
Generalizing: example(1, approve, [emp=yes, buy=comp, sex=f, married=no])
*** Removing: [emp=yes, sex=m]-[3, 8, 9, 10]
Hypothesis found: [emp=yes, buy=comp]
Covered examples: [3, 1, 6, 7, 8, 9, 10]
Generalizing: example(2, reject, [emp=no, buy=comp, sex=f, married=yes])
Hypothesis found: [emp=no]
Covered examples: [2, 11, 12]
Generalizing: example(4, approve, [emp=yes, buy=car, sex=f, married=yes])
Hypothesis found: [emp=yes, married=yes]
Covered examples: [4, 6, 9, 10]
Generalizing: example(5, reject, [emp=yes, buy=car, sex=f, married=no])
Hypothesis found: [buy=car, married=no]
Covered examples: [5]