# Derivation of Bayes classifier in Murphy's book

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}$$.)

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.

• Do you mean that in the expression $\rho(a,x) = \sum_y L(y,a)p(y,x)$ letter $y$ is the sum index that runs all values from label space $\mathcal{Y}$, whereas in the expression $\rho(a|x) = \sum_{y' \neq y}p(y'|x)$ letter $y$ is the unique constant label that is equal to constant $a$ (in that case $1-p(y|x) = 1-p(a|x)$)? I guess that this notation issue is the key. – Rodvi Dec 20 '19 at 21:21
• Agree, most of the difficulty here has to do with notation. Yes, the sum runs over the whole label space, that is why I chose y'. To stress the fact that, with the zero loss, the cost only depends on the true label, and is the same for all actions that do not exactly match the true label. – jpmuc Dec 21 '19 at 9:01

I think the answer to the second question is "yes" and my explanation is the following.

Indeed, $$\displaystyle \operatorname*{argmax}_{a \in \mathcal{A}}{p(a(x)|x)}$$ is a functional maximization task. But the key thing is that $$x$$ in $$p(a(x)|x)$$ is fixed, hence $$a(x)$$ in the expression $$p(a(x)|x)$$ is just some constant number (function value). Using different functions $$a: \mathcal{X} \to \mathcal{Y}$$ from the hypothesis space $$\mathcal{A} = \{a\}$$ on sample $$x$$, we will get different numbers $$\hat y = a(x)$$. Therefore, instead of the hypothesis (function) space $$\mathcal{A} = \{a\}$$, we should do maximization on the number set $$B = \{a(x), \, a \in \mathcal{A}\}$$. Next, we suggest that hypothesis space $$\mathcal{A}$$ is rich enough, hence $$B \equiv \mathcal{Y}$$. So, we have the following maximization task:
$$\operatorname*{argmax}_{\hat y \in \mathcal{Y}}{p(\hat y|x)},$$ which is exactly the task from the aforementioned Mehryar Mohri presentation.
Finally, it is just more convenient to use notation $$y$$ instead of $$\hat y$$, so we get the final expression $$\operatorname*{argmax}_{y \in \mathcal{Y}}{p(y|x)}.$$ Please correct me, if I am wrong. Thanks!

• I edited my previous answer to provide an answer to your second question. Hope is helpful. – jpmuc Dec 21 '19 at 9:30