I know that with some classification algorithms, you can get higher accuracy if you use weak learners and have them vote. So if each weak learner has 55% accuracy, I can have all of them tell me the class they predict and take the more common class (in the case of binary classification). I'm trying to understand the math behind this.

Suppose I have two random variables X_1 and X_2 and I'm trying to predict a class Y. I'm told that P(Y=true | X_1=true) = 0.55 and P(Y=true | X_2=true) = 0.55. I think usually with this voting idea, I want my X_1 and X_2 to be independent. Otherwise, if they always vote the same way, I'll only get 55% accuracy.

1) How would I calculate my maximum classification accuracy if X_1 and X_2 are independent?

2) Is it possible for X_1 and X_2 to be independent and still have P(Y=true | X_1=true) = 0.55 P(Y=true | X_2=true) = 0.55? That is, aren't I learning something aboutX_2throughX_1's relationship withY`?



and take the more common class (in the case of binary classification). ... Suppose I have two random variables

It's unclear what a majority vote for two classifiers means, exactly (what if one indicates 1 and the other 0?) Furthermore, your 2) can be constructed in several ways, showing that your 1) is not well defined.

Consider the square $-0.5 < x_1 < 0.5, -0.5 < x_2 < 0.5$, and the square inside it$-d < x_1 < d, -d < x_2 < d$, for $d = {0.55 \over 2}$. Let $Y = 1$ if a point, chosen uniformly in the outer square, is in the inner square. Let $X_1$ be $-d < x_1 < d$, and $X_2$ be $-d < x_2 < d$. Then $$X_1 \perp X_2, \\P(Y=1|X_1) = 0.55 = P(Y_2|X_2),$$ and $$P(Y=1|X_1 = 1 = X_2) = 1.$$

enter image description here

Now consider a different case where $X_1 = 1$ is a deterministic RV, as is $X_2 = 1$. Let $Y = 1$ if $Z \sim U(0, 1)$ is less than 0.55, for some completely other, unrelated, $Z$. Then $X_1 \perp X_2$, because $P(X_1 = 1 | X_2 = 1) = P(X_1 = 1)$ and so forth. Note that in this case $$X_1 \perp X_2, \\ P(Y = 1 | X_1 = 1) = 0.55 = P(Y = 1 | X_2 = 1),$$ as before, but $$P(Y = 1 | X_1 = 1 = X_2) = 0.55.$$

  • $\begingroup$ how do you draw that graph? $\endgroup$
    – Haitao Du
    Feb 23 '18 at 14:33
  • $\begingroup$ @hxd1011 On draw.io $\endgroup$
    – Ami Tavory
    Feb 23 '18 at 14:46
  • 1
    $\begingroup$ Thanks for letting me know. It is very nice. (I usually use power point to draw) $\endgroup$
    – Haitao Du
    Feb 23 '18 at 14:49

To understand how weak classifiers interact it is important to understand what the numbers mean. The discussion is based on idealised situations, in real life there are confidence intervals associated with sampling. When I refer to probabilities I mean the true underlying probability, not an experimentally measured one.

At P = 0.5 100% of the prediction is random chance

At P = 1 0% of the prediction is random chance

In between these two extremes the random chance is 2 times 1-P

At P = 0.75 the prediction is right 50% time because the model is correct and 25% percent of the time it got lucky and 25% of the time unlucky.

So at P=0.55 there still 90% random variation unaccounted for by your model. Independent variations combine as the square root of the sum of squares (which is why mathematicians tend to work with variances which make this easier), so at 0.55 there is plenty of random variation to allow the two to have no interaction, therefore it is possible that both have p=0.55 and be independent as only 10% of the correct answers are due to the underlying model and these could be a different 10% in X1 and X2.

For two classifiers at P = 0.75 independence is guaranteed to break down. Here the model being appropriate accounts for exactly half the outcomes. Either they start to overlap or they will be mutually exclusive. Either way a correlation is unavoidable.

In between the probability of independence declines continuously as P increases. At P = 0.625 25% of the prediction is due to the underlying model, so while it is still possible for the two models to pick from different 25% of the dataset it is less likely than from different 10%s.

To answer questions

1) depends on how you decide ties. With 2 classifiers you will get draws each time.

2) basically the above is a long wind way of saying that it is possible both are independent and have a slight positive performance. But this can't be stretched too far.


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.