0% found this document useful (0 votes)

469 views45 pages

ConceptLearning-Candidate Elimination Algorithm

This document describes the candidate elimination algorithm for concept learning. It begins by recapping the FIND-S algorithm and introducing the concepts of consistent hypotheses and version spaces. It then describes the list-then-eliminate algorithm before detailing the more efficient candidate elimination algorithm. The candidate elimination algorithm maintains a specific boundary S and general boundary G that compactly represent the version space. It generalizes S for positive examples and specializes G for negative examples. An example run on a sports domain dataset is provided to illustrate the algorithm.

Uploaded by

ASWINI KALYAN

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PPTX, PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

469 views45 pages

ConceptLearning-Candidate Elimination Algorithm

Uploaded by

ASWINI KALYAN

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PPTX, PDF, TXT or read online on Scribd

You are on page 1/ 45

CANDIDATE ELIMINATION

ALGORITHM
OVERVIEW
 FIND-S Recap
 Consistent hypotheses

 Version spaces

 LIST-THEN-ELIMINATE Algo

 Compact representation of Version Spaces

 CANDIDATE-ELIMINATION Algo

 Conclusion
FIND-S ALGORITHM
 Start with most specific hypothesis
h = (∅, ∅, ∅, ∅, ∅, ∅)
 Iteratively generalize h for each positive example
FIND-S ALGORITHM
EXAMPLE-1
EXAMPLE-2 :
THOUGHTS ABOUT FIND-S
 Assumes that the target function t is in H and the training
data contains no errors

 So negative examples can be safely ignored.

THOUGHTS ABOUT FIND-S
 Cant tell when training data is inconsistent because it
ignores the negative
THOUGHTS ABOUT FIND-S
 Assume a consistent and unknown h that has generated
the training set
 Algorithm cant tell whether it has learned the target function
because it picks one hypothesis out of many possible ones
 Picks a maximally specific h. Is this reasonable?
THOUGHTS ABOUT FIND-S
 There might be many consistent hypotheses in H.
 FIND-S finds one of them.

 We can exploit the others too.

CONSISTENT HYPOTHESIS
 Given
 training
example d = (x, t(x)) in D
 hypothesis h in H

 A hypothesis is consistent with the training examples if it

correctly classifies the examples.
 h is consistent with D if h(x) = t(x) for each example (x,
t(x)) in D
CONSISTENT HYPOTHESES

D = { (x1, t(x1)), (x2, t(x2)), (x3, t(x3)), (x4, t(x4)) }

d1 d2 d3 d4

Which following hypotheses are consistent with which

examples?

h1 = <?, Warm, ?, Strong, ?, ?>

h2 = <Sunny, ?, ?, Strong, ?, Change>

CONSISTENT HYPOTHESIS
 Given
 training
data D
 hypothesis h in H

 h is consistent with D if h is consistent with every d in D

 h1 = <?, Warm, ?, Strong, ?, ?> is consistent with D

 h2 = <Sunny, ?, ?, Strong, ?, Change> is inconsistent
with D
CONSISTENT HYPOTHESES
 All hypotheses of H, which are consistent with the
training data D

h1 = <?, Warm, ?, Strong, ?, ?>

h2 = <Sunny, ?, ?, Strong, ?, ?>
h3 = <?, Warm, ?, ?, ?, ?>
h4 = <Sunny, Warm, ?, Strong, ?, ?>
h5 = <Sunny, ?, ?, ?, ?, ?>
h6 = <Sunny, Warm, ?, ?, ?, ?>
USE OF CONSISTENT HYPOTHESES
 Useful to predict the outcome of unseen instance
z = <Rainy, Cold, High, Strong, Warm, Same>

 Majority of h1(z), h2(z), h3(z), h4(z), h5(z), h6(z)

VERSION SPACE
 Given
 Trainingdata D
 Hypotheses space H

 Version space V
 All consistent hypotheses with D
VERSION SPACES
VERSION SPACES
 The focus is on algorithms that generate version space
 LIST-THEN-ELIMINATE
algorithm
 CANDIDATE-ELIMINATION algorithm
THE LIST-THEN-ELIMINATE ALGORITHM
 Enumerate members of H
 Eliminate h which is inconsistent with D

 Crude and impractical method

CANDIDATE ELIMINATION ALGORITHM
 Avoids enumeration of members in H
 Exploits more-general-than relation on H

 Exploits Version Space’s compact specification by its

two subsets
 General boundary
 Specific boundary
COMPACT SPECIFICATION OF
VERSION SPACE FOR SPORTS EXAMPLE
 Version space = {h1, h2, h3, h4, h5, h6}

h1 = <?, Warm, ?, Strong, ?, ?>

h2 = <Sunny, ?, ?, Strong, ?, ?>
h3 = <?, Warm, ?, ?, ?, ?>
h4 = <Sunny, Warm, ?, Strong, ?, ?>
h5 = <Sunny, ?, ?, ?, ?, ?>
h6 = <Sunny, Warm, ?, ?, ?, ?>
COMPACT SPECIFICATION OF
VERSION SPACE FOR SPORTS EXAMPLE
GENERIC AND SPECIFIC BOUNDARIES
 G = { g in V : there is no g’ in V such that g’ is general
than g }
 S = { s in V: there is no s’ in V such that s’ is specific
than s }
CANDIDATE ELIMINATION ALGO
S = { < , , , , , > }
G = { <?,?,?,?,?,?> }

for every d in D
if d is + then generalize S
if d is – then specialize G
TRACING CE FOR SPORTS EXAMPLE

x1 = (Sunny, Warm, Normal, Strong, Warm, Same) +

x2 = (Sunny, Warm, High, Strong, Warm, Same) +
x3 = (Rainy, Cold, High, Strong, Warm, Change) –
x4 = (Sunny, Warm, High, Strong, Cool, Change) +
S0 = { < , , , , , > }

G0 = { <?,?,?,?,?,?> }
S0 = { < , , , , , > }

x1 = (Sunny, Warm, Normal, Strong, Warm, Same) +

G0 = { <?,?,?,?,?,?> }
S0 = { < , , , , , > }

S1 = { <Sunny, Warm, Normal, Strong, Warm, Same> }

x1 = (Sunny, Warm, Normal, Strong, Warm, Same) +

G1 = {<?,?,?,?,?,?> }

G0 = {<?,?,?,?,?,?> }
S0 = { < , , , , , > }

S1 = { <Sunny, Warm, Normal, Strong, Warm, Same> }

x1 = (Sunny, Warm, Normal, Strong, Warm, Same) +

x2 = (Sunny, Warm, High, Strong, Warm, Same) +

G1 = {<?,?,?,?,?,?> }

G0 = {<?,?,?,?,?,?> }
S0 = { < , , , , , > }

S1 = { <Sunny, Warm, Normal, Strong, Warm, Same> }

S2 = {<Sunny, Warm, ?, Strong, Warm, Same> }

x1 = (Sunny, Warm, Normal, Strong, Warm, Same) +

x2 = (Sunny, Warm, High, Strong, Warm, Same) +

G2 = {<?,?,?,?,?,?> }

G1 = {<?,?,?,?,?,?> }
G0 = {<?,?,?,?,?,?> }
S2 = <Sunny, Warm, ?, Strong, Warm, Same>