16
$\begingroup$

If you fit a non linear function to a set of points (assuming there is only one ordinate for each abscissa) the result can either be:

  1. a very complex function with small residuals
  2. a very simple function with large residuals

Cross validation is commonly used to find the "best" compromise between these two extremes. But what does "best" mean? Is it "most likely"? How would you even start to prove what the most likely solution is?

My inner voice is telling me that CV is finding some sort of minimum energy solution. This makes me think of entropy, which I vaguely know occurs in both stats and physics.

It seems to me that the "best" fit is generated by minimising the sum of functions of complexity and error ie

minimising m where m = c(Complexity) + e(Error)

Does this make any sense? What would the functions c and e be?

Please can you explain using non mathematical language, because I will not understand much maths.

$\endgroup$
  • 1
    $\begingroup$ Best is the model with lowest future error and cross-validation gives you that estimate. The reason for c(Complexity)+e(Error) formulas is because you could use error on training data as estimate of future error, but that's overly optimistic, so you add a term to make this estimate unbiased, which is usually some function of model complexity $\endgroup$ – Yaroslav Bulatov Sep 23 '10 at 14:32
  • $\begingroup$ On the other hand reasoning in light of Runge phenomenon (Physics inspirations again) drives to a conclusion that future error is something about Complexity/Train_Error. $\endgroup$ – user88 Sep 24 '10 at 12:25
  • $\begingroup$ Matt Krause has given an excellent answer to a similar question here: stats.stackexchange.com/a/21925/14640 Paraphrasing from his answer: The goal is to balance model complexity with the model's explanatory power and so the concept of parsimony is a better measure of a model's appropriateness than is the concept of best fit to error. This is because a highly complex model can overfit the data without being better able to predict or explain new results. $\endgroup$ – Assad Ebrahim Oct 20 '12 at 16:20
6
$\begingroup$

I think this is an excellent question. I am going to paraphase it just to be sure I have got it right:

It would seem that there are lots of ways to choose the complexity penalty function $c$ and error penalty function $e$. Which choice is `best'. What should best even mean?

I think the answer (if there is one) will take you way beyond just cross-validation. I like how this question (and the topic in general) ties nicely to Occam's Razor and the general concept of parsimony that is fundamental to science. I am by no means an expert in this area but I find this question hugely interesting. The best text I know on these sorts of question is Universal Artificial Intelligence by Marcus Hutter (don't ask me any questions about it though, I haven't read most of it). I went to a talk by Hutter and couple of years ago and was very impressed.

You are right in thinking that there is a minimum entropy argument in there somewhere (used for the complexity penalty function $c$ in some manner). Hutter advocates the use of Kolmogorov complexity instead of entropy. Also, Hutter's definition of `best' (as far as I remember) is (informally) the model that best predicts the future (i.e. best predicts the data that will be observed in the future). I can't remember how he formalises this notion.

