Bayes classifier

Template:Short description Template:Bayesian statistics 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^{\ast }$, 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 ${𝒽}^{\ast }$as $${𝒽}^{\ast }(x)=\{\begin{array}{cc}1& \text{if }\eta (x)⩾0.5,\\ 0& \text{otherwise.}\end{array}$$

Then we have the following results: Template:Ordered list

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^{\ast }=R(h^{\ast })$.

Proof of (b): $$\begin{array}{cc}R(h)-R^{\ast }& =R(h)-R(h^{\ast })\\ & ={𝔼}_X[\eta (X){𝕀}_{\{h(X)=0\}}+(1-\eta (X)){𝕀}_{\{h(X)=1\}}-\eta (X){𝕀}_{\{h^{\ast }(X)=0\}}-(1-\eta (X)){𝕀}_{\{h^{\ast }(X)=1\}}]\\ & ={𝔼}_X[|2\eta (X)-1|{𝕀}_{\{h(X)\ne h^{\ast }(X)\}}]\\ & =2{𝔼}_X[|\eta (X)-0.5|{𝕀}_{\{h(X)\ne h^{\ast }(X)\}}]\end{array}$$

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

Proof of (d): $$\begin{array}{cc}R(h^{\ast })& ={𝔼}_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)\\ & =𝔼[Pr(Y=1|X=x){𝕀}_{\{\hat{y}=2,3,\dots ,n\}}+Pr(Y=2|X=x){𝕀}_{\{\hat{y}=1,3,\dots ,n\}}+\dots +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