bayes classifier

Suppose a pair $(X,Y)$ takes values in $\backslash mathbb\{R\}^d\; \backslash times\; \backslash \{1,2,\backslash dots,K\backslash \}$, 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\backslash mid\; Y=r)\; \backslash sim\; P\_r\; \backslash quad\; \backslash text\{for\}\; \backslash quad\; r=1,2,\backslash dots,K$$

where "$\backslash 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:\; \backslash mathbb\{R\}^d\; \backslash to\; \backslash \{1,2,\backslash dots,K\backslash \}$, 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

$$\backslash mathcal\{R\}(C)\; =\; \backslash operatorname\{P\}\backslash \{C(X)\; \backslash neq\; Y\backslash \}.$$

The Bayes classifier is

$$C^\backslash text\{Bayes\}(x)\; =\; \backslash underset\{r\; \backslash in\; \backslash \{1,2,\backslash dots,\; K\backslash \}\}\{\backslash operatorname\{argmax\}\}\; \backslash operatorname\{P\}(Y=r\; \backslash 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, $\backslash operatorname\{P\}(Y=r\; \backslash 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 $\backslash mathcal\{R\}(C)\; -\; \backslash mathcal\{R\}(C^\backslash 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.{{Cite journal|url=https://dl.acm.org/doi/abs/10.1109/18.243433 | doi = 10.1109/18.243433 | title = Strong universal consistency of neural network classifiers|year = 1993|last1 = Farago|first1 = A.|last2 = Lugosi|first2 = G.|journal = IEEE Transactions on Information Theory|volume = 39|issue = 4|pages = 1146–1151|url-access = subscription}}

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

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\; =\; \backslash \{0,1\backslash \}$. Let the posterior probability of a point belonging to class 1 be $\backslash eta(x)=Pr(Y=1|X=x)$. Define the classifier $\backslash mathcal\{h\}^*$as

Then we have the following results:

{{ordered list | list-style-type = lower-alpha

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

| 2 = For any classifier $h$, the excess risk satisfies $R(h)-R^*=2\backslash mathbb\{E\}\_X\backslash left[|\backslash eta(x)-0.5|\backslash cdot\; \backslash mathbb\{I\}\_\{\backslash left\backslash \{h(X)\backslash ne\; h^*(X)\backslash right\backslash \}\}\backslash right]$

| 3 = $R^*\; =\; \backslash mathbb\{E\}\_X\backslash left[\backslash min(\backslash eta(X),1-\backslash eta(X))\backslash right]$

| 4 = $R^*\; =\; \backslash frac\{1\}\{2\}\; -\; \backslash frac\{1\}\{2\}\backslash mathbb\; E\; [|2\backslash eta(X)\; -\; 1|]$

}}

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

$$\backslash begin\{align\}$$

R(h) &= \mathbb{E}_{XY}\left[ \mathbb{I}_{ \left\{h(X)\ne Y \right\}} \right] \\

&=\mathbb{E}_X\mathbb{E}_{Y|X}[\mathbb{I}_{ \left\{h(X)\ne 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{align}

where the second line was derived through Fubini's theorem

Notice that $R(h)$ is minimised by taking $\backslash forall\; x\backslash in\; X$,

$$h(x)\; =\; \backslash begin\{cases\}$$

1&\text{if }\eta(x)\geqslant 1-\eta(x),\\

0&\text{otherwise.}

\end{cases}

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

Proof of (b):

$$\backslash 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)\ne h^*(X)\right\}}]\\

&= 2\mathbb{E}_X[|\eta(X)-0.5|\mathbb{I}_{\left\{h(X)\ne h^*(X)\right\}}]

\end{aligned}

Proof of (c):

$$\backslash 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}

Proof of (d):

$$\backslash 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}

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.

$$\backslash begin\{align\}$$

\mathbb{E}_Y(\mathbb{I}_{\{y\ne \hat{y}\}}) &= \mathbb{E}_X\mathbb{E}_{Y|X}\left(\mathbb{I}_{\{y\ne \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{align}

This is minimised by simultaneously minimizing all the terms of the expectation using the classifier $h(x)\; =\; k,\backslash quad\; \backslash arg\backslash max\_\{k\}Pr(Y=k|X=x)$ for each observation x.

• Naive Bayes classifier

{{reflist|1}}

Category:Bayesian statistics

Category:Statistical classification