Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I have 10,000 data in 2-D and I want to fit a curve to them. There are many functional forms this curve could take -- polynomial, B-spline, trigonometric, and so on. I've decided that I only want to use 4 parameters.

Is there a way to figure out what is the most accurate functional form? That is, considering all possible functions with 4 parameters, which one fits the best in, e.g., an $L_2$ sense?

edit: maybe I should ask about the most accurate function with the same V-C dimension as a polynomial of degree 4 rather than "4 parameters"?

share|improve this question
"I've decided that I only want to use 4 parameters." That's the wrong way to approach things, choose the # of parameters via principle (you know the form of the model generating the data), or a data-driven approach (BIC, AIC, cross-validation, etc), not arbitrarily. – benhamner Jun 29 '11 at 4:44
You can do this with zero parameters, because there are many functions that fit the points exactly. (E.g., you can write down a rational polynomial that goes through the points and then, by expanding its integral coefficients as sums and differences, re-express it with no parameters at all.) One solution therefore also penalizes a function for its "complexity." A 1D solver, "Eureqa," is freely available. By fitting functions to the two 2D coordinates separately (in an L2 sense) you can obtain an L2 optimum for the curve. – whuber Jun 29 '11 at 12:58
VC dimension is a property of a class of functions, not of an individual function. For example, take a class that exists of exactly 1 function that fits your data perfectly (such as a polynomial of degree 10,000). Then this will have VC dimension of zero (since for any point we can set the label such that our classifier will get it wrong). Yet you have the minimum possible $L_2$ error. – Simon Byrne Jun 30 '11 at 12:11
@Lao Tzu: that's my whole point: there isn't a "class of functions with VC dimension 4". Any given function can be in a class of any VC dimension you want (even 0 as per my example). – Simon Byrne Jun 30 '11 at 16:52
If you could explain why you wanted a function with four parameters it might help to clarify the issue. – Dikran Marsupial Jul 1 '11 at 13:52

If the aim is to discover the best model with four terms (e.g. polynomial, fourier series, Taylor series) then it is essentially a model selection issue and an optimisation problem, as such it is almost certainly covered by the no-free-lunch theorem, so the model that is most accurate will depend on the particular dataset you have at hand. That means unless the problem is restricted to a particular kind of dataset, there will be no solution better than to fit all the models and find out.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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