= Weighted decision stump optimization
For stumps $h(x)=\operatorname{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)$.
Back to article page
