B4B33RPZ · Pattern Recognition and Machine Learning

Minimax

Lab 3: decisions without priors, the minimax strategy, and how it relates to Bayes

Klára JanouškováFEE CTU, Prague

Test next week

Test 1: 16. 10. (next week), during your lab

Topics: Bayesian and non-Bayesian decision making: problems and theory
Can't come? Let us know in advance.
No minimum score to pass (well, the minimum is zero :)
Bring a calculator. Nothing else is allowed: no laptop, no notes, no phone.

Bonus tasks

Presented in person after the labs
You explain the task and convince us that your solution is correct

Part I

Recap

Warm-up quiz: Bayes from lab 2

0/1 loss, $p(A \mid x) = 0.3$ , $p(C \mid x) = 0.7$ . The Bayesian strategy says…

With the 0/1 loss, $q^*(x) = \operatorname{argmax}_k p(k \mid x)$ : the most probable class.

To compute the Bayesian risk $R(q)$ we need…

$R(q)$ sums $p(x, k)\, W(k, q(x))$ and $p(x, k) = p(x \mid k)\, p(k)$ . Today: no priors.

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

The wider Gaussian decays more slowly. Narrow C wins only near its mean: an interval $[t_1, t_2]$ .

The Bayesian decision problem

$X$	observations: what we know
$K$	hidden states: what we don't know
$D$	decisions
$p_{XK}$	joint probability $X \times K \to \mathbb{R}$
$W$	loss $K \times D \to \mathbb{R}$
$q$	strategy $X \to D$

Risk of a strategy: the average loss

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

Bayesian strategy: the smallest risk

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

Many things simplify with the 0/1 loss:

R(q)

= probability of a mistake,

q^*

= most probable class.

Name the parts: two more examples

	Medical diagnosis	Self-driving car: pedestrian?
$X$	test results, symptoms (fever, blood values)	camera and sensor readings
$K$	has the disease / healthy	pedestrian present / not
$D$	treat / don't treat / more tests	brake / keep driving
$W$	untreated sick patient: very large; treated healthy one: moderate	missed pedestrian: huge; needless braking: small
$q$	"treat if $p(\text{disease} \mid x) > 0.2$ "	"brake if $p(\text{pedestrian} \mid x) > 0.05$ "

Question: is $p(\text{pedestrian})$ the same outside a school at 8:00 and on a motorway at 3:00? And who sets the price of a missed pedestrian in CZK?

Bayesian strategy with a reject option

Question: the classifier may answer "not known" for a fixed price $\varepsilon$ . When should it?

$D = K \cup \{\text{not known}\}$ , loss

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

↓ As in lab 2, decide each $x$ on its own: minimise the partial risk $R(x, d) = \sum_k p(k \mid x)\, W(k, d)$ .

q^*(x) = \operatorname*{argmin}_{d \in D} \sum_{k \in K} p_{K|X}(k \mid x)\, W(k, d)

↓ Answer a class $d = k$ : we pay 1 whenever the truth is another class.

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

↓ Answer "not known": we pay $\varepsilon$ whatever the truth, and $\sum_k p(k \mid x) = 1$ .

R(x, \text{not known}) = \varepsilon

↓ The best class costs $1 - \max_k p(k \mid x)$ ; take it only if that is cheaper than $\varepsilon$ .

q^*(x) = \begin{cases} \operatorname*{argmax}_{k} p_{K|X}(k \mid x) & \text{if } 1 - \max_{k} p_{K|X}(k \mid x) < \varepsilon \\ \text{not known} & \text{otherwise} \end{cases}

Part II

Non-Bayesian decision problems

When can't we use the Bayesian formulation?

Question: Bayes needs the priors $p(k)$ and the loss $W$ . What if we don't have them?

