From a Single Tree to a Forest: Mathematical Principles, Algorithmic Evolution, and Engineering Practices of Tree Models

A store owner wants to predict how many units of a product will sell tomorrow. Drawing on experience, they could write a rule: “If tomorrow is a weekend and a promotion is planned, predict higher sales.” Such a rule-based system is easy to understand and inspect. But once price, holidays, and differences between products also matter, it becomes difficult to anticipate every combination of conditions.

Suppose these factors have a repeatable relationship with sales, but no ready-made formula captures it well. If the store has enough representative historical records, a model can learn from them. A decision tree is an intuitive starting point: it finds useful conditions in past records, separates different situations, and makes a prediction for each. Every path through the tree can still be read as an “if…then…” rule.

Tree models evolved along several paths from single trees to ensembles. In the 1980s, ID3 and CART examined how a tree should choose its split conditions. In the 1990s, C4.5 refined single-tree learning, while bagging brought multiple trees together. Around 2000, random forests and GBDT offered two different ways to combine trees. In the 2010s, XGBoost, LightGBM, and CatBoost addressed further challenges, including training efficiency and categorical data. This timeline is only a roadmap; the decades refer to representative publications, not the dates when the software itself was first developed.

This evolution went hand in hand with advances in hardware. More memory and greater parallel processing capacity made larger datasets practical. Yet as the number of samples and features grew, repeatedly reading data and evaluating splits remained costly. Better training and data-processing methods therefore mattered as much as more computing power.

Article Guide #

The article follows three connected questions: How does a single tree learn, and why combine trees (Chapters 1–4)? What training problems do XGBoost, LightGBM, and CatBoost address (Chapters 5–7)? And how should we evaluate models amid outliers and class imbalance before using forecasts for store replenishment (Chapters 8–9)? Two fixed synthetic cases provide a common thread. Each has an eight-row teaching table for hand calculations and a larger, independently generated dataset for training, validation, and testing.

The synthetic data, generation scripts, and experiment notebooks used in this article are available from the public GitHub repository from-tree-to-forest.

Teaching Cases: Two Cases Throughout the Article #

Formulas are easier to follow when each feature, split, and metric has a concrete business meaning. This article uses two cases and four fixed CSV files: Case A simulates bank-transaction fraud detection; Case B simulates next-day sales forecasting across store–product pairs. Each case keeps its eight-row teaching table separate from the full experimental dataset while preserving the same field meanings and business setting. All four files come from invented rules and fixed random seeds. None represents a real bank, retailer, or industry average.

Case A: Bank-Transaction Data and the Fraud-Classification Task #

Start with the data. Each row represents one bank transaction and records four fields available when it occurs, together with the true label y obtained later. Every example in the rightmost column comes from teaching row S1, so the values form one complete record.

Why might these fields matter? For the 6,000 randomly generated experimental transactions, the script draws an amount \(a_i\), a distance \(d_i\), a merchant type \(c_i\), and a merchant ID \(m_i\). It then sets an invented fraud probability:

The indicator \(\mathbb{1}(\cdot)\) is 1 when its condition holds and 0 otherwise. The term \(b_{m_i}\) is a fixed random effect shared by transactions with the same merchant ID. A large amount or distance changes the sampling probability; no single feature determines the label. Amount and distance come from lognormal distributions, while merchant type follows preset probabilities.

A separate teaching CSV stores eight deliberately specified transactions, S1–S8. They are not sampled from this probability rule; their only purpose is to support later hand calculations of entropy, gradients, and split gain. Four are legitimate and four fraudulent. The full experimental dataset contains 168 frauds (2.8%) and fixed stratified partitions of 3,600 training, 1,200 validation, and 1,200 test transactions. The teaching table does not enter those partitions or the software metrics.

Now suppose a bank wants to design a transaction-record fraud classifier. At transaction time, the model reads amount, distance, merchant type, and merchant ID and estimates the probability of fraud; the later label y is used only for training and evaluation, not as an input. If these fields contain repeatable patterns related to fraud, no ready-made formula captures those relationships well, and the bank has enough representative historical records, a model can learn from the data. This is a binary-classification task.

Case B: Daily Store-Product Sales Data and the Next-Day Forecasting Task #

Start with the data. Each row records one product at one store on one day, together with product, store, date, promotion, discount, and historical-sales fields. The example column uses teaching row D1 throughout.

The CSV spans 20 products, two stores, and 120 days. The generator assigns each product a fixed effect \(v_s\) and gives the two stores effects \(v_u\) of \(-2\) and \(3\) units. For an ordinary generated row, sales for product \(s\), store \(u\), and day \(t\) follow:

Here \(W_t\) is 1 on weekends and 0 otherwise. The discount \(q_{s,u,t}\) is measured in percentage points, so a 10% discount enters the formula as 10. The noise \(\epsilon_{s,u,t}\) has a standard deviation of four units. The weekend, discount, and periodic effects are teaching assumptions, not estimates from a real store. A preset distribution selects the promotion type, which determines the ordinary rows’ discounts.

The historical feature is calculated separately from past sales. It must not include the forecast day’s own target:

The first seven days (days 0–6, 280 rows) provide history only. Days 7–79 contain 2,920 training rows, days 80–99 contain 800 validation rows, and days 100–119 contain 800 test rows. Every row in the full experimental dataset follows the generation mechanism above. D1–D8 live in the separate teaching CSV; their lag7 values are explicitly specified for arithmetic and do not enter the panel’s chronological partitions or software metrics.

Now suppose a retailer wants to design a next-day store-product sales model. After each daily close, the model uses the then-available sku_id, store_id, promo_type, discount, weekday, and lag7 fields to predict next-day sales y; business_date establishes chronological order. If these factors contain repeatable patterns related to next-day sales, no ready-made formula captures those relationships well, and the retailer has enough representative historical records, a model can learn from the data. This is a regression task. The current data assume sufficient inventory, so y is fully observed sales; under stockouts, recorded sales and latent demand can differ, and Chapter 9 returns to the definition of a demand-forecasting target. Both datasets preserve their original categorical fields, and Chapter 8 compares XGBoost, LightGBM, and CatBoost on the same fields and partitions.

For now, the important distinction is between features and targets; the library interfaces come later.

1. How Does a Decision Tree Perform Classification and Regression? #

1.1 Starting with Store Sales Prediction #

What records does a decision tree learn from? Start with eight rows from the Case B next-day store-product sales teaching data, one for each store–product pair on the same day. The discount and promotion are planned in advance; the seven-day mean uses sales observed before that day.

These rows were chosen for arithmetic, not sampled as a “typical store.” A simple illustrative regression tree uses only the planned discount:

               Discount ≤ 25%?
                /           \
              Yes            No
        Predict 21.6     Discount ≤ 35%?
                         /           \
                       Yes            No
                  Predict 60      Predict 116

D7, with a planned 40% discount, follows the rightmost path. That leaf contains D7 (92 units sold) and D8 (140 units sold), so its prediction for D7 is \((92+140)/2=116\) units. The 21.6-unit left leaf is the mean of D1–D5. These specified splits illustrate a path; they are not claimed to be the splits a model would learn from the complete CSV. A close fit to eight rows does not establish accuracy on future dates.

The example shows how a prediction follows one path. Before discussing how a tree grows and where it stops, let’s look at its structure.

1.2 The Structure of a Decision Tree #

Stripped of its feature names, the tree above has this shape:

                 Root              depth 0: 1 node
                 /  \
             Leaf  Split            depth 1: 2 nodes
                   /   \
                 Leaf  Leaf         depth 2: 2 leaves

Starting at the top:

• The root node makes the first decision;
• Internal nodes test feature conditions;
• Branches represent the outcomes of those tests;
• Leaf nodes output predictions;
• A path from the root to a leaf forms one prediction rule.

We count the root as depth 0 and add one for each branch followed downward. This tree has three levels and a maximum depth of 2. The levels contain 1, 2, and 2 nodes, respectively; its maximum width is 2. Width describes the shape, not a training parameter.

Each internal node has two children, so this is a binary tree. “Binary” describes the number of branches at a split, not the number of classes the tree can predict. Other decision trees can have more than two branches.

A decision tree need not assume a linear relationship between sales and discount. The three paths divide the inputs into three regions, each with its own prediction. This is the intuition behind the “piecewise constant function” described next.

1.3 A Decision Tree Is Essentially a Piecewise Constant Function #

To express these paths in a common notation, let \(i\) index samples and \(j\) index leaf nodes. Let \(N\), \(J\), and \(p\) denote the numbers of samples, leaves, and input features. For classification, \(k\) indexes classes and \(C\) is the number of classes. Later sections define new symbols where they first appear.

The input features for a record can be expressed as:

Each complete path on the tree corresponds to an input region. If there are \(J\) leaf nodes in total, there are \(J\) non-overlapping regions:

For a regression problem, the prediction function can be expressed as:

where:

• \(R_j\): The feature region corresponding to the \(j\)-th leaf node;
• \(c_j\): The prediction value for that leaf node;
• \(\mathbb{I}(\cdot)\): Indicator function, which is 1 if the condition is true, and 0 otherwise.

The region \(R_j\) contains possible feature values; let \(I_j=\{i:x_i\in R_j\}\) be the indices of training samples that fall into it. The quantity \(|I_j|\) is therefore the number of samples in the leaf. For an ordinary regression tree trained with squared error, the leaf predicts their mean target value:

In the illustrative tree, D7 and D8 both have discounts above 35% and enter the same leaf. Their sales are 92 and 140 units, so the leaf output is \((92+140)/2=116\) units. A regression tree approximates more complex relationships with such local constants.

For the Case A bank-transaction fraud-classification task, a tree still partitions records along paths. Its leaves now summarize legitimate and fraudulent samples rather than returning sales units.

Let the class index be \(k=1,\ldots,C\). For class \(k\), the empirical probability of a leaf node can be expressed as:

If the label is chosen directly from the leaf’s class probabilities, it is usually the class with the highest probability:

A predicted class and a predicted probability are different outputs. Binary classification can instead use a chosen decision threshold. If the Case A bank-transaction fraud model assigns a transaction a fraud probability of 0.72, a threshold of 0.5 flags it for review; a threshold of 0.8 does not. The review rule changes; the model’s probability does not. The training objective, probability estimate, and final business decision therefore need to be considered separately.

1.4 Fundamental Differences Between Classification and Regression #

Although classification trees and regression trees can adopt similar structures, their optimization goals differ.

In the Case A bank-transaction fraud-classification task, precision asks how many flagged transactions are fraudulent, while recall asks how many fraudulent transactions are found. False alarms consume investigators’ time; missed fraud can cause losses. In the Case B next-day store-product sales-forecasting task, MAE measures the average error in sales units, while Forecast Bias shows whether forecasts tend to run high or low. Sections 8.2 and 9.5 return to both cases to connect these metrics to business trade-offs.

This distinction affects both evaluation and the criteria used to split a tree. Split criteria guide training, while final evaluation metrics assess the fitted model; they are not interchangeable. Chapter 4 introduces the training loss used in boosting.

1.5 What Exactly Needs to Be Determined When Training a Tree? #

Both teaching cases distinguish features \(x_i\), available at prediction time, from the target \(y_i\). From here, we can set aside their particular CSV fields and write \(N\) training samples as \(D=\{(x_i,y_i)\}_{i=1}^{N}\).

The decisions made before and after training can be divided into three categories:

