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

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

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

Consistent Hypotheses

Example to demonstrate the consistent hypothesis


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

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


 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

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


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. Required fields are marked *