I am currently practicing decision theory and bayes rule. I want to find the optimal decision given the problem below.

Consider a binary classification problem where we have a pair $(X,Y)$ with $X \in \chi$ and $Y \in \{-1,1\}$. We want to construct a classifier that, given $X$, predicts the label $Y$. The action space is $N = \{-1,1\}$.

I have defined a symmetric zero-one loss function $L(y,a) = I_{\{y \neq a\}}$ where $a$ is an action.

With the given loss function, the posterior risk function becomes $r(\delta|x) = L(-1,\delta (x))p_{Y|X}(-1|x)+L(1|\delta (x))p_{Y|X}(1|x)$

I have continued by rewriting the posterior risk function as

$r(\delta |x) = I_{\{1\neq \delta(x)}\}P(Y=1|X)+I_{\{-1\neq \delta(x)}\}(1-P(Y=1|X))$

From here I am not sure how to proceed. Usually I take the derivative with respect to $\delta$ to find the minimum of the risk function, but as we are working with indicator functions in this problem I am not sure that's the correct procedure.


1 Answer 1


Just note that $$r(\delta|x) = I_{\{1 \neq \delta(x)\}} P(Y = 1 | x) + I_{\{-1 \neq \delta(x)\}} \left( 1 - P(Y = 1 | x) \right) $$ satisfies the inequality $$r(\delta|x) \geq \left(I_{\{1 \neq \delta(x)} + I_{\{-1 \neq \delta(x)\}}\right) \text{min} \left(P(Y = 1|x), 1 - P(Y=1|x) \right)\geq \text{min} \left(P(Y = 1|x), 1 - P(Y=1|x) \right)$$ because $I_{\{1 \neq \delta(x)} + I_{\{-1 \neq \delta(x)\}} \geq 1$. On the other hand, for the classifier $\delta(x)$ which takes the value 1 if $P(Y = 1|x) \geq 1 - P(Y = 1|x)$ and -1 otherwise, the quantity $r(\delta|x)$ precisely equals $\text{min} \left(P(Y = 1|x), 1 - P(Y=1|x) \right)$. This proves the optimality of this classifier.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .