Gradient-boosted decision trees form an ensemble by training small decision trees sequentially. Each new tree targets errors left by the current ensemble, and the final prediction combines contributions from all trained trees. The learning rate scales each tree's contribution; it does not determine the tree's complexity. Tree complexity instead depends on properties such as the number of splits, while a smaller learning rate generally requires more trees.

University of Michigan - Ann Arbor

Google

A decision tree divides the prediction space into a series of simple regions according to the stratifying criteria. Decision trees can be applied to both regression and classification problems and can thus be of two types.

Decision Tree

Boosting is another approach that can be used for both classification and regression. Boosting improves predictions of a decision tree by learning slowly. Unlike bagging, boosting works sequentially, where each tree grown uses the information from those created before it, and works on modified versions of the original data set. Boosting combines a large number of trees ($\hat{f}^{1}, ...,  \hat{f}^{B}$). Decision trees are fitted based on the residuals of the model rather than the response (Y), then update the residuals by adding it to the fitted function. This means that each model created is slowly reducing the error of the previous ones. This causes an improvement of $\hat{f}$, particularly in places where it does not do as well as others. Decision trees using boosting tend to be very small.


Boosting

Linear Regression Model: 
$$ f(X) = \beta_0 + \sum_{j=1}^{p} X_j \beta_j $$
Regression Trees Model: 
$$ f(x) = \sum_{m=1}^{M} c_m · 1(x \in R_m) $$
Linear regression is a good choice if the relationship between predictive variables and response variables can be well fitted by linear models. On the other hand, the tree method is more appropriate if the relationship is highly nonlinear and complex. 


Trees VS. Linear Models

1) Decision trees are easily explainable to others

2) Compared to other statistical methods like regression, some believe that trees are much more similar to human decision making

3) Decision trees can be displayed graphically, which make them easy to interpret

4) There is no need to create dummy variables when handling qualitative predictors


Advantages to Using Decision Trees

1) Although trees may be easier to understand and interpret, they do not provide the same level of predictive accuracy compared to traditional regression and classification methods

2) Small changes in data can cause large changes in the final estimated tree

3) Not fit for continuous variables - While working with continuous numerical variables, decision tree loses information, when it categorizes variables in different categories.

4) Overfitting - Can create over-complex trees that do not generalize the data well and suffer from high variance. This problem gets solved by setting constraints on model parameters and pruning.


Disadvantages to Using Decision Trees

1. Regression trees
2. Classification trees

Types of decision trees

The algorithm required to build a decision tree involves 3 steps:

1. Start with an empty tree

2. Split on the feature with the highest information gain

3. Recurse with step 2

Creating a minimally sized tree which minimizes training error is actually an extremely hard, (NP-Hard) problem). To approximate this optimal solution, we build a tree by greedily splitting on the feature which results in the most information gain, i.e., pick the feature to split on that more certainly leads to a classification. 


Learning Decision Trees

Approaches for improving decision trees' predictions 

Decision trees can be applied to both regression and classificatioin problems, and can thus be divided into

- Regression trees
- Classification trees

Decision trees applied to regression and classificatioin problems

https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html

Post pruning decision trees with cost complexity pruning

Max depth controls the maximum depth or the number of split points the decision can have and it's the most common parameter used to reduce tree complexity and thus reduce overfitting. The min samples leaf parameter is the threshold that controls what the minimum number of data instances has to be in a leaf to avoid splitting it further. This setting also reduces tree complexity. Finally, max leaf nodes limits the total number of nodes that are leaves of the tree.

Scikit learn key decision tree parameters

- N_estimators: sets # of small decision trees to use in the ensemble 
   - More trees can lead to overfitting
   - Chosen to best exploit the speed and memory capabilities
- Learning_rate: controls emphasis on fixing errors from previous iteration 
   - Adjusted given n_estimators
- The above two are typically tuned together 
   - Small learning rate requires more n estimators to maintain model complexity 
- Max_depth: typically set to a small value (3-5) for most applications
Can effect model complexity


Decision tree key parameters

A decision tree of depth 2 is visualized below. Using the 'value' attribute of each leaf, find the accuracy score for the tree of depth 2 and the accuracy score for a tree of depth 1. What is the improvement in accuracy between the model of depth 1 and the model of depth 2?

Find the Accuracy Score of a Decision Tree

A decision tree is composed of several key components that define its structure and partition logic:

* **Nodes**: Split points where the dataset is partitioned based on feature values.
* **Split point**: The threshold or decision rule that separates one class or range from another.
* **Pure node**: A node where all observations belong to a single class, representing perfect classification.
* **Mixed node**: A node containing a mixture of classes that requires further splitting.
* **Leaf nodes**: The terminal nodes at the end of a branch that represent the final predicted class or value.
* **Informativeness of split**: A measure of the information gained from a split, used to select the optimal split point.

Decision Tree Terminology

Gradient-Boosted Decision Trees

There are 3 tuning parameters when using Boosting:

1. The number of trees, denoted by $$B$$. Cross-validation is used in order to select $$B$$. If the value of $$B$$ is too big, it may overfit the data, albeit slowly.
2. The shrinkage parameter ($$\lambda$$), which controls the rate at which the boosting learns. This value is typically a small positive value; if it is very small, a large $$B$$ value may be required for it to work well.
3. The number of splits in each tree, denoted by $$d$$. This value controls how complex the boosting will be. If $$d = 1$$, there is a single split, where each model has at most 1 variable (also known as a stump). It is also known as the 'interaction depth', which controls the interaction order.

Tuning Parameters in Boosting

Boosting is heavily dependent on the trees formed before it, whereas in bagging, each tree is formed independently and varies instead based on the sample of predictors chosen. 

Boosting vs Bagging

Boosting algorithms are methods to help transform weak learners to stronger learners. There are 3 common boosting algorithms used in data science:

1. AdaBoosting (Adaptive Boosting)
2. GradientBoosting
3. XGBoost (Extreme Gradient Boosting)

Common Boosting algorithm

Below is a video that I found helpful in understanding boosting and how its used with decision trees. The coursera course the video is a part of may be useful as well.

[SAS]. Boosting [Video File]. Retrieved from [www.coursera.org/lecture/machine-learning-sas/boosting-2J0Df](https://www.coursera.org/lecture/machine-learning-sas/boosting-2J0Df) 

Coursera: Boosting with Decision Trees

https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/

what is boosting

Below is a representation of under and overfitting of the boundaries of U.S. sates. The data comes from the US Census Bureau. In its original format, the data is a single Keyhole Markup Language (KML) file which contains latitude and longitude coordinates of the borders of US states. The necessary latitude, longitude, and label (state) data were parsed from the KML files using a simple Python script. The main idea here is to understand the bias-variance trade-off and how that relates to under and overfitting. 

Additionally there are two examples of ways they avoided under and overfitting and created a much more accurate map using (gradient) boosting and random forest classifiers.

Learn Before

Related