Scribd
Upload
4 views2 pages

Candidate Elimination Algorithm

The candidate elimination algorithm incrementally constructs a version space based on a hypothesis space and a set of examples, updating general and specific boundaries with each new example. It processes both positive and negative examples, generalizing from positive cases and making general hypotheses more specific from negative cases. The algorithm involves initializing hypotheses, processing training examples, and synchronizing the resulting general and specific hypotheses to produce the final output.

Uploaded by

sridhar2879
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

Candidate Elimination Algorithm

The candidate elimination algorithm incrementally constructs a version space based on a hypothesis space and a set of examples, updating general and specific boundaries with each new example. It processes both positive and negative examples, generalizing from positive cases and making general hypotheses more specific from negative cases. The algorithm involves initializing hypotheses, processing training examples, and synchronizing the resulting general and specific hypotheses to produce the final output.

Uploaded by

sridhar2879
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

ML – Candidate Elimination Algorithm

The candidate elimination algorithm incrementally builds the version space given a hypothesis space H
and a set D of examples. The examples are added one by one; each example possibly shrinks the version
space by removing the hypotheses that are inconsistent with the example. The candidate elimination
algorithm does this by updating the general and specific boundary for each new example.

 You can consider this as an extended form of Find-S algorithm.

 Consider both positive and negative examples.

 Actually, positive examples are used here as Find-S algorithm (Basically they are generalizing
from the specification).

 While the negative example is specified from generalize form.

Terms Used:

 Concept learning: Concept learning is basically learning task of the machine (Learn by Train
data)

 General Hypothesis: Not Specifying features to learn the machine.

 G = {‘?’, ‘?’,’?’,’?’…}: Number of attributes

 Specific Hypothesis: Specifying features to learn machine (Specific feature)

 S= {‘pi’,’pi’,’pi’…}: Number of pi depends on number of attributes.

 Version Space: It is intermediate of general hypothesis and Specific hypothesis. It not only just
written one hypothesis but a set of all possible hypothesis based on training data-set.

Algorithm:

Step1: Load Data set

Step2: Initialize General Hypothesis and Specific Hypothesis.

Step3: For each training example

Step4: If example is positive example

if attribute_value == hypothesis_value:

Do nothing

else:
replace attribute value with '?' (Basically generalizing it)

Step5: If example is Negative example

Make generalize hypothesis more specific.

Algorithmic steps:

Initially : G = [[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?],

[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?]]

S = [Null, Null, Null, Null, Null, Null]

For instance 1 : <'sunny','warm','normal','strong','warm ','same'> and positive output.

G1 = G

S1 = ['sunny','warm','normal','strong','warm ','same']

For instance 2 : <'sunny','warm','high','strong','warm ','same'> and positive output.

G2 = G

S2 = ['sunny','warm',?,'strong','warm ','same']

For instance 3 : <'rainy','cold','high','strong','warm ','change'> and negative output.

G3 = [['sunny', ?, ?, ?, ?, ?], [?, 'warm', ?, ?, ?, ?], [?, ?, ?, ?, ?, ?],

[?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, ?], [?, ?, ?, ?, ?, 'same']]

S3 = S2

For instance 4 : <'sunny','warm','high','strong','cool','change'> and positive output.

G4 = G3

S4 = ['sunny','warm',?,'strong', ?, ?]

At last, by synchronizing the G4 and S4 algorithm produce the output.

Output :

G = [['sunny', ?, ?, ?, ?, ?], [?, 'warm', ?, ?, ?, ?]]

S = ['sunny','warm',?,'strong', ?, ?]

You might also like