Scribd
Upload
12 views7 pages

Candidate Elimination Algorithm in ML

Demonstrate the working model and principle of candidate elimination algorithm

Uploaded by

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

Candidate Elimination Algorithm in ML

Demonstrate the working model and principle of candidate elimination algorithm

Uploaded by

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

MACHINE LEARNING LABORATORY

2 Demonstrate the working model and principle of candidate elimination


Aim algorithm
For a given set of training data examples stored in a .CSV file, implement and
Program demonstrate the Candidate-Elimination algorithm to output a description of
the set of all hypotheses consistent with the training examples

CONCEPT - CANDIDATE-ELIMINATION LEARNING ALGORITHM

The CANDIDATE-ELIMINTION algorithm computes the version space containing all


hypotheses from H that are consistent with an observed sequence of training examples.

CANDIDATE-ELIMINATION Algorithm
Initialize G to the set of maximally general hypotheses in H
Initialize S to the set of maximally specific hypotheses in H
For each training example d, do
• If d is a positive example
• Remove from G any hypothesis inconsistent with d
• For each hypothesis s in S that is not consistent with d
• Remove s from S
• Add to S all minimal generalizations h of s such that
• h is consistent with d, and some member of G is more general than h
• Remove from S any hypothesis that is more general than another hypothesis in S

• If d is a negative example
• Remove from S any hypothesis inconsistent with d
• For each hypothesis g in G that is not consistent with d
• Remove g from G
• Add to G all minimal specializations h of g such that
• h is consistent with d, and some member of S is more specific than h
• Remove from G any hypothesis that is less general than another hypothesis in G

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 1
MACHINE LEARNING LABORATORY

To illustrate this algorithm, assume the learner is given the sequence of training examples
from the EnjoySport task

Example Sky AirTemp Humidity Wind Water Forecast EnjoySport


1 Sunny Warm Normal Strong Warm Same Yes
2 Sunny Warm High Strong Warm Same Yes
3 Rainy Cold High Strong Warm Change No
4 Sunny Warm High Strong Cool Change Yes

CANDIDATE-ELIMINTION algorithm begins by initializing the version space to the set of


all hypotheses in H;

Initializing the G boundary set to contain the most general hypothesis in H


G0 ?, ?, ?, ?, ?, ?

Initializing the S boundary set to contain the most specific (least general) hypothesis
S0 , , , , , 

• When the first training example is presented, the CANDIDATE-ELIMINTION algorithm


checks the S boundary and finds that it is overly specific and it fails to cover the positive
example.
• The boundary is therefore revised by moving it to the least more general hypothesis that
covers this new example
• No update of the G boundary is needed in response to this training example because Go
correctly covers this example

• When the second training example is observed, it has a similar effect of generalizing S
further to S2, leaving G again unchanged i.e., G2 = G1 = G0

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 2
MACHINE LEARNING LABORATORY

• Consider the third training example, this negative example reveals that the G boundary
of the version space is overly general, that is, the hypothesis in G incorrectly predicts
that this new example is a positive example.
• The hypothesis in the G boundary must therefore be specialized until it correctly
classifies this new negative example

Given that there are six attributes that could be specified to specialize G2, why are there only
three new hypotheses in G3?
For example, the hypothesis h = (?, ?, Normal, ?, ?, ?) is a minimal specialization of G 2 that
correctly labels the new example as a negative example, but it is not included in G3. The reason
this hypothesis is excluded is that it is inconsistent with the previously encountered positive
examples

• Consider the fourth training example.

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 3
MACHINE LEARNING LABORATORY

• This positive example further generalizes the S boundary of the version space. It also
results in removing one member of the G boundary, because this member fails to
cover the new positive example

After processing these four examples, the boundary sets S4 and G4 delimit the version space
of all hypotheses consistent with the set of incrementally observed training examples.

Training Instances: (The below data is saved as [Link] file)

Sky AirTemp Humidity Wind Water Forecast EnjoySport

Sunny Warm Normal Strong Warm Same Yes


Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cool Change Yes

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 4
MACHINE LEARNING LABORATORY

Program:

import pandas as pd

data = pd.read_csv('[Link]')
concepts = [Link][:, :-1].values
target = [Link][:, -1].values
n=len(concepts[0])-1
specific_h = ['0'] * n
general_h = ['?'] * n
print("The initialization of the specific and general hypothesis ")
print(" S0:",specific_h,"\n G0:",general_h)

def learn(concepts, target):


specific_h = concepts[0].copy()
general_h = [["?" for _ in range(len(specific_h))] for _ in range(len(specific_h))]
for i, h in enumerate(concepts):
if target[i] == "yes":
print(f"\n the {i+1} training instance is Positive \n",concepts[i])
for x in range(len(specific_h)):
if h[x] != specific_h[x]:
specific_h[x] = '?'
general_h[x][x] = '?'
else:
print(f"\nThe {i+1} training instance is Negative \n",concepts[i])
for x in range(len(specific_h)):
if h[x] != specific_h[x]:
general_h[x][x] = specific_h[x]
else:
general_h[x][x] = '?'

