独立弱分类器投票有效性证明：多数投票正确率优于单分类器

Let's break down this problem step by step. We have $m$ independent binary classifiers, each with a correct classification probability $p > 0.5$, and we want to show that using majority voting gives us a higher correct probability $q > p$. We'll also connect this to the binomial CDF condition mentioned.

Key Setup #

Let $X$ be the number of classifiers that make a correct prediction. Since each classifier is independent, $X$ follows a binomial distribution: $X \sim \text{Binomial}(m, p)$.

The majority vote is correct if:

• For odd $m = 2t+1$: At least $t+1$ classifiers are correct (i.e., $X \geq t+1$)
• For even $m = 2t$: Strictly more than half are correct (i.e., $X \geq t+1$; ties are considered incorrect here)

In both cases, the probability of correct majority vote is:
$$q = 1 - \text{CDF}\left(\frac{m}{2}, m, p\right)$$
where $\text{CDF}(k, m, p)$ is the cumulative distribution function of the binomial distribution, representing $P(X \leq k)$.

Equivalence to the CDF Condition #

We need to show $q > p$. Substitute $q$ from above:
$$1 - \text{CDF}\left(\frac{m}{2}, m, p\right) > p$$
Rearranging terms gives exactly the condition we need to prove:
$$\text{CDF}\left(\frac{m}{2}, m, p\right) < 1 - p$$
So proving $q > p$ is equivalent to showing this CDF inequality holds.

Proving $q > p$ (Induction Approach) #

We'll focus on odd $m$ first (even $m$ can have ambiguous ties, e.g., $m=2$ gives $q=p^2 < p$ which doesn't satisfy the condition—odd $m$ ensures a clear majority).

Base Case: $m=3$ #

For $m=3$, the majority requires at least 2 correct classifiers:
$$q = P(X=2) + P(X=3) = 3p^2(1-p) + p^3 = 3p^2 - 2p^3$$
Compute $q - p$:
$$q - p = 3p^2 - 2p^3 - p = p(-2p^2 + 3p -1) = p(-(2p-1)(p-1))$$
Since $p > 0.5$, $2p-1 > 0$ and $p-1 < 0$. The product $-(2p-1)(p-1)$ is positive, so $q - p > 0$ → $q > p$.

Inductive Step #

Assume for $m=2t+1$, $q_m > p$. Now consider $m' = 2(t+1)+1 = 2t+3$.

The majority vote probability for $m'$ can be written using the recurrence of binomial probabilities:
$$q_{m'} = q_m + \binom{2t+1}{t} p^{t+1}(1-p){t+1}(2p-1)$$
Since $p >0.5$, $2p-1 >0$, and all other terms are positive, the added term is positive. Thus:
$$q_{m'} = q_m + \text{positive value} > q_m > p$$
The inductive step holds.

Intuitive Explanation #

Each classifier has a bias towards correctness ($p>0.5$). When combining them via majority vote, the "correct" votes are more likely to outnumber incorrect ones. The binomial distribution is skewed to the right (since $p>0.5$), so the probability of having more than half correct predictions is higher than the individual classifier accuracy.

内容的提问来源于stack exchange，提问作者Hanan Shteingart