The input $X \in \{0, 1\}$ and label $T \in \{0,1\}$ are binary random variables, and the set of predictors that we consider are the functions $y : \{0, 1\} \rightarrow \{0, 1\}$. Recall the $0$-$1$ loss when predicting $t$ with $y(x)$,
\begin{equation*} L_{0-1}(y(x), t) = \begin{cases} 0 & \text{if}~~ y(x) = t, \\ 1 & \text{if}~~ y(x) \neq t \\ \end{cases} \end{equation*} and recall the definition of the expected error, \begin{equation*} \mathcal{R}\big[y\big] = E\big[L_{0-1}(y(X), T)\big] = \sum_{t\in\{0,1\}}\sum_{x\in\{0,1\}}L_{0-1}(y(x), t) \cdot P(X=x,T=t) \end{equation*} Assume that $P(X = x) > 0$ for all $x\in\{0,1\}$.

Assuming that $P(T=0|X=0) \neq P(T=1|X=0)$ and $P(T=0|X=1) \neq P(T=1|X=1)$, prove that \begin{equation*} y^*(x) = \text{arg}~~~\min_{t\in\{0,1\}}~~~P(T=t|X=x) \end{equation*} is the unique optimal predictor.
(In other words, prove that $\mathcal{R}\big[y^*\big] \leq \mathcal{R}\big[y\big]$ with equality only if $y^*(x)=y(x)$ for all $x\in\{0,1\}$.

$\textbf{My Attempt:}$
First, I find out the 4 possible predictors for this question are $y_1(x)=x$, $y_2(x)=1-x$, $y_3(x)=0$ and $y_4(x)=1$
Since, by Bayes Law on conditional probability, I have $P(X=x,T=t) = P(T=t|X=x) \cdot P(X=x)$.
Then, I can find out the expected errors for the 4 possible predictors, where
$\mathcal{R}[y_1] = P(T=1|X=0) \cdot P(X=0) + P(T=0|X=1) \cdot P(X=1)$,
$\mathcal{R}[y_2] = P(T=0|X=0) \cdot P(X=0) + P(T=1|X=1) \cdot P(X=1)$,
$\mathcal{R}[y_3] = P(T=1|X=0) \cdot P(X=0) + P(T=1|X=1) \cdot P(X=1)$,
$\mathcal{R}[y_4] = P(T=0|X=0) \cdot P(X=0) + P(T=0|X=1) \cdot P(X=1)$.

But then I am stuck in finding out $\mathcal{R}[y^*]$ and I don't know how to prove next.
$\textbf{So what should I do to complete the prove ?}$


1 Answer 1


For a given $X=x$, the summation reduces to $$R_X(y)=p_X(x)\sum_{t\in\{0,1\}}L(y(x),t) p_{T|X}(t|x)$$

Here, $p_X(x)$ is constant. If you choose the argmax $t$ of $p_{T|X}(t|x)$, this loss function will be equal to $$R_X^*(y)=p_X(x)\min_t p_{T|X}(t|x))$$ And, this is always smaller than or equal to $R_X(y)$ because only one of the summands is non-zero and therefore the expression is either $p_X(x)\min_t p_{T|X}(t|x)$ or $p_X(x)\max_t p_{T|X}(t|x)$. Since this is true for all $x$, the overall expression is minimum when we choose argmax of the conditional probability. It's unique because in every choice it chooses the minimum term in the sum, and any other choice will end up with a larger loss (since there is no equality in conditional probabilities as you mentioned.

P.S. I'm not inline with you about the four possible predictors.


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.