Hypothesis Space Search & Inductive Bias (ID3)

Source: Unit 1 §8

Like every inductive learner, ID3 searches a space of hypotheses looking for one that fits the training data. Naming that space, and naming what ID3 prefers inside it, is what turns "greedy tree building" into a statement about what the algorithm will and will not learn.

ID3 as a hypothesis-space search

≡FactsThe search, in four terms

• The hypothesis space is the set of all possible decision trees.
• The search is a simple-to-complex, hill-climbing search.
• The start point is the empty tree; ID3 then considers progressively more elaborate trees.
• The evaluation function guiding the hill-climb is information gain.

ID3 climbs from the empty tree to progressively more elaborate trees, and information gain is the only thing telling it which way is uphill.

Key properties of ID3's search

Property	Explanation
Complete hypothesis space	The space of all decision trees is a complete space of finite discrete-valued functions. Every such function is representable by some tree, so ID3 avoids the risk - faced by conjunction-only methods like Find-S - that the target function is not even in the space.
Single current hypothesis	ID3 keeps only one current hypothesis as it searches. Unlike Candidate-Elimination it therefore cannot say how many alternative trees are consistent with the data, nor pose queries designed to discriminate among them.
No backtracking	In its pure form ID3 does no backtracking: once an attribute is picked at a level, it is never reconsidered. The risk is convergence to a locally rather than globally optimal tree.
Statistically based, uses all examples	Each choice is made from all training examples at once, via information gain, rather than from individual examples as in Find-S and Candidate-Elimination. The advantage is that ID3 is far less sensitive to errors and noise in any single example, and is easily extended to noisy data.

⇄CompareChoosing from all examples vs one example at a time

ID3 (statistical, batch)Information gain is computed over the whole current set of examples, so one mislabelled row barely moves the decision. Extends naturally to noisy data.

Find-S / Candidate-Elimination (incremental)The hypothesis is revised from individual examples, so a single erroneous example can distort the hypothesis badly.

Inductive bias of ID3

Inductive bias is the set of assumptions a learner uses to generalize beyond the training data. For ID3 it is the basis on which it picks one consistent tree out of the many that fit.

Given a data set, many trees are consistent with it. Which does ID3 return? The first acceptable tree encountered in its simple-to-complex hill-climbing search. Roughly, that strategy:

1. Prefers shorter trees over longer ones.
2. Prefers trees that place high-information-gain attributes closest to the root.

◎Exam cueThe two statements of ID3's bias

Approximate: shorter trees are preferred over larger trees.

Closer approximation: shorter trees are preferred over longer trees, and trees that place high-information-gain attributes near the root are preferred over those that do not.

Preference bias, not restriction bias

This is a preference (search) bias - a preference for certain hypotheses within a space that contains all of them - and not a restriction bias. ID3 searches a complete space but prefers some trees in it. Candidate-Elimination is the contrast: it carries a restriction bias, because its hypothesis space is incomplete to begin with.

Both learners narrow the answer down, but at different moments: a preference bias orders a complete space, a restriction bias deletes most of it before the search begins.

⚠GotchaDo not call ID3's bias a restriction bias

The distinction is the whole point of the section. A restriction bias can make the target function unreachable; a preference bias never can, it only changes which of the reachable hypotheses is returned first.

✓Best practiceJustify the preference with Occam's Razor

The reason to prefer short trees is Occam's Razor: prefer the simplest hypothesis that fits the data. Quote it whenever you are asked why ID3's bias is a reasonable one rather than an arbitrary one.