ID3 and decision-tree learning

The first issue of the journal Machine Learning, in March 1986, carried Ross Quinlan's account of ID3. Given a table of examples, the algorithm picks the attribute whose value tells you the most about the answer, measured by Shannon's information gain, splits the data on it, and recurses. The result is a tree of questions a person can read: if the outlook is sunny and the humidity is high, do not play tennis.

Decision trees were the practical machine learning of the late 1980s and 90s. They needed no gradients, handled mixed data, and, crucially for the businesses that adopted them, could explain themselves. Quinlan's C4.5 of 1993 and the commercial C5.0 ran in banks and insurers when neural networks were an academic curiosity.

They also turned out to be the best base learner for the ensemble methods that dominated applied machine learning until deep learning and, on tabular data, still do. Leo Breiman's random forests of 2001 average hundreds of trees; gradient boosting stacks them; XGBoost won most Kaggle competitions of the 2010s that did not involve images or text. When a modern language model calls a tool to make a prediction from a spreadsheet, the tool is often a descendant of ID3.