B4B33RPZ · Pattern Recognition and Machine Learning

Bayesian Decision Making

Lab 2: Bayesian risk, the optimal strategy, and two worked examples

Klára JanouškováFEE CTU, Prague

Part I

Recap

Warm-up quiz: probability from lab 1

A test finds 90 % of sick patients. Which probability is 0.9?

We know the patient is sick (right of the bar) and ask about the test result.

$P(H) = 0.5$ , $P(E \mid H) = 0.6$ , $P(E \mid \neg H) = 0.2$ . What is $P(H \mid E)$ ?

$P(H \mid E) = \frac{P(E \mid H)\,P(H)}{P(E \mid H)\,P(H) + P(E \mid \neg H)\,P(\neg H)}$ $= \frac{0.6 \cdot 0.5}{0.6 \cdot 0.5 + 0.2 \cdot 0.5} = \frac{0.3}{0.4} = 0.75$ The wolf and the pens from lab 1.

Warm-up quiz, continued

Which of these always sums to 1?

A conditional distribution sums to 1 over the variable left of the bar.

You roll a fair die and win the number shown in CZK. Expected win?

$\sum_{i=1}^{6} \tfrac{1}{6}\, i = 3.5$ . Today's risk is the same kind of average, of penalties.

Can a probability density $p(x)$ be larger than 1?

Only the area under it must be 1. A narrow Gaussian peaks above 1.

Statistical pattern recognition: the mushroom case

You find a mushroom in the forest. Eat it or not? What is each symbol here?

Symbol	Meaning	Mushroom example
$X$	observations $x \in X$ : what we know (measurement, feature vector)	cap colour, smell, ring… and context: rain, temperature, month, place
$K$	hidden states (classes) $k \in K$ : what we don't know	edible / poisonous
$D$	possible decisions (actions)	eat / leave it
$p_{XK}$	joint probability $p_{XK}(x, k)$ of seeing $x$ when the state is $k$	how often a red smelly one is poisonous
$W$	penalty (loss) $W(k, d)$ : the price of decision $d$ when the truth is $k$	ate a poisonous one: hospital
$q$	strategy (decision function) $q\colon X \to D$	your rule: "red with white dots → leave it"

Why do we need a penalty $W$ ?

Penalty $W(k, d)$ for the mushroom:

truth $k$ \ decision $d$	eat	leave it
edible	0	1 (no dinner)
poisonous	1000 (hospital)	0

Question: the mushroom is 95 % likely edible. Should you eat it?

No: 5 % × 1000 = 50 is far worse than 95 % × 1 = 0.95.

Picking the most probable class is not enough. We need the expected penalty of each decision.

How good is a strategy $q$ ? The Bayesian risk

Question: over many mushrooms, what penalty does strategy $q$ pay on average?

One pair $(x, k)$ : we decide $q(x)$ and pay $W(k, q(x))$ .

This pair occurs with probability $p_{XK}(x, k)$ .

Average = sum over all pairs, weighted by probability: the Bayesian risk

R(q) = \sum_{x \in X} \sum_{k \in K} p_{XK}(x, k)\, W(k, q(x))

This is the standard expectation $\mathbb{E}_{z \sim p}[f(z)] = \sum_z p(z)\, f(z)$ , with $z = (x, k)$ :

\underbrace{R(q)}_{\mathbb{E}[f(z)]} = \underbrace{\sum_{x \in X} \sum_{k \in K}}_{\sum_z}\; \underbrace{p_{XK}(x, k)}_{p(z)}\; \underbrace{W(k, q(x))}_{f(z)}

Is $R(q)$ bounded?

Yes:

\min W \le R(q) \le \max W

, a weighted mean with weights summing to 1.

The Bayesian strategy

Question: we can score any strategy with $R(q)$ . Which one do we want?

Bayesian strategy: smallest risk

q^* = \operatorname*{argmin}_{q\colon X \to D} R(q)

The minimum is over all strategies: whole functions

q\colon X \to D

, one decision for every

x

.

How many strategies are there? Say $x$ is just the cap colour (4 values), $D$ = {eat, leave}.

In general

|D|^{|X|}

. The lab has 21 values of

x

:

2^{21} \approx 2

million. Trying them all does not scale. Next: we don't have to.

Finding the strategy $q^*$

Question: must we try all $|D|^{|X|}$ strategies? No, decide each $x$ separately

Start from the definition:

R(q^*) = \displaystyle\min_{q\colon X \to D} \sum_{x \in X} \sum_{k \in K} p_{XK}(x, k)\, W(k, q(x))

