From Decision Trees to Boosting

I covered decision trees and boosting in a recent weekly paper, but I wanted to go through the ideas again in more detail instead of leaving them as a short comparison.

As an aside, I learned about deep learning today, and roughly half of it stayed in my head while the rest leaked out. The equations and deeper mechanics will need another pass through the lecture material. I even caught myself comparing that review process to backpropagation: send the error backward, adjust the connections, and try again. Not a literal neuroscience explanation, obviously, but the thought amused me.

Anyway, back to decision trees.

A decision tree works through a problem by asking one question at a time. Its path is easy to follow, but changing the first question can also change every question below it and eventually produce a different answer.

Ensemble learning reduces that dependence on a single model by combining several predictions. It is similar to asking several people to solve the same problem and then reconciling their answers.

The methods differ in how they organize that group. Voting lets multiple models solve the problem independently and then takes a vote. Bagging trains the same type of model on slightly different datasets and combines the results. Boosting lets each new model focus on what the models before it still got wrong. I started from the decision tree itself and worked through those differences one by one.

Following Conditions Down a Decision Tree

A decision tree divides data by applying conditions to its features. In a loan approval problem, for example, it might ask whether an applicant’s income exceeds a threshold and whether the applicant has a history of late payments. The leaf node reached at the end of that path produces the prediction.

The node at the top is the root. Nodes that test conditions are internal nodes, and nodes that produce final predictions are leaves. A single data point starts at the root and follows one branch after another until it reaches a leaf.

During training, the tree searches for the feature and threshold that separate the data most effectively. In the loan example, it might compare questions such as whether income exceeds $50,000 or whether the applicant has at least one late payment. It evaluates the candidates and chooses the question that separates approvals from rejections most cleanly.

Measuring the Mix with Gini Impurity

For classification trees, impurity measures how mixed the labels are inside a node. Gini impurity uses the proportion of each class:

\operatorname{Gini}(t) = 1-\sum_{k=1}^{K}p_k^2

Here, $t$ is the current node, $K$ is the number of classes, and $p_k$ is the proportion of class $k$ in that node.

If a node contains only approved applications, the approval proportion is 1 and the rejection proportion is 0. Its Gini impurity is therefore 0.

1-1^2-0^2=0

If approvals and rejections each make up half of the node, the impurity is 0.5. For binary classification, this is the most mixed state.

1-0.5^2-0.5^2=0.5

Suppose a parent node contains six approvals and four rejections. Its Gini impurity is 0.48.

\operatorname{Gini}(\text{parent}) = 1-\left(\frac{6}{10}\right)^2-\left(\frac{4}{10}\right)^2 = 0.48

Now suppose a candidate condition sends four approvals to the left node. The right node receives the remaining two approvals and four rejections. The left node is pure, so its impurity is 0. The right node has an impurity of approximately 0.444.

\operatorname{Gini}(L)=0

\operatorname{Gini}(R) = 1-\left(\frac{2}{6}\right)^2-\left(\frac{4}{6}\right)^2 \approx 0.444

The child nodes cannot be compared by simply averaging those two numbers because they contain different amounts of data. Their impurities are weighted by their sample counts.

\operatorname{Gini}_{\text{split}} = \frac{n_L}{n}\operatorname{Gini}(L) + \frac{n_R}{n}\operatorname{Gini}(R)

Here, $n$ is the number of samples in the parent node, while $n_L$ and $n_R$ are the sample counts in the left and right child nodes.

\operatorname{Gini}_{\text{split}} = \frac{4}{10}\times0 + \frac{6}{10}\times0.444 \approx 0.267

The split reduces impurity by approximately 0.213, from 0.48 in the parent node to 0.267 across the child nodes.

\Delta\operatorname{Gini} = \operatorname{Gini}(\text{parent}) - \operatorname{Gini}_{\text{split}}

\Delta\operatorname{Gini} = 0.48-0.267 = 0.213

