The History of AI

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

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.

Open in the interactive timeline