Bayes classifier

Short description: Classification algorithm in 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 ${\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\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:{\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:

1. $R(h^{*})=R^{*}$, i.e. $h^{*}$ is a Bayes classifier,
2. 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)\}}]$
3. $R^{*}={\mathbb{𝔼}}_X[\min (\eta (X),1-\eta (X))]$
4. $R^{*}=\frac{1}{2}-\frac{1}{2}\mathbb{𝔼}[|2\eta (X)-1|]$

Proof of (a): For any classifier $h$, we have $$\begin{array}{rl}R(h)& ={\mathbb{𝔼}}_{XY}\left[{\mathbb{𝕀}}_{\{h(X)\ne Y\}}\right]\\ & ={\mathbb{𝔼}}_X{\mathbb{𝔼}}_{Y|X}[{\mathbb{𝕀}}_{\{h(X)\ne Y\}}]\\ & ={\mathbb{𝔼}}_X[\eta (X){\mathbb{𝕀}}_{\{h(X)=0\}}+(1-\eta (X)){\mathbb{𝕀}}_{\{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}{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{𝔼}[\mathrm{Pr}(Y=1|X=x){\mathbb{𝕀}}_{\{\hat{y}=2,3,\dots ,n\}}+\mathrm{Pr}(Y=2|X=x){\mathbb{𝕀}}_{\{\hat{y}=1,3,\dots ,n\}}+\dots +\mathrm{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