Introduction
A computer vision system must look at an object and say what it is. This topic studies the last step of that system, where the decision is made. Bayes decision theory builds the decision rule that makes the fewest mistakes, starting from a guess that everybody makes by instinct and ending with classifiers you can compute.
Main idea
Pick the class that is most likely after you see the measurement, $\omega_k=\arg\max_{\omega_i}p(\omega_i|\mathbf{x})$. No other rule makes fewer mistakes. Write this as one score per class, $g_i(\mathbf{x})=\ln p(\mathbf{x}|\omega_i)+\ln p(\omega_i)$. If each class is a Gaussian, the score becomes a distance to the class mean, and the boundary between two classes becomes a curve, a tilted hyperplane, or a hyperplane perpendicular to the line between the means.
Overview
The whole topic is one chain, where each note answers the question the last one raises:
Step 1: computer vision system

The system has three stages:
- preprocessing and normalization takes the raw input and gives the measured data
- feature extraction and dimensionality reduction maps to a short feature vector
- classification gives the output for classes, one bit per class with a 1 for the decided class, for example for apple and for pear
Two kinds of knowledge feed the stages: knowledge type 1 is human knowledge, and knowledge type 2 is a database of training samples.
Visual object recognition is very easy for the human brain but very difficult for a machine. This topic is about the last stage, classification. The classifier receives the feature vector , but in the classifier notes its input is written with components, so from here on means the vector being classified.
Step 2: what this topic builds
In order, the notes:
- develop decision theory from an intuitive process that everybody understands into an abstract mathematical theory
- find the optimal decision rule: the MAP or Bayes decision rule
- evaluate a pattern recognition system by its accuracy, or its probability of error
- turn the decision into evaluating one discriminant function per class
- work out the discriminant function when each class is a multivariate Gaussian
- compare the Mahalanobis and Euclidean distances
- reach the linear classifier and the minimum distance classifier as special cases
Reading order
- Decisions Under Uncertainty: what is the best guess before any measurement, and how often is it wrong?
- MAP Decision Rule: which class should I pick once I measure , and why is it optimal?
- Prior, Likelihood and Posterior: how do I get the posterior from quantities I can measure?
- Probability of Error: how many mistakes does the rule make over all , and why do more features help?
- Discriminant Functions: how do I turn the rule into one score per class?
- Gaussian Discriminant Function: what is a Gaussian class, and what does its score look like?
- Mahalanobis and Euclidean Distance: what is the distance hidden inside the Gaussian score?
- Quadratic Classifier: what happens when every class has its own covariance?
- Linear Classifier: what happens when all classes share one covariance?
- Minimum Distance Classifier: what happens when that covariance is , and how do I build a classifier from samples?
Concept map
flowchart TD A["Decisions under uncertainty<br/>max p(ωi), error = 1 − max p(ωi)"] --> B["MAP decision rule<br/>max p(ωi|x), error at x is smallest"] B --> C["Prior, likelihood, posterior<br/>p(ωi|x) = p(ωi)p(x|ωi)/p(x)"] C --> D["Probability of error<br/>p(e) = ∫ p(ek|x) p(x) dx"] D --> E["Discriminant functions<br/>gi(x) = ln p(x|ωi) + ln p(ωi)"] E --> F["Gaussian discriminant<br/>gi = −½ dΣ + bi"] F --> G["Mahalanobis distance dΣ"] G -->|"different Σi"| H["Quadratic classifier<br/>curved boundary"] G -->|"shared Σ"| I["Linear classifier<br/>tilted hyperplane"] G -->|"Σ = σ²I, equal priors"| J["Minimum distance classifier<br/>nearest mean, perpendicular bisector"]
Why do we need this
A classifier must decide under uncertainty, because two classes can give the same measurement. This topic answers three questions in order:
- what is the best possible rule when the classes overlap
- how good is that rule, measured as a probability of error
- how do we turn the rule into something we can calculate from a mean, a covariance and a prior
Key math ideas
The math ideas this topic relies on, and where each one appears:
- Likelihood: says how well each class explains the measurement, in Prior, Likelihood and Posterior, the MAP Decision Rule and the Gaussian Discriminant Function
- Softmax and posterior: the scores are log posteriors, so the largest score is the largest posterior, in Prior, Likelihood and Posterior and Discriminant Functions
- Covariance matrix: is the shape of each class in the Gaussian Discriminant Function, and its three cases give the Quadratic Classifier, the Linear Classifier and the Minimum Distance Classifier
- Inverse covariance and whitening: measures offsets in units of the class spread, in the Gaussian Discriminant Function and the Linear Classifier
- Mahalanobis distance: the distance term of the Gaussian Discriminant Function, which every classifier in this topic uses in some form, down to the Euclidean distance of the Minimum Distance Classifier
- Eigenvectors and eigenvalues: the axes of the equal-distance ellipses in Mahalanobis and Euclidean Distance, and the whitened direction in the Linear Classifier
- Dot product and projection: the Minimum Distance Classifier and the Linear Classifier both reduce to template matching, plus a constant
Visual 1: whole chain on one example

Student heights, with for male and for female:
- panel 1: with no measurement the rule always picks , so every female is wrong and
- panel 2: once the height is measured, MAP compares and the decision flips at the crossing ; the red area under the lower curve is what is still wrong
- panel 3: the scores are parabolas for Gaussian classes, and they cross at the very same , so the score gives the same decision
- panel 4: that red area is , down from with no measurement, which is why every later note works with