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=a(x)$ – some classification algorithm (action)):

$\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: enter image description here enter image description here

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


Your Answer

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

Browse other questions tagged or ask your own question.