$6$ Risk Minimization with Doubt

Suppose we have a classification problem with classes labeled $1,$dots,c and an additional "doubt"

category labeled c$+1.$ Let f:R$^($d$)->\{1,$dots,c$+1\}$ be a decision rule. Define the loss function

L$($f$($x$),$y$)=\{(0$ if f$($x$)=$y$,$f$($x$)$in$\{1,$dots,c$\},),(\backslash$lambda $\_($c$)$ if f$($x$)!=$y$,$f$($x$)$in$\{1,$dots,c$\}),(\backslash$lambda $\_($d$)$ if f$($x$)=$c$+1)$:$\}$

where $\backslash$lambda $\_($c$)>=0$ is the loss incurred for making a misclassification and $\backslash$lambda $\_($d$)>=0$ is the loss incurred for

choosing doubt. In words this means the following:

When you are correct, you should incur no loss.

When you are incorrect, you should incur some penalty $\backslash$lambda $\_($c$)$ for making the wrong choice.

When you are unsure about what to choose, you might want to select a category correspond$-$

ing to "doubt" and you should incur a penalty $\backslash$lambda $\_($d$).$

In lecture, you saw a definition of risk over the expectation of data points. We can also define the

risk of classifying a new individual data point x as class f$($x$)$in$\{1,2,$dots,c$+1\}$ :

R$($f$($x$)|$x$)=\backslash$sum$\_($i$=1)^$c L$($f$($x$),$i$)$P$($Y$=$i$|$x$)$

$($a$)$ First, we will simplify the risk function using our specific loss function separately for when

f$($x$)$ is or is not the doubt category.

i$.$ Prove that R$($f$($x$)=$i$|$x$)=\backslash$lambda $\_($c$)(1-$P$($Y$=$i$|$x$))$ when ii$!=$c$+1.$

ii$.$ Prove that R$($f$($x$)=$c$+1|$x$)=\backslash$lambda $\_($d$).$

$($b$)$ Show that the following policy f$\_($opt $)($x$)$ obtains the minimum risk:

$($R$1)$ Find the non$-$doubt class i such that P$($Y$=$i$|$x$)>=$P$($Y$=$j$|$x$)$ for all j$,$ meaning

you pick the class with the highest probability given x $.$

$($R$2)$ Choose class i if P$($Y$=$i$|$x$)>=1-(\backslash$lambda $\_($d$))/(\backslash$lambda $\_($c$))$

$($R$3)$ Choose doubt otherwise.

Hint: In order to prove that f$\_($opt $)($x$)$ minimizes risk, consider proof techniques that show that

f$\_($opt $)($x$)$ "stays ahead" of all other policies that don't follow these rules. For example, you could

take a proof$-$by$-$contradiction approach: assume there exists some other policy, say f$^(\text{'})($x$),$ that

minimizes risk more than f$\_($opt $)($x$).$ What are the scenarios where the predictions made by f$\_($opt $)($x$)$

and f$^(\text{'})($x$)$ might differ? In these scenarios, and based on the rules above that f$\_($opt $)($x$)$ follows,

why would f$^(\text{'})($x$)$ not be able to beat f$\_($opt $)($x$)$ in risk minimization?

$($c$)$ How would you modify your optimum decision rule if $\backslash$lambda $\_($d$)=0?$ What happens if $\backslash$lambda $\_($d$)>\backslash$lambda $\_($c$)?$

Explain why this is or is not consistent with what one would expect intuitively.