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

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

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

Рассмотрим задачу бинарной классификации. Пусть $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$.

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