INDUCTIVE BIAS

 The fundamental questions for inductive inference

1. What if the target concept is not contained in the hypothesis space?
2. Can we avoid this difficulty by using a hypothesis space that includes every possible hypothesis?
3. How does the size of this hypothesis space influence the ability of the algorithm to generalize to unobserved instances?
4. How does the size of the hypothesis space influence the number of training examples that must be observed?

 These fundamental questions are examined in the context of the CANDIDATE- ELIMINTION algorithm

A Biased Hypothesis Space

Suppose the target concept is not contained in the hypothesis space H, then obvious solution is to enrich the hypothesis space to include every possible hypothesis.

• Consider the EnjoySport example in which the hypothesis space is restricted to include only conjunctions of attribute values. Because of this restriction, the hypothesis space is unable to represent even simple disjunctive target concepts such as

"Sky = Sunny or Sky = Cloudy."

• The following three training examples of disjunctive hypothesis, the algorithm would find that there are zero hypotheses in the version space

áSunny Warm Normal Strong Cool Changeñ                    Y
áCloudy Warm Normal Strong Cool Changeñ                  Y
áRainy Warm Normal Strong Cool Changeñ                     N

• If Candidate Elimination algorithm is applied, then it end up with empty Version Space. After first two training example

S= á? Warm Normal Strong Cool Changeñ

• This new hypothesis is overly general and it incorrectly covers the third negative training example! So H does not include the appropriate c.
• In this case, a more expressive hypothesis space is required.