Priors drift: flu cases next winter, pedestrians at 8:00 vs. 3:00. The world changes, independently of us.
Priors react to us: a spammer sends more of what gets through our filter. The prior depends on our own $q$ , so no estimate stays valid.
Losses not comparable: no agreed exchange rate between the two mistakes
- missed tumour vs. unnecessary biopsy
- convicting an innocent vs. freeing a guilty person
- deleting a legitimate post vs. leaving a harmful one

What we can still compute without priors: how often each class is misclassified, the class error

\epsilon(k) = \sum_{x\colon q(x) \ne k} p(x \mid k)

↑ Bayes decided per $x$ with $p(k \mid x) = p(x \mid k)\,p(k)/p(x)$ , which needs $p(k)$ . Here we fix the true class $k$ and ask how often we are wrong: only $p(x \mid k)$ .

Non-Bayesian problems: choose

q

by a rule on the

\epsilon(k)

, not on

\sum_k p(k)\,\epsilon(k)

.

Three non-Bayesian formulations

Neyman–Pearson

1 = dangerous, 2 = normal (smoke detector: fire / no fire). Missing a danger is $\epsilon(1)$ , a false alarm is $\epsilon(2)$ .

q^* = \operatorname*{argmin}_{q\colon X \to K}\ \underbrace{\epsilon(2)}_{\text{false alarms}}

\text{s.t.}\ \underbrace{\epsilon(1)}_{\text{missed dangers}} \le \bar\epsilon_1

Limit missed dangers, then minimise false alarms. The limit alone is met by "always alarm" ( $\epsilon(1) = 0$ ), useless.

Minimax

Unknown mix (face unlock: how often impostors try is unknown). Make the worst class error as small as possible. In biometrics this is the equal error rate, the usual way to compare systems.

q^* = \operatorname*{argmin}_{q\colon X \to K} \max_{k \in K} \epsilon(k)

\epsilon(k) = \sum_{x\colon q(x) \ne k} p(x \mid k)

Whatever the mix of classes, the total error is at most $\max_k \epsilon(k)$ .

Wald

A reject option without priors or prices. Both errors must stay below $\epsilon$ ; what we cannot decide safely goes to a human (a cheque reader passes unclear amounts to a clerk). Send the clerk as little as possible.

q^* = \operatorname*{argmin}_{q\colon X \to D} \max_{i} \kappa_i

\text{s.t. } \epsilon_1 \le \epsilon,\ \epsilon_2 \le \epsilon

$\kappa_i = \sum_{x\colon q(x) = ?} p(x \mid i)$ : how much of class $i$ the clerk sees. The caps alone are met by "always ?" (no errors, all work for the clerk).

None of them needs $p(k)$ or $W$ . Neyman–Pearson examples are in the lecture; today: minimax.

Quick check

Reject option, $\varepsilon = 0.2$ . For some $x$ , $\max_k p(k \mid x) = 0.7$ . Decide…

Rule: answer a class only if $1 - \max_k p(k \mid x) < \varepsilon$ . Here $1 - 0.7 = 0.3 \ge 0.2$ .

Which formulation needs the priors $p(k)$ ?

The non-Bayesian ones only use the class errors $\epsilon(k)$ , built from $p(x \mid k)$ .

$q_a$ : $\epsilon(1) = 0.10$ , $\epsilon(2) = 0.30$ . $q_b$ : $\epsilon(1) = \epsilon(2) = 0.25$ . Minimax prefers…

Compare the worst errors: $\max = 0.30$ for $q_a$ , $0.25$ for $q_b$ . The smaller worst case wins, even though $q_a$ has the smaller average.

Part III

Exercises

Discrete minimax: female or male?

$x = (h, w)$ : height bin $h_1$ – $h_3$ , weight bin $w_1$ – $w_4$ . Classes: 1 = female, 2 = male.

$p(x \mid 1)$ , female

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	.197	.145	.094	.017
$h_2$	.077	.299	.145	.017
$h_3$	.001	.008	.000	.000

