Trees, Forests, and Boosting

Bagging trains many copies of one model on bootstrap resamples of the training rows, then averages their predictions. Averaging cancels the errors that differ from copy to copy, cutting variance; the systematic error every copy shares survives, so bias stays.

Gradient boosting starts from a single constant prediction, then repeatedly fits a shallow tree to the errors the model still makes and adds that tree to the running total. Earlier trees are never refitted.

Level-wise growth splits every leaf at the current depth before going deeper, producing balanced trees. Leaf-wise growth repeatedly splits whichever leaf anywhere in the tree promises the largest loss reduction, producing deeper, lopsided trees that fit harder and overfit sooner.

Four pre-pruning limits: a maximum tree depth, a minimum node size to split, a minimum number of samples per resulting leaf, and a minimum impurity decrease per split. Any split breaking one of them is refused.

No. The number of trees is a Monte Carlo averaging parameter, so error converges to a limit and flattens rather than degrading. Overfitting in a forest comes from how deep and how pure the individual trees may grow.

The learning rate scales every tree's output before it is added to the ensemble. Shrinking it makes each round a smaller correction, so you need proportionally more rounds; roughly, learning rate times rounds sets how far the fit travels.

Gini impurity is 1 - sum(p_i^2) and entropy is -sum(p_i * log2 p_i). Both are zero at a pure node and largest when classes are evenly mixed, and they rank splits so similarly that the choice rarely changes the tree.

AdaBoost scales misclassified examples' weights up and correct ones down, then renormalises, so the next weak learner targets current mistakes. That learner's vote weight is 0.5 * ln((1 - e) / e), where e is its weighted error.

A regression tree's leaves store constants, usually the mean target of the training rows that land there. Anything past the largest split threshold falls into the same edge leaf, so the prediction stops moving and stays inside the range of training targets.

Histogram-based split finding pre-bins each continuous feature into a few hundred buckets once, before training. Split scoring then scans a few hundred candidate cut points per feature instead of every sorted data value, and stores one byte per value.

Impurity importance sums, for every split that uses the feature, the drop in node impurity weighted by the fraction of training rows reaching that node. The totals are combined across the forest's trees and normalised to sum to one.

An ordered target statistic encodes each row using only the rows that precede it in a random permutation and share its category. The row's own label never enters its own encoding, so the feature cannot cheat on training data.

Cost-complexity pruning scores a tree as training error plus alpha times its leaf count, then collapses the subtree with the smallest error cost per leaf removed. Larger alpha yields a smaller tree, and alpha is chosen by cross-validation.

A random forest restricts every split to a random subset of the features. That stops one strong predictor dominating every tree, so the trees are less correlated — and correlation between trees is what limits how much variance averaging can remove.

Expanding the loss to second order around the current predictions turns each leaf into a one-variable quadratic in its output. Minimising that quadratic gives the leaf weight -G/(H+lambda): minus the summed gradients over the summed curvatures plus the penalty.

A CART tree scores every candidate split - each feature crossed with each candidate cut point - by the sample-weighted impurity of the two children it would create, then keeps the single split with the largest impurity drop and recurses.

Base models memorise their own training rows, so in-sample predictions look far better than they ever will on new data. Out-of-fold predictions, where each row is scored by a model that never saw it, give the meta-learner honest inputs.

Choose a random forest when tuning time is short and the data is small or noisy: its defaults sit close to its best and averaging dilutes bad rows. Choose gradient boosting when you can afford a search and need maximum accuracy.

A near-unique column offers thousands of candidate cut-points, so the greedy splitter can almost always find one that lowers training impurity by chance. Those spurious splits accumulate credit because impurity importance is measured on the training rows only.

Boosting supplies accuracy through many rounds, so it needs a high-bias, low-variance base learner only slightly better than chance. A stump, one feature and one threshold, is the cheapest such learner and refits fast each reweighted pass.

Hard voting takes each model's predicted class label and picks the majority. Soft voting averages the models' predicted class probabilities and picks the highest average, so a confident model outweighs several hesitant ones.

Tabular columns are heterogeneous, thresholded and interaction-heavy. Axis-aligned splits handle mixed units, categories and missing values with no scaling, and boosting's stage-wise fitting keeps adding capacity exactly where the ensemble is still wrong.

Split choice is a greedy pick of the single best-scoring cut, and the top candidates are often nearly tied. A one-row change can flip which cut wins, and because the choice is at the root, every subtree below is rebuilt on a different partition.

Drawing n rows with replacement, a given row is missed on every draw with probability (1 - 1/n)^n, which converges to 1/e, about 0.368. So roughly 63.2% of the distinct rows land in-bag and 36.8% are out-of-bag.

Each tree fits the negative gradient of the loss at the current prediction, not the raw error. For squared error that equals the plain residual; for log loss it is the label minus the predicted probability.

Total gain sums the objective reduction every split on the feature achieved; split count only counts how many nodes used the feature, treating a decisive root split and a trivial deep one as equal. They routinely rank the same model's features differently.

Fitting each round's tree on a random fraction of rows and columns decorrelates successive trees, adds a regularising noise to the gradient estimate, and cuts per-round cost. It usually validates better than the full-data fit, until the subsample is so small the fit turns unstable.

A regression tree scores each candidate split by the sample-weighted variance of its two children and keeps the largest variance reduction. Each leaf then predicts the mean of the training targets that land in it.

Exponential loss penalises a wrong prediction exponentially in how wrong it is, so a mislabelled row that can never be fit gains weight every round. Tens of rounds later a few such rows can own most of the distribution.