Bootstrap aggregation, or bagging, is a way to help construct more powerful prediction models by reducing high variance of a statistical learning method. It is often used to improve the performance of decision trees. In order to reduce the variance, $B$ different bootstrapped training data sets are produced (typically taken from a single training data set). It then uses the $b$th bootstrapped training data set to train the method to produce  $\hat{f}^{*b}(x)$. Afterwards, all the predictions are then averaged in order to get  $\hat{f}_{bag}(x) =  \frac{1}{B} \sum_{b=1}^B \hat{f}^{*b}(x)$. 

Bagging

The Random Forest is a model made up of many decision trees. It trains each one on a slightly different set of the observations, splitting nodes in each tree considering a limited number of the features. The final predictions of the random forest are made by averaging the predictions of each individual tree. In random forest algorithm, we do not need to do pruning for each "weak" decision tree. 

Advantage of Random Forest:
- Less overfitting
- Parallel implementation

Random Forest

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

Pruning decision trees is the process of removing certain branches which are not beneficial towards the model’s goal. Decision trees frequently over-fit, which leads to an excess of branches. As a result, a decision tree performs extremely well on the training set, but is over-fitting leading to poor test set performance. To prevent this, individuals can ‘prune’ the decision tree leading to fewer branches preventing over-fitting. Types of pruning include minimum error, smallest tree, and early stopping.

Pruning Decision Trees

University of Michigan - Ann Arbor

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

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

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

Leaf nodes: the end of a branch that represents an object

Nodes: split points

Pure node: all in this category are in one class; perfect classification

Mixed node: a mixture of classes that requires further splitting

Split point: the threshold that separates one class from another

Informativeness of split: a measure of how much information is gained from that node; the decision tree builds nodes the split points based on which gives the most informative split

Decision Tree Terms

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

- Training builds a series of small decision trees 
- Each tree attempts to correct errors from previous stage 
- The learning rate controls how hard each tree tries to correct remaining mistakes from previous round
   - High learning rate: more complex trees 
   - Low learning rate: simpler trees 


Gradient Boosted Decision Trees 

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?

Learn Before

Related

Learn After