Байесовский классификатор

В статистической классификации байесовский классификатор — это классификатор, имеющий наименьшую вероятность неправильной классификации среди всех классификаторов, использующих тот же набор признаков. ^[1]

Определение

Предположим, что пара принимает значения в , где — метка класса элемента, характеристики которого заданы как . Предположим, что условное распределение X , учитывая, что метка Y принимает значение r , задается как , где " " означает "распределен как", а где обозначает распределение вероятностей. ${\displaystyle (X,Y)}$ ${\displaystyle \mathbb {R} ^{d}\times \{1,2,\dots ,K\}}$ ${\displaystyle Y}$ ${\displaystyle X}$ $${\displaystyle (X\mid Y=r)\sim P_{r}\quad {\text{for}}\quad r=1,2,\dots ,K}$$ ${\displaystyle \sim }$ ${\displaystyle P_{r}}$

Классификатор — это правило, которое присваивает наблюдению X = x предположение или оценку того, какой на самом деле была ненаблюдаемая метка Y = r . В теоретических терминах классификатор — это измеримая функция , с интерпретацией, что C классифицирует точку x в класс C ( x ). Вероятность неправильной классификации, или риск , классификатора C определяется как ${\displaystyle C:\mathbb {R} ^{d}\to \{1,2,\dots ,K\}}$ $${\displaystyle {\mathcal {R}}(C)=\operatorname {P} \{C(X)\neq Y\}.}$$

Байесовский классификатор — это $${\displaystyle C^{\text{Bayes}}(x)={\underset {r\in \{1,2,\dots ,K\}}{\operatorname {argmax} }}\operatorname {P} (Y=r\mid X=x).}$$

На практике, как и в большинстве статистических исследований, трудности и тонкости связаны с эффективным моделированием распределений вероятностей — в данном случае. Классификатор Байеса является полезным эталоном в статистической классификации . ${\displaystyle \operatorname {P} (Y=r\mid X=x)}$

Избыточный риск общего классификатора (возможно, зависящий от некоторых обучающих данных) определяется как Таким образом, эта неотрицательная величина важна для оценки производительности различных методов классификации. Классификатор считается согласованным , если избыточный риск стремится к нулю, когда размер обучающего набора данных стремится к бесконечности. ^[2] ${\displaystyle C}$ ${\displaystyle {\mathcal {R}}(C)-{\mathcal {R}}(C^{\text{Bayes}}).}$

Считая компоненты взаимно независимыми, получаем наивный байесовский классификатор , где ${\displaystyle x_{i}}$ ${\displaystyle x}$ $${\displaystyle C^{\text{Bayes}}(x)={\underset {r\in \{1,2,\dots ,K\}}{\operatorname {argmax} }}\operatorname {P} (Y=r)\prod _{i=1}^{d}P_{r}(x_{i}).}$$

Характеристики

Доказательство того, что байесовский классификатор оптимален и коэффициент байесовой ошибки минимален, выполняется следующим образом.

Определим переменные: Риск , Байесовский риск , все возможные классы, к которым могут быть отнесены точки . Пусть апостериорная вероятность принадлежности точки к классу 1 будет . Определим классификатор как ${\displaystyle R(h)}$ ${\displaystyle R^{*}}$ ${\displaystyle Y=\{0,1\}}$ ${\displaystyle \eta (x)=Pr(Y=1|X=x)}$ ${\displaystyle {\mathcal {h}}^{*}}$ $${\displaystyle {\mathcal {h}}^{*}(x)={\begin{cases}1&{\text{if }}\eta (x)\geqslant 0.5,\\0&{\text{otherwise.}}\end{cases}}}$$

Тогда мы имеем следующие результаты:

1. ${\displaystyle R(h^{*})=R^{*}}$, т.е. является байесовским классификатором, ${\displaystyle h^{*}}$
2. Для любого классификатора избыточный риск удовлетворяет ${\displaystyle h}$ ${\displaystyle R(h)-R^{*}=2\mathbb {E} _{X}\left[|\eta (x)-0.5|\cdot \mathbb {I} _{\left\{h(X)\neq h^{*}(X)\right\}}\right]}$
3. ${\displaystyle R^{*}=\mathbb {E} _{X}\left[\min(\eta (X),1-\eta (X))\right]}$
4. ${\displaystyle R^{*}={\frac {1}{2}}-{\frac {1}{2}}\mathbb {E} [|2\eta (X)-1|]}$