The second category is usually called hyperparameters or algorithm configuration, set by the modeler before training and selected through validation data if necessary. The third category is the model obtained from this training: it includes both the tree structure and the leaf node outputs, and should not be thought of as a fixed set of coefficients like in linear regression. How specific software names these settings can be referenced once the splitting principle is understood.

Now we can describe “training a tree” more concretely: it needs to decide both where to split and what each leaf node predicts. Taking a squared error regression tree as an example, let \(\mathcal T\) denote the tree structure, \(q_{\mathcal T}(x_i)\) denote the leaf node number that sample \(x_i\) falls into, and \(c_j\) be the prediction value of the \(j\)-th leaf node. Training aims to minimize, within the allowed trees:

For example, if the maximum depth \(d_{\max}\) is set and each leaf node must have at least \(n_{\min}\) training samples, then the allowed trees must also satisfy \(\operatorname{depth}(\mathcal T)\leq d_{\max}\) and \(|I_j|\geq n_{\min}\). Here, \(d_{\max}\) and \(n_{\min}\) are pre-training constraints; node splitting and \(c_j\) are obtained through training. Given the leaf node partitions, the mean formula from Section 1.3 gives the \(c_j\) that minimizes the squared error for that leaf node.

This objective also explains why tree complexity needs constraints. Sales for D1–D8 are 10, 14, 18, 26, 40, 60, 92, and 140 units. On these eight rows alone, a tree with no split predicts their mean of 50 units and has a training SSE of \(14{,}560\) units². A single split at discount \(\leq25\%\) sends D1–D5 left and D6–D8 right. Their leaf predictions are 21.6 and about 97.33 units, reducing SSE to about \(3{,}805.87\) units². Further splits could even give each row its own leaf and zero training error. That does not mean the deeper tree forecasts future sales better. The full experimental CSV holds out later dates for validation and testing; Chapter 9 also discusses multi-origin backtesting.

The formula specifies what training aims to minimize. It does not mean that standard CART searches every possible tree for a global optimum. Training usually starts at the root, compares candidate splits at the current node, chooses the locally best split, and repeats for the child nodes. Stopping and pruning rules also shape the final tree. Classification trees likewise learn a structure and leaf outputs, but typically assess splits with Gini impurity or information entropy and store class proportions in the leaves. Having separated what the modeler specifies from what the algorithm learns, we can now examine how a node compares candidate splits.

2. How Do Decision Trees Choose the Best Split? #

A tree’s central training decision is:

Which feature should be used, and where should the data be split?

Every candidate split raises the same question: Can the child nodes make better predictions than the parent? Different algorithms define “better” differently. This chapter presents ID3, C4.5, and CART in an order that makes their split criteria easier to compare, rather than in publication order.

2.1 ID3: Using Information Entropy to Measure Classification Uncertainty #

Quinlan introduced ID3 (Iterative Dichotomiser 3) in a 1986 paper[1]. The algorithm builds a tree by repeatedly selecting conditions that separate the classes in the training data.

When nearly all samples in a node belong to the same class, its prediction is relatively unambiguous. A mixture of classes makes the outcome less certain. ID3 quantifies this uncertainty with information entropy.

For a dataset \(D\) containing \(C\) classes, information entropy is defined as:

where \(p_k\) is the proportion of samples belonging to class \(k\).

Start with S1–S8 from the Case A bank-transaction fraud teaching data. The table shows only the merchant fields and labels needed for this calculation. Four transactions are legitimate, four are fraudulent, and each has a different merchant ID.

This deliberately balanced root node has entropy:

If all eight transactions belonged to one class, entropy would be zero. The 1-bit value describes the teaching table, not the full experimental dataset, where fraud makes up only 2.8%.

ID3 aims to find features that maximize the reduction in entropy.

For a candidate feature \(A\), Information Gain is defined as:

where \(D_v\) denotes the subset obtained by splitting according to value \(v\) of feature \(A\).

For example, merchant type separates five retail transactions, one fraudulent, from three digital transactions, all fraudulent. Weighted post-split entropy is \((5/8)H(1/5)\approx0.451\), so information gain is about \(1-0.451=0.549\) bits. A larger gain means less class mixture in these rows; a finer split need not generalize.

Limitations of Information Gain #

S1–S8 happen to have eight distinct merchant IDs. Grouping each row by its ID yields zero training entropy and a full 1-bit information gain—higher than merchant type’s 0.549—by memorizing labels. Merchant IDs recur in the full experimental dataset, so only validation can tell us whether an ID carries a stable signal. This illustrates why information gain can favor high-cardinality features.

2.2 C4.5: Using Gain Ratio to Correct Feature Selection Bias #

Quinlan extended this line of classification-tree research in his 1993 book C4.5[2]. Because information gain can favor features with many distinct values, C4.5 introduced gain ratio to counter that preference.

It introduced Gain Ratio:

where:

SplitInfo describes how many parts a feature itself divides the samples into, and the distribution of the sizes of these parts.

For S1–S8, merchant type forms groups of five and three, giving \(\mathrm{SplitInfo}\approx0.954\) and gain ratio \(0.549/0.954\approx0.575\). Eight unique merchant IDs give 1 bit of information gain but 3 bits of \(\mathrm{SplitInfo}\), so their ratio is about 0.333. The denominator reduces the score of a one-row-per-group split; it does not guarantee that gain ratio always picks the right feature.

When a split produces a very uneven partition, however, SplitInfo can be small and inflate the ratio. C4.5 therefore does not simply choose the highest ratio: it also uses information gain to screen candidate features.

Besides gain ratio, C4.5 also improved continuous feature handling, missing value treatment, and pruning mechanisms.

2.3 CART: Unifying Classification and Regression #

Breiman et al. presented Classification and Regression Trees (CART) in 1984[3], along a research path that developed in parallel with ID3 and C4.5. This article places CART after information entropy to make the split criteria easier to compare, not to imply a chronological order.

Unlike earlier decision tree methods primarily focused on classification, CART supports both classification and regression. Each CART split creates a left and a right child, yielding the binary tree structure introduced in Chapter 1.

Classification: Gini Impurity #

For classification tasks, CART often uses Gini Impurity:

For the four legitimate and four fraudulent rows in the Case A bank-transaction fraud teaching data:

For a candidate split, the model calculates the weighted impurity of the two child nodes after the split:

After splitting on merchant type, the retail group’s Gini impurity is \(1-(1/5)^2-(4/5)^2=0.32\), while the digital group’s is zero. The weighted impurity is \((5/8)\times0.32=0.20\), a reduction of 0.30. The model looks for a split that maximizes this reduction.

Regression: Squared Error #

For regression tasks, CART can use squared error to measure variation within a node. Here, \(D\) is the set of sample records in the current node, and \(D_L\) and \(D_R\) are the two subsets after a split:

where \(\bar y_D\) is the mean of the target values within the node.

The reduction in error from one split is:

Regression trees select the split that maximizes the reduction in squared error: the more similar the targets within each child node, the larger \(\Delta SSE\). Section 5.8 repeats D1–D8 from the Case B next-day store-product sales teaching data and works through one candidate split in full; this section keeps the criterion without repeating the same numbers.

Here, \(SSE\) is the sum of squared errors within a node. If an implementation instead reports node mean squared error, its sample-weighted reduction is proportional to \(\Delta SSE\) for candidate splits under the same parent, so the ranking is unchanged. The raw values still use different normalizations and should not be compared directly.

Both formulas describe the same structural action—partitioning the feature space—but optimize different goals: classification trees seek purer child nodes, while regression trees seek child nodes whose target values are closer together.

2.4 Why Are Decision Trees Prone to Overfitting? #

Chapter 1’s D1–D8 already reveal the overfitting risk. A tree that keeps splitting until each leaf contains one row can minimize training error while treating random fluctuations, measurement errors, or incorrect labels as general patterns.

In the Case B next-day store-product sales teaching data, D8 sold 140 units during a deliberately specified high-discount promotion; its size alone does not make it an error. Section 8.10 separately injects recording errors into about 3% of training labels. A tree that overfits those corrupted rows may create paths for values that were never true sales.

Common methods to control tree complexity include:

• Limiting the maximum depth;
• Setting the minimum samples per leaf node;
• Limiting the number of leaf nodes;
• Requiring a sufficiently large error reduction from a split;
• Using pruning to remove branches that do not provide sufficient generalization benefit.

These restrictions can typically reduce memorization of training records, but if too strict, they might miss useful distinctions. Finding a balance between fitting the training data and performance on new samples is precisely the starting point for discussing multiple trees in the next chapter.

Interface comparison.

The training settings from Chapter 1 map to parameters such as criterion, max_depth, and min_samples_leaf in scikit-learn’s DecisionTreeRegressor; they are not the node-specific split locations learned during training. The squared-error example above corresponds to criterion="squared_error". The interface also offers absolute-error and Poisson criteria, which change how splits and leaf outputs are evaluated[4]. Its documentation defines squared_error using node mean squared error, so values reported by the interface should not be read as the unnormalized \(\Delta SSE\) used above.

3. Why Isn’t One Tree Enough? From Bagging to Random Forest #

3.1 The High Variance Problem of a Single Decision Tree #

A single decision tree can be unstable. It may memorize outliers, and a small change in the training sample can change the feature chosen at the root. That change can reshape later branches and alter predictions for new records. In statistical learning, this sensitivity to the training sample is called variance.

For squared-error regression, fix an input \(x\) and consider how the fitted model changes across training samples. Assuming, among other things, that the noise in a new observation is independent of the training sample, the expected error at that input decomposes as:

where:

• \(\operatorname{Bias}(x)\) is the difference between the model’s average prediction at \(x\) and the true conditional mean \(\mathbb E[Y\mid X=x]\);
• \(\operatorname{Var}(\hat f(x))\) is the variance in predictions caused by changes in the training sample;
• \(\sigma^2(x)\) is the irreducible variance of the target at that input.

To discuss overall prediction error, we must also average over the distribution of inputs \(x\). This statistical bias is distinct from the Forecast Bias metric in Section 9.5, which measures overall over- or underforecasting.

A fully grown tree may fit the training data closely yet produce quite different predictions when the sample changes. Could averaging predictions from several slightly different trees make the result more stable?

3.2 Bagging: Training Multiple Trees and Averaging Predictions #

In his 1996 paper on Bagging (Bootstrap Aggregating), Breiman proposed using resampling and prediction averaging to improve unstable learners[5]. For decision trees, the idea is direct: train multiple trees independently, then combine their predictions.

Bagging creates multiple bootstrap datasets by sampling with replacement from the original training data. Each dataset trains one tree, and the final model combines their predictions. A record may appear several times in one bootstrap sample and not at all in another, creating variation among the trees.

Let \(B\) trees be trained in total, with the prediction of the \(b\)-th tree denoted as \(\hat f_b(x)\). For regression tasks:

For classification tasks, class probabilities can be averaged:

Then, the predicted class is chosen based on these probabilities.

If the prediction errors of multiple trees are not perfectly correlated, averaging predictions can generally reduce variance.

At a fixed input \(x\), write the average above as \(\bar f(x)=\hat f_{bag}(x)\). Let the variance of each tree’s prediction be \(v\), and the correlation coefficient between predictions of any two trees be \(\rho\). Under the simplified assumption of equal variance and equal correlation, the variance of the average prediction is:

