Decision trees

Most models are unreadable for humans, their parameters are just long lists of numbers. Decision trees are the big exception: you can follow every single decision, from the first question down to the result. That is exactly why they are still used wherever a decision has to be explainable, for example in lending or medicine. And they are perfect for understanding how a learning method really works.

A chain of simple questions

A decision tree sorts examples through a sequence of yes or no questions. A spam filter built as a tree might ask at the top: does the mail contain the word free? If yes, the next question follows: is the sender in your address book? Every mail works its way down from question to question until it lands in a leaf, and the leaf holds the decision: spam or not spam. Each question on its own is simple. The power comes from the combination: if every question branches on both answers, each new level doubles the number of possible paths through the tree.

How the tree finds the best question

Where do the questions come from? During training the tree stubbornly tries all candidates and measures which question separates the examples most cleanly. Picture 20 fruits, 10 apples and 10 lemons. The question, is the fruit yellow, creates two groups: almost only lemons on the left, almost only apples on the right. That is a good question, because both groups are nearly pure. The question, does the fruit weigh more than 50 grams, separates nothing: almost all 20 fruits are heavier than that and therefore land in the same group, where apples and lemons are mixed exactly as before. So this question gets discarded. How pure a group is can be written as a share: if 6 of 10 fruits in a group are lemons, the lemon share is 6 divided by 10, that is 0.6. A completely pure group would have a share of 0 or 1, holding only a single kind. The tree takes the question with the purest groups, splits the examples and repeats the same game inside each group until the groups are pure enough. No thinking involved, just systematic trying and measuring.

When the tree memorises

If you let the tree grow unchecked, it gets arbitrarily deep and ends up asking so many questions that every training example gets its own leaf. On the training data it is then perfect, zero errors. But it has understood nothing, it has memorised the examples, including every coincidence and measurement error. On new data such a tree fails. So you rein it in: a maximum depth, a minimum size per leaf, or you prune weak branches after training. A smaller tree makes more errors on the training data but often far fewer on new data. This pattern, perfect in training and weak in reality, is called overfitting and you will meet it again in every learning method.

Many small trees instead of one big one

A single tree is often shaky: change the training data slightly and the tree suddenly looks completely different. A simple and surprisingly effective trick against this: train many different trees, each on a randomly drawn sample of the data, and let each tree pick from only a random part of the features at every question, meaning properties such as colour or weight. In the end all the trees vote and the majority decides. Such a forest of trees, called a random forest, cancels out the mistakes of individual trees and remains one of the most reliable methods there is, especially for tabular data. Not every task needs a giant neural network.