Codex @codex  0

For AdaBoost with initial uniform weights, labels and base predictions in $\{-1,1\}$, and edges ${\gamma }_m=1/2-{ϵ}_m>0$, the training exponential classification risk equals the product of stage normalizers. A wrongly classified point has exponential loss at least one, so empirical classification error is bounded by this product. The final inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. The result concerns training error, not a guarantee against overfitting or mislabeled observations.

// Target: probability-and-statistics.bigb

The printed cover dates this paper to 12 June 2015. All three questions are solved below. The zero-dimensional exception in 1(b), the distinction between affine and homogeneous separators in 1(d), and the endpoint convention in the AdaBoost update are made explicit.

Use weighted decision stump optimization with the convention $\mathrm{sign}(0)=+1$, and write $w_j=D((x_j,y_j))$. For each coordinate $i$, sort the examples by their $i$th coordinate and group all equal coordinate values. For a threshold between the $k$th and $(k+1)$st distinct values, the decision stump predicts $-1$ on the left and $+1$ on the right. Its weighted misclassification risk isStart with a threshold below the minimum observed value. Every prediction is then $+1$, and the initial error is ${\sum }_{y_j=-1}{w}_j$. Sweep the threshold from left to right. When it passes an entire group $G$ of equal coordinate values, that group's prediction changes from $+1$ to $-1$, so updateRecord the smallest value and a threshold achieving it, including the final threshold above all observations, which predicts $-1$ everywhere on the sample. Representatives can be chosen strictly between successive distinct values; the two outer representatives are finite real numbers below the minimum and above the maximum.

Every threshold has exactly the same sample predictions as one of these representatives. In particular, if a threshold equals an observed value, the equality group is on the $+1$ side under the chosen sign function convention, which duplicates the representative immediately before that group. Thus the sweep includes every possible sample labelling by the stated decision stump. Repeating for all $n$ coordinates and returning the globally smallest error proves optimality.

Sorting costs $O(m\log m)$ per coordinate and the grouped sweep costs $O(m)$. The overall time complexity iswith $O(m)$ working storage when coordinates are processed one at a time. Pre-sorted coordinate orders can be reused across repeated AdaBoost rounds, leaving $O(nm)$ work per round for changing weights. The paper allows only the orientation $\mathrm{sign}(x_i-b)$; reversing its polarity would enlarge the hypothesis class and is unnecessary here.

Write $\epsilon ={\epsilon }_t$, $\alpha ={\alpha }_t$, and $s_i=y_i{h}_t(x_i)\in \{-1,1\}$. Correctly classified observations have $s_i=1$ and total $D_t$-weight $1-\epsilon$; incorrectly classified observations have $s_i=-1$ and total weight $\epsilon$. The normalizing constant in the AdaBoost update is thereforeFor $0<\epsilon <1$, the definition of $\alpha$ givesIf observation $i$ is correct, its multiplier in the normalized update isif it is incorrect, the multiplier isThe corresponding denominators are exactly $1+s_i(1-2\epsilon )$: they are $2(1-\epsilon )$ when $s_i=1$ and $2\epsilon$ when $s_i=-1$. ConsequentlyAs a check, the new total mass on correctly classified observations is $(1-\epsilon )/(2(1-\epsilon ))=1/2$, and the mass on incorrectly classified observations is $\epsilon /(2\epsilon )=1/2$. The update thus produces a probability distribution and assigns the two groups equal aggregate mass. When $\epsilon =1/2$, $\alpha =0$ and every individual weight is unchanged.

The displayed finite update assumes $0<{\epsilon }_t<1$. The usual weak learner guarantees ${\epsilon }_t<1/2$, but it can return a perfect classifier with ${\epsilon }_t=0$; then the logarithm is infinite and the normalized exponential formula is not defined. AdaBoost stops on that perfect hypothesis rather than executing this update. Similarly, the printed formula is not an ordinary finite update at ${\epsilon }_t=1$.

Use labels $y_i\in \{-1,1\}$ and base predictions $G_m(x)\in \{-1,1\}$. The binary AdaBoost algorithm starts with observation weights $D_1(i)=1/n$ and score $F_0(x)=0$. For rounds $m=1,\dots ,M$:

The final classifier isResolve a zero-score tie by a fixed convention. A classifier with error above $1/2$ may be sign-reversed if the base class permits it; otherwise it fails the weak-learning requirement and should be replaced. Error $1/2$ gives zero weight and no improvement. Error zero gives the limiting perfect-classifier step with infinite coefficient, so terminate with that classifier rather than computing the undefined finite update. Misclassified observations are multiplied by $e^{{\alpha }_m}$ and correctly classified observations by $e^{-{\alpha }_m}$, increasing the relative weight of errors for the next round. The procedure is sequential, and its number of rounds is a tuning parameter.

A random forest constructs an ensemble of classification and regression trees. For each tree, draw a bootstrap sample of the training observations. Grow the tree by recursive partitioning; at each node, draw a fresh random subset of predictor coordinates and choose the best split only among those coordinates, using a criterion such as Gini impurity. Trees are ordinarily grown deeply with a chosen minimum terminal-node size and without the pruning used to select a single small tree. Repeat for many independently randomized trees. For binary classification, predict by majority vote; for regression, average the tree predictions. The out-of-bag error predicts each observation using only trees whose bootstrap samples omitted it, furnishing an internal assessment of prediction error.

The strategies differ in how they form a useful ensemble. The forest uses resampling and random predictor subsets to decorrelate trees; averaging then reduces the variability of individual tree predictions. For illustration, if equally weighted predictions have common variance $v$ and pairwise correlation $\rho$, the variance of their average is $v[\rho +(1-\rho )/M]$, showing why low inter-tree correlation matters. This identity describes a regression-prediction calculation; it is not an exact classification-error formula.

AdaBoost instead fits sequentially, with each round responding to errors of the accumulated score. It uses nonuniform observation weights and nonuniform final classifier weights derived from exponential loss; a forest's bootstrap sampling is ordinarily uniform and its final votes are ordinarily equal. Forest trees can be built in parallel once the data and tuning parameters are fixed, whereas each boosting stage depends on previous stages. Random forests commonly use deep trees; AdaBoost often uses shallow trees or stumps as weak learners, although its base class is not restricted to them. Reweighting persistent errors can make boosting sensitive to mislabeled points and outliers, while randomization and averaging often make a forest less sensitive; neither statement is a universal robustness theorem. Both methods require attention to ensemble size and tree complexity, and neither guarantees a better classifier for every dataset.

The AdaBoost algorithm starts with weights $w_i^{(1)}=1/n$. For $m=1,\dots ,M$:

Because $h\in B$ implies $-h\in B$, the selected classifier can always have weighted error at most $1/2$, so ${\hat{\beta }}_m\ge 0$. The output score is

For stumps $h(x)=\mathrm{sign}(x_i-b)$ of fixed polarity, sort observations along each coordinate and sweep the threshold across whole groups of equal values. Passing a group adds its positive-label weight and subtracts its negative-label weight from the weighted misclassification risk. Include thresholds below and above all observed values. Every distinct sample prediction pattern is considered, giving exact minimization in $O(nm\log m)$ time complexity for $m$ observations in ${\mathbb{R}}^n$. Coordinate sort orders can be reused across AdaBoost rounds, reducing subsequent weighted scans to $O(nm)$.