Bayes classifier

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

Definition

Suppose a pair $(X,Y)$ takes values in ${ℝ}^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\text{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:{ℝ}^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}{cc}1& \text{if }\eta (x)⩾0.5,\\ 0& \text{otherwise.}\end{array}$$

Then we have the following results:

1. $R(h^{*})=R^{*}$, i.e. $h^{*}$ is a Bayes classifier,
2. For any classifier $h$, the excess risk satisfies $R(h)-R^{*}=2{𝔼}_X[|\eta (x)-0.5|\cdot {𝕀}_{\{h(X)\ne h^{*}(X)\}}]$
3. $R^{*}={𝔼}_X[\min (\eta (X),1-\eta (X))]$
4. $R^{*}=\frac{1}{2}-\frac{1}{2}𝔼[|2\eta (X)-1|]$

Proof of (a): For any classifier $h$, we have $$\begin{array}{cc}R(h)& ={𝔼}_{XY}\left[{𝕀}_{\{h(X)\ne Y\}}\right]\\ & ={𝔼}_X{𝔼}_{Y|X}[{𝕀}_{\{h(X)\ne Y\}}]\\ & ={𝔼}_X[\eta (X){𝕀}_{\{h(X)=0\}}+(1-\eta (X)){𝕀}_{\{h(X)=1\}}]\end{array}$$ where the second line was derived through Fubini's theorem

Notice that $R(h)$ is minimised by taking $\mathrm{\forall }x\in X$, $$h(x)=\{\begin{array}{cc}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}{cc}R(h)-R^{*}& =R(h)-R(h^{*})\\ & ={𝔼}_X[\eta (X){𝕀}_{\{h(X)=0\}}+(1-\eta (X)){𝕀}_{\{h(X)=1\}}-\eta (X){𝕀}_{\{h^{*}(X)=0\}}-(1-\eta (X)){𝕀}_{\{h^{*}(X)=1\}}]\\ & ={𝔼}_X[|2\eta (X)-1|{𝕀}_{\{h(X)\ne h^{*}(X)\}}]\\ & =2{𝔼}_X[|\eta (X)-0.5|{𝕀}_{\{h(X)\ne h^{*}(X)\}}]\end{array}$$

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

Proof of (d): $$\begin{array}{cc}R(h^{*})& ={𝔼}_X[\min (\eta (X),1-\eta (X))]\\ & =\frac{1}{2}-{𝔼}_X[\max (\eta (X)-1/2,1/2-\eta (X))]\\ & =\frac{1}{2}-\frac{1}{2}𝔼[|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}{cc}{𝔼}_Y({𝕀}_{\{y\ne \hat{y}\}})& ={𝔼}_X{𝔼}_{Y|X}({𝕀}_{\{y\ne \hat{y}\}}|X=x)\\ & =𝔼[\mathrm{Pr}(Y=1|X=x){𝕀}_{\{\hat{y}=2,3,\dots ,n\}}+\mathrm{Pr}(Y=2|X=x){𝕀}_{\{\hat{y}=1,3,\dots ,n\}}+\dots +\mathrm{Pr}(Y=n|X=x){𝕀}_{\{\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