For example, if \(v=100\) and \(\rho=0.2\), the variance of the average prediction of 10 trees under this simplified model is \(0.2\times100+0.8\times100/10=28\); even if the number of trees continues to increase, the first term (20) will not disappear. This illustrates that the more similar the trees are, the harder it is to further reduce fluctuations by simply increasing their number.

Adding trees is not enough; their errors also need to be less correlated.

3.3 Random Forest: Reducing Correlation through Feature Randomization #

Breiman presented random forests in 2001[6]. Bagging can reduce variance through averaging, but trees that repeatedly rely on the same strong features may still make highly correlated errors.

A random forest adds feature sampling to bagging: at each split, a tree considers only a randomly selected subset of features. A strong feature may therefore be absent from some candidate sets, giving other features a chance and making the trees more diverse.

In the Case B next-day store-product sales-forecasting task, suppose discount often explains much of the training error. Bagged trees may repeatedly prefer it. By considering only some features at each split, a random forest gives the seven-day sales mean or product identity a chance to influence a split. This explains the mechanism; it does not claim which field actually dominates on the full CSV.

The basic random-forest process is:

Training Data
   |
   +-- Bootstrap Sample 1 --> Tree 1 --+
   |                                    |
   +-- Bootstrap Sample 2 --> Tree 2 --+--> Average or Vote
   |                                    |
   +-- Bootstrap Sample 3 --> Tree 3 --+
   |
   +-- ...

The trees in a random forest can be trained relatively independently, which makes the method easy to parallelize.

This is fundamentally different from Boosting, which will be discussed later.

3.4 Distinction Between Bagging and Boosting #

Before delving into how Boosting optimizes loss iteratively, let’s first overview the overall differences between these two ensemble approaches.

A random forest is not an older version of GBDT, and GBDT is not a simple upgrade to a random forest.

Interface comparison. An algorithm’s feature-randomization mechanism is not necessarily enabled by a library’s defaults. The scikit-learn RandomForestRegressor used in the experiments defaults to max_features=1.0, so every node considers all features. To restrict each split to a feature subset, set a smaller max_features explicitly. bootstrap=True controls sampling with replacement[7].

The next chapter will follow the “iterative correction” approach from the table, examining how a subsequent tree determines its correction direction.

4. From Boosting to GBDT: How a Subsequent Tree Corrects a Previous One #

4.1 Boosting: Incrementally Constructing Stronger Predictive Models #

Bagging trains trees relatively independently and averages their predictions. Boosting instead adds models in sequence, using each new model to improve the current prediction. The key question is how to determine that correction.

Freund and Schapire studied AdaBoost in a representative 1997 paper[8]. In binary classification, AdaBoost changes sample weights so that later weak learners pay more attention to previously misclassified cases. Suppose training runs for \(M\) rounds and produces weak learner \(h_m\) in round \(m\).

The final model can be expressed as:

where:

• \(h_m(x)\) is the \(m\)-th weak learner;
• \(\alpha_m\) is the combination weight for this learner.

AdaBoost organizes training primarily by changing sample weights. Gradient boosting instead connects each round’s correction to the optimization of a general loss function.

4.2 GBDT: Viewing the Training Process as Function Optimization #

In a 2001 paper on gradient boosting machines, Friedman linked the incremental addition of models to the gradient of a loss function, providing a general framework for additive models[9]. With decision trees as base learners, this approach is commonly called gradient boosted decision trees (GBDT). A random forest primarily reduces variance by averaging predictions; GBDT uses the loss to guide each successive tree’s correction.

Assume the model is composed of multiple trees added together:

Where \(M\) is the total number of rounds, \(m\) is the current round; \(F_0(x)\) is the initial prediction, \(f_m(x)\) is the \(m\)-th tree, and \(\eta\) is the learning rate.

GBDT aims to minimize the training loss:

Here \(l\) is the loss for one sample, while \(\mathcal L\) sums it over the training data. Chapter 5 keeps this distinction when adding a penalty for tree complexity.

It updates the prediction function in an additive, step-by-step manner:

The key is not merely to add another tree, but to determine how the \(m\)-th tree should correct the current prediction. Under squared error, residuals make that direction intuitive; under a general loss, it comes from the gradient.

4.3 From Residuals to Negative Gradients #

Consider D6 in the Case B next-day store-product sales teaching data: it sold 60 units, and we explicitly start all eight rows at a 50-unit prediction. How does squared error tell the next tree to correct upward? Let the loss be:

Taking the derivative with respect to the model’s prediction:

The negative gradient is therefore:

Under squared error, the negative gradient is the prediction residual. For D6:

The next tree learns a correction, not the final sales volume. Here it tries to account for the 10 units the current prediction missed.

For a general loss function, GBDT uses the negative gradient:

Saying that “GBDT learns residuals” is accurate for squared error. More generally, the negative gradient of the loss at the current prediction guides the next tree.

4.4 GBDT in Classification Tasks #

For binary classification problems, the model typically does not directly sum class labels, but rather sums raw prediction scores.

Let:

Here, \(\sigma\) is the sigmoid function.

The binary log loss is:

Taking the derivative with respect to the raw score \(F(x_i)\):

Classification and regression therefore produce different gradient formulas, but the overall GBDT framework remains unchanged: the model still optimizes the loss by adding trees round by round.

4.5 Relationship with Machine Learning Optimization Theory #

GBDT can also be compared with familiar parameter-optimization methods. The earlier article “Optimization in Machine Learning: From Gradient Descent to Boosting, Neural Networks, and MAP” discusses losses, gradients, and regularization in more detail; here, the comparison is limited to what each method updates.

Standard gradient descent directly updates the parameter vector:

Gradient boosting instead adds new base learners in function space:

Both methods utilize the local direction of change of the loss function to optimize the model, but their update objects and mechanisms differ. This idea lays the foundation for understanding XGBoost’s second-order optimization.

5. XGBoost: How to Optimize Tree Models Using Second-Order Information? #

Chen and Guestrin presented XGBoost (Extreme Gradient Boosting) in their 2016 paper[10]. Gradient boosting was already established; the challenge was to train it efficiently as datasets grew. Tree training repeatedly reads features and evaluates candidate splits, so larger datasets raise both computation and data-access costs.

This chapter asks two questions: How large should the correction at each leaf be? And how can candidate splits be evaluated efficiently on large datasets? XGBoost addresses them through a regularized objective, a second-order approximation, sparse-feature handling, and systems-level optimizations.

5.1 XGBoost’s Prediction Function #

Assume the model adds \(M\) trees iteratively. Following Chapter 4’s notation \(F_m\) for the raw prediction score of an additive model, the model’s prediction score after \(M\) iterations is:

where each tree belongs to the function space:

A single tree can be represented as:

Here:

• \(q(x)\) maps an input sample to a leaf node;
• \(w_j\) is the output weight of the \(j\)-th leaf node;
• \(J\) is the number of leaves in this tree; \(q(x)=j\) is equivalent to \(x\in R_j\). The weight \(w_j\) corresponds to Chapter 1’s \(c_j\), but represents an increment in the additive model.

This is consistent with the piecewise constant function form in Chapter 1, but the role of leaf nodes differs: In Chapter 1, \(c_j\) is the direct prediction value given by a single regression tree; whereas here, \(w_j\) typically serves as an increment, added to the current prediction score, rather than being the direct final prediction.

In regression tasks, this increment can be used to adjust prediction values, such as sales.

In classification, this increment typically updates a raw score such as a logit, which a sigmoid or softmax function converts into a probability. The rest of the article uses \(z_i^{(m)}\) for the raw score optimized during training, \(\hat p_i=\sigma(z_i^{(m)})\) for a binary-classification probability, and \(\hat y_i\) for a regression prediction. Under squared-error regression, \(\hat y_i=z_i^{(m)}\).

5.2 Objective Function: Data Loss and Model Complexity #

Training error alone cannot assess whether a correction is useful: the model also needs a penalty against creating too many leaves for a few records. XGBoost therefore combines data loss with model complexity:

where:

• The first term measures the model’s prediction error;
• The second term constrains the complexity of the tree model.

Different rounds can produce trees with different numbers of leaves. In the single-candidate-tree derivation below, \(J\) counts only that tree’s leaves; if we expanded the \(m\)-th term in the sum above, we would write its leaf count as \(J_m\).

For a typical tree model, its regularization term can be expressed as:

where:

• \(\gamma\) controls the complexity cost required for adding new leaf nodes;
• \(\lambda\) controls the strength of L2 regularization on leaf node weights.

Here, \(\gamma J\) penalizes the number of leaf nodes, which differs from L1 regularization that takes the absolute value of leaf node weights.

If L1 regularization is enabled, the following term must also be added to the objective function:

The objective now penalizes both additional leaves and large leaf weights. The next question is how to evaluate the costs and benefits of many candidate tree structures efficiently.

5.3 Why Use Second-Order Taylor Expansion? #

The next sections derive optimal leaf weights and split gain. Section 5.8 then works through D1–D8 from the Case B next-day store-product sales teaching data. Keep two questions in mind: how much should a leaf correct, and is a split worth making?

Assume \(m-1\) trees have been trained, and we are now ready to add the \(m\)-th tree. To derive the optimal leaf node weights for a candidate tree, we first examine a tentative update without the learning rate:

We construct a local objective function for this tentative update; after finding the optimal leaf node weights, the actual model will still be updated according to \(z_i^{(m)}=z_i^{(m-1)}+\eta f_m(x_i)\):

Directly searching all possible tree structures is usually computationally infeasible. XGBoost instead estimates “how the loss function changes when the current prediction score is slightly modified.” To do this, it performs a second-order Taylor approximation of the loss function:

where:

These respectively represent the first-order gradient and second-order derivative of the loss function with respect to the prediction value. To build an intuitive understanding, let’s first examine the squared error loss function: if \(l(y,z)=\frac12(y-z)^2\), then the first-order gradient \(g_i=z_i^{(m-1)}-y_i\), and the second-order derivative \(h_i=1\). The gradient \(g_i\) describes the direction of change of the loss function with respect to the prediction value (negative gradient being the direction of descent), while the second-order derivative \(h_i\) is a constant in this example. The case for classification loss functions will be compared and explained in Section 5.7.

After removing the constant term \(l(y_i,z_i^{(m-1)})\) unrelated to the current new tree, the simplified objective function is:

This second-order Taylor expansion is a local approximation, not an exact identity for every loss function.

5.4 From Sample Gradients to Leaf Node Statistics #

Assume the current candidate tree has \(J\) leaf nodes.

Recall the set of sample indices from Section 1.3. The leaf mapping \(q\) now describes the same set as:

Since samples within the same leaf node have the same tree output:

We can therefore aggregate the samples’ first derivatives and second derivatives (Hessians) within each leaf:

The objective function then becomes:

This crucial step aggregates the per-sample loss changes (represented by \(g_i\) and \(h_i\)) into the statistics \(G_j\) and \(H_j\) for each leaf node. As a result, instead of checking changes for each individual sample, we now only need to combine information within the same leaf node; after a candidate split is given, the correction magnitude can be efficiently calculated by aggregating the statistics of the left and right child nodes separately.

5.5 Optimal Leaf Node Weights #

With the split positions temporarily fixed, the next step is to determine the magnitude by which each leaf node should correct. After fixing the tree structure, we differentiate the objective function with respect to a leaf node weight \(w_j\):

Setting the derivative to zero, we solve for \(w_j\):

Yielding:

This assumes L1 regularization is not enabled, and the denominator \(H_j+\lambda\) is positive.

