Decision tree (ID3/C4.5)

Base stats

Compare with

Parameters: 10
Data: 15
Compute: 8
Context: 0
Generality: 15
Transparency: 92
Total: 140

Approximate, ordinal scales meant for comparing species with each other; the hard numbers are in the data sheet.

Weaknesses

If it grows until every leaf is pure, it overfits: it needs pruning.
Unstable: a small change in the data can change the question at a node and everything hanging from it.
With numeric attributes it only draws axis-parallel boundaries; diagonals are approximated as staircases.
Information gain favors attributes with many values, such as an ID number.

Habitat

It was born among chess endgames and toy Saturday mornings. Today it lives in credit scoring, clinical triage and fraud detection and, in herds (random forests, gradient boosting), it still wins competitions on tabular data.

Moves

Abilities

Information gain

At each node it picks the attribute that most reduces the entropy of the classes, measured in bits.

Divide and conquer

It splits the examples by their answer and repeats the procedure on each branch until the nodes are pure.

Transparent box

Every prediction is a readable path from root to leaf: a conjunction of conditions anyone can audit.

Anatomy

The tree ID3 induces from the 14 days of the weather data (Witten et al., 2017, p. 109). In parentheses, how many training days reach each leaf. Outlook sits at the root because it has the highest information gain: 0.247 bits.

A decision tree is a classifier shaped like a questionnaire: at each node it asks a question about one feature of the case ("what is the outlook?"), follows the branch matching the answer and, on reaching a leaf, returns a class. The interesting part is not the questionnaire but that nobody writes it: the algorithm induces it from a table of labeled examples. It is the first Symbolic type in this Pokédex that learns from data.

How it works

The canonical example is the weather data that Witten et al. (2017) use throughout their book: fourteen days described by four attributes (outlook, temperature, humidity and windy) and a class, whether or not some unspecified game was played (2017, pp. 10–11). The example comes from Quinlan (1986), where the objects were "Saturday mornings" and the classes were called P and N (1986, pp. 85–86).

The algorithm is recursive: pick an attribute for the root, open one branch per value, and repeat the procedure on each branch using only the examples that reach it; stop when a node is pure, that is, when all its examples share the same class (Witten et al., 2017, pp. 105–106). The key question is which attribute to pick. ID3 uses Shannon entropy: the information, in bits, still needed to determine the class of a case that has reached that node. The root holds 9 "yes" and 5 "no," which amounts to 0.940 bits; splitting on outlook brings the expected information down to 0.693 bits. The difference, 0.247 bits, is the information gain of outlook, higher than that of humidity (0.152), windy (0.048) and temperature (0.029) (Witten et al., 2017, p. 107). So outlook is asked first; on the "sunny" branch humidity wins, and the result is the tree in the diagram (2017, p. 109).

Read with a logician's eye, the tree is a formula in disjunctive normal form: play if and only if (outlook = overcast) ∨ (outlook = sunny ∧ humidity = normal) ∨ (outlook = rainy ∧ windy = false). Each path from the root to a "yes" leaf is a conjunction; the learned concept is the disjunction of those paths. You can experiment with this in the decision-tree lab.

What changed

In expert systems, rules were obtained by interviewing specialists; here they are induced from data. ID3 was in fact born from a challenge posed by Donald Michie: to decide, from board features alone, whether a position in a chess endgame (king and rook against king and knight) was lost within a given number of moves (Quinlan, 1986, p. 84). At about the same time, four statisticians at Californian universities (Breiman, Friedman, Olshen and Stone) developed CART without knowing of Quinlan's work: a case of parallel invention in statistics and machine learning (Witten et al., 2017, p. 30).

C4.5, ID3's successor, added the gain ratio, numeric attributes, missing values, pruning and the conversion of trees into rules (Witten et al., 2017, pp. 113, 210). From the 2000s on, trees came back in herds: random forests let many randomized trees vote (2017, p. 485), and gradient boosting over trees is, according to Chollet (2021), perhaps the best algorithm available for non-perceptual data (2021, sec. 1.2.4).

Limits

Overfitting. A tree grown until every leaf is pure fits the training set too closely. That is why almost all systems build the full tree and then prune it, replacing subtrees with leaves (Witten et al., 2017, pp. 210, 213–214).
Many-valued attributes. An ID code for each day earns the highest possible gain (0.940 bits) and generalizes nothing; C4.5 corrects this bias with the gain ratio (Witten et al., 2017, pp. 110–111).
Instability. A small change in the data can alter the attribute chosen at a node, and with it the whole subtree below (Witten et al., 2017, p. 481).
Straight borders. With numeric attributes, a tree only draws decision boundaries parallel to the axes; a diagonal must be approximated by a staircase of rectangles (Witten et al., 2017, p. 251).
Transparency that evaporates. A five-leaf tree can be read at a glance; one with thousands of nodes, or a forest of five hundred trees, cannot.

Professor Robledom's note

Fourteen days are compatible with infinitely many trees. Why settle on this one? Quinlan answers with Occam's razor: between two trees that are correct on the training set, prefer the simpler, since it is more likely to capture the structure of the problem (Quinlan, 1986, p. 87). Witten et al. (2017) put it without metaphysics: all learning involves a bias (the language in which concepts are described, the order of search, and the criterion for curbing complexity), and a language able to express any subset, such as one rule per example, does not generalize: it merely records the data (2017, pp. 33–34). It is Hume's problem in a spreadsheet.

There is a second lesson, about transparency. Witten and colleagues report that an expert in machinery diagnosis rejected the first induced rules because he could not relate them to his own knowledge: "mere statistical evidence was not, by itself, an adequate explanation" (2017, p. 26). He accepted them only once he could justify them in terms of his mechanical knowledge. A tree says with complete clarity how it classifies, but not why the world is that way.

For discussion: is the preference for the shortest tree an epistemic norm or an engineering convenience? And is a model you can read in full already an explanation, or just a very legible description? Compare Rudin (2019)'s defense of interpretable models for high-stakes decisions.

Sources

Chollet, F. (2021). Deep learning with Python (2nd ed.). Manning Publications. §

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. https://doi.org/10.1007/BF00116251 §

Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5), 206–215. https://doi.org/10.1038/s42256-019-0048-x §

Witten, I. H., Frank, E., Hall, M. A., & Pal, C. J. (2017). Data mining: Practical machine learning tools and techniques (4th ed.). Morgan Kaufmann. https://doi.org/10.1016/C2015-0-02071-8 §