FIND-S: FINDING A MAXIMALLY SPECIFIC HYPOTHESIS

 FIND-S Algorithm

 1.   Initialize h to the most specific hypothesis in H

2.   For each positive training instance x

For each attribute constraint ai in h

If the constraint ai is satisfied by x

Then do nothing

Else replace ai in h by the next more general constraint that is satisfied by x

3.   Output hypothesis h

To illustrate this algorithm, assume the learner is given the sequence of training examples from the EnjoySport task

Example	Sky	AirTemp	Humidity	Wind	Water	Forecast	EnjoySport
1	Sunny	Warm	Normal	Strong	Warm	Same	Yes
2	Sunny	Warm	High	Strong	Warm	Same	Yes
3	Rainy	Cold	High	Strong	Warm	Change	No
4	Sunny	Warm	High	Strong	Cool	Change	Yes

• The first step of FIND-S is to initialize h to the most specific hypothesis in H

h - (Ø, Ø, Ø, Ø, Ø, Ø)

• Consider the first training example

x1 = <Sunny Warm Normal Strong Warm Same>, +

Observing the first training example, it is clear that hypothesis h is too specific. None of the "Ø" constraints in h are satisfied by this example, so each is replaced by the next more general constraint that fits the example

h1 = <Sunny Warm Normal Strong Warm Same>

• Consider the second training example

x2 = <Sunny, Warm, High, Strong, Warm, Same>, +

 The second training example forces the algorithm to further generalize h, this time substituting a "?" in place of any attribute value in h that is not satisfied by the new example

h2 = <Sunny Warm ? Strong Warm Same>

• Consider the third training example

x3 = <Rainy, Cold, High, Strong, Warm, Change>, -

 Upon encountering the third training the algorithm makes no change to h. The FIND-S algorithm simply ignores every negative example.

h3 = < Sunny Warm ? Strong Warm Same>

• Consider the fourth training example

x4 = <Sunny Warm High Strong Cool Change>, +

 The fourth example leads to a further generalization of h

h4 = < Sunny Warm ? Strong ? ? >

The key property of the FIND-S algorithm

• FIND-S is guaranteed to output the most specific hypothesis within H that is consistent with the positive training examples
• FIND-S algorithm’s final hypothesis will also be consistent with the negative examples provided the correct target concept is contained in H, and provided the training examples are correct.

Unanswered by FIND-S

1. Has the learner converged to the correct target concept?
2. Why prefer the most specific hypothesis?
3. Are the training examples consistent?
4. What if there are several maximally specific consistent hypotheses?