1
$\begingroup$

In the boosting algorithm,AdaBoost ,those observations which were misclassified by the classifier in the (m-1)th step have their weights increased in the mth step, and those which were correctly classified have their weights decreased. My question is, that isn't it possible that the new classifier now classifies the low weights ones wrong ,so that this cycle can continue and not yield much of a benefit?

$\endgroup$

1 Answer 1

2
$\begingroup$

According to Bishop's "Pattern Recognition and Machine Learning"(page 658) the weights of the correctly classified points are not decreased. Only the weights of the incorrectly classified points are increased.

The new classifier might indeed classify the old points incorrectly. However the previous 'versions' of the classifier(from previous iterations) are not thrown away. The end result is an ensemble/average of all the classifiers of each step where the contribution of each classifier is weighted by how well that particular classifier did at that round.

For example if we have an outlier that is hard to classify correctly, the outlier will accumulate a lot of weight. The classifier will be forced to give priority to that point and classify it correctly. This might mean that all the other points are misclassified. However, this classifier's 'opinion' will not be so important in the end because only one point was classified correctly(the outlier). This is also a good way to detect outliers. Just find the points with very large weight.

I should add that you usually do not want to let AdaBoost converge because it will most probably overfit. You need to use a method like cross-validation to find the optimal number of rounds instead.

For a more formal treatment of why AdaBoost works, I would recommend you read Bishop's chapter 14.3.1 or this paper which is the first to provide a theoretical analysis of AdaBoost. It basically minimises the exponential error function.

$\endgroup$
8
  • $\begingroup$ This is wrong , as in ESL book Pg 338 , "Misclassified observations have their weights increased while the correctly classified have their weights decreased" $\endgroup$
    – sww
    Commented Mar 13, 2018 at 19:20
  • $\begingroup$ There are different variations of the algorithm. For example in the book 'Pattern recognition and Machine Learning' of Christopher M. Bishop you can see that there is an indicator function that prevents the weights of the correctly classified points to decrease. If you renormalise the weights to add up to 1, then yes some of the weights will decrease. $\endgroup$
    – Andreas G.
    Commented Mar 13, 2018 at 19:31
  • $\begingroup$ So that is exactly what my question is addressing . How can we guarantee that weights of correctly classified decreasing will not make them incorrectly classified? $\endgroup$
    – sww
    Commented Mar 13, 2018 at 19:34
  • $\begingroup$ Usually it is indeed the case that after changing the weights, some correctly classified points are misclassified by the classifier of that round. The final classifier however will combine all classifiers of all rounds to give a result. I will add an example to my answer soon $\endgroup$
    – Andreas G.
    Commented Mar 13, 2018 at 19:39
  • $\begingroup$ I want a theoretical justification[Proof] ,that it would work in all cases . Intuitively i understand it. $\endgroup$
    – sww
    Commented Mar 13, 2018 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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