2
$\begingroup$

In AdaBoost, the weight of a weak learner $\alpha$ is set as

$\alpha_t = \frac{1}{2}ln\frac{1-e_t}{e_t}$

under the assumptions that

$e_t = \frac{1}{2} - \gamma$ and $\gamma > 0$

Therefore:

$\alpha_t = 0$ for $e_t \geq 0.5$

So what happens in the case of the XOR problem and AdaBoost with Decision Stumps?

No weak learner can achieve an error rate better (i.e. lower) than $0.5$ in the first round, hence it should be $\alpha_t = 0$ for all $t$, making AdaBoost (with decision stumps) fail to solve the XOR problem.

However, it seems odd that a highly versatile classifier such as AdaBoost fails to solve this rather simple problem due to the fact that this assumption is violated in the first round of boosting.

Does AdaBoost with decision stumps really fail it? If yes, what are extensions to overcome this problem? I have seen images of AdaBoost correctly solving the XOR problem, however, I believe that these were modified forms of AdaBoost.

$\endgroup$
3
$\begingroup$

To develop the point made by Andreas:

No weak learner can achieve an error rate better (i.e. lower) than 0.5 in the first round, hence it should be αt=0 for all t, making AdaBoost (with decision stumps) fail to solve the XOR problem.

Indeed in this particular (degenerate) case the AdaBoost algorithm using the following settings will fail:

  • Estimator = decision tree
  • Max_depth = 1
  • Max_leaf_nodes 2

The point is that Adaboost is not limited to Decision trees, and can be used together with many other weak estimators such as Logistic Regression Support Vector Machines etc..

In general, AdaBoost is often used with Decision Trees, in which case the tree parameters are adjusted to the problem at hand. You could, in this example, increase the maximum depth to 2 in which case the issue disappears.

In Sklearn, the default estimator is a Decision tree with unlimited max depth and 2 leaf_nodes

$\endgroup$
0
$\begingroup$

Your premise that a weak learner cannot do better than 0.5(i.e random) is incorrect. Yes, a stump cannot perform better than 0.5 in this case. However, you can use any other linear classifier, e.g perceptron to classify 3/4 points correctly(which in the case of the XOR problem is just the next step from 2/4).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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