0
$\begingroup$

I have a homework question about a machine-learning algorithm that uses ensemble learning with simple majority voting. Assuming we have K hypotheses, each with an error ɛ, the question asks us to calculate the formula for the error of the ensemble algorithm. The errors are independent.

I have always been terrible with probability, but I decided to figure this out and I went back and looked at some basics. I used the simple binomial distribution to figure out the probability that exactly m (where m is floor(k / 2) + 1) hypotheses of of K making an error is (K choose m)(ɛ)^m(1 - ɛ)^(K - m). I thought that this would be the answer.

But the correct answer seems to involve adding all the probability of errors. That it, it is the probability of the error of exactly m hypotheses being wrong, plus the probability of m + 1 hypotheses being wrong, and so on until K hypotheses. I don't understand why the all these probabilities need to be added up. Don't we just need the probability that exactly m hypotheses are wrong? Why do we need to add up all the other probabilities of errors?

EDIT Ok I got it. It's because it's majority voting, at least m have to be wrong, but at most K have to be wrong. So we have to add them up.

$\endgroup$
  • $\begingroup$ I'm not sure I follow your edit at the end, but if you believe you have an answer to your question, could you post it as an answer? $\endgroup$ – Glen_b -Reinstate Monica Mar 1 '15 at 4:27
  • $\begingroup$ I will add my answer! $\endgroup$ – sucksatprobability Mar 5 '15 at 0:59
1
$\begingroup$

The reason we have to consider the other probabilities is because when it is majority voting, we need a minimum of floor(K / 2) + 1 hypotheses making the wrong prediction, to have the ensemble make a wrong prediction. But if we want the probability of an error, we want to look at all the cases where the ensemble can make an error. A simple majority where floor(K / 2) + 1 are wrong is just one case. We can have the cases where floor(K / 2) + 2 are wrong and so on until all K are wrong.

This is why we have to add up all the probabilities.

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