↓ Recall $q\colon X \to D$ : a strategy is one decision $q(x) \in D$ for every $x$ , and $q(x)$ only appears in the term of its own $x$ . So each term can be minimised on its own: the min moves inside the sum.

= \displaystyle\sum_{x \in X} \min_{q(x) \in D} \sum_{k \in K} p_{XK}(x, k)\, W(k, q(x))

↓ For a fixed $x$ , the value $q(x)$ is just some decision: call it $d$ and minimise over $d \in D$ . Split the joint: $p_{XK}(x, k) = p(x)\, p_{K|X}(k \mid x)$ . The factor $p(x)$ is the same for every $d$ , so it can go in front of the min: multiplying all options by the same non-negative number does not change which one is smallest.

= \displaystyle\sum_{x \in X} p(x) \min_{d \in D} \underbrace{\sum_{k \in K} p_{K|X}(k \mid x)\, W(k, d)}_{R(x, d)}

Partial risk

R(x, d) = \sum_{k} p_{K|X}(k \mid x)\, W(k, d)

expected penalty of

d

once we have seen

x

Optimal strategy

q^*(x) = \operatorname*{argmin}_{d \in D} R(x, d)

for every

x

on its own

The 0/1 loss: which decision is best?

Question: if every mistake costs the same, which decision is best?

0/1 loss ( $D = K$ ):

W(k, d) = \begin{cases} 0 & \text{if } d = k \\ 1 & \text{if } d \ne k \end{cases}

↓ Plug $W$ into $R(x, d) = \sum_k p(k \mid x)\, W(k, d)$ : the term $k = d$ is multiplied by 0, all others by 1.

R(x, d) = \sum_{k \ne d} p_{K|X}(k \mid x)

↓ The posterior sums to 1 over all $k$ , so the sum over $k \ne d$ is 1 minus the missing term.

R(x, d) = 1 - p_{K|X}(d \mid x)

↓ Minimising $1 - p(d \mid x)$ is the same as maximising $p(d \mid x)$ .

q^*(x) = \operatorname*{argmax}_{k \in K} p_{K|X}(k \mid x)

↓ Bayes' rule: $p(k \mid x) = p(x \mid k)\, p(k) / p(x)$ . $p(x)$ is the same for every $k$ , so it does not change the argmax.

q^*(x) = \operatorname*{argmax}_{k \in K} p(x \mid k)\, p(k)

With the 0/1 loss,

R(q)

= probability of a wrong decision.

Quick check

In $q^* = \operatorname{argmin}_q R(q)$ , the argmin runs over…

$q^*$ is a whole function. It just happens that we can find it one $x$ at a time.

With the 0/1 loss, $R(q)$ is…

An average of 0s and 1s is a probability.

$p(\text{poisonous} \mid x) = 0.01$ , penalties as before (1000 / 1). Eat?

$R(x, \text{eat}) = 0.01 \cdot 1000 = 10$ , $R(x, \text{leave}) = 0.99 \cdot 1 = 0.99$ .

Part II

Exercise: letters on licence plates

CZ region recognition by licence plates

The second character of a plate is the region (kraj):

1A7 4551A = Praha

7C2 5025C = Jihočeský kraj

3J1 2272J = Vysočina

Our simplification: recognise only A and C.

Question: you stand at a crossroads in South Bohemia. Before looking at a plate: A or C?

C is much more likely: that is the prior

p(k)

.

Feature design: where does $p(x \mid k)$ come from?

So far $p(x \mid k)$ was given for every discrete $x$ . We only have images: $N \times 10 \times 10$ pixels.

Question: which single number $x$ would separate A from C?

sum of all pixels (ink)
the central pixel
top − bottom
left − right

Left vs. right: C is open on the right, A is symmetric.

Today, a toy version: $x = g(R - L)$ , where $g$ normalises, clips and rounds to $X = \{0, 1, 2, 3\}$ .

In the lab: $L - R$ , normalised and clipped to 21 values $\{-10, \dots, 10\}$ .

Bayes example: discrete $x$

x = g(R - L)

,

X = \{0, 1, 2, 3\}

K = \{A, C\}

q\colon X \to D

,

D = K

W\colon K \times D \to \mathbb{R}

, 0/1 loss

P(A) = P(C) = 0.5

(uniform, uninformed priors)

$x$	0	1	2	3
$P(x \mid A)$	0.3	0.2	0.1	0.4
$P(x \mid C)$	0.7	0.2	0.1	0

$W_{0/1}$ : $k$ \ $d$	A	C
A	0	1
C	1	0

