2
$\begingroup$

For a balanced binary training dataset i.e number of data points with class +1 are equal to number of data points with class -1 , what will happen if we use weak binary classifiers whose classification accuracy is less than 50%, say 30%? Will the performance of the combined classifier improve with more iterations?

I am aware that binary classifiers who perform worse than 50%, still contribute to final prediction, but will the performance of combined classifiers improve with more iterations ?

$\endgroup$

2 Answers 2

2
$\begingroup$

AdaBoost automatically adapts to a classifier that gives a below 50% accuracy by flipping its prediction. Meaning, a below-50% weak classifier becomes an above-50% weak classifier by flipping its prediction.

The weight formula is where this flipping happens:

$$w_t=\frac{1}{2}\mbox{log}(\frac{1}{\epsilon_t} - 1)$$

where $t$ is the current iteration. For $0.5 < \epsilon_t < 1$, weight becomes negative, and later it is multiplied by each predicted label $h_t(x_i) \in \{+1, -1\}$to flip it.

This means that classifiers at each and every iteration have an above 50% accuracy since their weighted prediction is used in the final combined prediction.

$\endgroup$
3
  • $\begingroup$ Does that mean that it will still improve the combined classifier with more iterations ? $\endgroup$
    – R_Moose
    Mar 14, 2019 at 23:16
  • $\begingroup$ @R_Moose total improvement at each iteration is not guaranteed since average accuracy before iteration 5 could be 72 but at iteration 5 we could get an classifier with accuracy 60. But over 50 is guaranteed. $\endgroup$
    – Esmailian
    Mar 15, 2019 at 7:40
  • $\begingroup$ @R_Moose to complete my comment, the training error of AdaBoost decreases exponentially by each iteration but in probability, not surely. Meaning there is a small probability that it fails to decrease as I gave an example. $\endgroup$
    – Esmailian
    Mar 15, 2019 at 20:46
2
$\begingroup$

Adaboost is a boosting algorithm. Every boosting algorithm has the following idea -

  • We combine many weak learners by some means, here a weak learner is an algorithm which is just better than chance model.

Adaboost helps tweak the subsequent weak learners in favour of those instances misclassified by previous classifiers. If at each iteration of tree depending on how the data was sampled ( weights ) it's almost difficult to get something that's worse than a weak learner. I would say that something worse than weak is a dumb classifier which just predicts +1 label ( at the start of the problem ) irrespective of anything.

Now depending on iteration your random chance classifier initially started with a 50% accuracy but it might change and accordingly, your individual weak learner might get worse accuracy than 50% but it should always be better than random chance. If not then your model is just a fluke nothing else.

$\endgroup$

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.