A decision tree works like a game of twenty questions. “Is the pixel in the middle dark? If yes: is the pixel at the top left dark too?” After a few such questions, the tree reaches an answer. Trees are popular in business because anyone can follow their logic, and they are the building block of some of the most successful methods for table data. They also show the most important trap in machine learning more clearly than any other model: overfitting.
This is part 3 of Level 1 in our learning path AI Fundamentals. You will learn how a tree finds its questions, what happened when we let our trees grow deeper and deeper on the handwritten digits from Level 0, and how combining many trees into a random forest solves the problem.
How a tree finds its questions
During training, the tree looks at all possible questions, for every pixel and every brightness value, and picks the one that best separates the digits: after the split, each group should contain as few different digits as possible. Then it repeats the search inside each group, and so on. Each question is a node, each final group a leaf, and the number of questions from the top to a leaf is the depth of the tree.
The figure shows the first three levels of a real tree from our experiment. Its very first question checks a pixel in the middle of the image: if it has almost no ink, the digit is most likely a 0, because a 0 is open in the middle. After three questions, this tree recognizes 48% of the test images. Most of its leaves are still mixed; to tell all ten digits apart, it needs many more questions.
The tree never stops on its own as long as a leaf still contains mixed digits. If you let it, it keeps asking until every training image sits in a leaf of its own kind. That is the moment it stops learning patterns and starts memorizing examples.
Our experiment: deeper is not better
We trained trees with a maximum depth from 1 to 20 on the training images and measured the share of correct answers twice: on the training images themselves and on the test images that the tree had never seen.
The result shows overfitting in its purest form. With enough depth, the tree recognized 100% of its training images: perfect. On the test images, it reached only 85.2%. The best test result, 85.7%, came at a depth of 10; every question beyond that only helped the tree remember individual training images, including their quirks and noise.
| Tree depth | Training data | Test data |
|---|---|---|
| 1 | 20.1% | 19.3% |
| 2 | 32.2% | 31.1% |
| 3 | 49.2% | 48.0% |
| 5 | 70.6% | 67.2% |
| 8 | 94.8% | 83.0% |
| 10 | 99.4% | 85.7% |
| 15 | 100.0% | 85.2% |
| 20 | 100.0% | 85.2% |
Our own experiment: dataset Optical Recognition of Handwritten Digits (E. Alpaydin, C. Kaynak, UCI Machine Learning Repository, license CC BY 4.0), 1797 images of 8 × 8 pixels, 540 of them held back for testing; scikit-learn 1.9.1, fixed random seed, so every run gives the same numbers.
This is why the gap between training and test results is the first thing to check in any machine learning project. A model that is much better on its training data than on new data has learned its examples, not the task. The opposite problem exists too: our shallowest trees were poor on both kinds of data, because a few questions are simply not enough to tell ten digits apart. That is called underfitting.
| Training result | Test result | Diagnosis | What usually helps |
|---|---|---|---|
| Low | Low | Underfitting: the model is too simple | A more flexible model, better features, longer training |
| High | Much lower | Overfitting: the model memorized its examples | Limit complexity, more data, combine models |
| High | Close to training | Good fit | Confirm on fresh data before relying on it |
The fix: many trees instead of one
A random forest trains many trees, each on a slightly different random sample of the training data and with a random subset of the features to choose from at each question. Every tree overfits in its own way, but their errors differ, so when the trees vote, many errors cancel out. Our forest of 200 trees recognized 96.5% of the test images, compared with 85.2% for a single tree grown without limits.
| Method | Test images recognized correctly |
|---|---|
| Logistic regression | 96.7% |
| k-nearest neighbors (k = 3) | 98.7% |
| Decision tree | 85.2% |
| Random forest (200 trees) | 96.5% |
| Support vector machine | 98.3% |
| Neural network (64 neurons) | 97.8% |
Source as for the first table on this page.
The single tree is the weakest method in this table, and the forest of the same kind of trees is among the strongest. The same idea, combining many weak models, is called an ensemble, and a related method called gradient boosting, which trains each new tree to fix the errors of the previous ones, is among the most successful methods for business data stored in tables.
How to avoid overfitting
- Always test on held-back data. Never judge a model by its training results alone.
- Limit the complexity. For trees, a maximum depth or a minimum number of examples per leaf; for other models, comparable settings.
- Use more data. The more examples, the harder it is to memorize them all.
- Combine models. Ensembles like random forests reduce the variance of single models.
- Keep a final test set untouched. If you tune your settings on the test data many times, you overfit to the test data too.
The next part compares six classic methods on the same data and explains cross-validation, the standard way to compare models fairly.