AdaBoost algorithm question 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?
 A: 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.