A decision tree repeats this calculation across candidate features and thresholds, then selects the split with the largest impurity reduction at the current node.

Entropy is another way to measure how mixed the classes are. Its formula differs, but the selection rule is similar: choose the question that produces the largest reduction from the parent entropy to the weighted child entropy.

H(t) = -\sum_{k=1}^{K}p_k\log_2p_k

A regression tree predicts a number rather than a class. Each node can use the mean of its target values as its prediction, and mean squared error measures how far the individual values are from that mean.

\operatorname{MSE}(t) = \frac{1}{n_t} \sum_{i=1}^{n_t} \left(y_i-\bar{y}_t\right)^2

Here, $n_t$ is the number of samples in the current node, $y_i$ is an observed target, and $\bar{y}_t$ is the mean target value in the node. A classification tree looks for the largest reduction in impurity, while a regression tree can look for the largest reduction in weighted mean squared error.

Why a Few Data Points Can Reshape the Whole Tree

Decision trees are easy to inspect because the conditions behind a prediction can be followed directly. They also learn nonlinear relationships and feature interactions without requiring those relationships to be written manually. Because they do not rely on distances between feature values, they generally do not require feature scaling.

At each node, however, the tree chooses the question that gives the largest immediate reduction in impurity or error. Suppose splitting on income reduces impurity by 0.213, while splitting on late-payment count reduces it by 0.210. Income becomes the first question.

Adding or removing only a few training samples might change those values to 0.211 and 0.216. Late-payment count would then become the first question instead. That change sends different samples into the left and right child nodes, so every candidate and score below the root must also be recalculated. This sensitivity to small changes in the training data is why decision trees are described as high-variance models.

It does not mean that one changed sample always changes every prediction. The problem appears when several split candidates have similar scores. A small data change can switch the winning split near the top of the tree, and an early switch can reshape every branch below it.

Why Deep Trees Overfit

A decision tree can continue adding questions as long as another split reduces impurity or error. Without a depth limit, it may begin with broad patterns shared by many samples and eventually create narrow conditions that separate only a handful of cases.

Imagine two applicants with almost identical income and payment histories, but only one received approval in the training data. The tree may add another condition on age or account balance solely to separate that one case. If splitting continues, some leaves may contain only one or two samples and reach a Gini impurity close to 0.

Perfect or near-perfect performance on the training set does not guarantee that those conditions will hold for new applicants. The tree may have encoded unusual cases, recording errors, or noise as if they were general rules. High training performance followed by poor performance on unseen data is overfitting.

Limiting the maximum depth prevents the tree from building increasingly specific questions. Requiring a minimum number of samples in each leaf and refusing splits that produce only a tiny impurity reduction serve the same purpose. Pruning removes branches whose contribution is too small after the tree has been built.

Those controls reduce the complexity of a single tree. Bagging and Random Forest take another approach: build multiple trees from different samples and feature subsets, then vote or average so that a change in one tree has less influence over the final prediction.

Three Ways to Combine Models

An ensemble combines predictions from multiple models. Voting, Bagging, and Boosting all do this, but the relationship among their models differs.

Voting trains several models independently on the same problem. The models are often different types, such as logistic regression, an SVM, and a decision tree. Hard Voting selects the class supported by the majority of final predictions. Soft Voting averages class probabilities and chooses from the combined probabilities.

Bagging usually trains multiple instances of the same learning algorithm on different bootstrap samples drawn with replacement from the original dataset. The models can be trained independently and therefore in parallel. Classification combines their votes, while regression averages their predictions. Averaging several decision trees reduces the variance of relying on one unstable tree.

Random Forest applies bagging to decision trees and also considers only a random subset of features at each split. If every tree always sees the same strongest feature, the resulting trees may become too similar. Random feature selection lowers the correlation among trees and makes their combined result more useful.

