Issues in Decision Tree Learning

Source: Unit 1 §9

Two problems stand between plain ID3 and a usable tree:

1. Over-fitting the data.
2. Handling continuous-valued attributes.

Over-fitting

ID3 grows each branch just deeply enough to perfectly classify the training examples. That is exactly the wrong stopping rule when there is noise in the data, or when there are too few examples to represent the true target function. The tree then over-fits.

≡FactsThe formal definition

Given a hypothesis space H, a hypothesis h ∈ H over-fits the training data if there exists an alternative h' ∈ H such that:

• h has smaller error than h' on the training examples, but
• h' has smaller error than h over the entire distribution of instances.

In short: h looks better on the training data but is actually worse on unseen data.

Training accuracy never stops rising, so it can never tell you when to stop. Only the independent test set shows the peak, and the gap after it is the over-fitting.

#NumbersReading the diabetes over-fitting graph

• x-axis - the total number of nodes as the tree is built. y-axis - prediction accuracy.
• The solid line is accuracy on the training data. It always increases.
• The dashed line is accuracy on an independent test set. It first increases and then decreases, peaking at about 25 nodes here.
• Past the peak, elaborating the tree hurts test accuracy while training accuracy keeps rising. That growing gap is the over-fitting.

Avoiding over-fitting

#	Approach	Idea
1	Pre-pruning (stop early)	Stop growing the tree before it perfectly classifies the training data.
2	Post-pruning	Let the tree over-fit, then prune nodes back afterwards.

✓Best practicePrefer post-pruning

Post-pruning is more successful in practice. The reason is precise: in the stop-early approach it is hard to estimate exactly when to stop growing the tree, whereas after the fact you can measure whether removing a node helps.

Deciding the correct final tree size

≡FactsThree criteria

• Separate validation set - hold out data distinct from the training set and use it to evaluate the utility of pruning each node.
• Statistical test on all the data - train on everything, but apply a statistical test to decide whether expanding or pruning a node is likely to help beyond the training set. Quinlan (1986) uses a chi-square ($\chi^2$) test.
• Explicit complexity measure - measure the encoding size of the examples plus the tree, and stop when that encoding size is minimised. This is the Minimum Description Length principle.

Handling continuous-valued attributes

Basic ID3 assumes the attributes and the target are discrete. The target must stay discrete, but the attributes tested at decision nodes can be made continuous.

The trick is to dynamically create a new Boolean attribute $A_c$ that partitions the continuous value into intervals:

$$A_c = \begin{cases} \text{TRUE} & \text{if } A < c \\ \text{FALSE} & \text{otherwise} \end{cases}$$

That leaves exactly one question: how do you choose the threshold $c$? The answer is to pick the $c$ that gives the greatest information gain.

→StepsFinding the candidate thresholds

1. Sort the examples by the continuous attribute $A$.
2. Find adjacent examples whose target classification changes.
3. The candidate thresholds are the midpoints between those values. The optimal $c$ always lies at such a boundary, which is why only these need testing.
4. Compute the information gain for each candidate and pick the best.

Worked example: Temperature

Temperature	40	48	60	72	80	90
Play Sport	no	no	yes	yes	yes	no

Only the two boundaries where the class flips can be optimal, so six sorted values produce just two candidate thresholds to score.

→StepsScoring the two candidates

1. The classification changes between 48 and 60, and again between 80 and 90. Two boundaries, therefore two candidate thresholds.
2. $c_1 = (48 + 60)/2 = 54$, giving the Boolean attribute Temperature > 54.
3. $c_2 = (80 + 90)/2 = 85$, giving the Boolean attribute Temperature > 85.
4. Compute the information gain of each. Temperature > 54 wins and is selected.
5. That new Boolean attribute then competes with the other discrete attributes for the next node of the tree.

⚠GotchaThe slide flips the inequality between the definition and the example

The definition above states the new attribute one way - $A_c$ is TRUE if $A < c$ - and the worked example then names it the other way, as Temperature > 54. Both appear in the source and both are reproduced here. Either convention is fine; what matters is that the same one is applied consistently on both branches, because swapping mid-tree silently inverts a subtree.

⚠GotchaThe candidate set is small on purpose

You do not scan every real number, and you do not scan every observed value. Only the midpoints at class changes can be optimal, so six sorted rows here yield two candidates rather than five.

An extension of the same idea splits the attribute into multiple intervals rather than just two, giving a multi-way split on a single continuous attribute.