# How does one augment AdaBoost with cross-validation?

How does one augment AdaBoost with cross-validation?

-
Need lots more detail! for starters, what do you mean by "augment"? –  Lev Reyzin Nov 2 '10 at 3:38
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 –  Neil G Nov 2 '10 at 4:11
@Lev & Chang: In my answer below, I added (hopefully) enough explanation of the terms used in the question. –  Sadeq Dousti Nov 2 '10 at 8:52
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. –  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 classiﬁers. 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.

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

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

where:

• $err(X_j)$ is the error rate of model $M_i$;
• $err(X_j)$ is the misclassiﬁcation error of tuple $X_j$: If the tuple was misclassiﬁed, 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 ﬁrst iteration, subsets $D_2, \ldots , D_k$ collectively serve as the training set in order to obtain a ﬁrst 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.

-
Thanks for an informative answer -- pity the OP didn't provide any background. –  András Salamon Nov 2 '10 at 12:45
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? –  Neil G Nov 2 '10 at 13:13
@Neil: No, I meant at each iteration of the k-fold cross-validation. –  Sadeq Dousti Nov 2 '10 at 15:38