# Finding the error probability of an optimal bayes classifier analytically

I have two classes $\omega_1,\omega_2$ with equal prior probability $P(\omega_1)=P(\omega_2)=0.5$. And the points in 2D are distributed $\mathcal{N}(\mu_i,\Sigma), \mu_1=(0,0)^T, \mu_1=(4,4)^T, \Sigma=\biggl(\begin{matrix}2&-1\\-1&2\end{matrix}\biggr)$.

I got that the optimal bayes classifier is: $f(x_1,x_2)=\begin{cases}\omega_1&x_1+x_2\leq4\\\omega_2&else\end{cases}$

I want to calculate the error probability of that classifier analytically, I want to express it as a function of the cumulative distribution function of the standard normal distribution $\mathcal{N}(0,1)$.

There's a clue given in the question to turn the problem into a one-dimensional one using a rotation of the axis.

can someone tell me how can that be done?

• I think I made a mistake with the classifier, I think this is the naive bayes classifier, and not the optimal one, in this case how do I find the optimal classifier? Commented Dec 30, 2016 at 20:54
• I think you mean distributed and not "distrusted". If you have the two densities you have integrate the posterior distribution with the lower density since the rule would pick the class with the higher posterior density. Note that this will change when the densities cross. Commented Dec 31, 2016 at 0:25
• In the case of the normal distributions with the same variance the boundary of equal density is a line. Since you are integrating normal densities doing this analytically means doing it numerically. In your case if you did it right the line x1+x2=4 is that boundary. Commented Dec 31, 2016 at 0:37
• I know that I need to integrate the posterior distributions with the lower density, but the question I'm trying to solve wanted me to right down a closed formula using the CDF of a standard normal distribution. that's what I'm having difficulty with. If what I found is correct, what does a naive bayes classifier look like? what's the difference? Commented Dec 31, 2016 at 12:12
• I meant to say that in general integrating a normal distribution over a range of values does not yield a closed form expression. So I don't think it is possible unless your definition of closed form is different from mine. Do you consider an infinite eries a closed form? Commented Dec 31, 2016 at 17:36

Let $$(X,Y)$$ denote the observation, and suppose that the conditional distribution of $$(X,Y)$$ is bivariate normal: specifically if $$(X,Y)$$ is from Class I, then $$(X,Y) \sim \mathcal N((0,0), \Sigma)$$ while if if $$(X,Y)$$ is from Class II, then $$(X,Y) \sim \mathcal N((4,4), \Sigma)$$, where the covariance matrix $$\Sigma$$ is $$\begin{bmatrix}2&-1\\-1&2\end{bmatrix}$$.Both classes are equally likely, and so we don't have to worry about the prior probabilities of the two classes mucking up the comparisons of the conditional posterior distributions of $$(X,Y)$$ for the two classes to determine which is larger. Put another way. the optimal Bayes classifier compares the likelihood ratio $$\frac{f_2}{f_1}$$ to $$\frac{\pi_1}{\pi_2}$$ to determine the decision, but since $$\frac{\pi_1}{\pi_2} = 1$$, the optimal Bayes classifier is the same as the maximum-likelihood classifier.
The Naive Bayes classifier treats $$X$$ and $$Y$$ as independent random variables (even though they aren't in this instance) in which case the decision boundary is just the line $$x+y=4$$ in the $$x$$-$$y$$ plane. The classification is announced to be Class II if the point $$(X,Y)$$ lies above this line and Class I if $$(X,Y)$$ lies below this line.
The Optimal (nonNaive or Sophisticated?) Bayes classifier looks at the likelihood ratio \begin{align}\Lambda(x,y) = \frac{f_2}{f_1} &= \frac{\mathcal N((4,4), \Sigma)}{\mathcal N((0,0), \Sigma)}\\ &= \frac{\exp\left[-\frac 23\left(\frac{(x-4)^2}{2}+ \frac{(y-4)^2}{2}+\frac{(x-4)(y-4)}{2}\right)\right]}{\exp\left[-\frac 23\left(\frac{x^2}{2}+ \frac{y^2}{2}+\frac{xy}{2}\right)\right]}\\ &= \exp\left[-\frac 13\left(-8x+16-8y + 16 -4y-4x+16\right)\right]\\ &= \exp[4x+4y-16] \end{align} to determine for which values of $$(x,y)$$ does $$\Lambda(x,y)$$ exceed $$1$$ and arrives at the same conclusion as the Naive Bayes classifier and the maximum likelihood classifier:
If $$(X,Y)$$ lies above the line $$x+y=4$$, then announce that the observation $$(X,Y)$$ belongs to Class II; else announce that $$(X,Y)$$ belongs to Class I.
Finally, turning to the calculation of the error probability, note that when $$(X,Y)$$ is actually in Class I, an error occurs whenever $$(X,Y)$$ lies above the line $$x+y = 4$$. Now, when the observation actually belongs to Class I, $$X+Y$$ is a $$\mathcal N(0,2+2-2) = \mathcal N(0,2)$$ random variable and so $$P(X+Y>4\mid \text{I}) = 1 - P(X+Y \leq 4 \mid \text{I}) = 1 - \Phi\left(\frac{4}{\sqrt{2}}\right).$$ Similarly, $$(X,Y)$$ is actually in Class II, an error occurs whenever $$(X,Y)$$ lies below the line $$x+y = 4$$. Now, when the observation actually belongs to Class II, $$X+Y$$ is a $$\mathcal N(8,2+2-2) = \mathcal N(8,2)$$ random variable and so $$P(X+Y\leq 4 \mid \text{II}) = \Phi\left(\frac{4-8}{\sqrt{2}}\right) = \Phi\left(\frac{-4}{\sqrt{2}}\right).$$ While the two calculations seem to give different results, both these error probabilities are in fact the same (proof of this is left as an exercise for the bemused reader) and the unconditional or average error probability is also equal to $$\Phi\left(\frac{-4}{\sqrt{2}}\right).$$
Note that if your naïveté extends to computing the error probability of the Naive Bayes classifier while continuing to use the assumption that $$X$$ and $$Y$$ are independent normal random variables, then $$X+Y$$ would be a normal random variable of variance $$4$$ instead of variance $$2$$ and the error probability would work out to be $$\Phi\left(\frac{-4}{2}\right) = \Phi(-2) > \Phi\left(\frac{-4}{\sqrt{2}}\right) = \Phi(-2.828\ldots).$$