This formula indicates:

• The sum of gradients \(G_j\) determines the direction of update;
• The sum of Hessians \(H_j\) reflects the local curvature of the loss function;
• The regularization parameter \(\lambda\) shrinks large leaf outputs and helps control overfitting.

If L1 regularization is enabled, the optimal weight \(w_j^*\) undergoes soft-thresholding:

This allows leaf node weights to be shrunk to zero when the gradient signal is weak.

5.6 How XGBoost Determines if a Split Is Worthwhile #

After determining the optimal correction magnitude for each leaf node, we still need to decide whether splitting a node is worth the additional complexity cost. As in the first formula of Section 5.5, the following derivation assumes L1 regularization is disabled. Substituting those optimal leaf weights gives the minimum approximate objective for the current tree structure:

For a candidate split point, let its parent node’s statistics be \(G\) and \(H\), and the statistics for the left and right child nodes be:

Then the Split Gain for this split is:

If the Gain is greater than zero, it indicates that, under consideration of the current approximate objective function and complexity penalty, the benefit of splitting into an additional leaf node outweighs its cost, meaning the split is advantageous.

This calculation turns the local optimization problem into a score that the tree search can evaluate efficiently.

Section 5.7 explains where the gradients come from for each task. Section 5.8 then compares split gain, CART’s SSE reduction, and GBDT’s residual update on the same retail rows.

5.7 Why Do Gradients Differ for Classification and Regression? #

Although XGBoost’s tree structure search employs a unified \(G,H\) statistical framework, different tasks generate different gradients and Hessian statistics.

Regression: Squared Error #

Section 5.3 showed that, for squared error \(l(y,z)=\frac12(y-z)^2\), sample \(i\) has gradient \(g_i=z_i^{(m-1)}-y_i\) and second derivative \(h_i=1\) at the start of round \(m\). The negative gradient is the residual, and the Hessian is constant. A classification loss produces different statistics.

Binary Classification: Logistic Loss #

For sample \(i\), let:

Then:

In classification, the Hessian \(h_i\) changes with the predicted probability \(\hat p_i\).

S1–S8 from the Case A bank-transaction fraud teaching data make the classification gradients concrete. The table repeats only the amount, distance, and true label needed for this calculation; \(y=0\) means legitimate and \(y=1\) means fraud.

For hand calculation, explicitly set every row’s initial probability to \(p_i^{(0)}=0.5\), which corresponds to raw score \(z_i^{(0)}=0\). Substitute S1’s label \(y_1=0\) into the formulas above:

For fraudulent transaction S5, \(g_5=0.5-1=-0.5\), while \(h_5=0.25\). At the same initial probability, the classes have opposite gradient directions but the same Hessian.

Where does S1’s next probability come from? Specify a teaching tree that first splits at amount \(\leq350\), then splits its left child at distance \(\leq160\). S1–S4 share one leaf. S8 has an amount below 350 but a distance of 300 km, so it goes to a different leaf. The S1–S4 leaf therefore has \(G=4(0.5)=2\) and \(H=4(0.25)=1\). Set \(\lambda=1\) and learning rate \(\eta=0.3\). The leaf-weight formula from Section 5.5 gives:

S1’s probability therefore becomes \(p_1^{(1)}=\sigma(-0.3)\approx0.4256\). Substituting it back into the same gradient formulas for round two gives:

This specified split shows how the data lead to the update; it is not a claim that a library learns the same tree on the full experimental dataset. Four of these eight teaching rows are fraudulent. Section 8.9 evaluates models on the independently generated, imbalanced data from the same case.

Even if two groups of samples have the same gradient sum \(G_j\), their Hessian sums \(H_j\) can differ, changing both the optimal leaf weight \(w_j^*\) and the split gain. This is how the same tree-search framework supports different objectives through their corresponding gradients and Hessians.

5.8 CART, GBDT, and XGBoost on the Same Data Set #

Continue with Chapter 1’s D1–D8. To make the arithmetic easy to check here, the table repeats only the planned discount and sales used in this section. These are the same eight rows from the Case B next-day store-product sales teaching CSV, not a new dataset.

Fix one candidate split: planned discount \(\leq25\%\). D1–D5 go left, D6–D8 right, and the eight-row mean is 50 units. CART uses that mean to measure node error. For the GBDT and XGBoost teaching calculations, we explicitly set their starting prediction to 50 units and learning rate to \(\eta=0.3\). The rows and split stay fixed, but each method computes something different. These specified calculations are not the first trees automatically learned by the libraries on the full CSV.

CART: Predict the Leaf Means Directly #

CART asks how much this split reduces the training sum of squared errors (SSE). Before the split, the parent predicts 50 units for every row:

After the split, the left leaf predicts \((10+14+18+26+40)/5=21.6\) units, and the right predicts \((60+92+140)/3\approx97.33\). Their SSEs are 563.20 and about 3,242.67 units², respectively, so CART’s reduction is:

GBDT: Fit Residuals, Then Apply the Learning Rate #

GBDT starts with \(F_0(x_i)=50\) units and asks what its first tree should correct. With squared error, the first round’s negative gradients are the sample residuals:

With the same split, the tree fits a mean residual of \(-142/5=-28.4\) units on the left and \(142/3\approx47.33\) on the right. These are corrections, not final forecasts. With learning rate \(\eta=0.3\):

Substituting these predictions for D1–D5 and D6–D8 gives a training SSE of about 9,075.39 units². One shrunken update has not reached CART’s direct leaf means.

XGBoost: Aggregate Gradients and Hessians to Score the Split #

XGBoost also starts with the specified \(z_i^{(0)}=50\) units, but first scores the candidate split using gradients and Hessians. With per-sample loss \(l(y_i,z_i)=\frac12(y_i-z_i)^2\), they are:

The gradients have the opposite signs from the GBDT residuals above; the squared-error Hessians all equal \(1\). Aggregating them under the same split gives these parent- and child-node statistics:

Set the L2 penalty on leaf weights to \(\lambda=1\) and the leaf-count penalty to \(\gamma=100\). The split-gain formula from Section 5.6 gives:

The positive net gain says the split helps under this teaching objective; \(\gamma\) has already been subtracted. The leaf weights are \(-142/6\) and \(142/4=35.5\), before applying the learning rate. If \(\lambda=0\), they would instead be \(-142/5=-28.4\) and \(142/3\approx47.33\), exactly matching the residual corrections in the GBDT calculation above. Here, \(\lambda=1\) changes the denominator from \(H_j\) to \(H_j+\lambda\), shrinking both leaf weights toward zero. This regularization explains why the XGBoost update differs from the preceding GBDT update. With \(\eta=0.3\), the left and right predictions become 42.9 and 60.65 units, with training SSE 10,111.32 units². A library searching the full CSV need not choose this split or report the same internal score.

The table puts the predictions after the specified steps on a common SSE scale. GBDT and XGBoost each show one update with \(\eta=0.3\):

The last column checks predictions using the same SSE definition; it is not a model ranking. CART’s 10,754.13 is an SSE reduction without the \(\frac12\) factor. GBDT’s 9,075.39 is an SSE after an update. XGBoost’s 4,100.83 is an approximate, regularized net gain before shrinkage. These quantities should not be compared as if they shared a definition.

The useful distinction is what each method computes. CART predicts leaf means directly. Under squared error, GBDT fits residuals with the next tree and updates in rounds. XGBoost uses gradients and Hessians to calculate candidate split gains and leaf weights.

D1–D8 show one specified split. The next section compares alternative thresholds on those same teaching rows and asks why the two branches need not grow together.

5.9 From a Hand-Worked Split to an Efficient Search #

Section 5.8 supplied discount \(\leq25\%\) in advance. During training, the model does not know that threshold; fields such as the seven-day sales mean in the Case B next-day store-product sales data can also be candidate features. First focus on discount and place the statistics needed for the search beside the calculation:

The rows are ordered by discount, so their gradients and Hessians can be accumulated from top to bottom to see what the search computes.

Move all rows at the same discount value to the left together. Running sums give \(G_L,H_L\); subtract them from the parent’s \((G,H)=(0,8)\) for the right side. Keep \(\lambda=1,\gamma=100\) and apply the Section 5.6 formula to five candidates:

In the first row, only D1 and D2 go left, so their gradients sum to \(40+36=76\); the right-side sum is \(-76\). Substitution gives about 1,275.24 net gain. Among discount thresholds at this node, 25% scores highest. We must still compare other features. After the root splits, the search repeats within each child.

Now consider the children. The root’s left child contains D1–D5; the right contains D6–D8. Their sales distributions differ, so a further split need not help both.

Now compare candidate splits within each child. Every \((G,H)\) below comes from the eight row-level gradients in Section 5.8. The best left-child candidate separates D1–D4 from D5. On the right, discount \(\leq35\%\) and seven-day mean sales \(\leq37.5\) both separate D6 from D7–D8 and therefore have the same net gain. The table keeps the discount split for continuity with the preceding example.

The branches need not keep growing together: even the best left-child candidate has negative net gain, so only the right branch grows under these assumptions. The three leaf weights are \(-142/6\), \(5\), and \(44\). With \(\eta=0.3\), their updated predictions are \(42.9\), \(51.5\), and \(63.2\) units. The last record still has second-round gradient \(g_i^{(2)}=63.2-140=-76.8\). Because these net gains already subtract \(\gamma\), we compare them with zero, not with \(\gamma\) again.

Checking every original feature value is easy to follow by hand, but more observations mean more candidates and more data access. XGBoost can instead use a histogram method: map continuous values to a finite set of bins, aggregate \(G,H\) by bin, and compare splits at bin boundaries. This reduces candidate positions, but constructing the histograms still requires processing observations. Section 6.1 uses discounts from the Case B next-day store-product sales teaching data as a shared starting point for the LightGBM comparison.

In practice, a record in the Case B next-day store-product sales data might be missing its planned discount while still having a sales label, gradient, and Hessian. For a candidate threshold, the algorithm compares sending missing values left or right and stores the better default direction. The fixed teaching CSV deliberately has no missing discount, so this deployment boundary is not part of the eight-row calculation.

Multithreading, cache-aware layout, compression, and sharding are not steps to perform only after a split. They are system techniques for running the same search across more features, observations, and computing resources. XGBoost’s 2016 paper discusses these designs[10]. If memory or disk access dominates repeated feature reads, a cheap gain formula alone will not make training fast. Actual benefits depend on the data and hardware, not merely the algorithm’s name.

5.10 XGBoost’s Interface: Parameter Mapping and Version Boundaries #

The paper explains algorithm design, but engineering code must conform to the interface of the installed version. The following explanations are based on the XGBRegressor and XGBClassifier Python APIs of XGBoost 3.4.2, accessed on October 14, 2026[11]. The comparative experiments in Section 8.9 use XGBoost 3.4.1; version 3.4.2 is cited here only because it was the documentation version checked for this discussion. Readers reproducing the experiments should verify the interface of their installed version. For categorical features, tree parameters, and multi-output limitations, consult the official categorical-data tutorial, parameter reference, and multi-output tutorial.

Regularization parameters. The L1 term in Section 5.2 corresponds to reg_alpha, and the L2 term corresponds to reg_lambda. The article’s \(\gamma J\) is a structural cost per added leaf; in the training API, gamma is an alias of min_split_loss, the minimum loss reduction required to make a further partition. The theory and interface therefore express closely related complexity control at different levels, rather than mapping \(\gamma\) to a learned leaf weight.

