## 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 *VS _{H,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.