Derivation of Bayes classifier in Murphy's book

Question

I am reading Kevin Murphy's Machine Learning book (MLAPP, 1st printing) and want to know how he got the expression for the Bayes classifier using minimization of the posterior expected loss.

He wrote that the posterior expected loss is (eq. 5.101 p.178)

$\rho(a|x) = p(a \neq y | x) \overset{(1)}{=} 1 - p(y|x).$

After that he wrote (eq 5.102):

Hence the action that minimizes the expected loss is the posterior mode or MAP estimate

$\displaystyle y^*(x) = \operatorname*{argmax}_{y \in \mathcal{Y}} p(y|x)$

And I am confused how he got the (1) equality. I tried to derive it and got the following (below $p$ is the conditional pmf of r.v. $Y|X;$ $L$ is the 0-1 loss; $P$ is a probability measure; $a: \mathcal{X} \to \mathcal{Y}$ – some classification algorithm (hypothesis, "action"), $\mathcal{A}$ is a hypothesis space; $\mathcal{Y}$ – output space):

$\displaystyle \rho(a|x) = \mathbb{E}_{Y|X}[L(Y, a(X)] = \sum_{y \in \mathcal{Y}} L(y, a(x)) p(y|x) = \sum_{y \in \mathcal{Y}} \mathbb{I}(y \neq a(x)) p(y|x) = $

$\displaystyle = \sum_{y \neq a(x), \,y \in \mathcal{Y}} p(y|x) = P(Y \neq a(x) | X=x) \overset{(2)}{=} 1-P(Y=a(x)|X=x) = 1-p(a(x)|x)$

Minimizing the posterior expected loss, I got:

$\displaystyle y^*(x) = \operatorname*{argmin}_{a \in \mathcal{A}} \rho(a(x)|x) = \operatorname*{argmin}_{a \in \mathcal{A}}{1-p(a(x)|x)} = \operatorname*{argmax}_{a \in \mathcal{A}}{p(a(x)|x)}.$

And here I have two questions:
1) Do equalities (1) and (2) mean the same thing?

2) Is the following true: $\displaystyle \operatorname*{argmax}_{a \in \mathcal{A}}{p(a(x)|x)} = \operatorname*{argmax}_{y \in \mathcal{Y}} p(y|x)$ ?

---

P.S. After some googling I found one presentation by Mehryar Mohri with the following info:

It looks like that $\hat y \equiv a$ in Murphy notations, so 2) is true. But I still don't sure about this (I am confused that functional maximization on $a \in \mathcal{A}$ is equal to scalar maximization on $y \in \mathcal{Y}$.)

P.P.S. The answer to the first question is "yes" if we assume that $\mathcal{A}$ is the entire function space (i.e. totally unrestricted space of functions), in that case we can move from functional minimization on $a \in \mathcal{A}$ to numeric minimization on $\hat y \in \mathbb{Y}$ (here is a more detailed explanation). Unfortunately, Murphy in his book didn't ever mention about this assumption and it confused me.

Answer 1

The key to answer both question is the definition of 0-1 loss (eq 5.100),

$$ L(y, a) = \left\{ \begin{array}{rl} 0, \text{ if } a = y \\ 1, \text{ if } a \neq y \end{array} \right. $$

where $y$ is the true class label, and $a = \hat{y}$ is the estimate. This means that in the sum

$$ \rho (a|x) = \sum_y L(y, a)p(y|x) $$

only those terms count for which $a \neq y$ count, that is, it is the same as writing $\rho (a|x) = \sum_{y' \neq y}p(y'|x)$, and thus $\rho (a|x) = 1-p(y|x)$.

About your second question. As stated in 5.102, $a$ is an action. In the case of the 0-1 loss is the MAP estimate, a point estimate.

Following the presentation you link to: first it refers to the result we just discussed (MAP estimation under the 0-1 loss is the optimal solution). But notice that the $p(y|x)$ used corresponds to the true data distribution, which is unknown. So how can we, in practice, use this rule?. The idea is to have a model for the probability distribution of the data, based on some assumptions and/or a priori knowledge, and plugin it in, and use as action the one that yields MAP estimate. Again, now according to our model, not the true data distribution. This is the issued listed in the slide titled "ML properties": "the underlying distribution may not be among those searched".

We use the loss to evaluate how well our model matches the unknown distribution.