Decision Trees

A decision tree is a machine learning model that predicts a value — a class or a quantity — by chaining simple questions about the data: each internal node tests an attribute, each branch corresponds to an outcome of that test, and each leaf assigns the final prediction. The result is a hierarchical diagram that reads top to bottom like a list of rules.

It is one of AI's most veteran methods and one of its most current: in practice, a single tree is rarely used on its own today. Instead, hundreds are combined into ensembles that dominate learning on tabular data.

How it works

The tree is grown by recursive partitioning: at each node, the algorithm looks for the question that best separates the data according to a purity criterion — Gini impurity or entropy for classification, squared error for regression, as documented by the scikit-learn library — and repeats the process on each subset until a stopping condition is met. The canonical algorithms set the pattern decades ago: CART (Breiman, Friedman, Olshen and Stone, 1984) introduced binary classification and regression trees built on the Gini index, while ID3 (Quinlan, 1986) and its successor C4.5 (Quinlan, 1993) relied on entropy and information gain, adding pruning and support for continuous attributes.

From one tree to ensembles

A single tree is rarely the best predictor; many trees combined almost always are. Random Forest (Breiman, 2001) trains each tree on random samples of data and features and averages their votes, gaining robustness to noise. Gradient boosting goes further, building trees in sequence, each one correcting the errors of those before it. Its three reference implementations are XGBoost (Chen and Guestrin, 2016), LightGBM (Ke et al., 2017), which speeds up training by more than 20 times at nearly identical accuracy, and CatBoost (Prokhorenkova et al., 2018), with its native handling of categorical variables.

Interpretability and limits

A small tree is a white-box model: it can be visualized, and every prediction can be explained with boolean logic. An ensemble of hundreds of trees loses that readability; feature importances and methods such as SHAP (Lundberg and Lee, 2017), which assign each variable its contribution to a specific prediction, are used to mitigate this. The classic limits remain: deep trees tend to overfit — hence pruning and depth caps — and they are unstable, since small variations in the data can produce a completely different tree, a problem that ensembles were precisely designed to soften, as the scikit-learn documentation warns.