Searching in Decision Trees

• ID3 can be seen as searching the space of possible decision trees
• simple to complex hill-climbing search
• complete hypothesis space of finite discrete-valued functions
• ID3 maintains only a single current hypothesis
• can't tell how many alternative decision trees are consistent with the available training data
• can't pose queries for new instances that optimally resolve the competing hypotheses
• pure ID3 performs no backtracking - can converge to local optimum
• ID3 not incremental - less sensitive to errors in individual training instances - easily extended to handle noisy data