ML - Candidate Elimination Algorithm

The candidate elimination algorithm incrementally builds the version space given a hypothesis space H and a set E 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 the Find-S algorithm.
• Consider both positive and negative examples.
• Actually, positive examples are used here as the Find-S algorithm (Basically they are generalizing from the specification).
• While the negative example is specified in the generalizing form.

Terms Used:  

• Concept learning: Concept learning is basically the 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'...}: The number of pi depends on a number of attributes.
• Version Space: It is an intermediate of general hypothesis and Specific hypothesis. It not only just writes one hypothesis but a set of all possible hypotheses 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.

Example:

Consider the dataset given below:

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', ?, ?] 

The Candidate Elimination Algorithm (CEA) is an improvement over the Find-S algorithm for classification tasks. While CEA shares some similarities with Find-S, it also has some essential differences that offer advantages and disadvantages. Here are some advantages and disadvantages of CEA in comparison with Find-S:

Advantages of CEA over Find-S:

1. Improved accuracy: CEA considers both positive and negative examples to generate the hypothesis, which can result in higher accuracy when dealing with noisy or incomplete data.
2. Flexibility: CEA can handle more complex classification tasks, such as those with multiple classes or non-linear decision boundaries.
3. More efficient: CEA reduces the number of hypotheses by generating a set of general hypotheses and then eliminating them one by one. This can result in faster processing and improved efficiency.
4. Better handling of continuous attributes: CEA can handle continuous attributes by creating boundaries for each attribute, which makes it more suitable for a wider range of datasets.

Disadvantages of CEA in comparison with Find-S:

1. More complex: CEA is a more complex algorithm than Find-S, which may make it more difficult for beginners or those without a strong background in machine learning to use and understand.
2. Higher memory requirements: CEA requires more memory to store the set of hypotheses and boundaries, which may make it less suitable for memory-constrained environments.
3. Slower processing for large datasets: CEA may become slower for larger datasets due to the increased number of hypotheses generated.
4. Higher potential for overfitting: The increased complexity of CEA may make it more prone to overfitting on the training data, especially if the dataset is small or has a high degree of noise.