Introduction

Once a measurement of the object is known, the class probabilities change. The maximum a posteriori (MAP) decision rule is the same rule as before, applied to these new probabilities: pick the class that is most likely after seeing . This note writes the rule down and shows that no other rule makes fewer mistakes.

Main idea

Decide $\omega_k=\arg\max_{\omega_i}p(\omega_i|x)$. If you decide $\omega_k$ at $x$, you are wrong with probability $p(e_k|x)=1-p(\omega_k|x)$. The largest posterior gives the smallest error, so MAP minimizes the probability of error at every $x$: $\arg\max_{\omega_i}p(\omega_i|x)=\arg\min_{\omega_i}p(e_i|x)$.


Overview


Step 1: probabilities after a measurement

Back in the Accounting classroom, suppose you now also know the student is m tall. How do you make the best decision?

The idea does not change: still pick the class with the larger probability. What changes is the probability itself:

  • the probabilities in the School of Accounting differ from those in the School of EEE, because the situation is different
  • in the same way, the probabilities after knowing the height differ from those without it

These new probabilities are written and , with , and are called posterior probabilities. No number is needed for this example: the point is only that knowing changes the probabilities. is the probability of class after the data value is known. The probabilities without knowing are renamed the prior probabilities.


Step 2: MAP decision rule

The rule is renamed from the maximum probability decision to the maximum a posteriori probability decision, or MAP decision. In general:

or in short:

"A posteriori" means "after seeing the data". With no measurement, the posterior is just the prior, and the rule goes back to the maximum probability decision.

The MAP decision rule is also called the Bayes decision rule, and a classifier that uses it is a Bayes classifier (or Bayesian, optimal classifier). All these names mean the same rule.


Step 3: error at one value of x

You decide based on the observed value . Given this , the object really is from with probability , so that is the probability your decision is correct. So the probability of a wrong decision, the error rate at , is:

The posteriors of all classes add up to 1, so this is also the sum of the posteriors of the classes you did not pick:


Step 4: why MAP is optimal

Explaining each step:

  • MAP picks so that is the largest posterior
  • the error is then the smallest possible at this
  • this holds at every value of , so the rule is optimal in the sense of minimizing the probability of a wrong decision
  • it is also optimal on average over all : the total error weights each by , which no rule can change, so making each smallest makes the total smallest (Probability of Error shows this)

So the MAP decision rule minimizes the probability of decision error, and the two ways of writing it are the same rule:


Why do we need this

It is the decision step of every classifier in this topic. The quadratic, linear and minimum distance classifiers are all this rule, written for Gaussian classes.


Next step

The posterior is hard to get directly. Prior, Likelihood and Posterior builds it from two quantities that are easy to get.


Visual 1: posteriors and the error at each height

Accounting classroom, for male:

  • the dashed lines are the priors, and the solid curves are the posteriors and after the height is known
  • at m the posterior of is , so MAP decides male even though the prior favours female
  • the shaded lower curve is the error , the posterior of the class not picked
  • picking the top curve at every leaves the lower one as error, which is why MAP has the smallest error at each

Visual 2: how a measurement moves the probability

How to read it:

  • the grey diagonal is the case with no measurement: the posterior equals the prior
  • a height of m is typical of males, so it lifts above the diagonal: becomes in Accounting
  • a height of m is typical of females, so it pushes below: becomes in EEE, and the decision flips to
  • the other two dots are the same heights in the other school: m gives in EEE and m gives in Accounting
  • the decision only depends on which side of the posterior lands