Decision trees to gradient boosting

How does growing a decision tree work? Let's try to understand. In a simple way. A decision tree sorts things with yes or no questions.

Is it heavier than one hundred grams? But nobody writes those questions. So where do they come from? The tree learns them from data.

You hand it many labeled examples, each with a few features and a known answer. A question is just one feature and one cut point. Heavier than eighty grams? Wider than five?

Every feature and cut point is a candidate question. The tree tries them out. Each candidate splits the examples into two groups. Then it looks at how the answers landed on each side.

That is the whole trick. A good question sends apples one way and lemons the other. A bad one leaves both sides mixed. So it scores each split by how mixed the groups still are.

It keeps the one question that separates them best right now, and makes that the node. It does not plan ahead; it just grabs the best split. That is greedy. Then it repeats inside each new group.

The next question is chosen only from the examples that landed there. So different branches naturally learn different questions. When a group is almost all one answer, there is nothing left to ask. That box becomes a leaf, and its answer is the prediction.

So a tree learns by trying many split questions, keeping the best, and repeating on each side. The data picks the questions, not you. Quick check now. One question is coming up.

Let's see if it clicked.

What exactly is impurity? Let's try to understand. In a simple way. A tree grows by splitting examples into two groups.

But which split is best? The tree needs a number for how good a group is. That is impurity. Impurity measures how mixed the labels are.

All apples is pure. Half apples, half lemons is as mixed as it gets. Impurity is zero when a group is all one label, and highest when the labels split evenly. Lower means cleaner.

The most common measure is Gini impurity. Grab one item. Guess its label from the mix. How often are you wrong?

That chance of being wrong is the Gini score. A pure group is never wrong, so zero. A fifty fifty group is wrong half the time, one half. A second measure is entropy, from information theory.

Different math, same spirit. It peaks at an even mix and hits zero when a group is pure. But a split makes two groups. The tree measures each child and blends them, weighted by how many examples landed inside.

A tiny pure group counts less than a big one. Compare the parent's impurity to the blended child impurity. The drop is the information gain. A big drop means the question pushed both groups toward pure.

So across every feature and cutoff, the tree scores this drop and keeps the largest one. That is a perfect split. The biggest fall in impurity. So impurity scores how mixed a group is.

The tree chops, measures the drop, and keeps the cleanest split. Quick check now. One question is coming up. Let's see if it clicked.

What exactly is an overfit tree? Let's try to understand. In a simple way. A decision tree splits the data again and again to separate the labels.

If nobody tells it to stop, it keeps going, deeper and deeper. With enough depth, it carves out a tiny box for almost every single training example. On the data it trained on, it gets nearly every answer right. That looks amazing.

Perfect scores on the training set. But that score is a lie. The tree did not learn the pattern. It just memorized.

Real data has noise: a mislabeled point, a strange outlier, a fluke. A deep tree grows a branch just to fit that one point, as if the noise were a rule. You can see it in the decision boundary. A healthy tree draws a few clean, broad regions.

An overfit tree draws a jagged edge wrapping tightly around every point. Then a new example arrives, one the tree never saw. It lands in a tiny, noise carved box, and the answer is wrong. So the training score stays high while the new data score drops.

That gap is the fingerprint of overfitting. The wider it grows, the more it memorized. So you hold the tree back. Cap how deep it can grow, or make each leaf hold several examples.

A little worse on training, far better on unseen data. So a big unpruned tree can score perfectly by memorizing noise. Beautiful on training, wrong in the wild. Keep it shallow, and it tells the truth.

Quick check now. One question is coming up. Let's see if it clicked.

How does a crowd of trees work? Let's try to understand. In a simple way. A single decision tree is clever, but shaky.

Grow it deep and it starts memorizing the training data. On new examples, it can be confidently, badly wrong. So here is the trick. Instead of trusting one tree, we grow a whole crowd of them.

Then we ask every tree the same question. And the trees do not all answer the same way. Each one was built a little differently, so each makes its own mistakes, on its own examples. To get one answer, we let them vote.

Whichever label most of the trees pick becomes the crowd's final prediction. Here is why that helps. One tree's error points one way, another's points a different way. When the mistakes are scattered, the majority still lands on the right answer.

The errors cancel out. But there is a catch. The trees have to actually differ. If every tree were identical, they would all make the same mistake, and a vote among copies changes nothing.

