Ансамблирование простым голосованием: предельный случай

Эта статья плохо повышает индекс цитируемости авторов других статей этой вики. Вы можете помочь, добавив навигационные ссылки.

Эта статья нуждается в структуризации! Вы можете помочь, кластеризовав информацию в этой статье. Возможно, следует разбить её на разделы или на несколько статей.

Рассмотрим задачу бинарной классификации. Пусть $f_i(x), i = \overline{1,M}$ — бинарные классификаторы, решающие данную задачу.

Введём случайные величины $\xi_i = \mathbf{I} [ f_i(x)$ ошибся $] \sim Bernoulli(p), p \in (0, 1)$ (допустим, смогли задать соответствующее вероятностное пространство). $\mathbb{E}[\xi_i] = p, \mathbb{D}[\xi_i] = p\cdot (1 - p)$. Пусть $\xi_i, i = \overline{1, M}$ независимые. Введём $\overline{\xi} = \frac{1}{M}\cdot\sum\limits_{i = 1}^{M}\xi_i$, тогда $\mathbb{E}[\overline{\xi}] = p, \mathbb{D}[\overline{\xi}] = \frac{p\cdot (1 - p)}{M}$.

Пусть $F(x)$ ансамбль из $\{f_i(x)\}_{i = 1}^{M}$, построенный по принципу простого голосования (голосование по большинству). Тогда нетрудно заметить, что $F(x)$ ошибается тогда и только тогда, когда $\overline{\xi} > 0.5$. Вероятность ошибки $F(x)$ равна $\sum\limits_{i = \lfloor \frac{M}{2} \rfloor + 1}^{M} \frac{M!}{(M - i)!\cdot i!}\cdot p^i\cdot (1 - p)^{(M - i)}$.

Рассмотрим случай сколь угодно большого числа независимых классификаторов $f_i (x)$. При стремлении $M$ к бесконечности значение $\mathbb{D}[\overline{\xi}]$ будет стремиться к нулю, то есть распределение $\overline{\xi}$ будет стремиться к вырожденному. Так как $\mathbb{E}[\overline{\xi}] = p$, то при бесконечном увеличении $M$ вероятность ошибки $F(x)$ будет стремиться к нулю, если $p < 0.5$.

Таким образом, при построении ансамбля простым голосованием счётного числа независимых классификаторов возможно построение идеального классификатора.