$p(x \mid 2)$ , male

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	.011	.005	.011	.011
$h_2$	.005	.071	.408	.038
$h_3$	.002	.014	.255	.169

Task: find the minimax strategy

q\colon X \to \{1, 2\}

and its worst class error.

Hint: there are $2^{12} = 4096$ strategies. Which ones are worth trying?

Three strategies to start with

Question: what is the worst class error of each? $\epsilon(k) = \sum_{x\colon q(x) \ne k} p(x \mid k)$

Everyone male

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	M	M	M	M
$h_2$	M	M	M	M
$h_3$	M	M	M	M

\epsilon(1) = 1

,

\epsilon(2) = 0

worst: 1.000

every woman is wrong, every man right

Everyone female

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	F	F	F	F
$h_2$	F	F	F	F
$h_3$	F	F	F	F

\epsilon(1) = 0

,

\epsilon(2) = 1

worst: 1.000

every man is wrong, every woman right

Light = female, heavy = male

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	F	F	M	M
$h_2$	F	F	M	M
$h_3$	F	F	M	M

\epsilon(1) = 0.273

,

\epsilon(2) = 0.108

worst: 0.273

women called male ( $w_3, w_4$ ): $0.094 + 0.017 + 0.145 + 0.017$

The extremes have worst error 1. A sensible split gets 0.273. How low can we go, and which of the 4096 splits should we try?

Discrete minimax: which strategies to try?

↓ How male-like is a cell compared with female-like? The likelihood ratio:

r(x) = \frac{p(x \mid M)}{p(x \mid F)}

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	0.056	0.034	0.117	0.647
$h_2$	0.065	0.237	2.814	2.235
$h_3$	2.000	1.750	∞	∞

↓ Sort the cells by $r$ , largest first (rank 1 = most male-like):

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	11	12	9	7
$h_2$	10	8	3	4
$h_3$	5	6	2	1

↓ Give the $i$ lowest-ranked cells to class 2 (male), the rest to class 1 (female). Taking a cell out of order costs more error for the same gain, so the best strategies follow this order (exactly so once we may randomise one boundary cell).

13 candidates:

i = 0, 1, \dots, 12

. This is the search the assignment asks for.

Continuous minimax I

Two classes, $x \in [-1, 1]$ :

p(x \mid 1) = |x|, \qquad p(x \mid 2) = 1 - |x|

Task: find the minimax strategy

q^* = \operatorname*{argmin}_{q} \max_{k} \epsilon(k)

and its worst error.

\epsilon(k) = \int_{x\colon q(x) \ne k} p(x \mid k)\, dx

Hint: which $x$ look like class 1? The likelihood ratio

r(x) = \frac{p(x \mid 1)}{p(x \mid 2)}, \qquad q(x) = 1 \text{ where } r(x) > \alpha

Try it: move the ratio threshold $\alpha$ (exercise I)

threshold

\alpha

Continuous minimax II

Two classes, $x \in [0, 1]$ :

p(x \mid 1) = 1, \qquad p(x \mid 2) = x + 0.5

Task: find the minimax strategy and its worst error.

Hint: which $x$ look like class 1? The likelihood ratio

r(x) = \frac{p(x \mid 1)}{p(x \mid 2)}, \qquad q(x) = 1 \text{ where } r(x) > \alpha

Question: is the threshold where the two densities cross?

Continuous minimax III: two Gaussians

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

K = \{1, 2\}

:

\mu_1 = -5,\ \sigma_1 = 2

\mu_2 = 1,\ \sigma_2 = 5

Task: find the minimax strategy

q^* = \operatorname*{argmin}_{q} \max_{k} \epsilon(k)

.

Remember: the best strategies are thresholds on the likelihood ratio

r(x) = \frac{p(x \mid 1)}{p(x \mid 2)}, \quad q(x) = \begin{cases} 1 & r(x) > \alpha \\ 2 & r(x) < \alpha \end{cases}

When is $r(x) > \alpha$ for two Gaussians?