Histogram method. The binning construction introduced in Section 5.9 can be selected via tree_method="hist" in the interface; it differs from splitting methods that compare raw values one by one.

Categorical features require the right data type and tree method. XGBoost has provided experimental native categorical support since version 1.5; since version 3.3, the Python DataFrame workflow enables it by default. With the scikit-learn interface, the relevant Pandas columns still need the category dtype; older releases usually also require enable_categorical=True. Categorical splits do not support the exact tree method, so use hist or approx. Save models containing categorical splits as JSON or UBJSON to preserve the category metadata.

Tree growth strategy is configurable. grow_policy="depthwise" prioritizes nodes closer to the root, while grow_policy="lossguide" prioritizes nodes with the largest loss reduction; the latter is available only with hist or approx. Describing XGBoost as inherently level-wise would therefore hide an important configuration choice.

Multi-output capabilities still have experimental boundaries. The Python package has experimentally supported multi-output regression and multi-label classification since version 1.6. The default multi_strategy="one_output_per_tree" builds a model for each target; multi_output_tree, introduced in version 2.0, uses vector leaf nodes and requires tree_method="hist". The XGBoost 3.4.2 documentation still describes multi-output support as experimental and limited, and vector-leaf trees as a work in progress with many features unavailable. Before production use, it should be independently verified for the number of targets, target correlation, serialization, and explanation tools, rather than just confirming that fit() can run.

6. LightGBM: How to Train Gradient Boosting Trees Faster? #

Chapter 5 used \(G,H\) and split gain to answer which split is worth making. It also exposed the cost of searching candidates and reading data. In a 2017 paper, a Microsoft Research team introduced LightGBM[12] to tackle the same practical question: as observations and features multiply, how can we make split search less expensive?

LightGBM also builds an additive model through gradient boosting and evaluates splits with gradient and Hessian statistics. The distinction is not first-order versus second-order optimization, nor does either library have a monopoly on histograms. This chapter first makes that shared foundation concrete with a binning example. It then compares which leaf grows next, which observations and features are processed, and when those choices help.

6.1 Histogram: Reducing Candidate Split Locations #

Section 5.9 explained why binning reduces the number of candidate splits. Now consider how the bin statistics are built. LightGBM maps continuous values to a finite number of bins and compares splits at bin boundaries instead of testing every original value. XGBoost’s histogram method follows the same basic approach.

Use the eight records from the Case B next-day store-product sales teaching data again. To show the arithmetic, we specify three discount bins for teaching; they are not necessarily the boundaries LightGBM would learn:

The first bin sums the gradients of D1–D5: \(40+36+32+24+10=142\). Its Hessian sum is \(1+1+1+1+1=5\). Merging the first two bins gives cumulative statistics \((G,H)=(132,6)\). We compare their boundary rather than every raw discount value. The boundary after the first bin represents Chapter 5’s \(25\%\) candidate split; retaining other raw thresholds would require finer bins.

Let \(\mathcal B_\ell\) be the set of sample indices in bin \(\ell\). The model accumulates the bin statistics \(G_\ell=\sum_{i\in\mathcal B_\ell}g_i\) and \(H_\ell=\sum_{i\in\mathcal B_\ell}h_i\), then compares split gains at bin boundaries. Chapter 5’s \(G_j,H_j\) aggregate samples in a leaf; here \(\ell\) indexes bins and is also distinct from the random-forest tree index \(b\). Binning sacrifices some precision in split locations in exchange for lower candidate-scanning and storage costs.

Histograms are shared ground, not a speed advantage unique to LightGBM. With those bin statistics in hand, which leaf should the tree expand next? How does LightGBM reduce the observations and features involved in the calculation?

6.2 Level-wise vs. Leaf-wise #

After binning, the tree still needs to decide which node to expand next. The teaching tree for the Case B next-day store-product sales task already has two children at the root. Under Chapter 5’s teaching objective and parameters, the left candidate has net gain \(-12.93\), while the right has \(308.50\). Only the right is worth splitting under those assumptions. This illustrates the leaf-wise choice; it does not claim that LightGBM must report the same internal gain as XGBoost. The diagrams use abstract nodes A and B to show the growth order when more candidates appear.

Level-wise #

The typical Level-wise strategy expands nodes according to the tree’s levels:

          Root
         /    \
        A      B
       / \    / \
      C   D  E   F

Level-wise growth traverses and considers all expandable nodes at the same level, making overall depth easier to control.

Leaf-wise #

LightGBM’s leaf-wise strategy prioritizes the leaf with the highest current gain. In the diagram, A represents the leaf worth expanding and B a leaf that stops. If A has the larger gain, the tree splits it first; if one of A’s children then has the largest gain, growth continues along that path:

          Root
         /    \
        A      B
       / \
      C   D
         / \
        E   F

If a certain local region still has significant room for loss reduction, the model prioritizes further splitting there. This can improve the local training objective more with the same number of leaves, but it does not guarantee lower test error. When training data are scarce, noise is high, or leaves contain too few samples, the model may over-partition local regions.

Leaf-wise trees therefore need joint controls on leaf count, depth, samples per leaf, and leaf-weight updates. Limiting only the number of leaves can still allow a few paths to grow too deep.

Level-wise and leaf-wise are two tree growth strategies and should not be seen as permanent labels for the two frameworks. Which strategies a specific framework supports depends on its interface configuration.

6.3 GOSS: Prioritizing Samples with Larger Gradients #

Leaf-wise addresses the problem of “which node to expand first.” Another performance bottleneck comes from the number of samples that need to be scanned when calculating candidate splits. GOSS (Gradient-based One-Side Sampling) is one of the sample-level acceleration methods proposed in the LightGBM paper[12].

GOSS starts from the observation that samples with larger absolute gradients can have more influence on the next split decision. Such samples often have larger errors under the current model.

GOSS’s strategy is therefore:

1. Retain samples with larger absolute gradient values;
2. Randomly sample a portion of samples with smaller gradients;
3. Apply weight correction to the sampled small-gradient samples;
4. Use these samples to estimate split gain.

The aim is to reduce computation while retaining information that matters for choosing splits, not simply to discard easy-to-predict samples. The companion experiment separately fits LightGBM with GOSS explicitly enabled; a small dataset and one run cannot establish a speed advantage.

Large gradients do not guarantee high-quality samples: incorrect labels can also produce large gradients. With a few erroneous records, the model may repeatedly focus on those errors. GOSS reduces sample scanning, but it cannot replace label-quality checks; boosting models more generally face the same issue.

6.4 EFB: Reducing Computational Cost for Sparse Features #

GOSS reduces the number of samples participating in statistics; if there are many feature columns, can we also reduce the number of columns that need to be scanned independently? EFB (Exclusive Feature Bundling) is another technique proposed by LightGBM[12].

It leverages the potential mutual exclusivity among sparse features to bundle multiple features into a more compact representation.

For example, some One-hot encoded features do not simultaneously take non-zero values:

Category_A  Category_B  Category_C
    1           0           0
    0           1           0
    0           0           1

If multiple features are sufficiently exclusive, feature bundling can reduce the number of effective features that need to be processed. In the Case A bank-transaction fraud data, one-hot columns for merchant type contain exactly one nonzero entry per row. This illustrates a structure EFB can exploit, not a measured saving in runtime or memory.

However, sparse features in real data are not necessarily strictly exclusive, and practical implementations still need to handle potential conflicts. How much computational overhead EFB can save depends on feature sparsity and data structure.

GOSS reduces the samples used for split statistics; EFB reduces the features scanned separately. Together, they address the costs of large datasets and high-dimensional inputs described in the 2017 paper[12]. As memory and parallel capacity grow, avoiding unnecessary scans helps use those resources for the statistics that influence splits.

6.5 Categorical Features Do Not Always Need One-hot Encoding #

The preceding text used one-hot features to explain EFB. But the two CSVs already contain categorical fields: merchant type and ID in the Case A bank-transaction fraud data, and product ID, store ID, and promotion type in the Case B next-day store-product sales data. Must they all become one-hot columns? The 80 merchant IDs in the full Case A dataset make the issue tangible: more categories can mean many more encoded columns.

For high-cardinality categorical features, one-hot encoding can greatly increase the number of input columns. LightGBM can instead find category partitions from gradient statistics without always expanding categories into many one-hot columns. That does not make fields such as sku_id and store_id automatically safe or useful: they may capture genuine business differences, or encourage memorization of entities repeated in the training set. Whether they generalize depends on whether validation correctly simulates future deployment.

For example:

• If the same batch of stores and products will be predicted in the future, historical entity information might be valuable;
• If new stores or products need to be predicted in the future, the model’s ability to handle unseen categories becomes even more critical.

6.6 Why LightGBM Is Not Necessarily Faster Than XGBoost #

LightGBM demonstrates excellent training efficiency in many large-scale tabular data tasks, but its speed advantage is not unconditionally guaranteed.

Actual performance depends on multiple factors:

• Number of samples and features;
• Ratio of continuous and categorical features;
• Feature sparsity;
• CPU, GPU, and memory configurations;
• Tree depth, number of leaves, and number of bins;
• Whether appropriate training algorithms are enabled;
• Software version used.

Comparisons between XGBoost and LightGBM should use the same validation design, comparable compute budgets, and similarly reasonable parameter-search ranges.

Without those controls, an apparent algorithmic difference may simply reflect different defaults or experimental conditions.

6.7 LightGBM Interfaces and Cross-Framework Engineering Boundaries #

The preceding text introduced algorithmic-level designs, but actual performance also depends on its interface and default settings. The following explanations are verified against the LGBMRegressor and LGBMClassifier Python APIs of LightGBM 4.7.0 (accessed on: October 14, 2026)[13]. GOSS default values and categorical handling mechanisms are based on the official Parameters documentation and Advanced Topics.

Tree Complexity Parameters. The number of leaf nodes and tree depth mentioned in Section 6.2 can be limited by num_leaves and max_depth respectively. min_data_in_leaf and min_sum_hessian_in_leaf constrain the conditions for leaf nodes to continue splitting, while lambda_l1 and lambda_l2 are used to constrain leaf node weights. Model complexity cannot be judged solely by num_leaves; other parameter limits must also be considered.

Growth-strategy boundaries. XGBoost also supports settings such as grow_policy="lossguide", so “XGBoost is always level-wise, and LightGBM is always leaf-wise” is inaccurate. Compare the strategies actually used, not just the framework names.

GOSS is central to the paper, but the current default data_sample_strategy is bagging, so GOSS is not enabled automatically. Since LightGBM 4.0.0, set data_sample_strategy="goss"; top_rate controls the share of large-gradient samples retained, while other_rate controls the share of small-gradient samples drawn. Older code may instead use boosting_type="goss". When migrating, check both the documentation for the installed version and the actual training logs.

For Pandas DataFrames, categorical_feature="auto" will only automatically recognize unordered category columns; ordered categories are split by numerical order by default. LightGBM converts categorical encodings to int32, treats negative values as missing values, and processes categories not present in the training set as missing values during prediction. High-cardinality features also require combining min_data_per_group, cat_smooth, and validation for deployment scenarios, rather than equating “native categorical support” with “no data design needed.”

Both frameworks are continuously evolving. The main text cites specific documentation versions and access dates; readers reproducing experiments should first print the actually installed version, then verify against the corresponding version’s documentation.

7. CatBoost: How to Handle Categorical Features and Prediction Shift in Gradient Boosting Trees? #

