# List then Eliminate Algorithm Machine Learning

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

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