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 hSolved Numerical Example – 1
Step – 1 of Find-S Algorithm
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
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.