↓ Write out both densities:

r(x) = \frac{\frac{1}{\sigma_1 \sqrt{2\pi}} \exp\!\big(-\frac{(x - \mu_1)^2}{2\sigma_1^2}\big)}{\frac{1}{\sigma_2 \sqrt{2\pi}} \exp\!\big(-\frac{(x - \mu_2)^2}{2\sigma_2^2}\big)}

↓ $\sqrt{2\pi}$ cancels; dividing two exponentials subtracts the exponents:

r(x) = \frac{\sigma_2}{\sigma_1} \exp\!\Big(-\frac{(x - \mu_1)^2}{2\sigma_1^2} + \frac{(x - \mu_2)^2}{2\sigma_2^2}\Big)

↓ $\ln$ is increasing and $r, \alpha > 0$ , so $r > \alpha \iff \ln r > \ln\alpha$ . The log undoes the exp:

\ln r(x) = \ln\frac{\sigma_2}{\sigma_1} - \frac{(x - \mu_1)^2}{2\sigma_1^2} + \frac{(x - \mu_2)^2}{2\sigma_2^2}

↓ Expand the squares, collect the powers of $x$ :

\ln r(x) = a x^2 + b x + c

a = \tfrac{1}{2\sigma_2^2} - \tfrac{1}{2\sigma_1^2}, \quad b = \tfrac{\mu_1}{\sigma_1^2} - \tfrac{\mu_2}{\sigma_2^2}

c = \tfrac{\mu_2^2}{2\sigma_2^2} - \tfrac{\mu_1^2}{2\sigma_1^2} + \ln\tfrac{\sigma_2}{\sigma_1}

↓ Our numbers ( $\mu_1 = -5, \sigma_1 = 2$ ; $\mu_2 = 1, \sigma_2 = 5$ ):

\ln r(x) = -0.105\,x^2 - 1.29\,x - 2.19

r(x) > \alpha \iff a x^2 + b x + c - \ln\alpha > 0

: a quadratic inequality, at most two roots

t_1, t_2

.

How does a ratio threshold split $x$ ?

↓ From the previous slide: $\ln r$ is a quadratic in $x$ .

\ln r(x) = -\tfrac{(x - \mu_1)^2}{2\sigma_1^2} + \tfrac{(x - \mu_2)^2}{2\sigma_2^2} + \ln\tfrac{\sigma_2}{\sigma_1}

↓ $\sigma_1 < \sigma_2$ : a parabola opening down.

↓ Say 1 above $\ln\alpha$ (here $\alpha = 1$ ): class 1 gets an interval $[t_1, t_2]$ .

↓ Class 1 is wrong in its tails, class 2 inside:

\epsilon(1) = \int_{-\infty}^{t_1}\! p(x \mid 1)\,dx + \int_{t_2}^{\infty}\! p(x \mid 1)\,dx

\epsilon(2) = \int_{t_1}^{t_2} p(x \mid 2)\, dx

Minimax: pick

\alpha

so that

\epsilon(1) = \epsilon(2)

. No closed form: solve numerically.

How do we solve $\epsilon(1) = \epsilon(2)$ numerically?

↓ For one fixed $\alpha$ , everything is computable. Roots of the quadratic:

a x^2 + b x + (c - \ln\alpha) = 0 \;\to\; t_1, t_2

↓ Errors from the normal CDF $\Phi$ (table, or norm.cdf):

\epsilon(1) = 1 - \Big[\Phi\big(\tfrac{t_2 - \mu_1}{\sigma_1}\big) - \Phi\big(\tfrac{t_1 - \mu_1}{\sigma_1}\big)\Big]

\epsilon(2) = \Phi\big(\tfrac{t_2 - \mu_2}{\sigma_2}\big) - \Phi\big(\tfrac{t_1 - \mu_2}{\sigma_2}\big)

↓ Larger $\alpha$ : fewer $x$ say 1, so $\epsilon(1)$ grows and $\epsilon(2)$ shrinks. They cross once.