$\endgroup$
  • $\begingroup$ You understand the question. I'll follow the links. $\endgroup$ – bart Sep 22 '10 at 23:09
  • $\begingroup$ You should know that these links are unlikely to take you anywhere `practical'. If you are trying to build something using cross validation (or some other sort of model selection) then in practice it is likely to always come down to something heuristic and a bit ad-hoc (although I agree this is unsatisfying). $\endgroup$ – Robby McKilliam Sep 22 '10 at 23:36
  • $\begingroup$ Now we are getting somewhere. en.wikipedia.org/wiki/Minimum_message_length seems to be what I was thinking. Thanks! $\endgroup$ – bart Sep 22 '10 at 23:48
  • $\begingroup$ No worries. This is just reflection, not practical. $\endgroup$ – bart Sep 22 '10 at 23:50
9
$\begingroup$

I will offer a brief intuitive answer (at a fairly abstract level) till a better answer is offered by someone else:

First, note that complex functions/models achieve better fit (i.e., have lower residuals) as they exploit some local features (think noise) of the dataset that are not present globally (think systematic patterns).

Second, when performing cross validation we split the data into two sets: the training set and the validation set.

Thus, when we perform cross validation, a complex model may not predict very well because by definition a complex model will exploit the local features of the training set. However, the local features of the training set could be very different compared the local features of the validation set resulting in poor predictive performance. Therefore, we have a tendency to select the model that captures the global features of the training and the validation datasets.

In summary, cross validation protects against overfitting by selecting the model that captures the global patterns of the dataset and by avoiding models that exploit some local feature of a dataset.

$\endgroup$
  • $\begingroup$ @Srikant I know all this. CV is a means for finding "best". What is the definition of "best"? $\endgroup$ – bart Sep 22 '10 at 18:13
  • $\begingroup$ @bart 'best model' = a model that 'best' captures global patterns while avoiding local features of a data. That is the best I can do for a non-math description. Perhaps, someone else can elaborate a bit more or be more specific. $\endgroup$ – user28 Sep 22 '10 at 18:15
  • $\begingroup$ @bart: "best" means the the function that fits the training data the best, and that "generalizes" well to the validation/unseen-test set data. I think this is quite clear from Srikant's answer. There are many ways to formally define a good generalization behavior. In a non-formal sense, you can think of it as finding a function that is "smooth" and not much wiggly. Trying to fit solely on the training data may lead to the wiggly looking function whereas smoothness usually ensures that the function will do reasonably well on both training and validation/test data. $\endgroup$ – ebony1 Sep 22 '10 at 18:27
  • $\begingroup$ @ebony: You are missing the point. I've rephrased the question to hopefully make it clearer $\endgroup$ – bart Sep 22 '10 at 18:34
5
$\begingroup$

In a general machine-learning view the answer is fairly simple: we want to build model that will have the highest accuracy when predicting new data (unseen during training). Because we cannot directly test this (we don't have data from the future) we do Monte Carlo simulation of such a test -- and this is basically the idea underneath cross validation.

There may be some issues about what is accuracy (for instance a business client can state that overshoot costs 5€ per unit and undershoot 0.01€ per unit, so it is better to build a less accurate but more undershooting model), but in general it is fairly intuitive per cent of true answers in classification and widely used explained variance in regression.

$\endgroup$
3
$\begingroup$

A lot of people have excellent answers, here is my $0.02.

There are two ways to look at "best model", or "model selection", speaking statistically:

1 An explanation that is as simple as possible, but no simpler (Attrib. Einstein)

- This is also called Occam's Razor, as explanation applies here.
- Have a concept of True model or a model which approximates the truth
- Explanation is like doing scientific research


2 Prediction is the interest, similar to engineering development.

- Prediction is the aim, and all that matters is that the model works
- Model choice should be based on quality of predictions
- Cf: Ein-Dor, P. & Feldmesser, J. (1987) Attributes of the performance of central processing units: a relative performance prediction model. Communications of the ACM 30, 308–317.

Widespread (mis)conception:

Model Choice is equivalent to choosing the best model

For explanation we ought to be alert to be possibility of there being several (roughly) equally good explanatory models. Simplicity helps both with communicating the concepts embodied in the model and in what psychologists call generalization, the ability to ‘work’ in scenarios very different from those in which the model was studied. So there is a premium on few models.

For prediction: (Dr Ripley's) good analogy is that of choosing between expert opinions: if you have access to a large panel of experts, how would you use their opinions?

Cross Validation takes care of the prediction aspect. For details about CV please refer to this presentation by Dr. B. D. Ripley Dr. Brian D. Ripley's presentation on model selection

Citation: Please note that everything in this answer is from the presentation cited above. I am a big fan of this presentation and I like it. Other opinions may vary. The title of the presentation is: "Selecting Amongst Large Classes of Models" and was given at Symposium in Honour of John Nelder's 80th birthday, Imperial College, 29/30 March 2004, by Dr. Brian D. Ripley.

$\endgroup$
3
$\begingroup$

Great discussion here, but I think of cross-validation in a different way from the answers thus far (mbq and I are on the same page I think). So, I'll put in my two cents at the risk of muddying the waters...

Cross-validation is a statistical technique for assessing the variability and bias, due to sampling error, in a model's ability to fit and predict data. Thus, "best" would be the model which provides the lowest generalization error, which would be in units of variability and bias. Techniques such as Bayesian and Bootstrap Model Averaging can be used to update a model in an algorithmic way based upon results from the cross validation effort.

This FAQ provides good information for more context of what informs my opinion.

$\endgroup$
1
$\begingroup$

The error function is the error of your model (function) on the training data. The complexity is some norm (e.g., squared l2 norm) of the function you are trying to learn. Minimizing the complexity term essentially favors smooth functions, which do well not just on the training data but also on the test data. If you represent your function by a set of coefficients (say, if you are doing linear regression), penalizing the complexity by the squared norm would lead to small coefficient values in your function (penalizing other norms leads to different notions of complexity control).

$\endgroup$
1
$\begingroup$

From an optimization point of view, the problem (with $(p,q)\geq 1,\;\lambda>0$),

$(1)\;\underset{\beta|\lambda,x,y}{Arg\min.}||y-m(x,\beta)||_p+\lambda||\beta||_q$

is equivalent to

$(2)\;\underset{\beta|\lambda,x,y}{Arg\min.}||y-m(x,\beta)||_p$

$s.t.$ $||\beta||_q\leq\lambda$

Which simply incorporates unto the objective function the prior information that $||\beta||_q\leq\lambda$. If this prior turns out to be true, then it can be shown ($q=1,2$) that incorporating it unto the objective function minimizes the risk associated with $\hat{\beta}$ (i.e. very unformaly, improves the accuracy of $\hat{\beta}$)

$\lambda$ is a so called meta-parameter (or latent parameter) that is not being optimized over (in which case the solution would trivially reduce to $\lambda=\infty$), but rather, reflects information not contained in the sample $(x,y)$ used to solve $(1)-(2)$ (for example other studies or expert's opinion). Cross validation is an attempt at constructing a data induced prior (i.e. slicing the dataset so that part of it is used to infer reasonable values of $\lambda$ and part of it used to estimate $\hat{\beta}|\lambda$).

As to your subquestion (why $e()=||y-m(x,\beta)||_p$) this is because for $p=1$ ($p=2$) this measure of distance between the model and the observations has (easely) derivable assymptotical properties (strong convergence to meaningfull population couterparts of $m()$).

$\endgroup$
  • 1
    $\begingroup$ Is $\lambda$ a parameter that is free to be chosen? $\endgroup$ – Robby McKilliam Sep 22 '10 at 21:49
  • $\begingroup$ @Robby:> thanks. I slightly appended the text to make the distinction between parameters and hyperparameters clear. $\endgroup$ – user603 Sep 22 '10 at 22:12
  • $\begingroup$ @kwak: I'm sorry to say I haven't a clue what this means. What do the symbols p, q, lambda, x, y, m and beta signify? $\endgroup$ – bart Sep 22 '10 at 23:05
  • $\begingroup$ @bart:> My answer is essentially the same as Srikant's. Where he provides an intuitive explication, I wanted to add a more rigorous one for the benefits of future visitors that may have the same question as you, but are more familliar with math than non-formal language. All the symbols you mention are defined in my answer (altough, again, this is done formally). $\endgroup$ – user603 Sep 22 '10 at 23:35
  • $\begingroup$ @kwak: Where, for example, is p defined? $\endgroup$ – bart Sep 22 '10 at 23:54

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.