Probability of Error

The probability of error $p(e)$ measures the performance of a pattern recognition system. It is the average of the error at each value of $x$, weighted by how often that value of $x$ occurs. It follows from the error of one decision in the MAP Decision Rule.

Main idea

$p(e)=\int_{-\infty}^{\infty}p(e_k|x)\,p(x)\,dx$. The MAP boundary (equal posteriors) removes the reducible error and gives the minimum error, the Bayes error.

---

Error at One Value of $x$

For the decision ${\omega }_k=\arg {\max }_{{\omega }_i}[p({\omega }_i|x)]$ at one value of $x$:

$$p(e_k|x)=1-p({\omega }_k|x)=\sum _{\begin{array}{c}i=1\\ i\ne k\end{array}}^{c}p({\omega }_i|x)$$

The performance of the whole system is the average of $p(e_k|x)$ over all possible values of $x$.

---

How to Average Correctly

A plain average is not correct:

$$p(e)\stackrel{?}{=}\frac{1}{n_x}\sum _{x=0}^{3}p(e_k|x)\text{(discrete }x\text{)},p(e)\stackrel{?}{=}\frac{1}{3}{\int }_0^{3}p(e_k|x)dx\text{(continuous }x\text{)}$$

Why it is wrong:

• $x$ is a random variable
• different values of $x$ have different probabilities of occurrence
• so each $p(e_k|x)$ must be weighted by $p(x)$

The correct average:

$$p(e)=\sum _{x=-\infty }^{\infty }p(e_k|x)p(x)\text{for discrete }x$$ $$p(e)={\int }_{-\infty }^{\infty }p(e_k|x)p(x)dx\text{for continuous }x$$

---

Derivation for Continuous $x$

Substitute $p(e_k|x)=1-p({\omega }_k|x)$ and Bayes formula $p({\omega }_k|x)=p({\omega }_k)p(x|{\omega }_k)/p(x)$:

$$\begin{array}{rl}p(e)& ={\int }_{-\infty }^{\infty }p(e_k|x)p(x)dx={\int }_{-\infty }^{\infty }[1-p({\omega }_k|x)]p(x)dx\\ & ={\int }_{-\infty }^{\infty }\left[1-\frac{p({\omega }_k)p(x|{\omega }_k)}{p(x)}\right]p(x)dx=1-{\int }_{-\infty }^{\infty }p({\omega }_k)p(x|{\omega }_k)dx\end{array}$$

The decision ${\omega }_k$ changes with the region of $x$. Classification partitions the whole space of $x$ into $c$ decision regions ${\Re }_i$. In region ${\Re }_i$ the system decides ${\omega }_i$. Therefore:

$$p(e)=1-\sum _{i=1}^c{\int }_{{\Re }_i}p({\omega }_i)p(x|{\omega }_i)dx=1-\sum _{i=1}^{c}p({\omega }_i){\int }_{{\Re }_i}p(x|{\omega }_i)dx$$

---

Two-Class Case

$$\begin{array}{rl}p(e)& =1-p({\omega }_1){\int }_{{\Re }_1}p(x|{\omega }_1)dx-p({\omega }_2){\int }_{{\Re }_2}p(x|{\omega }_2)dx\\ & =p({\omega }_1){\int }_{{\Re }_2}p(x|{\omega }_1)dx+p({\omega }_2){\int }_{{\Re }_1}p(x|{\omega }_2)dx\end{array}$$

The second line uses $p({\omega }_1)+p({\omega }_2)=1$ and ${\int }_{{\Re }_1}p(x|{\omega }_i)dx+{\int }_{{\Re }_2}p(x|{\omega }_i)dx=1$.

Meaning of the two terms:

• the first term is the error when the true class is ${\omega }_1$ but $x$ falls in ${\Re }_2$
• the second term is the error when the true class is ${\omega }_2$ but $x$ falls in ${\Re }_1$

Reading the figure:

• the pink area is the error for deciding ${\omega }_1$ when the true class is ${\omega }_2$
• the grey area is the error for deciding ${\omega }_2$ when the true class is ${\omega }_1$
• $x^{\ast }$ is a non-optimal decision point, and it adds the reducible error (the triangle)
• $x_B$ is the point of equal posterior probabilities, which is the MAP (Bayes) decision point
• at $x_B$ the reducible error is gone and the total shaded area is the minimum, the Bayes error rate

---

More Features Give Lower Error

If we know the height $x_1$ and also the hair length $x_2$, we can make a better decision with a lower error. The principle is the same. Replace the scalar $x$ with a vector:

$$\mathbf{x}=[x_1,x_2{]}^T$$

What changes:

• the probability distribution becomes two dimensional
• the scalar threshold in 1D becomes a curve in the plane of $\mathbf{x}$

In this figure, the two classes overlap a lot in each single feature. In 2D, a line separates them well. In general, more information or a higher feature dimension increases the probability of a correct decision and reduces the probability of error.