Inductive bias is the set of assumptions that, together with the training data, deductively justify the classifications assigned by the learner to future instances
Given a collection of training examples, there are typically many decision trees consistent with these examples. Which of these decision trees does ID3 choose?
ID3 search strategy
- Selects in favour of shorter trees over longer ones
- Selects trees that place the attributes with highest information gain closest to the root.
Approximate inductive bias of ID3: Shorter trees are preferred over larger trees
- Consider an algorithm that begins with the empty tree and searches breadth first through progressively more complex trees.
- First considering all trees of depth 1, then all trees of depth 2, etc.
- Once it finds a decision tree consistent with the training data, it returns the smallest consistent tree at that search depth (e.g., the tree with the fewest nodes).
- Let us call this breadth-first search algorithm BFS-ID3.
- BFS-ID3 finds a shortest decision tree and thus exhibits the bias "shorter trees are preferred over longer trees.
A closer approximation to the inductive bias of ID3: Shorter trees are preferred over longer trees. Trees that place high information gain attributes close to the root are preferred over those that do not.
- ID3 can be viewed as an efficient approximation to BFS-ID3, using a greedy heuristic search to attempt to find the shortest tree without conducting the entire breadth-first search through the hypothesis space.
- Because ID3 uses the information gain heuristic and a hill climbing strategy, it exhibits a more complex bias than BFS-ID3.
- In particular, it does not always find the shortest consistent tree, and it is biased to favour trees that place attributes with high information gain closest to the root.
0 Comments