How does one augment AdaBoost with cross-validation?

  • 2
    $\begingroup$ Need lots more detail! for starters, what do you mean by "augment"? $\endgroup$ – Lev Reyzin Nov 2 '10 at 3:38
  • $\begingroup$ I found some papers that I think are what I was looking for: Improving Adaptive Boosting with k-Cross-Fold Validation; Using Validation Sets to Avoid Overfitting in AdaBoost $\endgroup$ – Neil G Nov 2 '10 at 4:11
  • $\begingroup$ Please help us to help you: add more details and definitions to your problem, and narrow down the information you want by asking specific questions; see meta.cstheory.stackexchange.com/questions/300/… for more tips! $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 2 '10 at 7:55
  • $\begingroup$ @Lev & Chang: In my answer below, I added (hopefully) enough explanation of the terms used in the question. $\endgroup$ – M.S. Dousti Nov 2 '10 at 8:52
  • 1
    $\begingroup$ Not to belabor the point, but the reason some of us took issue with the question is not because we did or didn't know how to use cross validation with boosting in some way (I have in fact done research in this area), but because we didn't know what you were asking -- though I can only speak for myself. The subject of your question is indeed interesting, but I'm writing this so that perhaps for future questions you could keep this in mind and give more details about what you want to know. $\endgroup$ – Lev Reyzin Nov 2 '10 at 16:13

The question is stated very succinctly; yet I think I can help since I'm familiar with the terminology. I'm gonna use information from Data Mining: Concepts and Techniques, which is a standard textbook.

Chapter 6 discusses different algorithms for classification. Then, in section 6.14, two methods are introduced for increasing the accuracy of a classifier:

  • Bagging: Creates an ensemble of models (classifiers or predictors) for a learning scheme where each model gives an equally-weighted prediction.
  • Boosting: Creates an ensemble of classifiers. Each one gives a weighted vote.

The two methods incorporate a base classifier, trying to improve its accuracy by sampling the data several times, and training the classifier on the sampled instance.

AdaBoost is a boosting method. (The name stands for "Adaptive Boosting".)

AdaBoost works as follows:


The equation (6.66) mentioned in the image is as follows:

$error(M_i)=\sum\limits_j^d{w_j \times err(X_j)}$


  • $error(M_i)$ is the error rate of model $M_i$;
  • $err(X_j)$ is the misclassification error of tuple $X_j$: If the tuple was misclassified, then $err(X_j)$ is 1. Otherwise, it is 0.

Now, what is cross-validation?

Quoting a part of section 6.13.2 of the above textbook:

In k-fold cross-validation, the initial data are randomly partitioned into $k$ mutually exclusive subsets or “folds,” $D_1, D_2, \ldots , D_k$, each of approximately equal size. Training and testing is performed $k$ times. In iteration $i$, partition $D_i$ is reserved as the test set, and the remaining partitions are collectively used to train the model. That is, in the first iteration, subsets $D_2, \ldots , D_k$ collectively serve as the training set in order to obtain a first model, which is tested on $D_1$; the second iteration is trained on subsets $D_1, D_3, \ldots , D_k$ and tested on $D_2$; and so on.

Can AdaBoost be Augmented with Cross-Validation?

Yes. In AdaBoost, you need $D$, a set of $d$ class-labeled training tuples. Applying a k-fold cross-validation on this set, you will have 1 test sample (containing $d/k$ tuples) and $k-1$ training samples (containing $d(k-1)/k$ tuples). Using this strategy, and iterating $k$ times, the algorithm will benefit from the best of both worlds.

Note that cross-validation is an accuracy evaluation method, while AdaBoost is an accuracy improvement method. In the method I suggested above, cross-validation is used to retain the best classifier obtained from AdaBoost (in terms of accuracy), and discarding other classifiers.

  • 1
    $\begingroup$ Thanks for an informative answer -- pity the OP didn't provide any background. $\endgroup$ – András Salamon Nov 2 '10 at 12:45
  • $\begingroup$ Thanks for filling in the background for people unfamiliar with cross-validation and AdaBoost. When you say "discarding other classifiers", you mean at each iteration of AdaBoost, right? $\endgroup$ – Neil G Nov 2 '10 at 13:13
  • $\begingroup$ @Neil: No, I meant at each iteration of the k-fold cross-validation. $\endgroup$ – M.S. Dousti Nov 2 '10 at 15:38
  • $\begingroup$ I've noticed that there are one or more images in your question which are hosted on ImageShack that have been erased and replaced by advertisements and are no longer recoverable. Do you have backup copies of these images you could upload here? Thank you! $\endgroup$ – user35258 Aug 25 '15 at 6:06

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.