List then Eliminate Algorithm Machine Learning

Video Tutorials
Artificial Intelligence Tutorial
Machine Learning Projects TutorialPython Video tutorial
Computer Graphics Video TutorialC++ Video Tutorial
Big Data Analytics Video TutorialSoft Computing Video Tutorial
Placement Video TutorialJava Video Tutorial

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


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

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


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 *