Bayes classifier

In statistical classification, the Bayes classifier is the classifier having the smallest probability of misclassification of all classifiers using the same set of features.

Definition

Suppose a pair $(X,Y)$ takes values in ${\mathbb{ℝ}}^d\times \{1,2,\dots ,K\}$, where $Y$ is the class label of an element whose features are given by $X$. Assume that the conditional distribution of X, given that the label Y takes the value r is given by

$(X\mid Y=r)\sim P_r$ for $r=1,2,\dots ,K$

where "$\sim$" means "is distributed as", and where $P_r$ denotes a probability distribution.

A classifier is a rule that assigns to an observation X=x a guess or estimate of what the unobserved label Y=r actually was. In theoretical terms, a classifier is a measurable function $C:{\mathbb{ℝ}}^d\to \{1,2,\dots ,K\}$, with the interpretation that C classifies the point x to the class C(x). The probability of misclassification, or risk, of a classifier C is defined as

${ℛ}(C)=\mathrm{P}\{C(X)\ne Y\}.$

The Bayes classifier is

$C^{\text{Bayes}}(x)=\underset{r\in \{1,2,\dots ,K\}}{\mathrm{argmax}}\mathrm{P}(Y=r\mid X=x).$

In practice, as in most of statistics, the difficulties and subtleties are associated with modeling the probability distributions effectively—in this case, $\mathrm{P}(Y=r\mid X=x)$. The Bayes classifier is a useful benchmark in statistical classification.

The excess risk of a general classifier $C$ (possibly depending on some training data) is defined as ${ℛ}(C)-{ℛ}(C^{\text{Bayes}}).$ Thus this non-negative quantity is important for assessing the performance of different classification techniques. A classifier is said to be consistent if the excess risk converges to zero as the size of the training data set tends to infinity.

Considering the components $x_i$ of $x$ to be mutually independent, we get the naive bayes classifier, where $C^{\text{Bayes}}(x)=\underset{r\in \{1,2,\dots ,K\}}{\mathrm{argmax}}\mathrm{P}(Y=r)\prod _{i=1}^d{P}_r(x_i).$

Properties

Proof that the Bayes classifier is optimal and Bayes error rate is minimal proceeds as follows.

Define the variables: Risk $R(h)$, Bayes risk $R^{*}$, all possible classes to which the points can be classified $Y=\{0,1\}$. Let the posterior probability of a point belonging to class 1 be $\eta (x)=Pr(Y=1|X=x)$. Define the classifier ${{𝒽}}^{*}$as

${{𝒽}}^{*}(x)=\{\begin{array}{ll}1& \text{if }\eta (x)⩾0.5,\\ 0& \text{otherwise.}\end{array}$

Then we have the following results:

(a) $R(h^{*})=R^{*}$, i.e. $h^{*}$ is a Bayes classifier,

(b) For any classifier $h$, the excess risk satisfies $R(h)-R^{*}=2{\mathbb{𝔼}}_X[|\eta (x)-0.5|\cdot {\mathbb{𝕀}}_{\{h(X)\ne h^{*}(X)\}}]$

(c) $R^{*}={\mathbb{𝔼}}_X[\min (\eta (X),1-\eta (X))]$

(d) $R^{*}=\frac{1}{2}-\frac{1}{2}\mathbb{𝔼}[|2\eta (X)-1|]$

Proof of (a): For any classifier $h$, we have

$R(h)={\mathbb{𝔼}}_{XY}\left[{\mathbb{𝕀}}_{\{h(X)\ne Y\}}\right]$

$={\mathbb{𝔼}}_X{\mathbb{𝔼}}_{Y|X}[{\mathbb{𝕀}}_{\{h(X)\ne Y\}}]$ (due to Fubini's theorem)

$={\mathbb{𝔼}}_X[\eta (X){\mathbb{𝕀}}_{\{h(X)=0\}}+(1-\eta (X)){\mathbb{𝕀}}_{\{h(X)=1\}}]$

Notice that $R(h)$ is minimised by taking $\mathrm{\forall }x\in X$,

$h(x)=\{\begin{array}{ll}1& \text{if }\eta (x)⩾1-\eta (x),\\ 0& \text{otherwise.}\end{array}$

Therefore the minimum possible risk is the Bayes risk, $R^{*}=R(h^{*})$.

Proof of (b):

$\begin{array}{rl}R(h)-R^{*}& =R(h)-R(h^{*})\\ & ={\mathbb{𝔼}}_X[\eta (X){\mathbb{𝕀}}_{\{h(X)=0\}}+(1-\eta (X)){\mathbb{𝕀}}_{\{h(X)=1\}}-\eta (X){\mathbb{𝕀}}_{\{h^{*}(X)=0\}}-(1-\eta (X)){\mathbb{𝕀}}_{\{h^{*}(X)=1\}}]\\ & ={\mathbb{𝔼}}_X[|2\eta (X)-1|{\mathbb{𝕀}}_{\{h(X)\ne h^{*}(X)\}}]\\ & =2{\mathbb{𝔼}}_X[|\eta (X)-0.5|{\mathbb{𝕀}}_{\{h(X)\ne h^{*}(X)\}}]\end{array}$

Proof of (c):

$\begin{array}{rl}R(h^{*})& ={\mathbb{𝔼}}_X[\eta (X){\mathbb{𝕀}}_{\{h^{*}(X)=0\}}+(1-\eta (X)){\mathbb{𝕀}}_{\{h*(X)=1\}}]\\ & ={\mathbb{𝔼}}_X[\min (\eta (X),1-\eta (X))]\end{array}$

Proof of (d):

$\begin{array}{rl}R(h^{*})& ={\mathbb{𝔼}}_X[\min (\eta (X),1-\eta (X))]\\ & =\frac{1}{2}-{\mathbb{𝔼}}_X[\max (\eta (X)-1/2,1/2-\eta (X))]\\ & =\frac{1}{2}-\frac{1}{2}\mathbb{𝔼}[|2\eta (X)-1|]\end{array}$

General case

The general case that the Bayes classifier minimises classification error when each element can belong to either of n categories proceeds by towering expectations as follows.

$\begin{array}{rl}{\mathbb{𝔼}}_Y({\mathbb{𝕀}}_{\{y\ne \hat{y}\}})& ={\mathbb{𝔼}}_X{\mathbb{𝔼}}_{Y|X}({\mathbb{𝕀}}_{\{y\ne \hat{y}\}}|X=x)\\ & =\mathbb{𝔼}[Pr(Y=1|X=x){\mathbb{𝕀}}_{\{\hat{y}=2,3,\dots ,n\}}+Pr(Y=2|X=x){\mathbb{𝕀}}_{\{\hat{y}=1,3,\dots ,n\}}+\dots +Pr(Y=n|X=x){\mathbb{𝕀}}_{\{\hat{y}=1,2,3,\dots ,n-1\}}]\end{array}$

This is minimised by simultaneously minimizing all the terms of the expectation using the classifier$h(x)=k,\arg \underset{k}{\max }Pr(Y=k|X=x)$

for each observation x.

See also

• Naive Bayes classifier