Decision theory - reject option

Question

In decision theory, we define a reject option ($\theta$) so that when making decision is difficult, the case will be ignored.

Suppose $1/k \leq \theta \leq1$:

• If $\theta=1/k$ no cases will be rejected

  and

• If $\theta=1$ all cases will be rejected.

Why this happes and how can I prove it for $\theta=1$ and $1/k$?

Section 1.5.3, chapter 1 of Pattern recognition by Bishop: (reject option)

We have seen that classification errors arise from the regions of input space where the largest of the posterior probabilities p(Ck|x) is significantly less than unity, or equivalently where the joint distributions p(x, Ck) have comparable values. These are the regions where we are relatively uncertain about class membership. In some applications, it will be appropriate to avoid making decisions on the difficult cases in anticipation of a lower error rate on those examples for which a classification decision is made. This is known as the reject option. For example, in our hypothetical medical illustration, it may be appropriate to use an automatic system to classify those X-ray images for which there is little doubt as to the correct class, while leaving a human expert to classify the more ambiguous cases. We can achieve this by introducing a threshold θ and rejecting those inputs x for which the largest of the posterior probabilities p(Ck|x) is less than or equal to θ. This is illustrated for the case of two classes, and a single continuous input variable x, in Figure 1.26. Note that setting θ = 1 will ensure that all examples are rejected, whereas if there are K classes then setting θ < 1/K will ensure that no examples are rejected. Thus the fraction of examples that get rejected is controlled by the value of θ.

Answer 1

An input $x$ is rejected if the largest posterior probability $\max_{i=1,\ldots,k}{\rm P}(\mbox{belongs to class } i|x)\leq\theta$.

There are $k$ classes and the probabilities must sum to 1: $$\sum_{i=1}^k{\rm P}(\mbox{belongs to class } i|x)=1.$$ A consequence of this is that $$\max_{i=1,\ldots,k}{\rm P}(\mbox{belongs to class } i|x)\geq 1/k$$ as the sum of probabilities otherwise necessarily must be less than $1$. This means that if $\theta=1/k$ the input is never rejected, since there is at least one posterior probability that is larger than $\theta$.

Similarly, we have that $$\max_{i=1,\ldots,k}{\rm P}(\mbox{belongs to class } i|x)\leq 1$$ with equality only if there are $x$ that only can belong to one class. If no such $x$ can exist, $$\max_{i=1,\ldots,k}{\rm P}(\mbox{belongs to class } i|x)< 1$$ which means that if $\theta=1$ all inputs are rejected, since the maximum posterior probability always is less than $1$.