4
$\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$
4
$\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$
  • $\begingroup$ toda. Could you please clarify what $ \phi(x) $ is and why x its input - what is x? $\endgroup$ – Alex Goft Mar 31 '17 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$ – Yuval Filmus Mar 31 '17 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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