Introduction
The MAP rule gives the smallest error at each single value of . To judge a whole pattern recognition system, we need its error over all values of . The probability of error is that one number. It measures how good a system is, shows why the MAP boundary is the best boundary, and shows why more features help.
Main idea
$p(e)=\int p(e_k|x)\,p(x)\,dx$, the error at each $x$ weighted by how often that $x$ occurs. Splitting the space into decision regions $\Re_i$ gives $p(e)=1-\sum_{i}p(\omega_i)\int_{\Re_i}p(x|\omega_i)\,dx$. The MAP boundary gives the smallest possible $p(e)$, the Bayes error rate. Any other boundary adds a reducible error, and adding a good feature lowers the error.
Overview
Step 1: error at one x
How good is the system? For the decision at one value of , the MAP Decision Rule gave the error below. The decided class depends on , so is really , written for short:
The performance of a recognition system can be measured by the average of over all possible values of .
Step 2: averaging over x
A plain average over the range of seems natural, for example with from 0 to 3, where is the number of values of :
Why this is wrong:
- is a random variable, so different values of occur with different probabilities
- a plain average counts a rare value of as much as a common one
- the error on the objects the system actually meets is what matters, so each must be weighted by , how often that value occurs
The right average for a random variable:
This is the expectation of the random quantity : in general, , with . A plain sample average fits the same pattern: group equal sample values together, and each value ends up weighted by the share of samples that take it. That share is an estimate of .
Why MAP gives the smallest overall: the weight comes from the data and does not depend on the rule, so the integral is smallest when the integrand is smallest at every , which is exactly what MAP does.
Step 3: continuous x and decision regions
Here is the class the rule decides at that , so changes as moves. The integral below is not over one fixed class.
Put in , then Bayes formula :
Explaining each step:
- the first term gives
- in the second term the above and below cancel
The decided class is different in different regions of . Decision, or classification, splits the whole space of into decision regions , where region is where the system decides . So the integral splits region by region:
The sum is the probability of a correct decision: for each class, the chance that an object is from that class and its lands in that class's own region.
Step 4: two classes and the reducible error
For two classes:
The second line uses and for each class. Its two terms:
- the first is the chance that an object is from but its falls in , so it is called
- the second is the chance that an object is from but its falls in , so it is called

Reading the figure:
- the two curves are and , with capital for the prior, and each error term is an area under one curve on the wrong side of the boundary
- the boundary is at a non-optimal point , so is left of and is right of it
- the pink area is , objects from decided as , and the gray area is , the converse
- the outlined triangle between and is the reducible error
- is where the two curves cross, and dividing both curves by shows this is where the posteriors are equal, the MAP point
- moving the boundary to removes the triangle, and the total shaded area left is the smallest possible, the Bayes error rate
The picture shows the general argument of Step 2 for one threshold: at every MAP keeps the larger curve, so only the smaller curve is left as error.
Step 5: more than one feature
Suppose you know not only a person's height but also the length of the hair . You can expect a better decision, with a lower error probability. The principle stays the same, with a vector in place of the scalar:
What changes:
- the class-conditional probability is now a two-dimensional distribution
- the scalar threshold that separates the two classes in 1D becomes a curve in the plane of , which can also be a straight line as a special case
- each decision region becomes an area of the plane

Reading the figure:
- the left plot is the 1D case: two class-conditional PDFs with equal priors , and the dashed threshold at their crossing splits the axis into and
- the right plot is the 2D case: each class-conditional PDF is a hill over the plane
- on the floor, the small circles are contours of the two hills, and the straight line splits the floor into and , here a straight line because both classes have the same circular shape
Step 6: why more features help

Reading the figure:
- projected onto either single axis, the two classes overlap a lot, so either feature alone gives a large error
- in the plane of both features, the two clouds lie on opposite sides of the green line, so they are almost fully separated
So increasing the information, or the feature dimension, in general increases the probability of a correct decision, and reduces the probability of error. This holds when is known exactly. When it must be estimated from a limited number of samples, extra features can make the estimate worse, because more features mean more numbers in to estimate from the same samples.
Why do we need this
The MAP rule says which class to pick, and says how good the result is. It gives one number to compare classifiers and features, and it shows why the boundary must sit where the weighted curves cross.
Next step
With a vector , comparing posteriors gets messy. Discriminant Functions turn the rule into one simple score per class.
Visual 1: total error against the threshold

Heights in EEE, deciding above the threshold:
- the two dashed curves are the two error terms of Step 4, each one growing as the threshold moves into its own class
- the black curve is their sum , and its lowest point is exactly the MAP threshold , where , the Bayes error
- any other threshold sits higher, and the red gap at is its reducible error,
Visual 2: why the average is weighted by p(x)

From top to bottom:
- the error at each height, , peaks at at the threshold, where the classes are equally likely
- shows how often each height really occurs among the students
- their product has area
- rare heights count less: the error is high only near , and it enters only as much as heights near really occur