↓ Bisection: $\alpha = 1$ has $\epsilon(1) < \epsilon(2)$ , $\alpha = 4$ has $\epsilon(1) > \epsilon(2)$ . Try the midpoint, keep the half where the order flips.

$[\alpha_{lo}, \alpha_{hi}]$	$\alpha$	$t_1, t_2$	$\epsilon(1)$	$\epsilon(2)$	keep half
[1, 4]	2.5	−9.00, −3.29	0.218	0.173	lower
[1, 2.5]	1.75	−9.54, −2.74	0.141	0.210	upper
[1.75, 2.5]	2.13	−9.26, −3.03	0.178	0.190	upper
[2.13, 2.5]	2.31	−9.13, −3.16	0.198	0.181	lower
[2.13, 2.31]	2.22	−9.19, −3.09	0.188	0.186	…

\alpha \approx 2.20

: class 1 on

[-9.20, -3.08]

,

\epsilon(1) = \epsilon(2) \approx 0.187

. Each step halves the interval.

The assignment searches over the prior $p(1) = \tfrac{1}{1 + \alpha}$ instead (one number, same idea), with fminbound on $\max_k \epsilon(k)$ .

Try it: move the ratio threshold $\alpha$

threshold

\alpha

Part IV

Minimax and Bayes

Priors exist, but we don't know them

Question: how large can the Bayesian error of a strategy $q$ get, if the priors are unknown?

Error of $q$ (0/1 loss): the mass of all pairs we get wrong.

\epsilon = \sum_{k} \sum_{x\colon q(x) \ne k} p(x, k)

↓ Split $p(x, k) = p(k)\,p(x \mid k)$ ; $p(k)$ does not depend on $x$ , so it leaves the inner sum.

\epsilon = \sum_{k} p(k) \underbrace{\sum_{x\colon q(x) \ne k} p(x \mid k)}_{\epsilon(k)}

↓ $p(k) \ge 0$ and $\sum_k p(k) = 1$ : $\epsilon$ is a convex combination of the $\epsilon(k)$ , so it is at most the largest one (reached with $p(k) = 1$ for that class).

\max_{\text{priors}}\, \epsilon = \max_{k}\, \epsilon(k)

To be safe for every prior, minimise the worst case:

\min_q \max_k \epsilon(k)

.

Minimax = Bayes with unknown priors and the worst prior assumed. Same solution.

Which strategies can be minimax?

Question: do we have to search all strategies, or just a few?

Bayesian strategy for a prior $p(1)$ (lab 2, 0/1 loss): say 1 if

p(x \mid 1)\, p(1) \ge p(x \mid 2)\, p(2)

↓ Divide both sides by $p(x \mid 2)\, p(1) > 0$ :

\frac{p(x \mid 1)}{p(x \mid 2)} \ge \frac{p(2)}{p(1)} = \alpha

↓ Every prior gives one $\alpha$ . Backwards: which prior gives a chosen $\alpha$ ? Use $p(2) = 1 - p(1)$ :

\alpha = \frac{1 - p(1)}{p(1)}

↓ Multiply by $p(1)$ , collect the $p(1)$ terms:

\alpha\, p(1) = 1 - p(1) \;\Rightarrow\; p(1) = \frac{1}{1 + \alpha}

Priors and ratio thresholds match one to one:

p(1) \in (0, 1) \leftrightarrow \alpha \in (0, \infty)

.

The minimax strategy is a ratio threshold, so it is a Bayesian strategy for some prior $c$ :

q^*_{\text{minimax}} = q^*_{\text{Bayes}}\big(p(1) = c\big)

→ Search over one number $p(1)$ , reusing the code from lab 2.

What if the true prior is different?

Design the Bayesian strategy $q_b$ for $p(1) = 0.7$ (exercise III).

Its risk for that prior:

