23
$\begingroup$

In the text books and youtube lectures I learned a lot about iterative models such as boosting, but I never saw anything about deriving a prediction interval.

Cross validation is used for the following:

  • Model selection: Try different models and choose the one that fits best. In the case of boosting, use CV to select tuning parameters.
  • Model assessment: Estimate the performance of the selected model

Several parameters are important of the model assessment, one of them is the expected prediction error. Cross validation provides a good estimate of the prediction error, as well described in the book "The Elements of Statistical Learning".

But how do we use the expected prediction error to build a prediction interval?

And if you predict the price of a house for example, the prediction interval will be higher for a house of 500.000€ compared to a house of 200.000€. How do we estimate these prediction intervals using cross validation?

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
3
$\begingroup$

After reading over this question again, I can give you the following bound:

Assume the samples are drawn iid, the distribution is fixed, and the loss is bounded by $B$, then with probability at least $1 - \delta$, $$ \mathbb{E}[\mathcal{E}(h)] \leq \hat{\mathcal{E}}(h) + B\sqrt{\frac{\log \frac{1}{\delta}}{2m}} $$

where $m$ is the sample size, and $1-\delta$ is the confidence. The bound holds trivially by McDiarmid's inequality.

$m$ is the sample size, $\mathbb{E}[\mathcal{E}(h)]$ is the generalization error, and $\hat{\mathcal{E}}(h)$ is the test error for hypothesis.

Please don't report only the cross validation error nor the test error, those are meaningless in general since they are just point estimates.

Old post for record:

I'm not sure that I completely understood your question, but I will take a stab at it.

First, I am not sure how you would define a prediction interval for model selection, since, as I understand it, prediction intervals make some distributional assumptions. Instead, you could derive concentration inequalities, which essentially bound a random variable by its variance for some probability. Concentration inequalities are used throught machine learning, including the advanced theory for boosting. In this case you want to bound the generalization error (your error in general, points you haven't seen) by your empirical error (your error on the test set) plus some complexity term and a term that relates to the variance.

Now I need to dispell a misunderstanding about cross validation that is extremely common. Cross validation will only give you an unbiased estimate of the expected error of a model FOR A FIXED SAMPLE SIZE. The proof for this only works for the leave one out protocol. This is actually fairly weak, since it gives you no information regarding the variance. On the other hand, cross validation will return a model that is close to the structural risk minimization solution, which is the theoretically best solution. You can find the proof in the appendix here: http://www.cns.nyu.edu/~rabadi/resources/scat-150519.pdf

So how to derive a generalization bound? (Remember a generalization bound is basically a prediction interval about the generalization error for a specific model). Well, these bounds are algorithm specific. Unfortunately there is only one textbook that puts bounds for all of the commonly used algorithms in machine learning (including boosting). The book is Foundations of Machine Learning (2012) by Mohri, Rostamizadeh, and Talwalkar. For lecture slides that cover the material, you can find them on Mohri's web-page: http://www.cs.nyu.edu/~mohri/ml14/

While Elements of Statistical Learning is an important and somewhat helpful book, it is not very rigorous and it omits many very important technical details regarding the algorithms and completely omits any sort of generalization bounds. Foundations of Machine Learning is the most comprehensive book for machine learning (which makes sense seeing as it was written by some of the best in the field). However, the textbook is advanced, so just beware of technical details.

The generalization bound for boosting can be found (with proof) here: http://www.cs.nyu.edu/~mohri/mls/lecture_6.pdf

I hope those are enough pointers to answer your question. I'm hesitant about giving a complete answer because it will take about 50 pages to go over all of the necessary details, let alone the preliminary discussions...

Good luck!

Improve this answer
$\endgroup$
5
  • $\begingroup$ So if I understand well, this gives an upper bound for the generalization error for any quantile, over the whole distribution (based on some assumptions). However I do not understand your sentence "Please don't report either the cross validation error nor the test error". Do you mean these two measures are useless or are they just useless to try to find a prediction interval? $\endgroup$
    – LouisBBBB
    Feb 20, 2017 at 10:38
  • $\begingroup$ @LouisBBBB CV error and test error are sort of like reporting a sample mean. It's typically bad practice to report the sample mean without some sort of confidence interval because every time I run the experiment I will get a different result. I said meaningless, but maybe "useless" is better... One could argue that there is some meaning in a point estimate (i.e., the definition). But point estimates, in general, are "useless" in the sense that they don't characterize the distribution of error in a "useful way." "Useful" in the context of making decisions. $\endgroup$
    – justanotherbrain
    Feb 21, 2017 at 12:55
  • $\begingroup$ I think I understand what you say. So you prefer analyzing the distribution of errors instead of the mean. And if I go back to the question, Kasper wanted estimates of prediction intervals "per point". Your answer was a global upper bound for the prediction interval length (or something close), is that right? So do you know a way to get a local upper bound? $\endgroup$
    – LouisBBBB
    Feb 21, 2017 at 13:29
  • $\begingroup$ Ah - thanks for clarifying. I think I misunderstood @Kasper's question and have a lot of follow up questions. Thanks for pointing this out, I'll do some digging. $\endgroup$
    – justanotherbrain
    Feb 21, 2017 at 13:34
  • $\begingroup$ Not that this is particularly important, but I think Elements of Statistical Learning was also written by some of the best in the field. Perhaps the two books you are contrasting have different target audience and cover different material. $\endgroup$
    – Richard Hardy
    Dec 31, 2019 at 8:59

Your Answer

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

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