next up previous
Next: Linear models for regression Up: NNA_Exercises_2009 Previous: Decision Theory I [1*

Decision Theory II [3+1* P]

a)
[2 P] In many pattern classification problems one has the option either to assign the pattern $ \mathtt{x}$ to one of $ c$ classes, or to reject it as being unrecognizable. If the cost for rejects is not too high, rejection may be a desirable action. Suppose that, for a new value of $ \mathtt{x}$ , the true class is $ C_i$ and that we assign $ \mathtt{x}$ to class $ C_j$ . Assume, In doing so, we incur the loss

$\displaystyle L_{ji}= \left\{ \begin{array}{ll} 0, & i=j   i,j=1,...,c  l_r,& j=c+1  l_s, & \text{otherwise} \end{array} \right.$ (1)

where $ l_r$ is the loss incurred for choosing the ($ c$ +1)th action, rejection, and $ l_s$ is the loss incurred for making a substitution error. Show that the minimum risk is obtained if we decide $ C_j$ if $ P(C_j\vert\mathtt{x}) \ge P(C_i\vert\mathtt{x})$ for all $ i$ and if $ P(C_j\vert\mathtt{x}) \ge 1-l_r/l_s$ , and reject otherwise. What happens if $ l_r=0$ ? What happens if $ l_r>l_s$ ?

b)
[1+1* P] Consider the classification problem with rejection option of a).

  1. Use the results of a) to show that the following discriminant functions are optimal for such problems:

    $\displaystyle g_{j}(\mathtt{x})= \left\{ \begin{array}{ll} P(\mathtt{x}\vert C_...
...}{l_s} \sum_{i=1}^c P(\mathtt{x}\vert C_i)P(C_i) & j = c+1. \end{array} \right.$ (2)

  2. Plot these discriminant functions and the decision regions for the two-class one-dimensional case having

    • $ P(x\vert C_1) \sim N(1,1)$ ,
    • $ P(x\vert C_2) \sim N(-1,1)$ ,
    • $ P(C_1)=P(C_2)=1/2$ , and
    • $ l_r/l_s = 1/4$ ,
    where $ N(\mu,\sigma^2)$ denotes the normal distribution with mean $ \mu$ and variance $ \sigma^2$ .
  3. Describe qualitatively what happens as $ l_r/l_s$ is increased from 0 to 1.
  4.  [1* P] Repeat for the case having

    • $ P(x\vert C_1) \sim N(1,1)$ ,
    • $ P(x\vert C_2) \sim N(0,1/4)$ ,
    • $ P(C_1)=1/3,   P(C_2)=2/3$ , and
    • $ l_r/l_s = 1/2.$


next up previous
Next: Linear models for regression Up: NNA_Exercises_2009 Previous: Decision Theory I [1*
Haeusler Stefan 2010-01-19