Question: for each

x

, which letter should we answer? And how often will we be wrong?

Quick check

Now $P(A) = 0.25$ , $P(C) = 0.75$ . What is $q^*(1)$ ?

$0.2 \cdot 0.25 = 0.05 < 0.2 \cdot 0.75 = 0.15$ : the prior breaks the tie.

Still $P(A) = 0.25$ . What is $q^*(3)$ ?

$p(3 \mid C) = 0$ : C never produces $x = 3$ , so any prior loses.

Uniform priors, but saying C when it is A costs 10. What is $q^*(0)$ ?

$p(A \mid 0) = 0.3$ : $R(0, C) = 0.3 \cdot 10 = 3$ , $R(0, A) = 0.7 \cdot 1 = 0.7$ .

Part III

Continuous $x$ : Gaussian classes

Bayes example: continuous $x$

Question: $x \in \mathbb{R}$ now. What changes in the risk?

Sums over

x

become integrals:

R(q) = \int_X \sum_{k \in K} p_{XK}(x, k)\, W(k, q(x))\, dx

Each class is a Gaussian:

p(x \mid k) = \frac{1}{\sqrt{2\pi\sigma_k^2}} \exp\!\left(-\frac{(x - \mu_k)^2}{2\sigma_k^2}\right)

Given: $\mu_A, \mu_C, \sigma_A, \sigma_C, p(A), p(C)$ , 0/1 loss. Still $q^*(x) = \operatorname{argmax}_k p(x \mid k)\,p(k)$ .

Where do we switch from A to C?

Where the two weighted curves cross.

Quadratic equations and inequalities

Roots of $a x^2 + b x + c = 0$ :

x_{1,2} = \frac{-b \pm \sqrt{\Delta}}{2a}, \qquad \Delta = b^2 - 4ac

Where is $a x^2 + b x + c > 0$ ? It depends on the sign of $a$ (picture).

In our case: $a > 0 \Leftrightarrow \sigma_A > \sigma_C$ . The wider class wins on both tails.

$\Delta > 0$ : two roots $x_1 < x_2$ , the sign changes at both: two thresholds.
$\Delta = 0$ : one double root $x_0 = -\tfrac{b}{2a}$ ; the parabola only touches the axis, so the sign does not change: one class everywhere (a tie only at $x_0$ ).
$\Delta < 0$ : no roots, the sign never changes: one class everywhere.

Lab (find_strategy_2normal): thresholds $t_1 \le t_2$ and a decision for each of the 3 intervals. Handle $a = 0$ , $\Delta = 0$ and $\Delta < 0$ . Play with it: desmos.com/calculator/qa60j7hx6u

Try it: two Gaussian classes

your threshold

t

\mu_A

\mu_C

\sigma_A

\sigma_C

prior

p(A)

same

\sigma

for both show posterior

p(A \mid x)

How do we compute the risk?

Question: with the 0/1 loss, $R(q)$ = P(mistake). How do we compute it?

$i$ numbers the intervals $X_1, X_2, X_3$ (right); in $X_i$ we answer $q_i$ : $q_1 = A$ , $q_2 = C$ , $q_3 = A$ .

↓ Intuitive: in $X_i$ we are wrong if the true class is any $k \ne q_i$ (hatched):

R(q) = \underbrace{\sum_{i=1}^{3}}_{\text{intervals}} \; \underbrace{\sum_{k \ne q_i}}_{\text{wrong classes}} p(k) \int_{X_i} p(x \mid k)\, dx

Problem: $K - 1$ integrals per interval (below: $K = 3$ ).

↓ In $X_i$ exactly one class is right, $q_i$ (shaded); right + wrong = 1:

R(q) = 1 - \sum_{i=1}^{3} p(q_i) \int_{X_i} p(x \mid q_i)\, dx

↓ Area between thresholds = area left of $t_2$ − area left of $t_1$ : $\int_{t_1}^{t_2} p(x \mid k)\, dx = F_k(t_2) - F_k(t_1)$

Code: norm.cdf(t2, mu, sd) - norm.cdf(t1, mu, sd)

Quick check

$\sigma_A = \sigma_C$ , $p(A) = p(C)$ . Where is the threshold?

$a = 0$ and the $\ln$ term is 0: halfway between the means.

Now $p(A)$ grows. The threshold moves…

A becomes more likely a priori, so A's region grows.

$\sigma_A = 2$ , $\sigma_C = 0.5$ . Far out in the tails we decide…

The wider Gaussian decays more slowly: $a > 0$ , A wins outside the roots. The lab data is this case.

