List then Eliminate Algorithm Machine Learning

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).

Version Space: a representation of the set of hypotheses that are consistent with D

  1. an explicit list of hypotheses (List-Then-Eliminate)
  2. a compact representation of hypotheses which 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

Consistent Hypotheses

Example to demonstrate the consistent hypothesis

ExampleCitationsSizeInLibraryPriceEditionsBuy
1SomeSmallNoAffordableOneNo
2ManyBigNoExpensiveManyYes

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

Version Space

List-Then-Eliminate algorithm

Version space as a list of hypotheses

See also  Advantages and Disadvantages of Regression Model

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, ?), (?, ?)

See also  Locally Weighted Regression Algorithm in Python

Problems: List-Then-Eliminate algorithm

  1. The hypothesis space must be finite
  2. Enumeration of all the hypothesis, rather inefficient

Video Tutorial of Consistent Hypothesis, Version Space and List then Eliminate Algorithm

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.

Leave a Comment

Your email address will not be published.