Chapter 5 explained how XGBoost scores a split; Chapter 6 examined how LightGBM reduces the cost of finding one. The merchant fields in the Case A bank-transaction fraud data and the product, store, and promotion fields in the Case B next-day store-product sales data raise another question: what information may training use without letting a model “see” a row’s target too soon?

XGBoost and LightGBM both support native categorical splits[11][13]. CatBoost is not the only framework that can handle categories; it takes a different route. The first two can find category partitions at tree nodes using split statistics. CatBoost constructs categorical statistics during training and uses sample permutations to restrict which target values enter those statistics. If we instead feed arbitrary category IDs as continuous numbers, a tree may treat their order as meaningful. If we compute target-mean encodings from all training samples before training, each row’s feature can contain part of its own label. Neither problem is inherent to XGBoost’s or LightGBM’s native categorical support.

In a 2018 paper, Prokhorenkova et al. described CatBoost’s ordered target statistics and ordered boosting[14]. The former addresses a row’s own label leaking into its category encoding. The latter addresses prediction shift: training rows and unseen rows can have different prediction distributions during boosting. Both concern what information training uses, not just how quickly split gains are computed.

7.1 Ordered Target Statistics: Why Not Directly Use Overall Target Means? #

In the Case B next-day store-product sales teaching data, D5–D8 all have promotion type “campaign.” Filling each row with their target mean of 83 units as an input would let D6’s feature contain part of its own 60-unit target. Restricting the mean to the training set does not prevent this within-training-set self-leakage: a training feature then knows more about its own target than a new row’s feature could.

Instead, fix the order D5, D6, D7, D8 and set an illustrative prior mean of 50 units and smoothing strength of 1. Each row uses only earlier campaign rows:

D6 receives \((40+50)/2=45\), excluding its own 60-unit target. D8 receives \((40+60+92+50)/4=60.5\), excluding its own 140-unit target. The formula generalizes this “earlier rows of the same category” rule.

CatBoost’s ordered statistics use a random permutation of training samples: when constructing categorical statistics for a sample in the permutation, only samples preceding it and a smoothing prior are used, not the sample’s own label. Let \(\pi(i)\) denote the position of sample \(i\) in the permutation and \(a_i\) its category value; a simplified target mean encoding can be written as:

Here, \(\mu\) is the prior mean, and \(\kappa>0\) controls smoothing. The formula illustrates the ordering principle, not CatBoost’s complete categorical processing for every task; features with few categories may take a one-hot path instead. A new row can use statistics derived from training data, but not its own unknown target. Actual training uses more rows and different permutations; 50 and 45 are teaching encodings, not the model’s final generated features.

S1–S8 from the Case A bank-transaction fraud teaching data illustrate the same principle with binary fraud labels. These values are simplified teaching encodings, not step-by-step reproductions of CatBoost’s internal CTR or Ordered Boosting.

One distinction matters here: a native categorical split is not the same as the full-data target-mean encoding above. XGBoost and LightGBM can partition categories at tree nodes without first writing an overall target mean into each training row. CatBoost’s ordered statistics offer another way to make categories usable. If we add target encoding ourselves for any framework, we must keep a row’s own label out of its training encoding and prevent leakage across validation sets or time boundaries.

7.2 Ordered Boosting: Why Can Training and Unseen Predictions Differ? #

Even with only numerical inputs and no target-mean encoding, boosting can introduce a different shift. Recall Chapter 5: the gradient \(g_i\) at round \(m\) depends on the current prediction \(z_i^{(m-1)}\). In ordinary boosting, earlier trees have already been trained using row \(i\)’s label. Their prediction for that same row is then used to compute its next gradient. The label of a truly unseen row did not train those earlier trees, so the two kinds of predictions can have different statistical properties. The CatBoost paper calls this prediction shift[14].

Ordered boosting applies the “earlier rows” idea again. When calculating a training row’s current prediction and gradient, it aims to use models trained only on rows preceding it in a permutation. The row should not improve its own current prediction through its label and then be treated as if that prediction came from an unseen case. The implementation uses approximations and reuse to control cost; it does not train an entirely separate ensemble for every row. CatBoost also offers Plain boosting, so ordered boosting is not a fact about every training configuration.

Self-leakage in categorical statistics occurs while constructing input features. Prediction shift can also arise while computing the next gradient. Neither is the same as leakage between training and validation sets. Ordered methods do not automatically prevent future sales from being used as current features or replace time-aware validation. “Ordered” usually refers to an internal sample permutation, not the chronological order of retail records; Chapter 9 returns to rolling backtests.

7.3 Symmetric Trees: Structural Constraints and Prediction Cost #

The first two sections concerned how training signals are formed. CatBoost’s default tree shape also changes how it uses those signals. Return to Section 6.2’s example: the root has children A and B, and A has more to gain from another split. LightGBM’s typical leaf-wise policy would expand A first. XGBoost can be configured to grow by depth or to prioritize gain. CatBoost’s default symmetric tree applies the same split condition to every current leaf at a given depth. It is more constrained than merely growing level by level: level-wise methods can still choose different conditions for different nodes.

A complete symmetric tree of depth \(d\) has \(2^d\) leaves. Shared split rules give it regular prediction paths and make leaf lookup efficient. In return, A and B cannot choose different next splits, and the tree cannot keep growing only along A’s high-gain path. That constraint may help when low-latency inference matters; it may also spend capacity where little signal remains. CatBoost supports other grow_policy settings, so compare validation error, model size, and inference time under the actual configurations rather than treating symmetric trees as an immutable framework label.

7.4 What to Verify When Using CatBoost? #

CatBoost’s Python interface provides CatBoostRegressor and CatBoostClassifier for regression and classification; cat_features identifies categorical columns. iterations, depth, learning_rate, and loss_function are set before training, not learned split thresholds. The descriptions of ordered statistics, boosting, and symmetric trees here were checked against the official algorithm and Python API documentation on October 14, 2026[15].

CatBoost offers two boosting types: Plain and Ordered; which type is actually used depends on the device, data scale, and specific configuration, so it cannot be assumed that every call will default to ordered boosting. It also allows selecting other tree growth strategies via the grow_policy parameter, so symmetric trees are not an unchangeable structural limitation[15].

In cases with fewer categories or different training configurations, CatBoost might also use one-hot encoding instead of computing the ordered statistics for each category as described in Section 7.1[15].

While native categorical handling reduces the burden of manual encoding, it does not automatically solve all generalization problems. Store IDs or product IDs might help predict seen entities but can also lead the model to over-memorize historical samples; when predicting for new stores or new products, it is still necessary to carefully check unseen categories, missing values, and how the validation set is constructed. Whether a model is more accurate and runs faster must be objectively measured under the same data availability and computational budget constraints, and not judged solely based on the framework’s design motivations.

8. XGBoost, LightGBM, and CatBoost: How Should We Address Real-World Data Problems and Choose a Model? #

All three frameworks support classification and regression, but they handle data and organize trees differently. Before asking which model performs best, ask whether the labels are reliable, whether the minority class can be detected, and whether extreme regression values reflect real events or recording errors. Only then is a model comparison meaningful. Competition results do not establish a universal winner for production use. At a minimum, consider:

1. Predictive quality;
2. Training and inference costs;
3. Data quality and distribution;
4. Deployment, maintenance, and monitoring costs.

8.1 What Does Each Boosting Framework Emphasize? #

The table lists key design considerations for each framework, not their fixed capability limits. For instance, XGBoost also supports categorical features, and CatBoost doesn’t always default to ordered boosting. Next, we turn to training data and evaluation: if positive classes are rare or labels are incorrect, even a perfectly implemented model might yield misleading metrics.

The two CSVs were designed around these questions. The Case A bank-transaction fraud data use rare fraud, recurring merchant IDs, and merchant types to examine categorical handling and review trade-offs. The Case B next-day store-product sales data use multiple products and stores, promotion categories, sales history, and a chronological split to examine bins, local splits, corrupted labels, and feature availability. Including a structure in synthetic data does not mean one framework must win because of it. Sections 8.9 and 8.10 report only what the specified configurations actually produced.

8.2 Classification Tasks: Why Can Accuracy Mislead Model Evaluation? #

The fixed test set for the Case A bank-transaction fraud-classification task has 1,200 transactions: 33 fraudulent and 1,167 legitimate. A model that always predicts “legitimate” achieves:

While this number looks high, the model failed to identify any fraudulent transactions. For the review team, the more pressing questions are: How many transactions flagged as “fraud” by the model are actually fraudulent? And how many actual fraud cases did the model catch?

For class imbalance problems, a confusion matrix is essential. The weighted CatBoost run in Section 8.9 gives these four outcomes on the same test set at a fixed 0.5 threshold:

These questions correspond to Precision and Recall, respectively. For a single metric combining both, consider F1:

The model flags 257 transactions: 12 are fraudulent and 245 are legitimate. It misses another 21 frauds. Precision is \(12/257\approx4.7\%\), recall is \(12/33\approx36.4\%\), and F1 is about \(8.3\%\). Accuracy is \((12+922)/1200\approx77.8\%\), yet the model catches some fraud that the always-legitimate rule misses.

The review team would need to examine 257 alerts, including 245 false alarms, while 21 fraud cases would still be missed. These counts show workload and missed fraud, not net benefit. That requires review costs, missed-fraud losses, and losses actually avoided by intervention. Changing training weights does not itself choose the operational threshold.

Other useful checks include:

• ROC-AUC: measures ranking performance across thresholds;
• PR curves and their summary metrics: show the precision–recall trade-off more clearly than accuracy when the positive class is rare;
• Log loss: measures the quality of probability predictions;
• Calibration: checks whether predicted probabilities align with observed event frequencies.

Average Precision (AP) summarizes the PR curve and should not be equated to “PR-AUC” from other integral definitions without clarification. AP is also influenced by the positive class ratio, so exercise caution when comparing across datasets with different sample distributions.

The confusion matrix above describes one decision threshold; it cannot by itself determine AP or ROC-AUC. Those metrics require continuous scores from the Case A bank-transaction fraud model to compare rankings across thresholds. Ranking metrics help narrow down candidate models, but the operational threshold still depends on review capacity and the costs of false alarms and missed fraud.

8.3 How Should Class Imbalance Be Handled? #

First, determine whether the business prioritizes avoiding false negatives or false positives, then decide how to train and use the scores. Common approaches fall into three categories:

• Adjust sample weights. Assign higher weights to minority-class samples in the loss function. This changes the training objective but does not choose the operating threshold.
• Adjust the decision threshold. A 0.5 cutoff is not automatically optimal. If missed fraud costs much more than manual review, the business may choose a lower threshold to increase recall.
• Adjust the training distribution. Consider undersampling, oversampling, or similar methods, but apply them only within the training data so the validation set retains its real distribution.

Class weighting and resampling can also alter probability calibration. If the business uses predicted probabilities to estimate risk or cost directly, calibration needs a separate check.

8.4 Regression Tasks: Should Outliers Be Deleted? #

While classification identifies rare positive examples, when regression encounters a few extreme sales figures, don’t rush to delete them. Identical “large values” can stem from three distinct sources, each requiring a different approach.

Category 1: Real Extreme Business Events #

In the Case B next-day store-product sales teaching data, D8 sold 140 units during a planned 50% discount. That high value was deliberately specified as promotional sales, not a recording error. Removing it just because it is large would discard information about high-discount demand. In real operations, check promotions, holidays, and other information available at the time before deciding what to do with an extreme value.

