On error probability bounds in Bayesian hypothesis testing

Question

In the Bayesian version of (binary) hypothesis testing one has to decide which of two hypotheses $A$ and $B$ holds true. The two hypotheses are given prior probability $p(A)$ and $p(B)$, summing up to 1. $A$ and $B$ induce two probability distributions on a set of possible observations $X$, say $p(x|A)$ and $p(x|B)$. One has two decide between $A$ and $B$ after looking at one observation $x$.

It is known that the best strategy, that is the one that minimizes the probability of uncorrect guess, is to choose the hypothesis $H\in\{A,B\}$ that maximizes the $p(H|x)$, where $x$ is the observation. The probability of error (averaged on all $x$ and $H$) can be expressed

$$P_e = 1-\sum_x \max( p(x|A)p(A), p(x|B)p(B))\tag{1}$$

The expression (1) is often regarded as 'intractable' due to the presence of the max operator. Hence tractable bounds are seeked. An example is the harmonic lower-bound

$$P_e \geq E_x[P(A|x)P(B|x)]\tag{2}$$

($E_x$ is expectation over $x$; see e.g. : Routtenberg, Tabrikian, "A General Class of Lower Bounds on the Probability of Error in Multiple Hypothesis Testing", http://arxiv.org/abs/1005.2880, May 2010, and references therein).

My questions:

1) In what sense are expressions like the rhs of (2) "more tractable" than (1)? Computationally, they still require integration over (functions of the) PMF's $p(x|A)$ and $p(x|B)$. Maybe they are more convenient from an analytical point of view?

2) An exact and simple expressions for $P_e$ is:

$$P_e = 1-\frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2\tag{3}$$

(Here $p(\cdot|H)$ is viewed as a vector in $R^{|X|}$, and $||\cdot||_1$ denotes the norm-1).

This is conceptually interesting because it relates probability of error to a distance between PMF's. Is this expression regarded as "intractable" in the same sense as (1)?

M.

Answer 1

It is known that the best strategy, that is the one that minimizes the probability of uncorrect guess, is to choose the hypothesis $H \in \{A,B\}$ that maximizes the $p(H|x)$, where $x$ is the observation.

As a personal peeve, I dislike this particular statement because in my mind it hides what is really going on, and makes what should be obvious rather obscure. Unfortunately, such Olympian pronouncements are what lots of people take away from a course on Bayesian methods....