R(q_b) = p(1)\,\epsilon(1) + p(2)\,\epsilon(2)

↓ Two classes: $p(2) = 1 - p(1)$ , so $R$ is a convex combination of $\epsilon(1)$ and $\epsilon(2)$ :

= p(1)\,\epsilon(1) + (1 - p(1))\,\epsilon(2)

↓ Collect the terms with $p(1)$ :

= p(1)\,\big(\epsilon(1) - \epsilon(2)\big) + \epsilon(2)

↓ $q_b$ is fixed, so $\epsilon(1), \epsilon(2)$ are fixed: a straight line in the true prior, $a \cdot p(1) + b$ .

Where is the minimax strategy?

Dots: pick a prior, design its Bayesian strategy (lab 2), compute its risk at that prior. Repeat for a few priors.

Blue: do it for every prior: the Bayes risk curve $R^*(p(1))$ .

Grey: a fixed strategy $q_b$ is a line, never below the blue curve, touching it at its design prior $p_0$ :

R(q_b, p) \ge R^*(p) = \min_q R(q, p), \quad = \text{ at } p = p_0

↑ $R^*$ is the best any strategy can do; $q_b$ is the best at $p_0$ .

Orange: the worst case of $q_b$ over all priors is the higher end of its line, $\max(\epsilon(1), \epsilon(2))$ . Plot it at $p_0$ .

Same for $p_0 = 0.2$ (here the right end is higher), then for every $p_0$ : the orange curve.

Black: the lowest worst case is a flat line. It touches the top of the blue curve.

The minimax prior is the worst prior for Bayes: the one with the largest Bayes risk.

Try it: one strategy, two views

design prior

p(1)

show worst case

\max(\epsilon(1), \epsilon(2))

Why $\epsilon(1) = \epsilon(2)$ ?

Question: the minimax line is flat. What does that say about its class errors?

Risk of a fixed $q$ when the true prior is $p(1)$ (two slides back):

R(q) = p(1) \cdot \big(\epsilon(1) - \epsilon(2)\big) + \epsilon(2)

↓ A tilted line has its maximum at an end, $\max(\epsilon(1), \epsilon(2))$ , larger than at the flat position. Flat means slope 0:

q^* \;\Leftrightarrow\; \epsilon(1) = \epsilon(2)

↓ Put slope 0 into the line:

R(q^*) = p(1) \cdot \underbrace{\big(\epsilon(1) - \epsilon(2)\big)}_{0} + \epsilon(2) = \epsilon(2)

The minimax strategy has the same risk for every prior: it does not care what the prior is.

Quick check

A fixed strategy has $\epsilon(1) = 0.1$ , $\epsilon(2) = 0.3$ . Its risk if $p(1) = 0.5$ ?

$R = p(1)\,\epsilon(1) + p(2)\,\epsilon(2) = 0.5 \cdot 0.1 + 0.5 \cdot 0.3 = 0.2$

The same strategy: its worst risk over all priors?

A line in $p(1)$ , largest at an end: $\max(\epsilon(1), \epsilon(2)) = 0.3$ (at $p(1) = 0$ ).

How does the risk of the minimax strategy change with the true prior?

$\epsilon(1) = \epsilon(2) = \epsilon$ , so $R = p(1)\,\epsilon + (1 - p(1))\,\epsilon = \epsilon$ for every prior: a flat line.

Quick check: minimax or Bayes?

Is the minimax strategy the Bayesian strategy for equal priors $p(1) = p(2)$ ?

It is the Bayesian strategy for the worst prior $c$ . That is $0.5$ only in special cases, e.g. a symmetric problem like exercise I. In exercises II and III it is not.

The true priors are equal. Which strategy has the smaller error?

Bayes is optimal for the prior it was designed for. Minimax pays for being safe under every prior (unless $c = 0.5$ ).

Implementing the discrete search

Question: how do we get $\epsilon(1), \epsilon(2)$ for all thresholds without a loop over strategies?