print(f"S{i+1}:\n", specific_h)
print(f"G{i+1}:\n", general_h)

general_h = [h for h in general_h if h != ['?' for _ in range(len(specific_h))]]


return specific_h, general_h

s_final, g_final = learn(concepts, target)

print("\nThe Final Specific Hypothesis:")


print(s_final)
print("\nThe Final General Hypothesis:")
print(g_final)

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 5
MACHINE LEARNING LABORATORY

Output:

The initialization of the specific and general hypothesis


S0: ['0', '0', '0', '0', '0']
G0: ['?', '?', '?', '?', '?']

The 1 training instance is Positive


['sunny' 'warm' 'normal' 'strong' 'warm' 'same']
S1:
['sunny' 'warm' 'normal' 'strong' 'warm' 'same']
G1:
[['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?']]

The 2 training instance is Positive


['sunny' 'warm' 'high' 'strong' 'warm' 'same']
S2:
['sunny' 'warm' '?' 'strong' 'warm' 'same']
G2:
[['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?']]

The 3 training instance is Negative


['rainy' 'cold' 'high' 'strong' 'warm' 'change']
S3:
['sunny' 'warm' '?' 'strong' 'warm' 'same']
G3:
[['sunny', '?', '?', '?', '?', '?'],
['?', 'warm', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', 'same']]

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 6
MACHINE LEARNING LABORATORY

The 4 training instance is Positive


['sunny' 'warm' 'high' 'strong' 'cool' 'change']
S4:
['sunny' 'warm' '?' 'strong' '?' '?']
G4:
[['sunny', '?', '?', '?', '?', '?'],
['?', 'warm', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?'],
['?', '?', '?', '?', '?', '?']]

The Final Specific Hypothesis:


['sunny' 'warm' '?' 'strong' '?' '?']

The Final General Hypothesis:


[['sunny', '?', '?', '?', '?', '?'],
['?', 'warm', '?', '?', '?', '?']]

Deepak D, Assistant Professor, Dept. of AI & ML, Canara Engineering College, Mangaluru 7

Common questions

Powered by AI

A negative training example necessitates adjustments to the G boundary because it indicates that the current hypotheses are too general if they incorrectly predict this example as positive. The G boundary is specialized to exclude the negative instance while ensuring consistency with prior positive examples by specialising hypotheses so that they remain more general than any hypothesis in the S set .

Upon encountering the fourth positive example, the Candidate-Elimination algorithm further generalizes the S boundary and potentially removes any member of the G boundary that fails to cover the new positive example. This adjustment ensures the inclusion of the new example into the hypothesis without contradicting negative instances .

A hypothesis is excluded from the G boundary during specialization if it is inconsistent with previously encountered positive examples. This ensures that the specialized hypotheses remain valid across the entire set of observed training examples, maintaining consistency with the positive instances .

After processing four examples, the final S boundary generalized to ['sunny', 'warm', '?', 'strong', '?', '?'], reflecting a minimal set of specific attributes consistent with all positive examples. The G boundary contained more general hypotheses like ['sunny', '?', '?', '?', '?', '?'] and ['?', 'warm', '?', '?', '?', '?'], which cover all training instances without being overly specific .

Throughout the EnjoySport task, the S boundary evolved to generalize from covering a single instance to representing a broader category capturing all positive instances without contradictions. Initially, it transformed after each positive example, and during negative examples, the G boundary adjusted by specializing to remain consistent with all prior data without error .

The Candidate-Elimination algorithm involves initializing the G set with the most general hypotheses and the S set with the most specific hypotheses. For each positive training example, it removes hypotheses from G inconsistent with the example and refines S by adding consistent hypotheses. For negative examples, it refines G by adding consistent specializations and removes inconsistent hypotheses from S .

'Minimal specializations' and 'minimal generalizations' are crucial in refining the G and S sets, respectively. Minimal generalizations generalize the specific hypotheses enough to cover new positive examples, while minimal specializations restrict general hypotheses to exclude negative examples without overfitting, ensuring correctness across all encountered examples .

When a positive training example is encountered, the algorithm removes hypotheses from the general boundary G that are inconsistent with the example. It then updates the specific boundary S by adding minimal generalizations that cover the example and are more specific than any hypothesis in the G boundary .

The initial specific hypothesis is set to the first positive instance to ensure that it definitely covers at least one observed instance of the concept to be learned. This serves as a starting point for all further specific hypotheses, which might be generalized as necessary to accommodate new positive instances .

The Candidate-Elimination algorithm does not inherently handle noise, such as false positives and negatives, effectively. It assumes that the training data is noise-free, which can lead to overfitting when the version space is refined to exclude noisy examples. The algorithm relies on precise positive and negative examples to accurately generalize and specialize hypotheses .

You might also like