Suppose that the observation $X$ is a discrete random variable. We observe that the event $\{X = x\}$ has occurred and need to decide choose between $A$ or $B$. But the observed event can be partitioned into $\{X = x, A\}$ and $\{X = x, B\}$ and we have that $$p(x) = p(X=x, A) + p(X=x, B).$$ Now, one of the two events $\{X = x, A\}$ and $\{X = x, B\}$ has occurred. Clearly if we choose $A$ upon observing $\{X = x\}$, we are correct with probability $p(X=x, A)$ and incorrect with probability $p(X=x, B)$ while if we choose $B$ upon observing $\{X = x\}$, we are correct with probability $p(X=x, B)$ and incorrect with probability $p(X=x, A)$. So, the probability of being incorrect in this instance is minimized if we choose $A$ if $p(X=x, B) < p(X=x, A)$ and choose $B$ if $p(X=x, B) > p(X=x, A)$. So, if $E$ and $C$ denote the events of the decision being in error and being correct respectively, we have that if the optimal (minimum-error probability) decision is made upon observing $\{X=x\}$, such occurrences contribute $\max\{p(X=x, A), p(X=x, B)\}$ to $P(C)$, and $\min\{p(X=x, A), p(X=x, B)\}$ to $P(E)$. We have $$\begin{align*} P(E) &= \sum_x \min\{p(X=x, A), p(X=x, B)\}\\ &= 1 - P(C)\\ &= 1 - \sum_x \max\{p(X=x, A), p(X=x, B)\} \end{align*}$$ Since $p(X=x, A) = p(x|A)P(A)$ and $p(X=x, B) = p(x|B)P(B)$, we can write $$\begin{align*} P(E) &= 1 - \sum_x \max\{p(x|A)P(A), p(x|B)P(B)\}\\ &= 1 - \sum_x \max\left\{\frac{p(x|A)P(A)}{p(x)}, \frac{p(x|B)P(B)}{p(x)}\right\}p(x)\\ &= 1 - E_x\left[\max\{P(A|x),P(B|x)\}\right]\\ &= E_x\left[\min\{P(A|x),P(B|x)\}\right] \end{align*}$$ where $E_x$ denotes expectation with respect to $x$. Alternatively, since $$ \max\{p,q\} = \frac{p+q+|p-q|}{2}, $$ we have $$\begin{align*} P(E) &= 1 - \sum_x \max\{p(x,A), p(x,B)\}\\ &= 1 - \sum_x \frac{p(x,A) + p(x,B)+ |p(x,A) - p(x,B)|}{2}\\ &= 1 -\frac{P(A) + P(B)}{2} - \sum_x \frac{|p(x,A) - p(x,B)|}{2}\\ &= 1 - \frac{1 + \sum_x |p(x|A)P(A) - p(x|B)P(B)|}{2}\\ &= 1 - \frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2 \end{align*}$$ as OP Michele writes it. Finally, for $p, q \in [0,1]$, $\min\{p, q\} \geq pq$ and so $$\begin{align*} P(E) &= E_x\left[\min\{P(A|x),P(B|x)\}\right]\\ &\geq E_x\left[P(A|x)P(B|x)\right]. \end{align*}$$

In summary, the three expressions for $P(E)$ appear different but are based on the same fundamental idea. All three require computation of an expectation with respect to $x$, and differ very little in computational complexity. Simplifications can be made if something specific is know about the variables, e.g. $X$ is a geometric random variable with different parameters under the two hypotheses in which case one could compute some sums analytically instead of numerically, but they would appear to apply equally in all three cases. I see very little difference in terms of computational tractability in (1)-(3) as exhibited in the OP's question.

Answer 2

When $p(A) = p(B) = 1/2$, equation $(3)$ is basically computing the total variation distance (also known as the variation distance, for short). The variation distance is an ${\cal L}_1$ distance between two probability measures, which is why the ${\cal L}_1$ norm appears in your equation $(3)$.

It is well-known that the variation distance represents a lower bound on the sum $\Pr[\text{type I error}] + \Pr[\text{type II error}]$ for any hypothesis testing method, and this bound is tight for the hypothesis testing method you described. Therefore, the variation distance measures the minimum achievable error rate of hypothesis testing (again, when $p(A) = p(B) = 1/2$).

However, as you indicated, the variation distance can be difficult to calculate with. It is particularly annoying to deal with, if we might have multiple independent observations from the underlying distribution. Imagine that a referee secretly flips a coin to decide whether to use $A$ or $B$; then gives you $n$ independent draws from $p(x|A)$ (if he is using $A$) or $n$ independent draws from $p(x|B)$ (if he is using $B$), without telling you which. Your job is to decide whether he is using $A$ or $B$. What's the error rate of the optimal decision procedure for $n>1$, and how does it relate to the error rate for the case where $n=1$? This question is difficult to answer. It is not easy to relate the variation distance for the $n$-observation problem (the product measure, where $n>1$) to the variation distance for the single-observation case.

One way that people deal with this in practice is to look at some other distance metric, such as the KL divergence or $\chi^2$ or something, that is well-behaved with product measures: i.e., some distance metric where we can cleanly relate the distance for the $n$-observation case to the $1$-observation case (where we can cleanly relate the distance measure for a product measure to the distance for the underlying distribution). Then, we use some bound that relates that distance metric to the variation distance, and Bob's our uncle.

For more on this theme, read Hypothesis testing and total variation distance vs. Kullback-Leibler divergence and What is the relationship of ${\cal L}_1$ (total variation) distance to hypothesis testing?