Theory

Theory 1 - Binary testing, MAP and ML

Binary hypothesis test

Ingredients of a binary hypothesis test:

• $H_0$ and $H_1$ — Complementary hypotheses
  • Maybe also know the prior probabilities $P[H_0]$ and $P[H_1]$
  • Goal: determine which case we are in, $H_0$ or $H_1$
• $A_0$ and $A_1$ — Complementary events of the Decision Rule
  • Directionality: given $H_0$, $A_0$ is likely; given $H_1$, $A_1$ is likely
  • Decision Rule: outcome $A_0$, accept $H_0$; outcome $A_1$, accept $H_1$
  • Usually: $A_i$ written in terms of decision statistic $X$ using a design
  • We cover three designs:
    • MAP and ML (minimize ‘error probability’)
    • MC (minimizes ‘error cost’)
  • Designs use $P_{X|H_0}$ and $P_{X|H_1}$ (or $f_{X|H_0}$, $f_{X|H_1}$) to construct $A_0$ and $A_1$

MAP design

Suppose we know:

• $P[H_0]$ and $P[H_1]$
  • Both prior probabilities
• $P_{X|H_0}(x)$ and $P_{X|H_1}(x)$ (or $f_{X|H_0}(x)$ and $f_{X|H_1}(x)$)
  • Both conditional distributions

The maximum a posteriori probability (MAP) design for a decision statistic $X$:

$$A_0=\text{set of }x\text{ for which:}$$

Discrete case:

$$P_{X|H_0}(x)\cdot P[H_0]\ge P_{X|H_1}(x)\cdot P[H_1]$$

Continuous case:

$$f_{X|H_0}(x)\cdot P[H_0]\ge f_{X|H_1}(x)\cdot P[H_1]$$

And $A_1=\{x\in ℝ|x\notin A_0\}$.

The MAP design minimizes the total probability of error.

ML design

Suppose we don’t know the priors, we know only:

• $P_{X|H_0}(x)$ and $P_{X|H_1}(x)$ (or $f_{X|H_0}(x)$ and $f_{X|H_1}(x)$)
  • Both conditional distributions

The maximum likelihood (ML) design for $X$:

$$A_0=\text{set of }x\text{ for which:}\begin{array}{cc}{P}_{X|H_0}(x)& \ge P_{X|H_1}(x)\text{(discrete)}\\ & \\ f_{X|H_0}(x)& \ge f_{X|H_1}(x)\text{(continuous)}\end{array}$$

ML is a simplified version of MAP. $$ (Set $P[H_0]$ and $P[H_1]$ to $0.5$.)

---

The false alarm error rate is called $P_{FA}$. The miss error rate is called $P_{\text{Miss}}$.

$$\begin{array}{cc}{P}_{FA}& =P[A_1|H_0]\\ & \\ P_{\text{Miss}}& =P[A_0|H_1]\end{array}$$

Total probability of error:

$$P_{\text{ERR}}=P[A_1|H_0]\cdot P[H_0]+P[A_0|H_1]\cdot P[H_1]$$

Wrong meanings of $P_{FA}$

Suppose $A_1$ sets off a smoke alarm, and $H_0$ is ‘no fire’ and $H_1$ is ‘yes fire’.

Then $P_{FA}$ is the odds that we get an alarm assuming there is no fire.

This is not the odds of experiencing a false alarm (no context). That would be $P[A_1{H}_0]$.

This is not the odds of a given alarm being a false one. That would be $P[H_0|A_1]$.

Theory 2 - MAP criterion proof

Explanation of MAP criterion - discrete case

First, we show that the MAP design selects for $A_0$ all those $x$ which render $H_0$ more likely than $H_1$. This will be used in the next step to show that MAP minimizes probability of error.

Observe this calculation:

$$\begin{array}{cccc}& P[H_i|X=x]& =P[X=x|H_i]\cdot \frac{P[H_i]}{P[X]}& \text{(Bayes’ Rule)}\\ & & & \\ & & =P_{X|H_i}(x)\cdot \frac{P[H_i]}{P[X]}& \text{(Conditional PMF)}\end{array}$$

