Candidate Elimination Learning Algorithm
Candidate Elimination Learning Algorithm is a method for learning concepts from data that is supervised. In this blog, we’ll explain the candidate elimination learning algorithm with examples.
Given a hypothesis space H and a collection E of instances, the candidate elimination procedure develops the version space progressively.
The examples are introduced one by one, with each one potentially shrinking the version space by deleting assumptions that contradict the example. For each new case, the candidate elimination method updates the general and particular boundaries.
To understand the algorithm better, let us have a look at some terminologies and what it means.
What is Version Space?
It’s a cross between a generic and a specific theory. It didn’t simply write one hypothesis; it wrote a list of all feasible hypotheses based on the training data.
With regard to hypothesis space H and training examples D, the version space, denoted as VSH,D, is the subset of hypotheses from H that are consistent with the training instances in D.
For example, consider the following dataset. The classic example of EnjoySport.
In the above example, We have two hypotheses from H in the case above, both of which are consistent with the training dataset.
h1=< Sunny, Warm, ?, Strong, ?, ?> and
h2=< ?, Warm, ?, Strong, ?, ?>
As a result, the collection of hypotheses h1, h2 is referred to as a Version Space.
Specific Hypothesis:
If a hypothesis, h, covers none of the negative cases and there is no other hypothesis, h′, that covers none of the negative examples, then h is strictly more general than h′, then h is said to be the most specific hypothesis.
The specific hypothesis fills in important details about all the variables given in the hypothesis.
S = < ‘ϕ’, ‘ϕ’, ‘ϕ’, ……, ‘ϕ’ >
General Hypothesis:
In general, a hypothesis is an explanation for anything. The general hypothesis explains the relationship between the key variables in general. I want to watch Avengers, for example, is a general hypothesis for selecting a movie.
G = < ‘?’, ‘?’, ‘?’, …..’?’>
Representations:
- The most specific hypothesis is represented using ϕ.
- The most general hypothesis is represented using ?.
Why Candidate Elimination Algorithm?
Candidate Elimination Learning Algorithm addresses several of the limitations of FIND-S.
Although the FIND-S algorithm outputs a hypothesis from H, that is consistent with the training examples, this is just one of many hypotheses from H that might fit the training data equally well.
The key idea in the CANDIDATE-ELIMINATlON Algo is to output a description of the set of all hypotheses consistent with the training examples.
Candidate Elimination:
Unlike Find-S(#Link to Find-S) algorithm, the Candidate Elimination algorithm considers not just positive but negative samples as well. It relies on the concept of version space.
At the end of the algorithm, we get both specific and general hypotheses as our final solution.
For a positive example, we move from the most specific hypothesis to the most general hypothesis.
For a negative example, we move from the most general hypothesis to the most specific hypothesis.
Candidate Elimination Algorithm:
1. Initialize both specific and general hypotheses.
S = < ‘ϕ’, ‘ϕ’, ‘ϕ’, ….., ‘ϕ’ >
G = < ‘?’, ‘?’, ‘?’, ….., ’?’>
Depending on the number of attributes.
2. Take the next example, if the taken example is positive make a specific hypothesis to general.
3. If the taken example is negative make the general hypothesis to a more specific hypothesis.
Let’s have a look at an example to see how the Candidate Elimination Algorithm works.
- Initializing both specific and general hypotheses.
G0 = < <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?>,
<?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ? >>
S0 = < ϕ, ϕ, ϕ, ϕ, ϕ, ϕ>
- When the first training example is supplied (in this case, a positive example), the Candidate Elimination method evaluates the S boundary and determines that it is too specific, failing to cover the positive example.
As a result, the border is shifted to the least general hypothesis that covers this new case. S1 indicates the updated border.
No update for G1 is needed in this example as G0 accurately represents the training instance.
G1 = G0 = < <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?>,
<?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ? >>
S1 = < ‘Sunny’, ‘warm’, ‘normal’, ‘strong’, ‘warm ‘, ‘same’>
- When the second (also positive) training example is observed, it has a similar effect of generalizing S to S2, while leaving G intact (i.e., G2 = G1 = G0).
G2 = G0 = < <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?>,
<?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ?> , <?, ?, ?, ?, ?, ? >>
S2 = < ‘Sunny’, ‘warm’, ‘?’, ‘strong’, ‘warm ‘, ‘same’>
- Similarly, considering the training instance 3, This negative example demonstrates that the version space’s G border is extremely general;
As a result, the hypothesis in the G border must be specialized until it appropriately categorizes this new negative case.
G3 = < <‘Sunny’, ?, ?, ?, ?, ?>, <?, ‘warm’, ?, ?, ?, ?>, <?, ?, ?, ?, ?, ?>, <?, ?, ?, ?, ?, ?>, <?, ?, ?, ?, ?, ?>, <?, ?, ?, ?, ?, ‘same’> >
S3 = S2 = < ‘Sunny’, ‘warm’, ‘?’, ‘strong’, ‘warm ‘, ‘same’>
- The fourth training example, generalizes the version space’s S boundary. It also results in the removal of one G border member, as this one fails to cover the new positive example.
G4 = < <‘Sunny’, ?, ?, ?, ?, ?>, <?, ‘warm’, ?, ?, ?, ?> >
S4 = <‘Sunny’, ‘warm’, ?, ‘strong’, ?, ?>
Finally, the result is produced by synchronizing the G4 and S4 algorithms.
The above diagram depicts the whole version space, including the hypotheses bounded by S4 and G4. The order in which the training examples are given has no impact on the learned version space.
The final hypothesis is,
G = <[‘Sunny’, ?, ?, ?, ?, ?>, <?, ‘warm’, ?, ?, ?, ?>>
S = <‘Sunny’, ‘warm’, ?, ‘strong’, ?, ?>
Reference