6
$\begingroup$

Consider domain $X$, label set $ Y=\{0,1\}$ and the zero-one loss.

Given any probability distribution D over $ X\times \{0,1\} $, we've defined the Bayes classifier $ f_D $ to be-

$$ f_{D}(x)= \begin{cases} 1 & \text{if }\mathbb{P}[y=1|x]\geq\tfrac{1}{2}\\ 0 & \text{otherwise.} \end{cases} $$

I wish to prove that, for any classifer $ g\colon X\rightarrow\{0,1\}$, $ L_D(f_D)\leq L_D(g)$, which means that $ f_D$ is optimal.

$L_D(h) $ is defined to be the "true error" of the classifier $h$. That is, $L_D(h)=D\{(x,y)\mid h(x)\not = y\}$.

I'm having some hard time proving this given the definitions above, and some hints/intuition will be appreciated.

$\endgroup$

1 Answer 1

11
$\begingroup$

The true error of a classifier $h$ is $$ \begin{align*} L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \begin{cases} \Pr[y \neq 0|x] & \text{if } h(x) = 0, \\ \Pr[y \neq 1|x] & \text{if } h(x) = 1. \end{cases} \end{align*} $$ (All probabilities are with respect to $D$.)

The optimal classifier is thus the one that minimizes the loss function $$ \phi(x) = \begin{cases} \Pr[y \neq 0|x] & \text{if } h(x) = 0, \\ \Pr[y \neq 1|x] & \text{if } h(x) = 1 \end{cases} $$ for all $x$. We can rewrite the loss function as $$ \phi(x) = \begin{cases} \Pr[y = 1|x] & \text{if } h(x) = 0, \\ 1-\Pr[y = 1|x] & \text{if } h(x) = 1 \end{cases} $$ So if $\Pr[y=1|x] < 1-\Pr[y=1|x]$ we should choose $h(x) = 0$, and if $\Pr[y=1|x] > 1-\Pr[y=1|x]$ we should choose $h(x) = 1$; if $\Pr[y=1|x] = 1-\Pr[y=1|x]$ then the choice doesn't matter.

Finally, $\Pr[y=1|x] < 1-\Pr[y=1|x]$ is the same as $\Pr[y=1|x] < 1/2$, and this explains the formula for $f_D(x)$.

$\endgroup$
3
  • 1
    $\begingroup$ toda. Could you please clarify what $ \phi(x) $ is and why x its input - what is x? $\endgroup$
    – Alex Goft
    Mar 31, 2017 at 11:45
  • $\begingroup$ The function $\phi(x)$ is the probability that the prediction of $h$ on $x$ is wrong. It's a function on $x$, since $h$ only gets to see $x$. $\endgroup$ Mar 31, 2017 at 13:24
  • $\begingroup$ Thanks @YuvalFilmus $\endgroup$ Nov 12, 2019 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.