Recall the MAP criterion:

$$P_{X|H_0}(x)\cdot P[H_0]\ge P_{X|H_1}(x)\cdot P[H_1]$$

Divide both sides by $P[X]$ and apply the above Calculation in reverse:

$$\gg \gg P[H_0|X=x]\ge P[H_1|X=x]$$

This is what we sought to prove.

---

Next, we verify that the MAP design minimizes the total probability of error.

The total probability of error is:

$$P_{\mathrm{ERR}}=P[A_1|H_0]\cdot P[H_0]+P[A_0|H_1]\cdot P[H_1]$$

Expand this with summation notation (assuming the discrete case):

$$\gg \gg \sum _{x\in A_1}{P}_{X|H_0}(x)\cdot P[H_0]+\sum _{x\in A_0}{P}_{X|H_1}(x)\cdot P[H_1]$$

Now, how do we choose the set $A_0\subset ℝ$ (and thus $A_1=A_0^c$) in such a way that this sum is minimized?

Since all terms are positive, and any $x\in ℝ$ may be placed in $A_1$ or in $A_0$ freely and independently of all other choices, the total sum is minimized when we minimize the impact of placing each $x$.

So, for each $x$, we place it in $A_0$ if:

$$P_{X|H_0}(x)\cdot P[H_0]\ge P_{X|H_1}(x)\cdot P[H_1]$$

That is equivalent to the MAP criterion.

Theory 3 - MC design

• Write $C_{10}$ for cost of false alarm, i.e. cost when $H_0$ is true but decided $H_1$.
  • Probability of incurring cost $C_{10}$ is $P_{FA}\cdot P[H_0]$.
• Write $C_{01}$ for cost of miss, i.e. cost when $H_1$ is true but decided $H_0$.
  • Probability of incurring cost $C_{01}$ is $P_{\text{Miss}}\cdot P[H_1]$.

Expected value of cost incurred

$$E[C]=P[A_1|H_0]\cdot P[H_0]\cdot C_{10}+P[A_0|H_1]\cdot P[H_1]\cdot C_{01}$$

MC design

Suppose we know:

• Both prior probabilities $P[H_0]$ and $P[H_1]$
• Both conditional distributions $P_{X|H_0}(x)$ and $P_{X|H_1}(x)$ (or $f_{X|H_0}(x)$ and $f_{X|H_1}(x)$)

The minimum cost (MC) design for a decision statistic $X$:

$$A_0=\text{set of }x\text{ for which:}$$

Discrete case:

$$P_{X|H_0}(x)\cdot P[H_0]\cdot C_{10}\ge P_{X|H_1}(x)\cdot P[H_1]\cdot C_{01}$$

Continuous case:

$$f_{X|H_0}(x)\cdot P[H_0]\cdot C_{10}\ge f_{X|H_1}(x)\cdot P[H_1]\cdot C_{01}$$

Then $A_1=\{x\in ℝ|x\notin A_0\}$.

The MC design minimizes the expected value of the cost of error.

MC minimizes expected cost

Inside the argument that MAP minimizes total probability of error, we have this summation:

$$P_{\mathrm{ERR}}=\sum _{x\in A_1}{P}_{X|H_0}(x)\cdot P[H_0]+\sum _{x\in A_0}{P}_{X|H_1}(x)\cdot P[H_1]$$

The expected value of the cost has a similar summation:

$$E[C]=\sum _{x\in A_1}{P}_{X|H_0}(x)\cdot P[H_0]\cdot C_{10}+\sum _{x\in A_0}{P}_{X|H_1}(x)\cdot P[H_1]\cdot C_{01}$$

Following the same reasoning, we see that the cost is minimized if each $x$ is placed into $A_0$ precisely when the MC design condition is satisfied, and otherwise it is placed into $A_1$.