Artificial Intelligence - Old Questions

7.  How concepts of most specific consistent hypothesis and most general consistent hypothesis are used in learning through examples. How generalization specialization tree is maintained for these concepts?

The most specific hypotheses (i.e., the specific boundary SB) are the hypotheses that cover observed positive training examples, and as little of the remaining feature space as possible. These are hypotheses which if reduced any further would exclude a positive training example, and hence become inconsistent. These minimal hypotheses essentially constitute a (pessimistic) claim that the true concept is defined just by the positive data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be negative. (I.e., if data has not previously been ruled in, then it's ruled out.)

The most general hypotheses (i.e., the general boundary GB) are those which cover the observed positive training examples, but also cover as much of the remaining feature space without including any negative training examples. These are hypotheses which if enlarged any further would include a negative training example, and hence become inconsistent.

Candidate Elimination Algorithm is used to construct generalization specialization tree.

• Nodes in the generalization tree are connected to a model that matches everything in its subtree.
• Nodes in the specialization tree are connected to a model that matches only one thing in its subtree.

Method: