Decision Tree Classification
Decision tree learning searches for a tree that minimizes the relevant bound, but solving that search exactly is computationally hard.
Why Tree Learning Needs a Search Strategy
Decision tree classification can be viewed as a search problem. The learner wants a tree that minimizes the relevant bound on the tree's learning performance. In principle, it could try to compare complete trees and choose the best one. In practice, finding that tree exactly is computationally hard, so practical algorithms construct a tree step by step instead.
The central difficulty is not merely assigning labels. It is selecting the complete decision structure. Because exact search is computationally hard, the practical method replaces one difficult global choice with a sequence of local choices.
The Initial Root Leaf
A practical tree-growing algorithm begins with a single root leaf. That leaf represents all labeled training examples currently reaching the tree. Before any split is selected, the leaf receives the majority label among those examples. This gives the tree a prediction even before it has any internal decision structure.
A Majority Label Before Splitting
Imagine a training set reaching one root leaf. The examples have two possible class labels, and one label occurs more often than the other.
Represent the examples: The single root leaf stands for every labeled example in the training set.
Assign the initial prediction: The algorithm gives the root leaf the majority label.
Prepare for comparison: The learner can now evaluate whether a feature-based split would improve the tree.
The tree begins with one labeled root leaf, even though no feature test has been selected yet.
Comparing Candidate Splits
After the current leaf has a majority-label prediction, the learner considers possible feature-based splits. A gain measure compares the improvement offered by those candidates. The gain procedure receives a training set and a feature index, evaluates the gain associated with splitting according to that feature, and turns several possible decisions into comparable candidates.
Choosing Between Two Current Candidates
A growing tree has one leaf to consider. The learner evaluates two available feature-based splits.
Keep the current leaf as the baseline: The leaf already has a prediction from the majority vote.
Evaluate each feature: The gain procedure compares the improvement offered by splitting according to each candidate feature.
Select the better current action: The candidate with the better gain is preferred for this stage, unless the algorithm chooses not to split.
Gain guides the next local decision. It does not by itself prove that the completed tree will be globally optimal.
Recursive Partitioning
When the learner replaces a leaf with a selected feature-based decision structure, the branches represent the outcomes of that split. The examples reaching the original leaf are consequently represented in the resulting child leaves according to those branch outcomes. The procedure can then continue evaluating leaves in the growing tree.
- Start with one root leaf containing the labeled training examples.
- Give that leaf the majority label.
- Evaluate candidate feature-based splits with a gain measure.
- Choose the locally best next action, or choose not to split.
- Replace the selected leaf with a decision structure whose branches represent the split outcomes.
- Continue evaluating leaves in the growing tree.
Greedy Choices and Global Quality
This construction is greedy because it chooses a locally best action at each stage. At a current leaf, the algorithm compares available splits using the gain measure and may choose the best one according to that criterion. It may also choose not to split. The decision is made using the information available at the current stage rather than by examining every possible completed tree.
| Locally best split | Globally optimal tree |
|---|---|
| A next action selected at the current stage | A complete tree selected for its overall performance |
| Uses a gain measure to compare current candidates | Requires considering the full tree-search problem |
| Supports practical step-by-step construction | Is difficult to find exactly |
| Does not guarantee the best completed tree | Is the target of the idealized global search |
A locally best split can lead to a tree that is not globally optimal because the gain measure evaluates the current comparison, whereas global quality depends on the complete decision structure. The practical algorithm accepts this distinction: it uses local decisions to make tree learning tractable rather than claiming that each local choice solves the entire search problem.
Common Misunderstandings
Assuming the tree is built by checking every possible complete tree.
The exact search for the best tree is computationally hard.
Fix:
Separate the global search goal from the practical greedy construction.Thinking the root leaf has no prediction until after the first split.
The root leaf is assigned the majority label before a split is selected.
Fix:
Remember that labeling happens before splitting.Treating gain as proof that a final tree will be optimal.
Gain compares the improvement offered by current candidate splits; it does not guarantee global optimality.
Fix:
Call it the locally preferred next action.Confusing a split with a complete tree.
A split replaces a leaf with a decision structure, after which the procedure can continue evaluating leaves.
Fix:
View the split as one step in recursive tree growth.
Check Your Understanding
What do you think happens?
A decision tree learner has just started. Before evaluating any feature split, what does the initial root leaf represent and what label does it receive?
Reveal answer
Answer: All labeled examples and their majority label
The practical construction begins with one root leaf representing the labeled examples. That leaf receives the majority label before a split is selected.
Explain, in your own words, why a split with the best current gain is not necessarily part of the globally optimal tree. Then describe the sequence from root leaf to candidate comparison to child leaves.
Hints
- Mention the difference between a current comparison and the complete tree.
- Include the majority label assigned to the initial root leaf.
- Explain that a selected split replaces a leaf with a decision structure.
Key Takeaways
- Finding the complete decision tree with the best relevant bound is computationally hard.
- Practical construction begins with one root leaf labeled by the majority class.
- A gain measure compares the improvement offered by candidate feature-based splits.
- Greedy growth selects a locally best action at the current stage or chooses not to split.
- A locally best split is not a guarantee of a globally optimal completed tree.
Key Takeaways
- Decision tree learning is a computationally hard global search problem.
- A practical learner starts with a majority-labeled root leaf.
- Gain compares candidate splits at the current stage.
- Greedy tree growth repeatedly makes local decisions and can continue after a leaf is split.
- Local gain does not guarantee global optimality.