Calculating the error of Bayes classifier analytically

If two classes $w_1$ and $w_2$ have normal distribution with known parameters ($M_1$, $M_2$ as their means and $\Sigma_1$,$\Sigma_2$ are their covariances) how we can calculate error of the Bayes classifier for them theorically?

Also suppose the variables are in N-dimensional space.

Note: A copy of this question is also available at https://math.stackexchange.com/q/11891/4051 that is still unanswered. If any of these question get answered, the other one will be deleted.

• Is this question the same as stats.stackexchange.com/q/4942/919 ? – whuber Nov 26 '10 at 20:40
• @whuber Your answer suggests it is the case indeed. – chl Nov 26 '10 at 20:47
• @whuber: Yes. i don't know this question suited to which one. I am waiting for a response for one to remove the other one. Is it against the rules? – Isaac Nov 26 '10 at 20:49
• It might be easier, and surely would be cleaner, to edit the original question. However, sometimes a question is restarted as a new one when the earlier version collects too many comments that are made irrelevant by the edits, so it's a judgment call. In any event it's helpful to place cross-references between closely related questions to help people connect them easily. – whuber Nov 26 '10 at 20:52

There's no closed form, but you could do it numerically.

As a concrete example, consider two Gaussians with following parameters

$$\mu_1=\left(\begin{matrix} -1\\\\ -1 \end{matrix}\right), \mu_2=\left(\begin{matrix} 1\\\\ 1 \end{matrix}\right)$$

$$\Sigma_1=\left(\begin{matrix} 2&1/2\\\\ 1/2&2 \end{matrix}\right),\ \Sigma_2=\left(\begin{matrix} 1&0\\\\ 0&1 \end{matrix}\right)$$

Bayes optimal classifier boundary will correspond to the point where two densities are equal

Since your classifier will pick the most likely class at every point, you need to integrate over the density that is not the highest one for each point. For the problem above, it corresponds to volumes of following regions

You can integrate two pieces separately using some numerical integration package. For the problem above I get 0.253579 using following Mathematica code

dens1[x_, y_] = PDF[MultinormalDistribution[{-1, -1}, {{2, 1/2}, {1/2, 2}}], {x, y}];
dens2[x_, y_] = PDF[MultinormalDistribution[{1, 1}, {{1, 0}, {0, 1}}], {x, y}];
piece1 = NIntegrate[dens2[x, y] Boole[dens1[x, y] > dens2[x, y]], {x, -Infinity, Infinity}, {y, -Infinity, Infinity}];
piece2 = NIntegrate[dens1[x, y] Boole[dens2[x, y] > dens1[x, y]], {x, -Infinity, Infinity}, {y, -Infinity, Infinity}];
piece1 + piece2

• Nice answer. Could you please provide commands to reproduce your beautiful figures? – Andrej Oct 5 '12 at 13:42
• (+1) These graphics are beautiful. – COOLSerdash Jun 25 '13 at 7:05

It seems that you can go about this in two ways, depending on what model assumptions you are happy to make.

Generative Approach

Assuming a generative model for the data, you also need to know the prior probabilities of each class for an analytic statement of the classification error. Look up Discriminant Analysis to get the optimal decision boundary in closed form, then compute the areas on the wrong sides of it for each class to get the error rates.

I assume this is the approach intended by your invocation of the Bayes classifier, which is defined only when everything about the data generating process is specified. Since this is seldom possible it is always also worth considering the

Discrimination Approach

If you don't want to or cannot specify the prior class probabilities, you can take advantage of the fact that the discriminant function can under many circumstances (roughly, exponential family class conditional distributions) be modelled directly by a logistic regression model. The error rate calculation is then the one for the relevant logistic regression model.

For a comparison of approaches and a discussion of error rates, Jordan 1995 and Jordan 2001 and references may be of interest.

Here you might find several clues for your question, maybe is not there the full response but certainly very valuable parts of it. http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2766788/

In classification with balanced classes, the Bayes error rate (BER) is exactly equal to $$(1 - TV) / 2$$, where $$TV$$ is the total variation distance between the +ve and -ve conditional distributions of the features. See Theorem 1 of this paper.

To complete, it's not hard to find good references computing the TV between multivariate Gaussian distributions.