Consistent Hypothesis, Version Space and List then Eliminate Algorithm
Consistent Hypothesis
The idea: output a description of the set of all hypotheses consistent with the training examples (correctly classify training examples).
Video Tutorial of Consistent Hypothesis, Version Space, and List then Eliminate Algorithm
Version Space
Version Space is a representation of the set of hypotheses that are consistent with D
- an explicit list of hypotheses (List-Then-Eliminate)
- a compact representation of hypotheses that exploits the more_general_than partial ordering (Candidate-Elimination)
Hypothesis h is consistent with a set of training examples D iff h(x) = c(x) for each example in D
Example to demonstrate the consistent hypothesis
| Example | Citations | Size | InLibrary | Price | Editions | Buy |
| 1 | Some | Small | No | Affordable | One | No |
| 2 | Many | Big | No | Expensive | Many | Yes |
h1 = (?, ?, No, ?, Many) – Yes —- is a consistent hypothesis
h2 = (?, ?, No, ?, ?) – yes —- is inconsistent hypothesis
Version Space
The version space VSH,D is the subset of the hypothesis from H consistent with the training example in D
List-Then-Eliminate algorithm
Version space as a list of hypotheses
VersionSpace <– a list containing every hypothesis in H
For each training example, <x, c(x)> Remove from VersionSpace any hypothesis h for which h(x) != c(x)
Output the list of hypotheses in VersionSpace
Example: List-Then-Eliminate algorithm
F1 – > A, B
F2 – > X, Y
Instance Space: (A, X), (A, Y), (B, X), (B, Y) – 4 Examples
Hypothesis Space: (A, X), (A, Y), (A, ø), (A, ?), (B, X), (B, Y), (B, ø), (B, ?), (ø, X), (ø, Y), (ø, ø), (ø, ?), (?, X), (?, Y), (?, ø), (?, ?) – 16 Hypothesis
Semantically Distinct Hypothesis : (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y (?, ?), (ø, ø) – 10
Solution:
Version Space: (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y) (?, ?), (ø, ø),
Training Instances
F1 F2 Target
A X Yes
A Y Yes
Consistent Hypothesis are: (A, ?), (?, ?)
Problems: List-Then-Eliminate algorithm
- The hypothesis space must be finite
- Enumeration of all the hypothesis, rather inefficient
Summary
This tutorial discusses the Consistent Hypothesis, Version Space and List then Eliminate Algorithm in Machine Learning. If you like the tutorial share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.