Decision Trees and Ensembles

Before taking a drone out, an experienced pilot runs through a few questions in their head. Is it raining? If so, stay home. If not, how windy is it? Too windy, stay home. Otherwise, fly. Nobody computed a weighted sum. They followed a short chain of questions, and each answer decided which question came next.

A decision tree is a model that has exactly this shape, and it can be learned from examples. Trees are easy to read, need little data preparation, and, combined in large groups, they are some of the most accurate models for spreadsheet-style data.

#A tree is a chain of questions

Each inner box of a tree asks a yes-or-no question about one feature. Each answer leads to another question or to a leaf, which holds the prediction. To predict, start at the top and follow the answers down.

Unlike the weighted sums in Regression and Classification, a tree can say "wind matters, but only on dry days". It handles that kind of interaction naturally, because the wind question only exists on one branch.

#How a tree is learned

You already know the core move. In What Is Machine Learning we tried every cut-off for one feature and kept the one with the fewest mistakes. A tree does that for every feature, picks the single best question, splits the examples into two groups, and then repeats the whole search inside each group.

To score a question, let each group predict its most common answer and count how many examples that gets wrong. Here are 8 past days, sorted by wind, with whether flying went well.

for each feature f:  for each value t of f:    split days into f >= t and f < t    cost = mistakes(group 1) + mistakes(group 2)    keep the split with the lowest costrepeat inside each group

The result is the tree in the figure above. Notice that wind ≥ 22 was the best single wind question at the top, but rain was better still. Picking the best question at each step, without looking ahead, is a greedy strategy. It is fast and works well, though it does not guarantee the best possible tree.

// Mistakes if a group predicts its most common label.
function mistakes(labels) {
  const yes = labels.filter((l) => l === 1).length;
  return Math.min(yes, labels.length - yes);
}
 
// Try the question "feature >= t" for every feature and value.
function bestSplit(rows, labels) {
  let best = null;
  for (let f = 0; f < rows[0].length; f++) {
    for (const t of new Set(rows.map((r) => r[f]))) {
      const yes = [], no = [];
      rows.forEach((r, i) => (r[f] >= t ? yes : no).push(labels[i]));
      if (no.length === 0) continue; // everyone said yes: no split
      const cost = mistakes(yes) + mistakes(no);
      if (best === null || cost < best.cost) best = { feature: f, t, cost };
    }
  }
  return best;
}
 
// Each row: [wind in km/h, rain (1 = yes)]. Label: 1 = good to fly.
const rows = [[5, 0], [8, 1], [10, 0], [12, 1], [15, 0], [18, 0], [22, 0], [25, 1]];
bestSplit(rows, [1, 0, 1, 0, 1, 1, 0, 0]); // { feature: 1, t: 1, cost: 1 }

def mistakes(labels):
    """Mistakes if a group predicts its most common label."""
    yes = sum(labels)
    return min(yes, len(labels) - yes)
 
def best_split(rows, labels):
    """Try the question "feature >= t" for every feature and value."""
    best = None
    for f in range(len(rows[0])):
        for t in sorted({r[f] for r in rows}):
            yes = [l for r, l in zip(rows, labels) if r[f] >= t]
            no = [l for r, l in zip(rows, labels) if r[f] < t]
            if not no:
                continue  # everyone said yes: no split
            cost = mistakes(yes) + mistakes(no)
            if best is None or cost < best[2]:
                best = (f, t, cost)
    return best
 
# Each row: [wind in km/h, rain (1 = yes)]. Label: 1 = good to fly.
rows = [[5, 0], [8, 1], [10, 0], [12, 1], [15, 0], [18, 0], [22, 0], [25, 1]]
best_split(rows, [1, 0, 1, 0, 1, 1, 0, 0])  # (1, 1, 1)

Real libraries score splits with a smoother measure than a mistake count, usually Gini impurity: for a group where a share p say yes, it is 1 − p² − (1 − p)². It is 0 for a pure group and largest for a 50/50 group. Unlike a mistake count, it rewards a split that makes a group purer even when the group's majority answer does not change.

#Trees overfit, forests do not as much

Left alone, a tree keeps splitting until every leaf is pure. With enough questions it can carve out a leaf for every single training example, which is memorization, the problem from Overfitting and Evaluation. You can limit the depth, or require a minimum number of examples per leaf. But there is a better trick: grow many trees and let them vote. A group of models used together is called an ensemble.

• Random forest. Train hundreds of trees, each on a random sample of the examples, and let each split consider only a random handful of features. Every tree overfits in its own different way. When they vote, their individual quirks mostly cancel out and the shared pattern remains.
• Gradient boosting. Train small trees one after another. Each new tree is trained on the errors the earlier trees still make, so it focuses on the cases they got wrong. Their predictions are added up.

#Common mistakes

#Try it yourself

#Check yourself

#What to practise next

Trees ask questions about the features you give them. Neural Networks learn their own intermediate features, layer by layer, which is what makes them so strong on images and text.