Category 2: Collection or Processing Errors #

For example:

• Duplicate order entries;
• Sales unit conversion errors;
• Incorrect product mapping;
• Inconsistent handling of negative sales and return records.

These records should first be checked against business rules, record origins, and field transformations. Only after confirming them as recording errors should they be corrected or excluded, rather than directly fed to the model for fitting.

Category 3: Observed Value Not Equal to True Target #

The Case B next-day store-product sales data assume enough inventory, so the CSV does not contain stockout-censored sales. If we took the same store scenario into a real replenishment system, a stockout could make recorded sales much lower than what customers wanted.

In this case:

If the model directly treats sales during stockouts as true demand, it risks systematically underestimating demand.

Such records cannot be handled solely by “outlier cleansing.” This involves target definition and observation mechanisms: if replenishment decisions require true demand, stockouts must be identified and censored demand—demand that sales cannot fully reveal when inventory runs out—considered. Chapter 9 will elaborate on this.

8.5 How Do Different Loss Functions Affect Outliers? #

Even after confirming D8’s high sales as a real event in the teaching data, the training objective determines how heavily the model responds. With the 50-unit initial forecast specified for the Case B next-day store-product sales teaching calculation, D6 has a 10-unit error and D8 a 90-unit error. Their squared-error terms are 100 and 8,100 units²; their absolute-error terms are 10 and 90 units. The units differ, so do not compare the raw losses directly. The rows show how each penalty grows as error increases.

Mean Squared Error #

Larger prediction errors incur a squared penalty, so MSE is highly sensitive to extreme errors.

Mean Absolute Error #

MAE grows linearly with extreme errors. It does not amplify large errors as quickly as squared error, but it is not differentiable at zero error and therefore requires specific handling by training algorithms.

Huber Loss #

Let the residual be:

Huber loss is defined as:

It uses squared loss for smaller errors and linear growth for larger errors, with \(\delta\) determining the transition point. Huber loss can therefore reduce the influence of extreme errors on the objective, but robust losses cannot identify erroneous data automatically or recover demand censored by stockouts.

8.6 Why Do a Few Incorrect Labels Matter? #

For classification problems, incorrect labels can arise from:

• Manual labeling errors;
• Changes in business rules;
• Labels not yet updated after an event occurred;
• Incorrect record association between different systems.

For instance, a fraudulent transaction might be marked as normal on the day it occurs, only to be confirmed as fraudulent weeks later. If the training set uses such premature labels, the model learns incorrect supervision; in boosting, these samples can repeatedly generate large gradients. This does not imply that boosting is always more sensitive to label errors than random forests: the impact also depends on the loss, tree complexity, sample weights, regularization, and data distribution.

More robust engineering practices include:

• Checking label generation logic;
• Distinguishing between true minority samples and incorrect labels;
• Sampling and auditing high-loss samples;
• Conducting data quality sensitivity experiments;
• Using an independent test set to evaluate if cleansing strategies improve generalization.

8.7 How to Compare the Three Boosting Trees in Engineering? #

Before running comparative experiments, establish clear comparison conditions. To choose among XGBoost, LightGBM, or CatBoost, at minimum, establish simple business rules or statistical baselines, and ensure identical training, validation, and test splits, feature availability times, evaluation metrics, and comparable computational budgets. Parameter search should also be given similar opportunities, rather than comparing only three untuned configurations.

Beyond predictive metrics, also record:

For mostly numerical data, testing all three under the same budget is reasonable. With many high-cardinality categorical features, test whether encoding choices, unseen categories, and CatBoost’s ordered statistics make a measurable difference. Neither one synthetic experiment nor a comparison of defaults produces a universal ranking. The decision depends on the full cost–benefit trade-off under the business constraints.

8.8 Is Model Ensembling Always Better? #

In machine learning competitions, XGBoost, LightGBM, and CatBoost are frequently combined. Common methods include weighted averaging, blending, and stacking. For regression problems, if non-negative weights \(\omega_X,\omega_L,\omega_C\) sum to 1, one can use:

Classification models can also combine predicted probabilities, but their calibration still matters. Ensembling helps only when the models’ errors are sufficiently complementary; highly similar errors leave little room for improvement. Stacking must build its second-level training data from out-of-fold predictions to avoid leakage from in-sample predictions. Competition-style ensembles should not become the default in production without evidence that this added complexity pays off.

8.9 Case A: Bank-Transaction Fraud-Model Evaluation #

Chapters 5–7 use two eight-row teaching CSVs to check formulas. Model training and testing use the fixed partitions in two separate full experimental CSVs. The two scales share a business setting and field meanings, but the teaching rows do not enter model training or evaluation. Hand-calculated net gains use stated formulas, starting predictions, and parameters. The metrics below come from fitted software predicting a fixed test set. They are not interchangeable.

The full experimental dataset for the Case A bank-transaction fraud-classification task contains 6,000 synthetic transactions, including 168 frauds, for an overall fraud rate of 2.8%. Stratification by label produces the fixed partitions below. Their fraud rates remain similar, and none includes the eight-row S1–S8 teaching table:

The training set lets each model learn relationships between the fraud label and transaction amount, distance, merchant type, and merchant ID. The validation set does not fit the model; it selects the decision threshold used later in this section. The test set does neither and measures how the frozen setup performs on data that played no role in the decisions. Within each model pair, the only training change is whether scale_pos_weight uses the training set’s negative-to-positive ratio, giving the rare fraud cases more weight in the loss.

The classification results at the fixed 0.5 threshold are shown below. Accuracy is included because, in an imbalanced task, high accuracy does not mean that the model identified the minority class:

Ranking metrics calculated from continuous probabilities:

At threshold 0.5, none of the base runs finds a fraud. This result does not mean the continuous scores contain no ranking information; AP and ROC-AUC use those scores. Weighting raises recall but leaves precision low: weighted CatBoost finds 12 frauds with 245 false alarms. The first table holds the threshold fixed to isolate the weight change, not because 0.5 is the best business threshold.

A fixed threshold of 0.5 makes the model settings easy to compare, but it does not account for how many transactions a bank can investigate. Suppose the 1,200 validation transactions represent one review cycle and the team can investigate at most 10% of them, or 120 alerts. More than 120 would create a backlog; substantially fewer would leave the stated capacity unused. The 10% limit is a teaching assumption used to explain the method, not a general banking benchmark.

Threshold selection then follows a concrete workflow. Each model scores the 1,200 validation transactions and ranks them from highest to lowest fraud probability. Among thresholds that produce no more than 120 alerts, the procedure chooses the one that sends the largest possible number for review. In this dataset, that is equivalent to reviewing the 120 highest-scoring validation transactions. The selected threshold is then frozen: test labels are not inspected and test results do not revise it. Finally, the same threshold is applied to the 1,200 test transactions to calculate the Accuracy, Precision, Recall, and F1 values below. The validation set therefore converts review capacity into a decision rule; the test set measures what that rule does on new data:

With the thresholds frozen, the six models generate 128, 122, 108, 106, 95, and 112 alerts, respectively, among the 1,200 test transactions. Their test alert rates therefore range from about 7.9% to 10.7%. New data need not reproduce the validation set’s exact 10%, and that variation belongs in capacity planning. Threshold values are not comparable across models because their score scales and calibration differ. Compare the workload, missed frauds, and false alarms produced under the same business rule instead. Threshold adjustment does not make every metric improve; it converts a technical score into an operational choice.

The labels are randomly drawn from synthetic probabilities, and these are single configurations, so the results cannot rank model families. A real system should choose its rule from actual review capacity, false-alarm costs, and missed-fraud losses, and should also check calibration.

8.10 Case B: How Does Training-Data Corruption Affect Next-Day Store-Product Sales Forecasts? #

Case B is a next-day store-product sales-regression task. Its full panel covers 20 products, two stores, and 120 consecutive days, giving 40 product–store records per day. The model uses product, store, promotion type, discount, and weekday information known at prediction time, together with lag7, the mean sales over the preceding seven days, to predict sales \(y\). The separate eight-row D1–D8 teaching table does not enter the training or evaluation below.

Randomly shuffling this dataset would allow future records to enter training for the past, so the experiment preserves time order. The first seven days provide history for the initial lag7 values; all later records use the fixed chronological partitions below. The sales distribution is included to put the later MAE and RMSE values back on their scale in units:

Each model is trained under two conditions. The clean condition keeps all 2,920 training targets unchanged. Using a fixed random seed, the corrupted condition selects 88 targets, about 3% of the training set, and adds or subtracts five training-target standard deviations from each one. This creates a small number of large artificial recording errors. Both conditions use identical validation and test sets, and no test target is cleaned. Differences between their test metrics therefore come from training-label corruption rather than a change in test records. Genuine high promotional sales such as D8’s are likewise not removed as errors.

Each cell below shows clean training → corrupted training on the same test set. WAPE and Forecast Bias are ratios; bias uses the forecast-minus-actual sign convention from Section 9.5.

All five models have higher test MAE and RMSE after training-label corruption. CatBoost changes less under this particular setup, but that does not establish general outlier robustness. The experiment does not compare training time, peak memory, inference latency, or equally tuned configurations. A production choice still requires the business constraints in Section 8.7 and time-aware validation in Chapter 9.

9. From Experiment to Production: How Tree Models Are Used for Retail Demand Forecasting? #

9.1 Forecasting Target: Sales or Demand? #

Return to the Case B next-day store-product sales-forecasting scenario. The fixed CSV assumes sufficient inventory and contains no stockouts. To illustrate the production choice of target, suppose instead that a product has 100 units of potential demand on a day with only 30 units on the shelf. Recorded sales can then show at most about 30 units. Should the model learn how many were sold or how many customers wanted to buy? The answer depends on the decision the forecast supports.

Let \(S_t\) be recorded sales on date \(t\), and \(D_t\) be actual customer demand that day (unlike \(D\), which denoted the training dataset earlier). Setting aside returns and pre-orders, the two may be close when stock is sufficient. During a stockout, however, \(S_t \lt D_t\) is common. Sales records show \(S_t\), not the gap between sales and demand.

Training a replenishment model directly on those records may teach it inventory-constrained sales rather than the demand the decision requires. Identify stockout periods, check which inventory information would have been available at forecast time, and backtest approaches that retain, exclude, or estimate demand hidden by stockouts.

9.2 Feature Engineering: Use Only Information Available at Prediction Time #

Once we have defined the target, we still cannot feed every available field into the model. The useful question is: what do we know when we make the forecast? Let \(x_{s,u,t}\) denote the features used to forecast demand for product \(s\), at store \(u\), on date \(t\). It is not a fixed list of fields. Candidates include:

• Calendar information: day of the week, weekends, month, public holidays, and days until or since a holiday.
• Product and store information: product category, brand, price segment, life-cycle stage, and store region.
• Historical sales: sales one, seven, or 28 days earlier (Lag 1, Lag 7, Lag 28), rolling mean and standard deviation, and the share of days with zero sales.
• Business plans and status: confirmed promotions, prices, and events, plus inventory status and opening hours known at forecast time.

The test for every field is not whether it exists in a database, but whether its value is available when we forecast. Suppose we forecast tomorrow’s demand after today’s store closing. The “past seven days’ average sales” can only use records through today. Including tomorrow’s actual sales would cause temporal leakage. When computing a rolling feature, shift to the forecast cutoff first, then calculate the historical window. For prices, promotions, and inventory, distinguish plans or states known in advance from outcomes recorded afterward.

