10. Twenty Questions About Pixels

A model that keeps questions instead of examples

Last time, k-nearest neighbors kept every training image and did all its work when a new one arrived. A decision tree does the opposite. It studies the training images once, boils them down to a short list of yes-or-no questions, and then throws the images away. To classify a new digit, it asks the questions in order, like a game of twenty questions played about pixels. Is pixel 350 darker than 100? If yes, ask this next. If no, ask that. At the end of the path sits a label.

The question for this chapter is how a tree decides which question to ask first, and how it knows when to stop. The answer is a small piece of arithmetic you can do by hand, and then a lesson on MNIST about how far a tree should be allowed to grow.

Measuring how mixed a group is

Say you have ten images, six sevens and four ones, and you look at one pixel in each. Before any question, the group is mixed. We want a number for how mixed.

The first number is Gini impurity. For each class, take its share of the group, square it, add those squares up, and subtract the total from one. Here the shares are 0.6 and 0.4. The squares are 0.36 and 0.16, which add to 0.52. One minus 0.52 is 0.48. A group with only one class gives one minus one, which is zero. A fifty-fifty group of two classes gives one minus a half, which is 0.5. So zero means pure, and bigger means more mixed.

The second number is entropy, measured in bits. For each class, take its share, multiply by the base-two logarithm of that share, add those up, and flip the sign. For shares of 0.6 and 0.4, that comes to about 0.97 bits. A pure group gives zero, and a fifty-fifty split gives exactly one bit. It reads as the average number of yes-or-no questions you would need to name the class of a random image drawn from the group. The two measures differ in detail but usually pick the same split, so the choice rarely matters.

Choosing a cut by hand

Now sort the ten images by that one pixel's value. A cut is a threshold: images below it go left, images at or above go right. The candidate thresholds are the midpoints between neighboring values in the sorted list. If two neighbors have values 40 and 80, the midpoint is 60.

The method we are working through is the CART algorithm, short for classification and regression trees. You do not need to test every midpoint by hand. If two neighbors have the same label, cutting between them cannot beat cutting at a spot where the label changes, so you can test only the midpoints where the label switches.

Say the sorted labels run: one, one, one, seven, one, seven, seven, seven, seven, seven. Three label changes exist. Cut A comes after the third image. Left holds three ones, so its Gini is zero. Right holds one one and six sevens, seven images in all. The shares are one seventh and six sevenths, and the Gini is one minus about 0.02 minus about 0.73, so roughly 0.24. Weighted by size, the children score 0.3 times zero plus 0.7 times 0.24, about 0.17. The drop from the parent is 0.48 minus 0.17, about 0.31.

Cut B comes after the fourth image. Left holds three ones and a seven, with a Gini of 0.375. Right holds one one and five sevens, six images, with a Gini of about 0.28. Weighted, that is 0.4 times 0.375 plus 0.6 times 0.28, about 0.32. The drop is only about 0.16.

Cut C comes after the fifth image. Left holds four ones and a seven, with a Gini of 0.32. Right holds five sevens, so its Gini is zero. Weighted, that is 0.5 times 0.32 plus 0.5 times zero, which is 0.16. The drop is 0.48 minus 0.16, or 0.32, just ahead of Cut A's 0.31. Cut C wins. The tree takes the largest drop, writes that question down, and repeats the whole process inside each side.

The weakness of looking one step ahead

This procedure is greedy. At every node it picks the best single question right now and never asks whether a worse question now would open up a better one later. Picture an XOR pattern, where a label depends on two pixels together: the class is one when exactly one of them is dark. Looking at either pixel alone, the classes stay evenly mixed, so no first cut shows any gain. A greedy tree can pass right over a pair that would have solved the problem. Finding the truly best tree is NP-complete, which in practice means no known method is fast enough to search for it. So trees settle for a good tree built one step at a time.

Growing a tree on MNIST

In scikit-learn the tool is DecisionTreeClassifier. The settings you will use are criterion, which picks Gini or entropy, max_depth, min_samples_leaf, and random_state. Keep the split from before: fit on the first fifty thousand training images, score on the next ten thousand, and leave the test set sealed.

Run a sweep where max_depth goes from 1, 2, 3 and on up to unlimited. Record training accuracy and validation accuracy at each step. A depth of one is a single question and can name at most two digits, so both scores will be low. As depth grows, both rise. Left unlimited, the tree keeps splitting until every leaf is pure, which means training accuracy reaches one hundred percent: it has memorized the training set. Validation accuracy rises, then flattens or even dips. The gap between the two curves is overfitting made visible. Measure where yours levels off rather than trusting a number from me, but expect it to land below logistic regression at about ninety-two percent and well below k-nearest neighbors at about ninety-seven. The floor to compare against is still about eleven percent, from always guessing one.

The setting min_samples_leaf attacks the same problem from another side. It forbids any leaf with fewer images than the number you give, so the tree cannot carve out tiny pockets for single odd images.

Reading what the tree used

After fitting, feature_importances_ gives one number per pixel: how much total impurity drop that pixel produced. Reshape it to twenty-eight by twenty-eight and draw it as a heat map. You will see bright pixels near the center and values near zero around the border, which matches what we found earlier, that border pixels are blank in almost every image.

Two cautions. First, predict_proba on a tree is just class counts inside a leaf. A deep tree has nearly pure leaves, so its probabilities are mostly zero or one, and they are poorly calibrated, a cousin of the coarse one-over-k steps from nearest neighbors. Second, trees are unstable. Refit on a slightly different fifty thousand, say with a random five percent dropped, and watch the top split and the shape below it change. One different image can tip an early cut, and everything beneath moves. That jitter is the reason to average many trees, which is where random forests come in next.

For the exercise, sweep max_depth against min_samples_leaf on validation only. Write down a guess before each run, note the fit time, and keep the test set sealed. Whether you do it is up to you; the sweep produces a grid of validation scores you can read for the best setting.

Two items from the news

Google DeepMind announced Gemini 4 Carbon on October 28, 2026, aimed at cybersecurity and engineering work. Access is limited to select partner programs, so for now it is an announcement, not something you can use. Treat any claims about it as unchecked until you can run it yourself.

A paper posted on October 29, arXiv 2610.39556, studies fraud detection under operating limits. It uses chronological holdouts, meaning train on earlier transactions and test on later ones, with tree ensembles XGBoost and LightGBM, explained using SHAP. Platt calibration, a logistic correction to raw scores, cut the Brier score on the PaySim data from 0.1141 to 0.0245. The Brier score is the average squared gap between predicted probability and the outcome, so lower means better calibrated. Then a rule alerting on only the top one percent of scores cut false-positive investigations from 192 to 117, but recall fell from 0.4236 to 0.2122. That is the threshold trade-off from earlier, now forced by how many cases investigators can handle. These numbers hold for that dataset and setup only, but they tie neatly to the leaf-count probabilities above: scores from trees need calibrating before you trust them as probabilities.