Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

How does one augment AdaBoost with cross-validation?

share|improve this question
2  
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
    
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! –  Hsien-Chih Chang 張顯之 Nov 2 '10 at 7:55
    
@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
1  
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
show 5 more comments

1 Answer 1

up vote 13 down vote accepted

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)}$

where:

  • $err(X_j)$ 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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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