Candidate elimination algorithm lecture example

1.4k views Asked by At

I am looking through some lecture slides and cannot understand why the bold hypothesis at last G are just discarded, I can come to the same answer but don't understand why they're just discarded.

   sky           temperature         humidity
 |     |        |          |        |       |
Sunny  Rainy      Warm       Coo     Normal   Low

and the set of positive and negative training examples:

    1.      ( S W N )+)
    2.      ( R C L )-)
    3 .     ( S C N )+)
    4.      ( S W L )-)

Training with the first example: ( S W N ) +) generalizing…

G = [( ? ? ? )] S = [( S W N )]

Training with the second example: ( R C L ) -) specializing…

G = [( S ? ? ) ( ? W ? ) ( ? ? N )
S = [( S W N )]

Training with the third example: ( S C N ) +) generalizing…

G = [( S ? ? )( ? ? N )] (the other is discarded )
S = [( S ? N )]

Training with the fourth example: ( S W L ) -) specializing…

G = [( S C ? )( S ? N )( R ? N )(? C N)] (bold are discarded )
S = [( S ? N )]

Convergence, the learned concept must be: [( S ? N )]

1

There are 1 answers

0
Sudeepa Nadeeshan On

enter image description here

G = [( S C ? )( S ? N )( R ? N )(? C N)] (bold are discarded )

It can be simply using the candidate elimination algorithm. According to that the reasons can be summarized as follows.

  1. Inconsistent hypothesis: According to the algorithm we have to first remove the hypotheses which are not consistent with target data(D)

    In this case ( R ? N ) is removed it's inconsistent with ( S ? N )

  2. Specific boundary being more general than the general boundary.

    If the specific boundy become more specific that the general one. There can be a boundary overlapping.

    if we compare derived ( S C ? ) with ( S ? N ) , we can compare middle c with ? of (S ? N). The derived one having a constant makes it more specific compared to the specific boundary. So it should be removed. Same goes with (? C N).

I see the question is bit older but I hope someone would find this useful.