Boosting trains models sequentially. Each new learner compensates for samples or errors that the current ensemble still handles poorly. Because one stage depends on the results of earlier stages, the full sequence cannot be trained as a collection of completely independent models.

Method	Relationship among models	How predictions are combined	Main purpose
Voting	Multiple models trained independently	Majority vote or probability average	Combine different judgments
Bagging	Same model type trained independently on different samples	Vote or average	Reduce the variance of one model
Boosting	Models trained sequentially from earlier errors	Weighted sum of weak learners	Correct errors left by earlier learners

AdaBoost Focuses on Incorrect Predictions

AdaBoost begins by assigning the same weight to every training sample. After the first weak learner makes its predictions, incorrectly classified samples receive more weight. The next learner therefore pays more attention to those samples.

The final prediction gives stronger learners more influence in the combined vote. Several small trees can outperform one tree, but the weighting rule can also spend too much effort on outliers and incorrect labels because those samples continue to look like unresolved mistakes.

Gradient Boosting Moves in a Loss-Reducing Direction

Gradient Boosting adds a new weak learner that reduces the error left by the current model. In regression, this is often introduced as fitting a tree to the residuals between predictions and actual values. More generally, the new tree approximates the negative gradient of the loss function.

The update adds only a fraction of the new tree’s prediction:

F_m(x) = F_{m-1}(x) + \eta h_m(x)

Here, $F_{m-1}(x)$ is the ensemble built so far, $h_m(x)$ is the new weak learner, and $\eta$ is the learning rate that controls how much the new learner contributes. A smaller learning rate makes each correction more conservative, but it may require more trees.

The trees are added one after another, so training can take longer than bagging. Tree count, depth, and learning rate also need to be considered together. If the ensemble becomes too complex, boosting can fit noise just as a deep individual tree can.

Boosting Models That Grew from the Same Starting Point

XGBoost, LightGBM, and CatBoost share the basic Gradient Boosting structure. They differ in how they reduce computation, control overfitting, and handle particular kinds of data.

XGBoost uses both first- and second-order derivative information and adds a regularization term that penalizes tree complexity. It also provides pruning, handling for missing and sparse values, and systems optimizations such as parallel split evaluation. Those controls are useful, but they also create many hyperparameters to understand.

LightGBM groups continuous feature values into histogram bins so it can evaluate split candidates efficiently. Rather than expanding all nodes at the same depth, its leaf-wise strategy splits the leaf expected to reduce the loss the most. This can provide fast training and lower memory use on large datasets. On small datasets, however, one branch can grow deep quickly and overfit unless the number of leaves, minimum data per leaf, and maximum depth are constrained.

CatBoost is designed around datasets with many categorical features. It calculates categorical statistics internally instead of requiring every value to be one-hot encoded in advance. Data ordering helps prevent the current row’s target from leaking into the statistic used for that same row. This reduces preprocessing work, although the categorical calculations and ordered procedure can increase training time depending on the data and configuration.

None of these models is always the best choice. Dataset size, the proportion of categorical features, training time, memory constraints, interpretability, and the time available for tuning all matter.

Understanding It Takes More Than One Pass

When I first saw XGBoost, LightGBM, and CatBoost listed together, I honestly wondered why there were so many similar models. Reading their strengths separately told me that XGBoost and LightGBM were fast and that CatBoost worked well with categorical data, but it did not explain how each one changed the original boosting process.

Working forward from the decision tree made the divide between Bagging and Boosting clearer. Bagging combines independently trained trees to reduce the instability of one tree. Boosting lets each new tree continue from the error left by the current ensemble. XGBoost, LightGBM, and CatBoost are not isolated algorithms that appeared from nowhere; each develops the boosting process in a different direction.

I still need practical experience to understand which model fits a dataset and how its hyperparameters should be tuned. Today’s deep learning material probably will not make sense after one pass either. Still, pulling an older topic back out and writing through it seems to connect ideas that had previously remained separate.