Flatten both tables $p(x \mid 1)$ , $p(x \mid 2)$ to vectors of length $N$ (21 × 21 = 441).
Ratio $r = p(x \mid 1) / p(x \mid 2)$ per cell. $0/0$ = NaN: treat as class 1 (assignment rule).
Sort cells by $r$ , largest first (most class-1-like): np.argsort, reversed.
Strategy $i$ : first $i$ sorted cells say 1, the rest 2; $i = 0, \dots, N$ ( $N + 1$ strategies).
$i^* = \operatorname{argmin}_i \max(\epsilon_1[i], \epsilon_2[i])$ ; map back to the 21 × 21 grid with the sort order.

↓ Moving from $i$ to $i + 1$ moves one cell to class 1: running sums give all errors at once.

\epsilon_2[i] = \sum_{j < i} p_2[\text{sorted}_j], \qquad \epsilon_1[i] = 1 - \sum_{j < i} p_1[\text{sorted}_j]

np.cumsum with a 0 prepended: arrays of length $N + 1$ .

Our table slide used

p(x \mid 2)/p(x \mid 1)

largest first (male side first): the same list from the other end. Cells with equal

r

may come in any order.

Take-away for the lab

Discrete

minimax_strategy_discrete: sort cells by the likelihood ratio, try every index $i$ , keep the smallest $\max(\epsilon(1), \epsilon(2))$
classify_discrete: apply the strategy to test images

Continuous (Gaussians)

risk_fix_q_cont: one strategy, all priors: a line
worst_risk_cont: Bayesian strategy for a prior → $\max(\epsilon(1), \epsilon(2))$
minimax_strategy_cont: minimise the worst risk over $p(1)$ (fminbound)

Copy the needed lab 2 functions into minimax.py (find_strategy_2normal, bayes_risk_2normal, classify_2normal); don't import them.

Optional

Extra: Neyman–Pearson, Wald, the error plane, games

Neyman–Pearson on the female/male tables

Same tables as the discrete minimax exercise. At most 20 % of class 1 may be misclassified; within that, as few class-2 errors as possible.

q^* = \operatorname*{argmin}_{q}\ \epsilon(2) \quad \text{s.t.}\ \epsilon(1) \le 0.2

Result (try it yourself first):

\epsilon(1) = 0.188

,

\epsilon(2) = 0.103

: the five most female-like cells say 1

$q^*(x)$

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	1	1	1	2
$h_2$	1	1	2	2
$h_3$	2	2	2	2

Neyman–Pearson is a knapsack problem

Question: which cells should we give to class 2?

knapsack	Neyman–Pearson
items	cells $x$ we give to class 2
weight	$p(x \mid 1)$ : adds to $\epsilon(1)$
capacity	$\bar\epsilon_1$
value	$p(x \mid 2)$ : removes from $\epsilon(2)$
greedy order	value / weight $= p(x \mid 2)/p(x \mid 1)$ : the likelihood ratio

Greedy by ratio is optimal if items may be split (fractional knapsack) = randomise one cell. That is the Neyman–Pearson lemma.

Whole cells only (0/1 knapsack): greedy can lose. Example $\bar\epsilon_1 = 0.1$ :

strategy	$\epsilon(2)$
ratio threshold $i$	0.576
best whole cells	0.511
randomised (split one cell)	0.295

The heavy cell $h_2 w_3$ ( $p(x \mid 1) = 0.145$ ) does not fit; whole-cell optimum skips it and packs lighter ones.

Wald on the female/male tables

Now "?" is allowed. Both errors at most $\epsilon = 0.15$ ; within that, as few undecided as possible. Use the likelihood-ratio order: two thresholds.

q^* = \operatorname*{argmin}_{q}\ \max_i \kappa_i \quad \text{s.t.}\ \epsilon_1, \epsilon_2 \le 0.15

Result (try it yourself first):

\epsilon_1 = 0.145

,

