3
$\begingroup$

I tried to understand the difference between true and empirical risk by the post in wiki.
There it states that the true risk cannot be computed because the distribution P(x,y) is unknown. My first question is what exactly the distribution P(x,y) means? Does it mean that from the space X and Y we have the cross set (x,y) from X*Y and some of the points do exist in reality and some not i.e. some have a probability of 1 and some 0? Can someone give a explanation maybe with an example?
Some other paper say that the true risk is the loss function over the test data and the empirical risk is the loss function over the training data. Is that correct? If yes, how do we extract this from the definition of wiki?

$\endgroup$
2
  • $\begingroup$ In my opinion it is more about the approach to the prediction problem. Statistician or econometrician would specify wellformed stochastic structure to the problem when computer scientist would use approximation methods. Decision tree vs maximum likelihood estimator comes to my mind as an analogy for the situation. $\endgroup$
    – Analyst
    Jun 28, 2018 at 21:01
  • $\begingroup$ That's maybe true. But I want to understand it once from a statistician perspective. $\endgroup$
    – Code Pope
    Jun 29, 2018 at 14:21

1 Answer 1

1
$\begingroup$

The assumption is that there is a data distribution $P(x, y)$ from which the training data are sampled. In risk minimization, we would ideally like to compute $$ \hat{\theta}_{RM} = \arg\min_{\theta} E_P[\mathcal{R}(x, y)] $$ where $\mathcal{R}(x, y)$ is some risk / loss function. However, $P(x, y)$ is unknown - the only thing we have is a dataset $(X_{\text{train}}, y_{\text{train}})$ sampled from that distribution. So the next best thing we can do instead is minimize the expected risk over the empirical distribution of the observed training dataset, $$ p_{\text{emp}}(x, y) = \frac{1}{N} \sum_{i=1}^N \delta(x-x_i)\delta(y-y_i). $$ This is equivalent to solving $$ \hat{\theta}_{ERM} = \arg\min_{\theta} E_{P_{\text{emp}}}[\mathcal{R}(x, y)] = \arg\min_{\theta} \sum_{i=1}^N \mathcal{R}(x_i, y_i). $$ Basically, the difference between $P$ and $P_{\text{emp}}$ is as you say: we only observed a limited number of samples $N$, so $p_{\text{emp}}(x, y)$ might be larger or smaller than $p(x, y)$ in different regions of the data space, including the possibility that we might not observe certain combinations $(x, y)$ at all in the training set (meaning $p_{\text{emp}}(x, y)=0$ for those combinations). However, by the Glivenko-Cantelli theorem (see wiki link above for details), $P_{\text{emp}}$ converges uniformly to $P$ almost surely for growing $N$.

Concerning the test data: first, you would have to assume that those are drawn from the same distribution $P$ as the training data, which is very often not the case. If you indeed assume that, then the empirical risk on the test data will be a better estimate of the true risk than the empirical risk computed on the training data, due to potential overfitting on the latter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.