Learned decision trees
Era 3 · From the expert boom to the statistical turn (1980–2011) › Statistical learning and probabilistic models
- Lineage
- Data and learning
- Kind
- Publication
Who
University of California, Berkeley, Stanford University
What happened
In 1984 Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone publish the book Classification and Regression Trees (CART). In 1986 the Australian Ross Quinlan publishes "Induction of Decision Trees" in Machine Learning, with the ID3 algorithm.
Why it mattered
A program builds, from examples, the tree of questions that classifies cases, instead of an expert writing the rules. Trees are the building block of random forests and boosting.
The full story
Expert systems needed an engineer to interview specialists and write down their rules one by one, slow work that became the field's bottleneck. Decision trees offered another route: get the rules from the data itself.
A decision tree classifies a case through a series of questions about its variables. The algorithm builds it from the top down: it finds the question that best separates the examples by class, splits the data into two or more groups, and repeats the process on each until the groups are nearly pure. Quinlan chose the question with a measure taken from information theory, information gain; CART used a similar impurity measure and added pruning to avoid trees that memorize the training data.
The two lines arose separately, CART in California statistics and ID3 in machine learning. The resulting tree can be read as a set of rules, something no other learning method offered, and that made it popular in medicine and in business.
Quinlan extended ID3 into C4.5 in 1993. Breiman, one of CART's authors, later combined many trees into random forests, and boosting uses them as its basic component too.
Leads to
Random forests (1995)
Documented direct influence
Breiman's random forests combine many decision trees built as in CART
Sources
Original source
- Classification and Regression Trees (Wadsworth, 1984; reissued by CRC Press) (opens in a new tab). Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone, 1984
- Induction of Decision Trees. Machine Learning, 1(1), pp. 81-106 (opens in a new tab). Ross Quinlan, 1986
Further reading
How to cite
“Learned decision trees.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/decision-trees
This entry was last reviewed on November 13, 2026.