\epsilon_2 = 0.130

,

\kappa_1 = 0.017

,

\kappa_2 = 0.038

: one cell is "?"

$q^*(x)$

	$w_1$	$w_2$	$w_3$	$w_4$
$h_1$	1	1	1	1
$h_2$	1	1	2	?
$h_3$	1	1	2	2

One picture for all formulations: the error plane

Each strategy $q$ is a point $(\epsilon(1), \epsilon(2))$ . Grey: all $2^{12} = 4096$ strategies.

● the 13 ratio thresholds; segments between them = randomised strategies. Nothing lies below this boundary.

□ Bayes, $p(1) = 0.5$ : push a line of slope $-p(1)/p(2)$ toward the origin.

◇ Neyman–Pearson: lowest point left of $\epsilon(1) = 0.2$ .

○ Minimax: threshold $i = 4$ (ring); the randomised optimum sits where the boundary crosses the diagonal (0.152).

✗ a whole-cell strategy that is not a threshold, worst error 0.154: better than $i = 4$ , still above the boundary.

Try it: the error plane

prior

p(1)

zoom in (0 to 0.3)

Minimax as a game against nature

Two players: we choose $q$ , nature chooses the prior $p(1)$ . Our loss:

R(q, p) = p(1)\,\epsilon_q(1) + p(2)\,\epsilon_q(2)

We move first, nature answers: $\min_q \max_p R$ = minimax.

Nature moves first, we answer with Bayes: $\max_p \min_q R$ = top of the Bayes-risk hill, the least favourable prior.

Always $\max\min \le \min\max$ . Equal (a saddle point) once $q$ may be randomised: von Neumann's minimax theorem.

	$\min_q \max_p$	$\max_p \min_q$
Gaussians (ex. III)	0.187	0.187
discrete, thresholds	0.162	0.152
discrete, whole cells	0.154
discrete, randomised	0.152

Minimax strategy = Bayes strategy for the least favourable prior.

\epsilon(1) = \epsilon(2)

makes nature indifferent: every prior gives the same loss.

Minimax

Test next week

Recap

Warm-up quiz: Bayes from lab 2

The Bayesian decision problem

Name the parts: two more examples

Bayesian strategy with a reject option

Non-Bayesian decision problems

When can't we use the Bayesian formulation?

Three non-Bayesian formulations

Quick check

Exercises

Discrete minimax: female or male?

Three strategies to start with

Discrete minimax: which strategies to try?

Continuous minimax I

Try it: move the ratio threshold α\alphaα (exercise I)

Continuous minimax II

Continuous minimax III: two Gaussians

When is r(x)>αr(x) > \alphar(x)>α for two Gaussians?

How does a ratio threshold split xxx?

How do we solve ϵ(1)=ϵ(2)\epsilon(1) = \epsilon(2)ϵ(1)=ϵ(2) numerically?

Try it: move the ratio threshold α\alphaα

Minimax and Bayes

Priors exist, but we don't know them

Which strategies can be minimax?

What if the true prior is different?

Where is the minimax strategy?

Try it: one strategy, two views

Why ϵ(1)=ϵ(2)\epsilon(1) = \epsilon(2)ϵ(1)=ϵ(2)?

Quick check

Quick check: minimax or Bayes?

Implementing the discrete search

Take-away for the lab

Extra: Neyman–Pearson, Wald, the error plane, games

Neyman–Pearson on the female/male tables

Neyman–Pearson is a knapsack problem

Wald on the female/male tables

One picture for all formulations: the error plane

Try it: the error plane

Minimax as a game against nature

Try it: move the ratio threshold $\alpha$ (exercise I)

When is $r(x) > \alpha$ for two Gaussians?

How does a ratio threshold split $x$ ?

How do we solve $\epsilon(1) = \epsilon(2)$ numerically?

Try it: move the ratio threshold $\alpha$

Why $\epsilon(1) = \epsilon(2)$ ?