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 )]
It can be simply using the candidate elimination algorithm. According to that the reasons can be summarized as follows.
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 )
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.