next up previous
Next: Markov Blanket [4 P] Up: MLA_Exercises_2007 Previous: Curse of Dimensionality [2*

Bayes' Decision Theory [5+2* 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)
[3+2* 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.  [2* 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: Markov Blanket [4 P] Up: MLA_Exercises_2007 Previous: Curse of Dimensionality [2*
Haeusler Stefan 2007-12-03