For a number instead of a label, you average the trees rather than counting votes. A few wild guesses get pulled back toward the middle, where the truth usually sits. The payoff is steadiness. The crowd swings far less on noise than any lone tree, and it usually predicts better too.

This team of trees is called an ensemble. So, a crowd of trees beats one. Many different trees, one combined vote, and their scattered errors quietly cancel. Quick check now.

One question is coming up. Let's see if it clicked.

How does a random forest work? Let's try to understand. In a simple way. Grow two trees on the same data with the same rules, and you get two identical trees.

A crowd of clones votes no better than one. The forest must make every tree differ. The first trick gives each tree its own data. From the training set, draw a new set of the same size, one row at a time, putting each back before the next.

That is a bootstrap sample. Because rows go back, some get drawn several times, others never appear. Every tree trains on a different slice. This is called bagging.

The second trick makes it a forest. At every split, the tree cannot see all features. It gets a small random handful to choose from. Why tie its hands?

If one feature is very strong, it would win the top split in every tree, making them alike. Hiding it forces different paths. Put both tricks together and each tree grows its own shape. Different data underneath, different features offered, different questions in a different order.

That difference is the point. Trees built differently make different mistakes, so their errors do not line up. Combine them and scattered errors mostly cancel. How many features per split?

A common default is the square root of the total. Fewer makes trees more varied, but each one weaker. So, a random forest makes different trees on purpose. Bootstrap samples give different data, a random feature subset varies each split, and scattered errors cancel.

Quick check now. One question is coming up. Let's see if it clicked.

What exactly is a weak learner? Let's try to understand. In a simple way. Here is a tempting idea.

For a hard problem, build one brilliant model. A single deep tree that tries to master every case alone. Call it the genius. But a lone genius is fragile.

It leans on its own view of everything. And when it gets a case wrong, nobody is there to catch the mistake. Now try the opposite. Instead of one expert, gather a team of simple models.

Each is shallow and plain, and each watches only a narrow slice of the problem. A model only a little better than a coin flip has a name. It is a weak learner. On its own, it is almost useless.

Here is the surprising part. Take many weak learners, combine their answers, and together they act like one strong learner. The team beats every member. The trick is division of labor.

Each simple model becomes a specialist on a different part of the problem. Where one is lost, another knows the answer. And the team is sturdy. If one weak learner is wrong, it barely moves the group's decision.

All the genius's eggs were in one basket. So why keep the members weak, and not strong? Because a weak model leaves room. You can always add another specialist to cover what the rest still miss.

So, a weak learner is a model barely better than guessing. Alone, it is weak. As a team, it is strong. Specialists beat one lonely genius.

Quick check now. One question is coming up. Let's see if it clicked.

How does boosting work? Let's try to understand. In a simple way. Boosting starts simple.

Make one rough first guess for every example. For a number, that can just be the average. It will be wrong almost everywhere, and that is fine. Now look at what is left over.

For each example, take the true answer and subtract our guess. That leftover gap is the error. These errors have a name. Residuals.

Here is the twist. The next tree does not predict the answer. It predicts those errors. Its only job is to explain what we got wrong.

Then we add that tree's output on top of the running guess. Every example slides a little closer to its true answer, and the biggest misses shrink the most. But new, smaller errors are still left. So we measure them again, and grow one more tree to fix those.

Round after round, tree after tree. Notice the order. Each tree is built after the last, aimed at the mistakes still standing. Boosting is sequential, not a crowd grown side by side.

So the final model is not a vote. It is a running sum. The first rough guess, plus every correction stacked on top. Because each tree attacks whatever is still wrong, the team keeps sharpening its weak spots.

Many small fixes add up to one strong model. So, boosting fixes old errors step by step. Guess, measure the leftover, and train the next tree on it. Each tree cleans up after the ones before.

Quick check now. One question is coming up. Let's see if it clicked.

How does a small learning rate work? Let's try to understand. In a simple way. Remember, each new tree hands us a correction to add on top.

The tempting move is to add that whole correction and trust it completely. Here is the trick. Before adding a correction, multiply it by a small number. That number is the learning rate.

Often about one tenth. So each tree nudges the model only part of the way. Why hold back? A full step bets everything on one tree.

One greedy leap can sail past the target, baking that tree's quirks into the model. A small step is cautious. No single tree can drag the model far off course. Whatever one tree gets wrong stays tiny, and later trees clean it up.

But there is a catch. Smaller steps mean slower progress. To reach the same fit, you now need many more trees. So the learning rate and the number of trees are two dials that trade off.

