FIND S Algorithm – Maximally Specific Hypothesis Solved Example

 

FIND S Algorithm – Maximally Specific Hypothesis Solved Example

FIND S Algorithm is used to find the Maximally Specific Hypothesis. Using the Find-S algorithm gives a single maximally specific hypothesis for the given set of training examples.

Click Here for Python Program to Implement FIND S Algorithm – to get Maximally Specific Hypothesis

Find-S Algorithm Machine Learning

1. Initilize h to the most specific hypothesis in H
2. For each positive training instance x
      For each attribute contraint ai in h
          If the contraint 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 the hypothesis h

Solved Numerical Example – 1

Step – 1 of Find-S Algorithm

Find-S Step 1

Step 2 of Find-S Algorithm First iteration

h0 = (ø, ø, ø, ø, ø, ø, ø)

X1 = <Sunny, Warm, Normal, Strong, Warm, Same>

h1 = <Sunny, Warm, Normal, Strong, Warm, Same>

Step 2 of Find-S Algorithm Second iteration

h1 = <Sunny, Warm, Normal, Strong, Warm, Same>

X2 = <Sunny, Warm, High, Strong, Warm, Same>

h2 = <Sunny, Warm, ?, Strong, Warm, Same>

Step 2 of Find-S Algorithm Third iteration

h2 = <Sunny, Warm, ?, Strong, Warm, Same>

X3 = <Rainy, Cold, High, Strong, Warm, Change> – No

X3 is Negative example Hence ignored

h3 = <Sunny, Warm, ?, Strong, Warm, Same>

Step 2 of Find-S Algorithm Fourth iteration

h3 = <Sunny, Warm, ?, Strong, Warm, Same>

X4 = <Sunny, Warm, High, Strong, Cool, Change>

h4 = <Sunny, Warm, ?, Strong, ?, ?>

Step 3

The final maximally specific hypothesis is <Sunny, Warm, ?, Strong, ?, ?>

Video Tutorial Example – 1

Solved Numerical Example – 2

Example - 2

1. How many concepts are possible for this instance space?

Solution: 2 * 3 * 2 * 2 * 3 = 72

2. How many hypotheses can be expressed by the hypothesis language?

Solution: 4 * 5 * 4 * 4 * 5 = 1600

Semantically Distinct Hypothesis = ( 3 * 4 * 3 * 3 * 4 ) + 1 = 433

3. Apply the FIND-S algorithm by hand on the given training set. Consider the examples in the specified order and write down your hypothesis each time after observing an example.

Step 1:

  h0 = (ø, ø, ø, ø, ø)

Step 2:

  X1 = (some, small, no, expensive, many) – No

  Negative Example Hence Ignore

  h1 = (ø, ø, ø, ø, ø)

  X2 = (many, big, no, expensive, one) – Yes

  h2 = (many, big, no, expensive, one)

X3 = (some, big, always, expensive, few) – No

  Negative example hence Ignore

  h3 = (many, big, no, expensive, one)

  X4 = (many, medium, no, expensive, many) – Yes

  h4 = (many, ?, no, expensive, ?)

  X5 = (many, small, no, affordable, many) – Yes

  h5 = (many, ?, no, ?, ?)

Step 3:

Final Maximally Specific Hypothesis is:

h5 = (many, ?, no, ?, ?)

Video Tutorial Example – 2

Summary

This tutorial discusses the Find-S Algorithm in Machine Learning. If you like the tutorial share with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published. Required fields are marked *