2
$\begingroup$

How does one augment AdaBoost with cross-validation?

$\endgroup$
10
  • 2
    $\begingroup$ Need lots more detail! for starters, what do you mean by "augment"? $\endgroup$
    – Lev Reyzin
    Commented Nov 2, 2010 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
    Commented Nov 2, 2010 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$ Commented Nov 2, 2010 at 7:55
  • $\begingroup$ @Lev & Chang: In my answer below, I added (hopefully) enough explanation of the terms used in the question. $\endgroup$ Commented Nov 2, 2010 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
    Commented Nov 2, 2010 at 16:13

1 Answer 1

15
$\begingroup$

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:

http://img181.imageshack.us/img181/8198/adaboost.png

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:

  • $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.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for an informative answer -- pity the OP didn't provide any background. $\endgroup$ Commented Nov 2, 2010 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
    Commented Nov 2, 2010 at 13:13
  • $\begingroup$ @Neil: No, I meant at each iteration of the k-fold cross-validation. $\endgroup$ Commented Nov 2, 2010 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
    Commented Aug 25, 2015 at 6:06

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.