<p>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 <a href="http://rads.stackoverflow.com/amzn/click/1558609016" rel="nofollow noreferrer">Data Mining: Concepts and Techniques</a>, which is a standard textbook.</p>

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

<ul>
<li><strong>Bagging:</strong> Creates an ensemble of models (classifiers or predictors) for a learning scheme where each model gives an <em>equally-weighted</em> prediction.</li>
<li><strong>Boosting:</strong> Creates an ensemble of classiﬁers. Each one gives a <em>weighted</em> vote.</li>
</ul>

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

<p>AdaBoost is a boosting method. (The name stands for "Adaptive Boosting".)</p>

<p>AdaBoost works as follows:</p>

<p><a href="http://img181.imageshack.us/img181/8198/adaboost.png" rel="nofollow noreferrer">http://img181.imageshack.us/img181/8198/adaboost.png</a></p>

<p>The equation (6.66) mentioned in the image is as follows:</p>

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

<p>where:</p>

<ul>
<li>$error(M_i)$ is the error rate of model $M_i$;</li>
<li>$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. </li>
</ul>

<hr>

<p>Now, what is cross-validation?</p>

<p>Quoting a part of section 6.13.2 of the above textbook:</p>

<blockquote>
  <p>In <strong>k-fold cross-validation</strong>, 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. </p>
</blockquote>

<hr>

<h3>Can AdaBoost be Augmented with Cross-Validation?</h3>

<p>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.</p>

<p>Note that cross-validation is an accuracy <strong>evaluation</strong> method, while AdaBoost is an accuracy <strong>improvement</strong> 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.</p>

CC BY-SA 2.5
2010-11-02T12:45:59.577Z
Thanks for an informative answer -- pity the OP didn't provide any background.
András Salamon
CC BY-SA 2.5
2010-11-02T13:13:12.123Z
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
CC BY-SA 2.5
2010-11-02T15:38:19.943Z
@Neil: No, I meant at each iteration of the k-fold cross-validation.
Sadeq Dousti
CC BY-SA 3.0
2010-11-02T08:29:15.463Z
2017-03-13T08:21:16.553Z
2017-03-13T08:21:16.553Z
Sadeq Dousti
<p>How does one augment AdaBoost with cross-validation?</p>

CC BY-SA 2.5
2010-11-02T03:38:17.967Z
Need lots more detail! for starters, what do you mean by "augment"?
Lev Reyzin
CC BY-SA 2.5
2010-11-02T04:11:43.530Z
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
CC BY-SA 2.5
2010-11-02T07:55:24.633Z
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 http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question for more tips!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-02T08:52:38.640Z
@Lev & Chang: In my answer below, I added (hopefully) enough explanation of the terms used in the question.
Sadeq Dousti
CC BY-SA 2.5
2010-11-02T12:56:54.763Z
I am quite familiar with all the concepts, including AdaBoost and cross validation, but the question was still unclear.  I'm glad your answer helped @Neil though.
Lev Reyzin
CC BY-SA 2.5
2010-11-02T12:58:50.427Z
I'm sorry that I couldn't elaborate more, but I was in the same boat as you: aware of all the terms and unsure about the best way to make use of cross-validation with AdaBoost.
Neil G
CC BY-SA 2.5
2010-11-02T16:13:52.537Z
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
CC BY-SA 2.5
2010-11-17T01:50:53.623Z
@Lev, I gave two example papers that make it clear that there are a variety of things that can be done.  The answer below is again one other thing that can be done.  If I could have been more specific, I would have been, but then I would have the answer to my question.
Neil G
CC BY-SA 2.5
2010-11-17T06:02:21.403Z
someone understood your question and it was answered quite well, sounds like a good outcome either way :)
Lev Reyzin
CC BY-SA 2.5
2010-11-17T06:05:35.080Z
Yes, you're absolutely right :)
Neil G
<lg.learning><machine-learning>
How does one augment AdaBoost with cross-validation?
Neil G
# How does one augment AdaBoost with cross-validation?

(Asked by: username_0 on 2010-11-02)

How does one augment AdaBoost with cross-validation?

**Tags:** lg.learning, machine-learning

> **Comments:**
> **username_1**: Need lots more detail! for starters, what do you mean by "augment"?  
> **username_0**: 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  
> **username_2**: 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 http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question for more tips!  
> **username_3**: @Lev & Chang: In my answer below, I added (hopefully) enough explanation of the terms used in the question.  
> **username_1**: I am quite familiar with all the concepts, including AdaBoost and cross validation, but the question was still unclear.  I'm glad your answer helped @Neil though.  
> **username_0**: I'm sorry that I couldn't elaborate more, but I was in the same boat as you: aware of all the terms and unsure about the best way to make use of cross-validation with AdaBoost.  
> **username_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.  
> **username_0**: @Lev, I gave two example papers that make it clear that there are a variety of things that can be done.  The answer below is again one other thing that can be done.  If I could have been more specific, I would have been, but then I would have the answer to my question.  
> **username_1**: someone understood your question and it was answered quite well, sounds like a good outcome either way :)  
> **username_0**: Yes, you're absolutely right :)  

---

## 1 answers

### Answer by username_3 on 2010-11-02. Score: 15 | Accepted answer

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](http://rads.stackoverflow.com/amzn/click/1558609016), 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.

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

> **Comments:**
> **username_4**: Thanks for an informative answer -- pity the OP didn't provide any background.  
> **username_0**: 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?  
> **username_3**: @Neil: No, I meant at each iteration of the k-fold cross-validation.  

---