Turn the rate down, and raise the tree count to match. The payoff is worth it. Leaning on many small steps instead of a few big ones, the model fits the real pattern, not the noise. It generalizes better.

Picture walking down into a valley. Giant leaps overshoot and bounce around the sides. Small steady steps settle you gently at the bottom. So, a small learning rate shrinks every tree's correction.

Each step is gentle, you add many, and the model lands on a smoother, sturdier answer. Quick check now. One question is coming up. Let's see if it clicked.

What exactly is the direction of steepest error? Let's try to understand. In a simple way. Boosting keeps adding trees to shrink the error.

But which way should the next tree push each prediction? That is the real question. First, gather all the wrongness into one number, the loss. Square every miss, add them up.

Higher loss, worse model. Now nudge one prediction up a hair. Does the loss rise or fall, and how fast? That rate of change is the gradient.

Flip the slope's sign and it points downhill. Each example gets an arrow. Which way to move, and how far, to cut the loss. Line up those arrows and you have a target.

These downhill values are the pseudo residuals. The next tree learns to predict them. Here is the neat part. With squared error loss, that arrow is exactly the residual.

True minus guess. Residuals were gradient descent all along. But the gradient works for any smooth loss. Pick one that ignores outliers, or one for yes or no labels.

The arrows change, the trees chase them. Picture the loss as a hillside. Each tree takes one step straight downhill. That is why we call it gradient boosting.

So the gradient does two jobs. It sets the direction to push each prediction, and the size of the push, tuned to your loss. So, the steepest direction is the loss's negative gradient. Turn every miss into a downhill arrow, and grow the next tree to follow it.

Quick check now. One question is coming up. Let's see if it clicked.

What exactly is a tree that fears the future? Let's try to understand. In a simple way. A tree left alone is greedy.

It keeps splitting until every training point sits in its own box. Perfect on what it has seen, lost on anything new. So we make the tree afraid of the future. Before any split, it must ask, will this still help on data I have never seen?

We do that by charging a fee. Every new leaf adds a penalty to the score. The goal is no longer raw fit. It is fit minus the cost of complexity.

So a split only survives if it lowers the error by more than its fee. Barely helps? The tree drops it. Weak branches get pruned away.

We also demand a crowd. A split resting on two or three examples is probably chasing noise. Require enough on each side, or it is not allowed. And we quiet the leaves.

A second penalty pulls every leaf value gently toward zero, so no leaf shouts a big number from thin evidence. Each of these is a fear of the future. The tree will not commit unless the evidence is strong. Real signal survives, faint noise gets ignored.

And every fear is a dial. Tighten them when the model memorizes, loosen them when it underfits. So, a tree that fears the future is a regularized tree. Charge for complexity, prune weak splits, hold the leaves back.

Give up a little training fit to win on data still to come. Quick check now. One question is coming up. Let's see if it clicked.

How does XGBoost run so fast? Let's try to understand. In a simple way. XGBoost is just gradient boosting, the same trees fixing errors in turn.

Its cousins reach the same answers. XGBoost only gets there faster. Where does the waiting go? Nearly all the time goes into finding the best split.

The plain way sorts a feature and tries every value as a cut. Thousands of rows, thousands of splits per node. First trick. Group each feature's values into a small number of buckets, say two hundred fifty six.

Now you test only the edges, a few hundred splits, not thousands. Those buckets form a histogram. One pass drops each row's error signal into its bucket. Score splits straight off those sums.

No sorting, no rescanning. A neat shortcut too. When a node splits, build the histogram for the smaller child only. The other is the parent minus it.

Half the work, for free. Second trick. Features are independent, so score them all at once, across every processor core. Trees still come one by one, but each search runs wide.

Third trick. The data sits in sorted, compressed blocks, arranged once. Later trees reuse them, keeping the numbers the processor wants close at hand. Do the buckets cost accuracy?

Barely. Boosting adds many trees, and later ones patch any rounding they caused. Nearly the same model, far less time. So, XGBoost is gradient boosting made fast.

Bucket the values, score off a histogram, reuse the parent, search features in parallel. Same trees, far less waiting. Quick check now. One question is coming up.

Let's see if it clicked.

How does XGBoost handle missing data? Let's try to understand. In a simple way. Real data has holes.

A row is missing a value, a blank where a number should sit. Most models choke on that. You must fill the blank first, guessing a mean or a zero. XGBoost does not ask you to fill anything.

