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

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

Определение

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

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

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

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

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

Считая компоненты взаимно независимыми, получаем наивный байесовский классификатор , где $x_{i}$ $x$ $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 будет . Определим классификатор как $R(h)$ $R^{*}$ $Y=\{0,1\}$ $\eta (x)=Pr(Y=1|X=x)$ ${\mathcal {h}}^{*}$ ${\mathcal {h}}^{*}(x)={\begin{cases}1&{\text{if }}\eta (x)\geqslant 0.5,\\0&{\text{otherwise.}}\end{cases}}$

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

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

Доказательство (а): Для любого классификатора мы имеем, где вторая строка была выведена с помощью теоремы Фубини $h$ ${\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}}$

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

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

Доказательство (б): ${\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): ${\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): ${\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 категорий, реализуется путем нарастающих ожиданий следующим образом. ${\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 . $h(x)=k,\quad \arg \max _{k}Pr(Y=k|X=x)$

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

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

Ссылки

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

[PTPR-1] Деврой, Л.; Дьерфи Л. и Лугоши Г. (1996). Вероятностная теория распознавания образов . Спрингер. ISBN 0-3879-4618-7.

[2] Фараго, А.; Лугоши, Г. (1993). «Сильная универсальная согласованность классификаторов нейронных сетей». Труды IEEE по теории информации . 39 (4): 1146–1151. doi :10.1109/18.243433.