What is the definition of "best" as used in the term "best fit" and cross validation?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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