A random forest is bagging applied to fully-grown C&RT trees, with each branch looking only at a few randomly projected features. When bootstrap draws N times, each example has about a 1/e ≈ 36.8% chance of not being used by a given tree. These out-of-bag examples give E_oob directly, a validation that needs no held-out data and no re-training; add the permutation test and you get an importance for every feature. The price is that the result wobbles with the random seed, so you keep adding trees until G is stable.
The sum of AdaBoost's weights in each round is exactly the sum of the exponential error exp(−ys). From that, this lecture derives that the gₜ found by the base algorithm is an approximate functional gradient direction, and the vote αₜ is the best step size along that direction. Swap the exponential error for squared error and the same derivation becomes 'in each round, run regression on the residuals yₙ − sₙ, then set the step size with one-variable linear regression'; with a weakened C&RT as the base model, that is GBDT.
A decision tree is a model that learns conditional aggregation as it goes: every path from the root to a leaf is a condition, and the leaf is a constant. C&RT splits the data in two with one decision stump at a time, picks the split with the smallest weighted impurity, and keeps going until nothing can be split. A tree grown this way almost always has E_in equal to 0, so it is pruned with "E_in plus λ times the number of leaves", with λ chosen by validation. The same recursion also handles multiclass problems, categorical features, and missing values.
HW4 Problem 3 quantifies why voting trees get more accurate in three steps: with p=0.6 the Hoeffding bound needs B≈691 independent trees to reach 10⁻⁶; correlation ρ between trees floors ensemble variance at ρσ²; and random forests' dense ensembling is compared with MoE's sparse routing.
Lecture 6 recursively grows a tree from decision stumps, measures label uncertainty with entropy, and selects splits by `I(Y;W)=H(Y)-H(Y|W)`; this is computationally practical greedy ERM, not a global optimal-tree guarantee.