At every split, it learns a default direction, one way the blanks should go, left or right. How does it learn that? To pick the split, it uses only the rows that have the value. Then it tries sending all the blanks left, then all of them right, and keeps whichever choice scores better.

That winning direction gets baked into the node. Later, when a row arrives with that value missing, it just follows the default arrow. No filling, no guessing. And every node learns its own default direction.

One split may send blanks left, the next may send them right. The data decides, node by node. This matters because a blank can carry signal. A missing income might mean something real.

Filling it with an average would erase that. Here the pattern of missingness is learned, not guessed. XGBoost treats a zero in sparse data the same way. Blanks and zeros skip the math and take the default route.

That keeps it fast on sparse data too. So, XGBoost handles missing data by learning a default direction at each split. It sends the blanks whichever way helps most, no imputation needed. Missing is just another path down the tree.

Quick check now. One question is coming up. Let's see if it clicked.

How does a tree ignore the scale of your data? Let's try to understand. In a simple way. Your features rarely share a scale.

Age runs zero to a hundred. Income runs into the hundreds of thousands. One column is tiny, another is huge. Many models feel that gap.

A neighbor search or a neural net lets the huge column dominate every distance and every step. So you must rescale first. A tree works differently. Every split is one yes or no question about one feature.

Is this value above the cut, or below it? To pick that cut, the tree only sorts the values and looks at their order. It never asks how big they are, just which comes before which. Now rescale that feature.

Multiply by a thousand, switch meters to kilometers, or standardize it. The order of the values does not change at all. Same order means the same rows fall left and right. The cut just slides along with them.

You grow the exact same tree, and the very same predictions. Skew and outliers barely bother it either. One giant value just sits at the end of the order. Only rank matters, never the raw magnitude.

So for trees you can skip the normalizing step. Feed the raw units straight in. One less thing to tune, and one less way to leak information. So, a tree reads the order of your values, not their size.

Any monotonic rescale leaves it unchanged. That is why trees do not care about scale. Quick check now. One question is coming up.

Let's see if it clicked.

How does a tree find feature combinations on its own? Let's try to understand. In a simple way. Sometimes the answer depends on two features together.

A loan is safe only when income is high and debt is low. Neither number alone tells you. This combined effect has a name. An interaction.

The features only reveal the truth as a pair, not one at a time. A straight line model adds up each feature on its own. So it misses the pairing, unless you hand build a combined feature yourself. A tree does it differently.

It splits, then splits again inside each branch. First it asks about income. Then, on the high income side, it asks about debt. Look at that lower question.

It sits inside the first. So the path from root to leaf reads, income high and debt low. That path is a feature combination. Picture it as a map.

The first split draws one line, the second draws another. Together they carve out a box, pinned down by both features at once. And each branch can ask its own second question. On the low income side, the tree might check something else.

So the pairing is discovered, not fixed in advance. Nobody told the tree which features to pair. The greedy search kept stacking useful splits, and the combination fell out for free. Go deeper, and it pairs three or more.

So, every path down a tree is an and rule combining features. Stack the splits, and the combinations appear on their own. Quick check now. One question is coming up.

Let's see if it clicked.

How do you choose a tree over a neural network? Let's try to understand. In a simple way. Both are strong tools, but very different.

A neural network learns its own features. A tree just asks yes or no questions. Which one wins depends on your data. Picture a spreadsheet.

Rows of records, columns of mixed features, like age, income, and a category. On tabular data, boosted trees are usually your strongest model. Why do trees win there? Each column can mean something different, and a split just puts a threshold on one at a time.

Different scales never bother it. Now change the data. Raw pixels of an image, a waveform of sound, a paragraph of text. Here a neural network is the one to pick.

Why the flip? One pixel means nothing alone. The signal lives in patterns across thousands of pixels. A network builds those patterns layer by layer.

A tree cannot. Size matters too. With only a few thousand rows, a network has too many knobs and memorizes. A tree ensemble stays strong on small and medium tables.

Trees bring practical wins too. They train in seconds, need little tuning, and give a strong baseline fast. They also show which features mattered. So here is the honest rule of thumb.

If your data is a table, start with gradient boosting. Images, audio, or language, reach for a network. So, trees rule the spreadsheet, and networks rule raw signal. Match the tool to your data, and you win before you train.

Quick check now. One question is coming up. Let's see if it clicked.