3
$\begingroup$

In boosting, the primary idea is to re-adjust weights of training instances, so that subsequent models learn how to fit difficult-to-classify samples.

From Wikipedia Boosting (Machine Learning):
While boosting is not algorithmically constrained, most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are weighted in a way that is related to the weak learners' accuracy. After a weak learner is added, the data weights are readjusted, known as "re-weighting". Misclassified input data gain a higher weight and examples that are classified correctly lose weight.[note 1] Thus, future weak learners focus more on the examples that previous weak learners misclassified.

However, in Gradient Boosting, I do not see any reference of training instance re-weighting being mentioned. Also, there is no such parameter in the implementation on Scikit-Learn.

I do see a parameter called learning rate, that combines subsequent models, however, that seems to be fixed and not adjustable for each subsequent model.

$\endgroup$
1
  • $\begingroup$ Depending from which reference you are using when it regards to boosting it often regards to AdaBoost. $\endgroup$ Oct 5, 2021 at 23:47

2 Answers 2

2
$\begingroup$

On generic gradient boosting you'd be able to as Menhmet Suzen put it out but even the gradient tree boosting coming from the generic algorithm they are not the same even if the weak learner $h$ is a regression tree. Friedman (2001) makes a change on gradient tree boosting which is to optimise the tree's output.

So the model updating from generic algorithm:

$F_m(x)=F_{m-1}(x)+\rho_m h_m(x)$

is switched by:

$F_m(x)=F_{m-1}(x)+h_m(x)$

where:

$h_m(x)=\sum_{j=1}^{J_m}\hat{b}_{jm}I(x \in R_{jm})$, $R_{jm}$ as the $j$-th terminal node of the $m$-th tree and $\hat{b}_{jm}$ its optimized output.

This approach has come from optimizing $b_{jm}=\rho_m \gamma_{jm}$ ($\gamma_{jm}$ also as a tree output) is better than optimizing $\rho_m$ and $\gamma_{jm}$ separately because the first one is a one dimensional optimization.

Finally there is a another change has been done to prevent overfitting which is to put a learning rate $\alpha$ on model update:

$F_m(x)=F_{m-1}(x)+\alpha h_m(x)$

As the weights and trees are actually the same thing I think the "re-adjusting weights" interpretation would make you confuse on gradient tree boosting algorithm. It would still make sense on generic algorithm, as I showed, but almost no one use gradient boosting without using trees as weak learners. There still is a pretty cool interpretation on gradient tree boosting, you can look that as additive algorithm where a update $F_m$ fix the residuals of previous model $F_{m-1}$ since $h_m$ is fitted to residuals (it's actually fitted to pseudo residuals but for quadratic loss they are the same) and then added to $F_{m-1}$ in order to attempt "undo" the errors generated by $F_{m-1}$, furthermore you can look at the learning $\alpha$ as a cap to the 'model fixing' for prevent overfitting.

Answering your main question a boosting algorithm is any model that fits a additive expansion like that:

$f(x)=\sum_{m=1}^{M} \beta_m f(x,\theta_m)$

or a tree expansion:

$f(x)=\sum_{m=1}^{M}\sum_{j=1}^{J_m}{b}_{jm}I(x \in R_{jm})$

$\endgroup$
1
$\begingroup$

Intuitively, the new model update, i.e., additive modelling step, in Algorithm 1 of Professor Friedman's work Greedy function approximation: A gradient boosting machine or in any similar step occurring other inceptions of the idea of so called stepwise-greedy learning is a boosting step as mentioned in the paper with the expression for $\rho_m$: $$ F_m(x) = F_{m-1}(x) + \rho_m h_m(x)$$ Here, $\rho_m$ plays a role of reweighing and penalise the new additive model, because $\rho_m$ is learned from training the new "weak learner". Similar update occurs explicitly in trees in the same work's Algorithm 3 (tree boost), with an indicator function instead of $\rho_m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.