Доказательство (а): Для любого классификатора мы имеем, где вторая строка была выведена с помощью теоремы Фубини ${\displaystyle h}$ $${\displaystyle {\begin{aligned}R(h)&=\mathbb {E} _{XY}\left[\mathbb {I} _{\left\{h(X)\neq Y\right\}}\right]\\&=\mathbb {E} _{X}\mathbb {E} _{Y|X}[\mathbb {I} _{\left\{h(X)\neq Y\right\}}]\\&=\mathbb {E} _{X}[\eta (X)\mathbb {I} _{\left\{h(X)=0\right\}}+(1-\eta (X))\mathbb {I} _{\left\{h(X)=1\right\}}]\end{aligned}}}$$

Обратите внимание, что минимизируется путем принятия , ${\displaystyle R(h)}$ ${\displaystyle \forall x\in X}$ $${\displaystyle h(x)={\begin{cases}1&{\text{if }}\eta (x)\geqslant 1-\eta (x),\\0&{\text{otherwise.}}\end{cases}}}$$

Поэтому минимально возможный риск — это байесовский риск . ${\displaystyle R^{*}=R(h^{*})}$

Доказательство (б): $${\displaystyle {\begin{aligned}R(h)-R^{*}&=R(h)-R(h^{*})\\&=\mathbb {E} _{X}[\eta (X)\mathbb {I} _{\left\{h(X)=0\right\}}+(1-\eta (X))\mathbb {I} _{\left\{h(X)=1\right\}}-\eta (X)\mathbb {I} _{\left\{h^{*}(X)=0\right\}}-(1-\eta (X))\mathbb {I} _{\left\{h^{*}(X)=1\right\}}]\\&=\mathbb {E} _{X}[|2\eta (X)-1|\mathbb {I} _{\left\{h(X)\neq h^{*}(X)\right\}}]\\&=2\mathbb {E} _{X}[|\eta (X)-0.5|\mathbb {I} _{\left\{h(X)\neq h^{*}(X)\right\}}]\end{aligned}}}$$

Доказательство (c): $${\displaystyle {\begin{aligned}R(h^{*})&=\mathbb {E} _{X}[\eta (X)\mathbb {I} _{\left\{h^{*}(X)=0\right\}}+(1-\eta (X))\mathbb {I} _{\left\{h*(X)=1\right\}}]\\&=\mathbb {E} _{X}[\min(\eta (X),1-\eta (X))]\end{aligned}}}$$

Доказательство (d): $${\displaystyle {\begin{aligned}R(h^{*})&=\mathbb {E} _{X}[\min(\eta (X),1-\eta (X))]\\&={\frac {1}{2}}-\mathbb {E} _{X}[\max(\eta (X)-1/2,1/2-\eta (X))]\\&={\frac {1}{2}}-{\frac {1}{2}}\mathbb {E} [|2\eta (X)-1|]\end{aligned}}}$$

Общий случай

Общий случай, когда классификатор Байеса минимизирует ошибку классификации, когда каждый элемент может принадлежать к любой из n категорий, реализуется путем нарастающих ожиданий следующим образом. $${\displaystyle {\begin{aligned}\mathbb {E} _{Y}(\mathbb {I} _{\{y\neq {\hat {y}}\}})&=\mathbb {E} _{X}\mathbb {E} _{Y|X}\left(\mathbb {I} _{\{y\neq {\hat {y}}\}}|X=x\right)\\&=\mathbb {E} \left[\Pr(Y=1|X=x)\mathbb {I} _{\{{\hat {y}}=2,3,\dots ,n\}}+\Pr(Y=2|X=x)\mathbb {I} _{\{{\hat {y}}=1,3,\dots ,n\}}+\dots +\Pr(Y=n|X=x)\mathbb {I} _{\{{\hat {y}}=1,2,3,\dots ,n-1\}}\right]\end{aligned}}}$$

Это минимизируется путем одновременной минимизации всех членов ожидания с использованием классификатора для каждого наблюдения x . ${\displaystyle h(x)=k,\quad \arg \max _{k}Pr(Y=k|X=x)}$

Смотрите также

• Наивный байесовский классификатор

Ссылки

1. Деврой, Л.; Дьерфи Л. и Лугоши Г. (1996). Вероятностная теория распознавания образов . Спрингер. ISBN 0-3879-4618-7.
2. Фараго, А.; Лугоши, Г. (1993). «Сильная универсальная согласованность классификаторов нейронных сетей». Труды IEEE по теории информации . 39 (4): 1146–1151. doi :10.1109/18.243433.