# List then Eliminate Algorithm Machine Learning

[wptelegram-join-channel]

## Consistent Hypothesis

The idea: output a description of the set of all hypotheses consistent with the training examples (correctly classify training examples).

### 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

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

## 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

1. The hypothesis space must be finite
2. 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.