# 1. Decision Trees ## 1.1 How decision trees split data A decision tree, the simplest of the tree-based models, uses **Gini impurity** — a measure of heterogeneity within a subset of data — to decide how to split the data at each step. The algorithm looks for the split that produces the highest purity, so that one resulting partition contains mostly (or entirely) one class and the adjacent partition contains mostly the other. Gini impurity ranges from 0 to 0.5: a value of 0 indicates a pure node where every example belongs to a single class, while 0.5 indicates maximum impurity, where classes are evenly split within the node. ## 1.2 The recursive tree-building algorithm Training a decision tree means recursively splitting the dataset into smaller subsets based on whichever feature best separates the classes. The process works as follows: 1. **Start at the root.** All the data begins at a single root node. 2. **Evaluate every feature and split point.** The algorithm examines all candidate features and possible split thresholds, calculating a measure like Gini impurity for each one, to find whichever feature and threshold create the most homogeneous resulting subsets. 3. **Base cases.** If every example remaining in a node already belongs to the same class, the algorithm creates a leaf node representing that class. If there are no features left to split on, or another stopping criterion is met (such as reaching a maximum tree depth or having too few examples left in the node), the algorithm creates a leaf node representing the most common class among the remaining data. 4. **Create a decision node.** Once the best splitting feature is identified, a new decision node is created to represent it. 5. **Branch and recurse.** The dataset is divided into subsets based on the values of that best feature, and the tree-building process is called recursively on each subset — with the just-used feature removed from consideration — to build out each subtree. 6. **Assemble the tree.** The resulting child subtrees are attached as branches off the root, forming the complete decision tree. The final nodes of the tree, called **leaves**, hold the model's predictions: for classification, the prediction is based on the proportion of each class present in that leaf; for regression, the prediction is the average of the target values that landed in that leaf. ## 1.3 The overfitting problem in a single tree A single decision tree is prone to **overfitting** as its depth increases — deeper trees create more flexible decision boundaries, which increases the model's variance and, in turn, hurts its performance on unseen data. This is the central weakness that both random forest and boosted trees are designed to address. # 2. Random Forest ## 2.1 How random forest works Random forest addresses a single decision tree's overfitting problem through **bagging** — bootstrap aggregation — which trains many decision trees independently on bootstrapped samples of the data and then averages their predictions: ``` 1. For b = 1 to B: (a) Draw a bootstrap sample Z* of size N from the training data. (b) Grow a decision tree T on the bootstrap sample. At each split, consider only a random subset of M features. 2. For a new observation, get a prediction from every trained tree, and take the majority vote (classification) or average (regression). ``` Because each tree is trained on a different bootstrap sample and a different random subset of features at each split, the individual trees end up relatively uncorrelated with one another — which is precisely what allows averaging their predictions to reduce variance. If every tree in the forest were trained on the exact same observations and features, it would produce the same prediction every time, defeating the entire purpose of a "random" forest. ## 2.2 Key hyperparameters **Number of trees.** As the number of trees increases, the model's variance decreases (much like how the variance of a sample statistic shrinks as sample size grows — with more trees, predictions converge toward a stable mean with less variability), though bias increases very slightly. More trees generally benefit generalization, but the improvement plateaus, and adding trees indefinitely eventually becomes wasteful without further benefit. **Tree depth.** Depth controls how tightly each individual tree fits the training data. Deeper trees increase variance and decrease bias. Finding the right balance between tree depth and the number of trees is essential to building a high-performing random forest. **Column and row sampling.** If two trees were trained on the exact same observations and the exact same features, they'd produce identical predictions — which defeats the purpose of averaging multiple independent estimators to reduce variance. Randomly sampling both observations (rows) and features (columns) for each tree is what prevents this, reducing overfitting and improving generalization. **Minimum samples per leaf and minimum samples to split.** These two parameters govern whether a given node is allowed to split further. For example, if the minimum-samples-to-split threshold is 8, a node with 9 observations will still be split — but if the minimum-samples-per-leaf threshold is 2, and the resulting split would create leaves with only 1 and 8 observations, that split will be rejected because it would violate the leaf-size minimum. As both thresholds are lowered, bias decreases while variance increases. # 3. Boosted Trees Boosted tree methods — including **XGBoost**, **AdaBoost**, **GBM**, **CatBoost**, and **LightGBM** — all share the same core idea: unlike random forest, which trains trees independently and averages them with equal weight, boosting builds trees **sequentially**, where each new tree's training data (and the weight given to each observation) is shaped by how the previous tree misclassified the data. In other words, boosting assumes sequential dependence between trees and combines them through weighted averaging, rather than random forest's assumption of independence and equal-weighted averaging. # 4. Bagging vs. Boosting **Bagging** trains multiple models independently and in parallel on random samples of the same original data, then averages their predictions — random forest is the canonical example, training $K$ decision trees independently and averaging their outputs. This is primarily a variance-reduction technique. **Boosting** instead trains weak learners (typically shallow decision trees) iteratively: the errors made by one weak learner get folded into the training weights used for the next learner in the sequence, and the final prediction combines the outputs of all the weak learners. Because each new model is explicitly trying to correct the mistakes of the previous ones, boosting reduces bias; and because the final prediction still averages across many learners, it reduces variance as well. # 5. Bias-Variance Comparison Across Tree Models Putting all three approaches side by side: a single **decision tree** has the lowest bias but the highest variance, which is exactly what makes it prone to overfitting the training data. **Random forest** addresses that high variance directly through bagging — averaging many independently trained trees — at the cost of a slight increase in bias, reflecting the usual bias-variance tradeoff. **Boosted trees**, when properly tuned, tend to deliver the best out-of-the-box performance of the three: low bias and moderate variance, assuming the hyperparameters (learning rate, tree depth, number of estimators, and so on) are set well.