Showing that Bayes classifier is optimal
The true error of a classifier $h$ is
$$
\begin{align*}
L_D(h) &amp;= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &amp;=
\sideset{\mathbb{E}}{}{}_{x,y \sim D}
\begin{cases}
\Pr[y \neq 0|x] &amp; \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] &amp; \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] &amp; \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] &amp; \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] &amp; \text{if } h(x) = 0, \\
1-\Pr[y = 1|x] &amp; \text{if } h(x) = 1
\end{cases}
$$
So if $\Pr[y=1|x] &lt; 1-\Pr[y=1|x]$ we should choose $h(x) = 0$, and if $\Pr[y=1|x] &gt; 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] &lt; 1-\Pr[y=1|x]$ is the same as $\Pr[y=1|x] &lt; 1/2$, and this explains the formula for $f_D(x)$.