I am reading "The elements of statistical learning" book by Hastie and have one question about the expected prediction error. He defines it as the following function (section 2.4):
$$\mathrm{EPE}(f) = \mathrm{E}_{X,Y}L(Y,f(X)),$$ where $L$ is a loss function and $f: \mathcal{X} \to \mathcal{Y}$ is a hypothesis.
In case of $L_2$-loss, he wrote that

L2 loss

Similarly, in case of categorical variable $G$, output space $\mathcal{G} = \{\mathcal{G}_1, \ldots, \mathcal{G}_K \}$ and hypothesis $\hat G: \mathcal{X} \to \mathcal{G}$, he wrote:

0-1 loss p.1 0-1 loss p.2

I want to know, is the following expression correct for any loss $L$ (assuming we have some hypothesis space $\mathcal{H} = \{f: \mathcal{X} \to \mathcal{Y} \}$):
$$ f(x) = \operatorname*{argmin}_{f \in \mathcal{H}} \mathrm{E}_{Y|X}[L(Y,f(X))| X=x] = \operatorname*{argmin}_{c \in \mathcal{Y}} \mathrm{E}_{Y|X}[L(Y,c)| X=x], \quad \forall x \in \mathcal{X} ~~?$$ In other words, can we replace functional minimization $(f \in \mathcal{H})$ by scalar minimization $(c \in \mathcal{Y})$ here? It looks like Hastie did this in (2.12) and (2.21), but I'm not sure. He didn't say any words about the hypothesis space...


You have the right idea in spirit, but there is no magic in replacing the functional minimization with a scalar minimization. In particular, the middle part of the equation you wrote, $$ f(x) = \operatorname*{argmin}_{f \in \mathcal{H}} \mathrm{E}_{Y|X}[L(Y,f(X))| X=x], $$ does not type-check, so to speak. The left-hand side is a single point in $\mathcal{Y}$, whereas the right-hand side is a function $f \in \mathcal{H}$, so the equation does not technically make sense.

In Hastie et al.'s formulation, supervised learning is a search for the function $f$ that minimizes the expected loss. This problem can be can be reduced to the task of finding, for each $x \in \mathcal{X}$, the value $$ \operatorname*{argmin}_{c \in \mathcal{Y}} \mathrm{E}_{Y|X}[L(Y,c)| X=x], $$ because this then fully specifies $f$. In practice, this optimization problem is impossible, since we don't know the true conditional distribution of $Y|X$. Instead of a general optimization over the entire function space $\{f: \mathcal{X} \to \mathcal{Y} \}$, we choose a narrowly defined hypothesis class $\mathcal{H}$ (e.g., the set of linear classifiers), and minimize an empirical loss function over a concrete dataset.

  • $\begingroup$ In other words, Hastie replaces task $\displaystyle f^* = \operatorname*{argmin}_{f \in \mathcal{H}} \mathrm{E}_{X,Y}[L(Y,f(X))]$ by the following set of tasks: $\displaystyle f^*(x) = \operatorname*{argmin}_{c \in \mathcal{Y}} \mathrm{E}_{Y|X}[L(Y,c)| X=x], \forall x \in \mathcal{X}$. Well, but can we always be sure that such optimal function $f^*$ (solution of the pointwise task) exists in $\mathcal{H}$? I mean, are there some general requirements on $\mathcal{H}$? Unfortunately, I didn't find information about this in Hastie's book. $\endgroup$
    – Rodvi
    Feb 2 '20 at 8:01
  • 1
    $\begingroup$ I see what your concern is. I've edited my answer to be a little clearer. I think the thing to realize is that Hastie hasn't introduced the notion of a hypothesis class yet, because at this point in the book we're still dealing with an idealization of the learning problem: What should we do if we had perfect information? $\endgroup$
    – tddevlin
    Feb 2 '20 at 19:21
  • $\begingroup$ Thanks for your answer, now these things became a bit clearer for me. But I want to add some thoughts about this topic, which are too long for comment. So I decided to write them in a separate answer below. $\endgroup$
    – Rodvi
    Feb 2 '20 at 21:07

Thanks tddevlin for your answer, now these things became a bit clearer for me. But I want to add some thoughts about this topic, which are too long for comment. So I decided to write them here.

I should note, that instead of using empirical risk we can also simply take the aforementioned "ideal" results
(Kevin Murphy in his book, section 5.7, calls them "Bayes estimators" because they minimize Bayesian posterior expected loss; and there is one subtle thing: Murphy writes that the bayesian estimation is done over some "action space" $\mathcal{A}$, i.e. our hypothesis $f$ is a map $f: \mathcal{X} \to \mathcal{A}$, but as tddevlin pointed out in the post above, we shoold choose $\mathcal{A} \equiv \mathcal{Y}$, i.e. consider the entire function space)
and then just plug-in some estimation of conditional density into them. I mean algorithms such as Naive Bayes classifier. As one more example, Murphy in his book wrote about MMSE gaussian linear regression model: $\hat f(x) = \mathrm{E}[Y|X=x, \mathcal{D}] = x^T \mathrm{E}[w|D], ~ \forall x \in \mathcal{X}$, where we plug-in the posterior mean parameter estimate for $w$.


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.