Section 9.1 raised another issue: low sales on a stockout day do not necessarily mean low demand. Historical sales may be available at forecast time, but we still need to flag or handle stockout periods and test whether those features help in backtesting.

9.3 Classification and Regression Can Jointly Serve Retail Forecasting #

Retail forecasting need not rely on one regression model. For products with infrequent demand, predicting quantity directly can blur two questions: will there be demand tomorrow, and how much will customers need if there is? Here, \(D_t\) is the random demand quantity and \(x_t\) contains features known at forecast time.

The Case B next-day store-product sales data mainly simulate products that sell regularly; they do not provide a separate intermittent-demand experiment. If we extended the same retail setting to products with frequent zero-sales days, a two-stage approach would be one option. First, a classifier estimates the probability \(p_t\) of any demand:

Then a regression model estimates the mean quantity \(m_t\) when demand occurs:

If demand is nonnegative, the true conditional expectation satisfies:

In practice, models only estimate \(p_t\) and \(m_t\); multiplying the estimates does not guarantee a better forecast than direct regression. A single regression model may suffice for high-frequency products. Compare both approaches over the same backtesting windows for low-frequency products. If the labels are stockout-constrained sales rather than demand, first address the target problem in Section 9.1.

9.4 Rolling-origin Backtesting #

Validation must follow the same time boundary as feature construction. A random split can train a model on future records and test it on earlier dates, producing a score that does not reflect deployment. Random K-fold is therefore a poor default for time-series forecasting. In rolling-origin backtesting, each training period comes before its validation period, and the forecast origin moves forward across rounds.

The Case B next-day store-product sales data use one fixed chronological holdout: days 7–79 for training, 80–99 for validation, and 100–119 for testing. That is not rolling-origin backtesting. To examine stability further, we could design additional origins on the same CSV while keeping every training period before its evaluation period:

• Round 1: train through day 59; evaluate days 60–79.
• Round 2: train through day 79; evaluate days 80–99.
• Round 3: train through day 99; evaluate days 100–119.

This is a possible follow-up protocol, not the source of Section 8.10’s numbers. If round 3 uses the original test period for model selection, we would need a new final test set.

Each round must simulate a forecast that could actually have been made at the time: use only data available at its forecast origin. If replenishment plans must be set 14 days ahead, check promotions, prices, inventory, and historical sales against that lead time. Do not reuse fields that would only be available for a next-day forecast.

9.5 How to Evaluate Demand Forecasting Models? #

After a chronological holdout or rolling backtest, business teams ask how far forecasts deviate on average, whether a few large errors matter especially, and whether forecasts tend to run high or low. MAE, RMSE, and Forecast Bias address those questions. WAPE adds total absolute error as a share of actual sales. The Case B next-day store-product sales results below come from one chronological holdout, not multi-origin backtesting.

Use the Case B next-day store-product sales results directly. These are the first three test rows predicted by XGBoost trained on clean labels. Error means forecast minus actual. The table rounds predictions to two decimals; the aggregate metrics below use all 800 rows and unrounded predictions.

These rows show error direction; do not recompute the full test metrics from only three rows. Across all 800 test rows, actual sales sum to 21,259 units, absolute errors to about 2,776.95 units, squared errors to about 15,077.56 units², and signed errors to about 641.61 units.

MAE #

On 800 test rows, \(MAE\approx2{,}776.95/800=3.471\) units. This gives average error size, not its direction.

RMSE #

On the same test set, \(RMSE\approx\sqrt{15{,}077.56/800}=4.341\) units. It exceeds MAE because squaring gives larger row-level errors more weight. The second row above, underforecast by about 8.07 units, deserves inspection, but three rows alone cannot show its contribution to the entire test error.

WAPE #

The test-set \(WAPE\approx2{,}776.95/21{,}259=13.1\%\). It expresses total absolute error as a share of actual sales, but can become unstable when that total is near zero and can be dominated by high-volume products.

Forecast Bias #

Test-set Forecast Bias is about \(641.61/21{,}259=3.0\%\). Under this definition, positive means overforecasting overall and negative means underforecasting overall. Positive bias does not mean every row was overforecast: the second row above was 8.07 units low. State the sign convention when reporting results so teams do not interpret “positive bias” differently.

These metrics describe forecast errors; they do not directly measure the value of a replenishment decision. If forecasts determine order quantities, evaluation must also consider inventory, lead times, and the different costs of excess stock and stockouts. Overall WAPE is not enough either; examine results by:

• High-frequency vs. low-frequency products;
• Promotional vs. non-promotional days;
• Regular weekdays vs. holidays;
• Large vs. small stores;
• New vs. mature products;
• High inventory vs. stockout-risk products.

If a Case B next-day store-product sales model has low overall error but systematically underforecasts high-discount rows, replenishment could still suffer. Group-level checks should address business risks, not merely improve a headline metric.

9.6 Relationship with Prophet Tutorial #

My previous “Prophet Retail Demand Forecasting Tutorial” focused on trends, seasonality, holidays, and time-series backtesting.

Prophet and GBDT emphasize different parts of the forecasting problem. Prophet explicitly models time-series components such as trend, seasonality, and holidays. GBDT frameworks such as XGBoost, LightGBM, and CatBoost typically rely on engineered features from historical sales, calendars, prices, promotions, and stores. The three frameworks also handle categorical features differently.

Regression trees also produce piecewise-constant predictions at their leaves, so they do not naturally continue a rising or falling trend beyond the conditions represented in the training data. When sales are trending, prices move outside their historical range, or a new store is still ramping up, evaluate temporal extrapolation explicitly. Possible responses include adding suitable trend features, combining the tree model with a time-series model, or using another model that represents the required structure.

Neither approach wins across all datasets and evaluation settings. When seasonality is stable and few external variables are available, Prophet is a useful starting point. With rich business features and many stores and products, GBDT is also worth testing. Predictions from a statistical model can become tree-model features, or the two approaches can be combined; train such combinations on time-ordered out-of-sample predictions to avoid leakage. Compare them with the same forecast horizon, feature-availability rules, and backtesting design.

9.7 From Offline Models to Production Systems #

Even if a data scientist trains a model with low error in offline backtesting, it may not be ready for reliable production use. Before deployment, data and model teams should build training and online features according to the availability rules in Section 9.2. They should check for missing, duplicate, or late-arriving fields required for prediction. If a problem occurs, record its scope and use an agreed fallback forecast; do not silently fill in information that became available only later. Flag categories not seen during training for new stores and products, and inspect the resulting predictions.

After deployment, teams should compare forecasts with observed results, paying particular attention to promotions, infrequently sold products, and stockout-prone products. If errors by group, missing-data rates, or prediction distributions repeatedly move outside their backtested ranges, investigate the data pipeline and business conditions before deciding whether to retrain or roll back. Define monitoring windows, trigger thresholds, and rollback responsibilities in advance; one change in the overall error is not enough to justify retraining.

Forecasts must also inform replenishment decisions. Teams should estimate the cost of excess stock from overforecasting and stockouts from underforecasting, then decide which high-risk predictions need manual review. Because these costs are often asymmetric, minimizing MSE may not yield the most suitable order quantities. If backtests and inventory outcomes consistently show this mismatch, teams can test quantile forecasting or a dedicated inventory optimization model, and track how offline errors affect replenishment outcomes.

Conclusion: From Tree Structures to Industrial-Grade Machine Learning Systems #

The progression from a single tree to ensembles addressed how to partition data, reduce prediction variance, and correct errors iteratively. Later work tackled large-scale training costs, categorical features, and prediction shift. Better hardware increased the scale of feasible datasets; better algorithms improved how that hardware is used. XGBoost, LightGBM, and CatBoost emphasize different problems, so their trade-offs must be evaluated against the data, metrics, and engineering constraints of the task.

Return to the product in the opening example. Before choosing a model, ask: Are we predicting recorded sales or the demand hidden by stockouts? Will price and promotion information be known when the forecast is made? Which backtesting window lets us assess the cost of under- and overforecasting? Without clear answers, a more complex tree model may simply fit the wrong target more precisely.

Tree models evolved through more than adding trees: statistical learning, numerical optimization, and engineering all shaped them. Using them well in business still starts with a clear target, available data, and a sound validation design.

References #

[1] Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1, 81–106. https://doi.org/10.1007/BF00116251

[2] Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.

[3] Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and Regression Trees. Wadsworth.

[4] scikit-learn Developers. DecisionTreeRegressor API. scikit-learn 1.9.1 documentation, Accessed on: 2026-10-14. https://scikit-learn.org/1.9/modules/generated/sklearn.tree.DecisionTreeRegressor.html

[5] Breiman, L. (1996). Bagging Predictors. Machine Learning, 24, 123–140. https://doi.org/10.1007/BF00058655

[6] Breiman, L. (2001). Random Forests. Machine Learning, 45, 5–32. https://doi.org/10.1023/A:1010933404324

[7] scikit-learn Developers. RandomForestRegressor API. scikit-learn 1.9.1 documentation, Accessed on: 2026-10-14. https://scikit-learn.org/1.9/modules/generated/sklearn.ensemble.RandomForestRegressor.html

[8] Freund, Y., & Schapire, R. E. (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 119–139. https://doi.org/10.1006/jcss.1997.1504

[9] Friedman, J. H. (2001). Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics, 29(5), 1189–1232. https://doi.org/10.1214/aos/1013203451

[10] Chen, T., & Guestrin, C. (2016). XGBoost: A Scalable Tree Boosting System. Proceedings of KDD 2016, 785–794. https://doi.org/10.1145/2939672.2939785

[11] XGBoost Developers. XGBRegressor and XGBClassifier Python API. XGBoost 3.4.2 documentation, Accessed on: 2026-10-14. https://xgboost.readthedocs.io/en/stable/python/python_api.html ; XGBoost 3.4 release notes. https://xgboost.readthedocs.io/en/stable/changes/v3.4.0.html

[12] Ke, G., et al. (2017). LightGBM: A Highly Efficient Gradient Boosting Decision Tree. Advances in Neural Information Processing Systems 30. https://proceedings.neurips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html

[13] LightGBM Developers. LGBMRegressor and LGBMClassifier Python API. LightGBM 4.7.0 documentation, Accessed on: 2026-10-14. https://lightgbm.readthedocs.io/en/v4.7.0/pythonapi/lightgbm.LGBMRegressor.html ; https://lightgbm.readthedocs.io/en/v4.7.0/pythonapi/lightgbm.LGBMClassifier.html

[14] Prokhorenkova, L., et al. (2018). CatBoost: Unbiased Boosting with Categorical Features. Advances in Neural Information Processing Systems 31. https://proceedings.neurips.cc/paper/2018/hash/14491b756b3a51daac41c24863285549-Abstract.html

[15] CatBoost Developers. Categorical Features, Training Parameters, CatBoostRegressor and CatBoostClassifier. CatBoost online documentation (not version-pinned), Accessed on: 2026-10-14. https://catboost.ai/docs/en/features/categorical-features ; https://catboost.ai/docs/en/references/training-parameters/common ; https://catboost.ai/docs/en/concepts/python-reference_catboostregressor ; https://catboost.ai/docs/en/concepts/python-reference_catboostclassifier ; CatBoost 1.2.10 release. https://github.com/catboost/catboost/releases/tag/v1.2.10