MAP Decision Rule

The maximum a posteriori (MAP) decision rule picks the class with the largest posterior probability. It is the optimal decision rule because it gives the smallest probability of a wrong decision. It is one step of the Bayes Decision and Classifiers topic.

Main idea

Decide $\omega_k=\arg\max_{\omega_i}\,p(\omega_i|x)$. This is the same as $\arg\min_{\omega_i}\,p(e_i|x)$.

---

Intuition: Decision with Prior Knowledge Only

You see a student in a classroom, but you cannot see the student clearly. You must decide if the student is male (${\omega }_1$) or female (${\omega }_2$).

School	$p({\omega }_1)$	$p({\omega }_2)$	Best decision	Error rate
EEE	0.7	0.3	${\omega }_1$ (male)	$p(e)=0.3$
Accounting	0.3	0.7	${\omega }_2$ (female)	$p(e)=0.3$

This is the maximum probability decision:

• decide ${\omega }_1$ if $p({\omega }_1)>p({\omega }_2)$, and vice versa
• the decision can still be wrong, but no other decision is better
• the opposite decision (decide female in EEE) has an error rate of $0.7$

---

Adding Data: Prior and Posterior Probability

Now you know that the student has a height of $x=1.75$ m. The best decision is still to pick the class with the larger probability. The difference is that the probabilities now include the knowledge of $x$.

Two kinds of probability:

• prior probability $p({\omega }_i)$ is the probability of class ${\omega }_i$ before you know the data value $x$
• posterior probability $p({\omega }_i|x)$ is the probability of class ${\omega }_i$ after you know the data value $x$ in a particular scenario

The rule changes name from maximum probability decision to maximum a posteriori probability decision, or MAP decision.

MAP decision rule:

$$\text{Decide }{\omega }_k:\text{ if }p({\omega }_k|x)>p({\omega }_i|x),i\ne k$$

or, more generally:

$${\omega }_k=\arg \underset{{\omega }_i}{\max }[p({\omega }_i|x)]$$

---

Why MAP is Optimal

When you decide ${\omega }_k$ from the observed value $x$, the probability that the decision is correct is $p({\omega }_k|x)$. The probability of a wrong decision (error rate) is:

$$p(e_k|x)=1-p({\omega }_k|x)$$

Because MAP picks the largest $p({\omega }_k|x)$, the error $p(e_k|x)$ is the smallest. So MAP minimises the probability of decision error:

$$\text{Decide: }{\omega }_k=\arg \underset{{\omega }_i}{\max }[p({\omega }_i|x)]=\arg \underset{{\omega }_i}{\min }[p(e_i|x)]$$

---

Calculating the Posterior with Bayes Formula

It is difficult to get $p({\omega }_i|x)$ directly. It is easier to get the prior $p({\omega }_i)$ and the class-conditional probability $p(x|{\omega }_i)$.

From the basic rule of probability $p(A,B)=p(A)p(B|A)=p(B)p(A|B)$:

$$p(x,{\omega }_i)=p(x)p({\omega }_i|x)=p({\omega }_i)p(x|{\omega }_i)$$

So:

$$p({\omega }_i|x)=\frac{p({\omega }_i)p(x|{\omega }_i)}{p(x)}$$

where the mixture PDF or PMF is:

$$p(x)=\sum _{i=1}^{c}p(x|{\omega }_i)p({\omega }_i)$$

This uses $p(A)={\sum }_{i=1}^{c}p(A,B_i)={\sum }_{i=1}^{c}p(A|B_i)p(B_i)$.

Why $p(x)$ can be removed:

• $p(x)$ is the probability (density) of a height $x$ over all classes
• it has the same value for all classes, so it does not change which class is the largest

---

The Challenge: Class-Conditional PDFs for All $x$

To recognise gender automatically for every value of $x$, we need $p(x|{\omega }_i)$ for all possible values of $x$. This is the big challenge.

Each class-conditional distribution must sum or integrate to 1 over all heights (0 m to 3 m here):

$$\sum _{x=0}^{3}p(x|{\omega }_1)=1,\sum _{x=0}^{3}p(x|{\omega }_2)=1$$ $${\int }_0^{3}p(x|{\omega }_1)dx=1,{\int }_0^{3}p(x|{\omega }_2)dx=1$$

The lecture then asks how to simplify the computation. The answer is to convert the decision into a classification with discriminant functions.