Take-away for the lab

Bayesian risk $R(q)$ = expected penalty of a strategy.
Minimise it per observation: $q^*(x) = \operatorname{argmin}_d R(x, d)$ (partial risk).
0/1 loss: $q^*(x) = \operatorname{argmax}_k p(x \mid k)\,p(k)$ , and $R(q^*)$ is the error probability.
Gaussian classes: the boundary solves a quadratic inequality; one threshold if $\sigma_A = \sigma_C$ , up to two otherwise.

In bayes.py

Discrete (21 values of

x

):

bayes_risk_discrete, find_strategy_discrete (ties → A), classify_discrete, classification_error

Continuous (two Gaussians):

find_strategy_2normal (

t_1

,

t_2

, 3 decisions), bayes_risk_2normal, classify_2normal

Try both losses:

W_1 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}

and

W_2 = \begin{bmatrix} 0 & 5 \\ 1 & 0 \end{bmatrix}

.

Optional

Extra: loss vs. prior

What does a different loss do?

Question: the lab also uses $W_2$ , where one kind of mistake costs 5. How does that move the decision?

Costs $W(A, C) = w_{AC}$ (true A, said C), $W(C, A) = w_{CA}$ , 0 when correct.

↓ In $R(x, d) = \sum_k p(k \mid x)\, W(k, d)$ only the wrong class survives:

R(x, A) = p(C \mid x)\, w_{CA}

R(x, C) = p(A \mid x)\, w_{AC}

↓ Decide A when $R(x, A) < R(x, C)$ ; write $p(k \mid x) = p(x \mid k)\, p(k) / p(x)$ and cancel $p(x)$ :

p(x \mid A)\, p(A)\, w_{AC} \;>\; p(x \mid C)\, p(C)\, w_{CA}

Divide by

p(x \mid C)\, p(C)\, w_{CA}

: decide A when

\underbrace{\frac{p(x \mid A)}{p(x \mid C)}}_{\text{likelihood ratio}} \cdot \underbrace{\frac{p(A)}{p(C)}}_{\text{prior odds}} \cdot \underbrace{\frac{w_{AC}}{w_{CA}}}_{\text{loss ratio}} \;>\; 1

The loss ratio multiplies the prior odds: an expensive mistake behaves like a more likely class. For Gaussians only

c

changes:

c \to c + \ln (w_{AC} / w_{CA})

.

Other losses in the continuous case

Question: two Gaussians ( $\mu_A = 0$ , $\mu_C = 3$ , $\sigma = 1$ , equal priors). Calling a true A "C" now costs 5 ( $w_{AC} = 5$ , $w_{CA} = 1$ ). Where does the threshold go?

0/1 loss: equal $\sigma$ and priors → halfway, $t = 1.5$ .

↓ With costs we compare the curves scaled by the cost of the other mistake (previous slide):

p(x \mid A)\, p(A)\, w_{AC} \;>\; p(x \mid C)\, p(C)\, w_{CA}

↓ Take $\ln$ as before; only $c$ changes, $c \to c + \ln 5$ , and $-3x + c > 0$ gives

t = (4.5 + \ln 5) / 3 \approx 2.04

: the A region grows.

↓ Risk ≠ error probability, so no "1 − P(correct)"; weight each mistake by its cost:

R(q) = \sum_{i} \sum_{k \ne q_i} W(k, q_i)\, p(k) \int_{X_i} p(x \mid k)\, dx

Bayesian Decision Making

Recap

Warm-up quiz: probability from lab 1

Warm-up quiz, continued

Statistical pattern recognition: the mushroom case

Why do we need a penalty WWW?

How good is a strategy qqq? The Bayesian risk

The Bayesian strategy

Finding the strategy q∗q^*q∗

The 0/1 loss: which decision is best?

Quick check

Exercise: letters on licence plates

CZ region recognition by licence plates

Feature design: where does p(x∣k)p(x \mid k)p(x∣k) come from?

Bayes example: discrete xxx

Quick check

Continuous xxx: Gaussian classes

Bayes example: continuous xxx

Quadratic equations and inequalities

Try it: two Gaussian classes

How do we compute the risk?

Quick check

Take-away for the lab

Extra: loss vs. prior

What does a different loss do?

Other losses in the continuous case

Why do we need a penalty $W$ ?

How good is a strategy $q$ ? The Bayesian risk

Finding the strategy $q^*$

Feature design: where does $p(x \mid k)$ come from?

Bayes example: discrete $x$

Continuous $x$ : Gaussian classes

Bayes example: continuous $x$