I. Introduction
Decision trees, random forests, and ensemble learning are a very important group of techniques in traditional machine learning.
They are widely used in financial risk control, user profiling, recommendation systems, marketing prediction, anomaly detection, industrial quality analysis, and other fields. Even though deep learning has become an important technical direction in artificial intelligence, ensemble models based on decision trees still occupy an important position in structured data modeling.
Among them:
- Decision Tree: Through a series of feature-based judgments, the data is gradually divided into different regions, ultimately producing a prediction result.
- Random Forest: By training multiple decision trees with diversity and then combining their prediction results, the model's stability and generalization ability are improved.
- Ensemble Learning: By combining multiple learners, a model with stronger overall performance is constructed.
There is a clear technical relationship among the three:
A decision tree is a basic learning algorithm, a random forest is an ensemble algorithm based on decision trees, and ensemble learning is a broader machine learning methodology.
Starting from the mathematical principles of decision trees, this article gradually analyzes ensemble methods such as random forests, Bagging, Boosting, and Stacking, and further introduces mainstream algorithms such as GBDT, XGBoost, LightGBM, and CatBoost.
II. Basic Concepts of Decision Trees
2.1 What Is a Decision Tree?
A decision tree is a supervised learning algorithm that makes predictions based on a tree structure.
It performs conditional checks on features to partition the sample space into multiple regions and generates prediction results in each region.
For example, based on a user's age, income, and historical purchasing behavior, determine whether the user is likely to purchase a certain product.
flowchart TB
A["Does the user have historical purchase records?"]
B["Is the historical spending amount relatively high?"]
C["Is the age greater than 30?"]
D["Prediction: Likely to purchase"]
E["Prediction: Unlikely to purchase"]
F["Prediction: Likely to purchase"]
G["Prediction: Unlikely to purchase"]
A -->|"Yes"| B
A -->|"No"| C
B -->|"Yes"| D
B -->|"No"| E
C -->|"Yes"| F
C -->|"No"| G
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
The core idea of a decision tree is:
Continuously search for features and split conditions that can effectively distinguish samples, so that the partitioned data has higher purity, and ultimately make predictions at the leaf nodes.
2.2 Basic Components of a Decision Tree
A decision tree is usually composed of the following nodes:
| Component | Description |
|---|---|
| Root Node | The starting point of the entire tree, containing all training samples |
| Internal Node | Performs conditional checks based on a certain feature |
| Branch | The path corresponding to a judgment condition |
| Leaf Node | Outputs the final prediction result |
| Split | Divides the data at the current node into multiple subsets |
From an algorithmic perspective, a decision tree mainly accomplishes two tasks:
- Select the most appropriate feature.
- Determine the splitting condition corresponding to the feature.
These two steps determine the structure of the tree and also directly affect the model's predictive capability.
2.3 Classification and Regression Decision Trees
According to the prediction target, decision trees can be divided into two types.
Classification Decision Tree (Classification Tree)
Used to predict discrete categories.
For example:
- Whether a user will churn.
- Whether an email is spam.
- Whether a transaction is fraudulent.
- Which category an image belongs to.
Leaf nodes usually output class probabilities or class labels.
Regression Decision Tree (Regression Tree)
Used to predict continuous values.
For example:
- House prices.
- Product sales.
- A user's future spending amount.
- Equipment operating temperature.
Leaf nodes usually output the mean of the target values of the training samples in that region, and specific implementations may also use other statistics.
The main difference between classification trees and regression trees lies in the split evaluation criteria and the prediction method at leaf nodes.
III. How Does a Decision Tree Choose Splitting Features?
The key question in decision tree training is:
Which feature should the current node choose for splitting?
Suppose a node contains 100 samples, of which:
- 60 positive samples.
- 40 negative samples.
If no split is performed, the current node contains both classes at the same time.
If a feature is selected for splitting, two child nodes are obtained:
- Child node A: 50 positive samples, 5 negative samples.
- Child node B: 10 positive samples, 35 negative samples.
The class distributions of the two child nodes are more concentrated, indicating that this feature has strong discriminative ability.
To quantify this effect, an impurity metric needs to be introduced.
3.1 Information Entropy (Entropy)
Information entropy is used to measure the uncertainty of a data set.
For a data set containing K classes:
Where:
- D: the data set of the current node.
- K: the number of classes.
- p_k: the proportion of samples of the k-th class in the current node.
For a binary classification problem:
Information entropy has the following characteristics:
- When all samples belong to the same class, the entropy is 0.
- The closer the proportions of samples in different classes, the larger the entropy.
- For binary classification with a 50% split between the two classes, entropy reaches its maximum value of 1.
The smaller the information entropy, the more concentrated the class distribution in the node.
3.2 Information Gain (Information Gain)
Information gain is used to measure the degree to which uncertainty decreases after a feature split.
Suppose feature A is used to partition data set D into D_1,D_2,\ldots,D_m.
Information gain is defined as:
Where:
- H(D): the information entropy before the split.
- H(D_i): the information entropy of the i-th child node.
- \frac{|D_i|}{|D|}: the proportion of samples in the child node.
The larger the information gain, the more significantly the overall uncertainty decreases after the feature split.
Note: information gain is biased toward features with many distinct values.
For example, a user ID is different for almost every sample. Splitting by user ID may leave each child node with only one sample, thereby producing a very high information gain.
However, such a split usually has no practical predictive value and easily leads to overfitting.
3.3 Gain Ratio (Gain Ratio)
The gain ratio is an important metric used by the C4.5 decision tree.
Building on information gain, it introduces split information (Split Information) for normalization:
Where:
Gain ratio can alleviate the problem of information gain being biased toward features with many distinct values.
However, gain ratio may also be biased toward certain splits with small split information. Therefore, C4.5 usually combines it with information gain when screening candidate features, rather than simply choosing the highest gain ratio unconditionally.
3.4 Gini Index (Gini Impurity)
The Gini index is a commonly used impurity metric for CART classification trees.
It is defined as:
For a binary classification problem:
It can also be written as:
The Gini index has the following characteristics:
- When all samples belong to the same class, the Gini index is 0.
- The more uniform the class distribution, the larger the Gini index.
- For binary classification with a 50% split between the two classes, the Gini index reaches its maximum value of 0.5.
CART classification trees usually choose the split that reduces the weighted child-node Gini index the most.
Weighted Gini index after the split:
Decrease in the Gini index:
The larger the decrease, the better the split.
3.5 Comparison of Splitting Metrics for Classification Trees
| Metric | Typical Algorithm | Core Idea |
|---|---|---|
| Information Gain | ID3 | Maximize the decrease in entropy |
| Gain Ratio | C4.5 | Normalize information gain |
| Gini Index | CART | Minimize the weighted Gini index after the split |
Note:
These metrics measure the impurity or uncertainty of a node, not the overall accuracy of the model.
Decision tree training usually adopts a local greedy strategy: at each step, choose the best split for the current node, rather than exhaustively enumerating all possible complete tree structures.
4. Splitting Mechanism of the CART Decision Tree
CART (Classification and Regression Tree) is a very widely used decision tree algorithm.
It supports both classification and regression tasks.
CART has two important characteristics:
- It uses a binary tree structure, where each split produces two child nodes.
- Classification tasks typically use the Gini index, while regression tasks typically use metrics such as squared error.
4.1 How are continuous features split?
For continuous features, a decision tree usually needs to find a split threshold.
For example, suppose the feature is user age:
The algorithm considers a series of candidate thresholds and divides the samples into:
and:
Suppose the candidate threshold is 30, then:
- Left child node: age less than or equal to 30.
- Right child node: age greater than 30.
The algorithm evaluates the split quality for different candidate thresholds and selects the threshold that reduces the target impurity the most.
In practice, candidate split points usually come from the midpoints between adjacent distinct feature values after sorting; there is no need to enumerate arbitrary real numbers.
4.2 How does a regression tree split?
A regression tree has no concept of class purity; it usually uses squared error to measure the dispersion of target values within a node.
For a node D, its mean is:
Node squared error:
For a single split:
The algorithm selects the feature and threshold that reduce the squared error the most after the split.
The prediction value of a regression tree leaf node is usually the mean of the target values of the training samples in that leaf node.
This means the regression tree partitions the feature space into multiple regions, with each region outputting a relatively fixed numeric value.
4.3 Decision tree training process
flowchart TB
A["Input training data"]
B["Create root node"]
C["Compute candidate features and split conditions"]
D["Select the optimal split"]
E["Generate left and right child nodes"]
F{"Are the stopping conditions met?"}
G["Continue recursive splitting"]
H["Generate leaf node"]
I["Obtain the trained decision tree"]
A --> B
B --> C
C --> D
D --> E
E --> F
F -->|"No"| G
G --> C
F -->|"Yes"| H
H --> I
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style H fill:#E5F0E9,stroke:#83A995,color:#315D49
style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
4.4 Stopping conditions for decision trees
If a decision tree keeps splitting, in theory it may partition the training data very finely, to the point where each leaf node contains only one training sample.
Such a tree usually fits the training set very well, but its generalization ability may be poor.
Therefore, the complexity of the tree needs to be controlled through stopping conditions.
Common parameters include:
| Parameter | Purpose |
|---|---|
| max_depth | Limits the maximum depth of the tree |
| min_samples_split | Minimum number of samples a node must contain to be allowed to split further |
| min_samples_leaf | Minimum number of samples a leaf node must contain |
| max_leaf_nodes | Limits the number of leaf nodes |
| min_impurity_decrease | Minimum impurity decrease required for a split |
| ccp_alpha | Controls the strength of cost-complexity pruning |
These parameters all essentially control model complexity.
4.5 Pre-pruning and post-pruning
There are two main ways to control the complexity of a decision tree.
Pre-pruning
Limit the growth of the tree in advance during training.
For example:
- Limit the maximum depth.
- Limit the minimum number of samples for a split.
- Limit the minimum number of samples in a leaf node.
- Limit the minimum impurity decrease.
The advantage is higher training efficiency.
The disadvantage is that stopping too early may lead to underfitting.
Post-pruning
First generate a relatively large tree, then remove branches that contribute little to generalization performance.
A common post-pruning method for CART is cost-complexity pruning.
Its objective function can be written as:
Where:
- T: The current decision tree.
- R(T): The empirical prediction error of the tree.
- |T|: The number of leaf nodes.
- \alpha: The complexity penalty coefficient.
The larger \alpha is, the more the model tends to retain a simple tree structure.
Post-pruning usually selects an appropriate complexity parameter through a validation set or cross-validation.
V. Advantages and Disadvantages of Decision Trees
5.1 Advantages
- Strong interpretability
The prediction process can be explained through the path of feature decisions, making it suitable for scenarios that require business interpretability.
- Supports nonlinear relationships
Complex nonlinear decision boundaries can be constructed through multiple feature splits.
- Does not require mandatory feature standardization
Tree models mainly split based on feature ordering and thresholds, and are usually insensitive to feature scales.
- Supports both classification and regression
The same tree structure can be applied to different types of supervised learning tasks.
- Can handle interactions between features
Split conditions at different levels can be combined to form complex rules.
5.2 Disadvantages
- Prone to overfitting
When a tree is too deep, it easily learns noise in the training data.
- Relatively sensitive to data changes
A small change in training samples may cause significant changes in split features and tree structure.
- Greedy algorithms do not guarantee global optimality
Each locally optimal split does not mean that the final tree structure is globally optimal.
- Predictions may not be smooth enough
Regression trees usually output piecewise constants, making it difficult to naturally express continuous trends.
- The predictive capability of a single tree is limited
In complex tasks, the generalization ability of a single decision tree is often inferior to that of a reasonably ensembled tree model.
One of the most prominent problems of decision trees is high model variance.
This is also an important reason why ensemble methods such as random forests can be effective.
VI. Basic Idea of Ensemble Learning
6.1 What Is Ensemble Learning?
Ensemble learning is a machine learning method that improves overall predictive performance by combining multiple learners.
Its core idea is:
Let multiple models with a certain degree of diversity make predictions together, and use the complementarity among models to reduce overall error.
For example, use 100 decision trees to predict whether a user will churn.
If some of the trees predict that the user will churn and the others predict that the user will not churn, the final result can be obtained by voting.
For regression tasks, the predictions of multiple models can be averaged.
Ensemble learning does not require all base models to be decision trees; it can also combine different types of learners such as linear models, neural networks, and support vector machines.
6.2 Basic Structure of Ensemble Learning
flowchart TB
A["Training data"]
B["Base model 1"]
C["Base model 2"]
D["Base model 3"]
E["Base model N"]
F["Prediction result combination"]
G["Final prediction result"]
A --> B
A --> C
A --> D
A --> E
B --> F
C --> F
D --> F
E --> F
F --> G
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#EAF3EC,stroke:#83A995,color:#315D49
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#DCEFE5,stroke:#4F8B70,color:#24563F
6.3 Why Is Ensemble Learning Effective?
The effectiveness of ensemble learning is closely related to the diversity among base models.
If multiple models are completely identical and their predictions are also completely consistent, then combining them will not bring obvious benefits.
If the models have a certain degree of diversity and their errors do not completely overlap, then combining them has a chance to offset some of the prediction errors.
Taking regression tasks as an example, suppose there are M models, and their prediction errors are respectively:
The error after simple averaging is:
If the variance of each model's error is \sigma^2, and the correlation coefficient between the errors of any two models is \rho, then the variance of the average error is:
This formula reveals an important principle of ensemble learning:
- Increasing the number of models can reduce the uncorrelated portion of the error.
- The lower the correlation among models, the better the ensemble usually performs.
- If the models are highly correlated, the gains from adding more models diminish.
Therefore, ensemble learning requires not just multiple models, but also a reasonable degree of diversity among them.
Seven. Bagging: Reducing Model Variance Through Parallel Training
7.1 What Is Bagging?
Bagging is short for Bootstrap Aggregating, and it is a typical ensemble learning method.
Its core idea is:
- Perform multiple random samplings with replacement from the original training set.
- Train multiple base models using the different sampling results.
- Combine the predictions of the multiple models.
Bagging typically uses parallel training, and the base models are independent of one another.
7.2 Bootstrap Sampling
Suppose the original training set contains N samples.
Bootstrap sampling draws N times from the original data with replacement each time, forming a new training set.
Because sampling is done with replacement:
- The same sample may be drawn more than once.
- Some samples may not be drawn even once.
- The training sets obtained by different models usually differ.
An important statistical conclusion is:
When N draws with replacement are made from N samples, the probability that a single sample is never drawn is:
When N is sufficiently large:
In other words, in each Bootstrap sampling, on average about 36.8% of the original training samples are not drawn.
These samples that are not drawn are called Out-of-Bag Samples.
7.3 The Bagging Training Workflow
flowchart TB
A["Original Training Set"]
B["Bootstrap Sample 1"]
C["Bootstrap Sample 2"]
D["Bootstrap Sample N"]
E["Train Model 1"]
F["Train Model 2"]
G["Train Model N"]
H["Combine Predictions"]
I["Final Model Prediction"]
A --> B
A --> C
A --> D
B --> E
C --> F
D --> G
E --> H
F --> H
G --> H
H --> I
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#EAF3EC,stroke:#83A995,color:#315D49
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style H fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
7.4 How Does Bagging Combine Predictions?
For classification tasks, majority voting is typically used:
For regression tasks, averaging the predicted values is typically used:
Here h_i(x) denotes the prediction of the i-th model for input x.
The main role of Bagging is to reduce model variance, and it is especially suited to learners that are sensitive to changes in the training data, such as decision trees whose complexity has not been sufficiently constrained.
Eight. Random Forest: Combining Bagging with Random Feature Selection
8.1 What Is a Random Forest?
A random forest is an ensemble algorithm that uses decision trees as its base learners.
It combines two random mechanisms:
- Bootstrap random sampling of the training samples.
- At each node split, searching for the optimal split only among a randomly selected subset of features.
The first mechanism ensures that different decision trees use different training samples.
The second mechanism further reduces the correlation between trees.
Therefore, a random forest can be seen as a combination of the Bagging idea and a random feature selection mechanism.
8.2 The Training Process of a Random Forest
Suppose the training data has 100 features and 200 decision trees are to be trained.
The basic workflow of a random forest is as follows:
- Perform Bootstrap sampling from the original training set.
- Train a decision tree using the sampled data.
- At each node split, randomly select a subset of features as the candidate set.
- Select the optimal split from the candidate features.
- Keep growing the decision tree until the stopping condition is met.
- Repeat the above process to train multiple decision trees.
- Vote or average the prediction results of all trees.
flowchart TB
A["Original training data"]
B["Bootstrap random sampling"]
C["Randomly select candidate features"]
D["Select the optimal split condition"]
E["Build a decision tree"]
F{"Have all trees been trained?"}
G["Continue training the next tree"]
H["Combine predictions from all decision trees"]
I["Output the final result"]
A --> B
B --> C
C --> D
D --> E
E --> F
F -->|"No"| G
G --> B
F -->|"Yes"| H
H --> I
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style H fill:#EAF3EC,stroke:#83A995,color:#315D49
style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
8.3 Why is random feature selection necessary?
Suppose a dataset contains a very strong feature A.
If every decision tree can use all features at each split, many trees may preferentially select A.
This can cause the structures of different trees to be highly similar.
Even with different Bootstrap samples, the models may still be highly correlated.
Random forest increases structural differences among trees by limiting the number of candidate features at each split.
This helps reduce correlation among models and makes ensemble predictions more stable.
8.4 Key Hyperparameters of Random Forest
| Parameter | Role |
|---|---|
| n_estimators | Number of decision trees |
| max_depth | Maximum depth of each tree |
| max_features | Number or proportion of features considered at each split |
| min_samples_split | Minimum number of samples required for a node to continue splitting |
| min_samples_leaf | Minimum number of samples at a leaf node |
| bootstrap | Whether to use Bootstrap sampling |
| max_samples | Number or proportion of samples drawn for each tree |
| class_weight | Class weights in classification tasks |
Among them, n_estimators and max_features are two especially important parameters for understanding random forests.
Generally:
- Increasing the number of trees can reduce random fluctuations in ensemble predictions, but it also increases computational cost.
- Reducing the number of features available at each split can usually reduce correlation between trees, but the fitting ability of an individual tree may also decrease.
- If trees are too shallow, they may underfit; if they are too deep, they may increase computational overhead and the variance of individual trees.
In practice, the parameters should be determined using a validation set or cross-validation.
8.5 Out-of-Bag Error (OOB Error)
Random forest has a practical property: out-of-bag samples can be used to estimate the model's generalization error.
For a given training sample, if it is not included in the Bootstrap training set of a certain tree, that tree can treat it as an out-of-bag sample.
By collecting the predictions of all trees that were not trained on that sample, the out-of-bag prediction for that sample can be obtained.
Then, by comparing the out-of-bag predictions of all training samples with their true labels, the OOB error can be estimated.
Advantages:
- No additional validation set is required.
- It can help evaluate the generalization ability of a random forest.
- It can be used to observe changes in model error as the number of trees increases.
Note:
OOB evaluation is not an independent test-set evaluation. If the training data has issues with time, grouping, or data leakage, OOB cannot automatically solve these problems.
8.6 Feature Importance
Random forest can calculate feature importance to analyze which features contribute more to model predictions.
There are two common methods.
1. Feature Importance Based on Impurity Decrease
Also called Mean Decrease in Impurity (MDI).
Calculate the impurity decrease contributed by a feature across splits in all trees, then aggregate and normalize it.
Advantages:
- High computational efficiency.
- It can be obtained directly from the model.
Disadvantages:
- It may favor features with more distinct values.
- It may favor continuous features.
- Among correlated features, importance may be spread out or redistributed.
2. Permutation-Based Feature Importance
Also called Permutation Importance.
Basic process:
- First, calculate the baseline evaluation metric of the model on the validation data.
- Randomly shuffle the values of one feature.
- Recalculate the model evaluation metric.
- Compare the degree of performance drop before and after shuffling.
If model performance drops significantly after shuffling a feature, it indicates that the model relies strongly on that feature.
Permutation importance is closer to the model's actual predictive dependence on the specified evaluation data than simply counting split contributions, but it is still not a causal explanation.
When multiple features are highly correlated, shuffling only one of them may not fully reflect their joint information.
8.7 Advantages and Disadvantages of Random Forests
Advantages:
- Compared with a single decision tree, it is usually more stable.
- It can learn complex nonlinear relationships.
- It can model interactions between features.
- It is usually insensitive to feature scaling.
- It supports both classification and regression.
- The error can be estimated via OOB.
- It can provide feature importance analysis.
Disadvantages:
- The model size is usually larger than a single decision tree.
- Inference requires executing multiple trees, resulting in higher computational overhead.
- Overall interpretability is lower than that of a single decision tree.
- For high-dimensional sparse features and some complex structured tasks, it may be inferior to specially optimized Boosting algorithms.
- It usually has limited ability to extrapolate to values outside the data distribution.
9. Boosting: Reducing Model Error Through Step-by-Step Learning
9.1 What Is Boosting?
Boosting is another important ensemble learning idea.
Unlike Bagging, which trains multiple independent models in parallel, Boosting usually trains multiple weak learners sequentially.
Subsequent learners continue to optimize based on the shortcomings of the current ensemble model, so that the overall model gradually improves.
Its basic idea is:
Through learning in multiple stages, later models focus on improving the problems that the current model has not yet solved.
Typical Boosting algorithms include:
- AdaBoost
- Gradient Boosting Decision Tree (GBDT)
- XGBoost
- LightGBM
- CatBoost
9.2 Basic Training Process of Boosting
flowchart TB
A["Input training data"]
B["Train initial model"]
C["Calculate current model error"]
D["Train new weak learner"]
E["Update ensemble model"]
F{"Has stopping condition been met?"}
G["Continue to next round of training"]
H["Output final ensemble model"]
A --> B
B --> C
C --> D
D --> E
E --> F
F -->|"No"| G
G --> C
F -->|"Yes"| H
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style D fill:#EAF3EC,stroke:#83A995,color:#315D49
style E fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style H fill:#DCEFE5,stroke:#4F8B70,color:#24563F
Boosting usually obtains the final prediction through a weighted combination of multiple learners:
where:
- h_m(x): the m-th base learner.
- \alpha_m: the weight corresponding to this learner.
- M: the number of learners.
The specific form of combination depends on the Boosting algorithm.
9.3 AdaBoost
AdaBoost (Adaptive Boosting) is a classic Boosting algorithm.
Its main idea is:
Continuously adjust the weights of training samples so that subsequent learners pay more attention to samples that were previously misclassified.
Assume the training data is:
Initially, each sample has the same weight:
After training a weak classifier, adjust the sample weights according to its prediction results.
Misclassified samples receive higher weights, making the next round's learner focus more on these samples.
The weighted error rate of the classifier in the m-th round:
Classifier weight:
For binary classification tasks, if the labels use \{-1,+1\}, the sample weights can be updated as follows:
The weights are then normalized.
In this way, the weights of misclassified samples increase, while the weights of correctly classified samples decrease.
AdaBoost ultimately obtains the prediction result through weighted voting by multiple weak classifiers.
9.4 Gradient Boosting
Gradient Boosting is a more general Boosting concept.
It treats the model training process as a step-by-step optimization process in function space.
Suppose the model's prediction function is:
The goal is to minimize the empirical loss:
At each round, Gradient Boosting computes the negative gradient of the current model on the training samples:
Here, r_{im} can be understood as the optimization direction of the current model on the i-th sample.
Then a new weak learner is trained to fit these negative gradients, and the new learner is added to the existing model.
The model update can be abstracted as:
where:
- F_{m-1}(x): the model from the previous round.
- h_m(x): the learner for this round.
- \eta: the learning rate.
The learning rate is used to control the magnitude of the model update at each round.
Key insight: Gradient Boosting essentially optimizes the model step by step in function space along the negative gradient direction of the loss function.
It does not simply increase the weights of samples mispredicted in the previous round; rather, it constructs a new learning target based on the gradient of the loss function.
For squared error loss, the negative gradient has a direct relationship with the residual:
Therefore, in squared-error regression tasks, GBDT can be understood as continuously fitting the residuals of the current model.