Feature-Based Splitting
Decision tree learning searches for a tree that minimizes the relevant bound, but solving that search exactly is computationally hard.
Why Tree Search Is Difficult
Decision tree learning seeks a tree that minimizes the relevant bound. The difficulty is that the learner could consider different feature-based splits at different stages, producing many possible complete tree structures. Searching all of those possibilities and selecting the best complete tree is computationally hard.
The Initial Root Leaf
A practical tree-growing algorithm begins with one root leaf. This leaf represents all training examples that have reached the beginning of the tree. Before any split is selected, the leaf receives the majority label among those examples. This labeling step gives the current leaf a prediction even before the learner decides whether to replace it with a decision structure.
Label before splitting
Suppose the examples reaching the root leaf have two possible labels, and one label occurs more often than the other. What label should the initial leaf receive?
Collect the current examples: At the beginning, the root leaf represents all training examples reaching the tree.
Compare label counts: Identify which label is the majority among those examples.
Assign the leaf label: Give the root leaf the majority label before selecting a split.
The initial root leaf receives the majority label. Labeling the leaf and selecting a split are separate actions.
Comparing Candidate Splits
After the current leaf has a label, the learner can evaluate possible feature-based splits. A gain measure compares the improvement offered by those candidate splits. The gain procedure receives a training set and a feature index, then evaluates the gain associated with splitting according to that feature. The resulting gain values turn different feature choices into comparable candidates.
Keep two questions separate: Which label should the current leaf predict, and which feature-based split should be considered next? Majority voting answers the first question. Gain comparison helps answer the second.
Choosing among feature candidates
A current leaf has three candidate feature-based splits. The learner evaluates a gain for each candidate. How should it use those results?
Evaluate each feature: Use the training set and each feature index to obtain comparable gain values.
Compare the gains: Determine which candidate offers the strongest improvement according to the gain criterion.
Choose the next action: Select the locally best candidate, or choose not to split if that is the algorithm's current action.
The gain measure guides the current comparison. It does not establish that the complete tree will be globally optimal.
The Greedy Growth Loop
Practical tree construction is greedy. At each stage, the algorithm considers a current leaf, evaluates possible feature-based splits, and chooses a locally best action according to the gain criterion. It may also choose not to split. If it does split, the single leaf is replaced by a decision structure with child leaves representing the outcomes of that feature-based split. The procedure can then continue evaluating leaves in the growing tree.
Local Choice and Global Quality
The split with the best current gain is a locally best choice: it is best according to the comparison being made at the current stage. That does not guarantee that the completed tree will be globally optimal. A different first split could lead to a better sequence of later choices, but discovering that would require reasoning about complete tree structures. This is why a gain value is a criterion for the next action, not a promise about the final tree.
Assuming the highest gain proves that the final tree is optimal.
Gain measures the improvement for the current comparison. It does not evaluate every possible completed tree.
Fix:
Describe the result as a locally best next action, not as a proof of global optimality.Treating the majority label and the split choice as the same operation.
Labeling predicts at the current leaf, while splitting replaces that leaf with a decision structure.
Fix:
First understand the current leaf's label, then evaluate whether and how to split it.Assuming practical tree learning examines every complete tree.
The complete search is computationally hard, so practical algorithms use step-by-step local decisions.
Fix:
Explain tree construction as greedy search guided by a gain criterion.
Practice the Decision Sequence
Describe what happens when a practical decision tree learner reaches a leaf. Include the leaf's initial label, the role of candidate feature-based splits, the purpose of gain, and what happens after a split is selected.
Hints
- Begin with the majority label for the current leaf.
- Explain that gain values make candidate splits comparable.
- End by describing child leaves and continued evaluation.
What do you think happens?
A feature split has the highest gain at the current leaf. Does that alone prove that the completed decision tree is globally optimal?
Reveal answer
Answer: No, because gain guides the current local comparison.
The gain measure helps select a locally best next action. Finding the globally optimal complete tree remains computationally hard.
Key Takeaways
- Finding the best complete decision tree is computationally hard because the learner would need to search among many possible feature choices and tree structures.
- A practical algorithm starts with one root leaf and assigns it the majority label.
- A gain measure compares the improvement offered by candidate feature-based splits.
- Greedy construction repeatedly makes a locally best decision, splits when appropriate, and continues with the growing tree.
- A locally best split is not a guarantee that the resulting complete tree is globally optimal.
Key Takeaways
- Decision tree learning searches for a tree that minimizes the relevant bound, but exact search over complete trees is computationally hard.
- The construction begins with a single root leaf labeled by majority vote.
- Gain values make candidate feature-based splits comparable at the current stage.
- Greedy growth chooses a locally best action or chooses not to split, then continues evaluating the growing tree.
- Local gain is useful for the next decision but does not guarantee global optimality.