Avoiding overfitting by averaging polynomials fit to part of the data?

Question

I was thinking about the problem of overfitting data. Suppose you have a hundred data points sampled from an unknown function (call this the training set). You could try fitting a hundred-dimensional polynomial to these points, but even though it fits all the sample points exactly, it probably wouldn't do a good job of fitting other points sampled from the same function (the test set). This is called overfitting the training set. So suppose you were to do this instead: choose ten points from the training set, and fit a ten-dimensional polynomial to them. Then do it again, with another ten random sampled points. Get a bunch of polynomials this way, and take an average of their predictions. Wouldn't that do a better job of avoiding overfitting? Surely someone else has had this idea before. I'm looking for what it is called, so I can read up on it.

Answer 1

The modern approach to avoid overfitting is to be found in Minimum Description Length, based on Bayesian probability (and closely linked with Kolmogorov Complexity). You can learn more about MDL at Wikipedia, Scholarpedia, mdl-research.org, or the wonderful book by Grünwald.

MDL basically gives you a principled way to trade off between model size (i.e. size of the polynomial used) and error.

Answer 2

A slightly more complicated method is called "early stopping." You split the data set into a training set and a validation set, and only train until the error on the validation set stops going down. Then you redivide the data. Repeat.

Answer 3

I doubt if that is a very good idea, but it may be related to "Boosting", which is a kind of comittee method: Use many weak predictors and combine their output. See chapter 10 of Haste, Tibshirani, Friedman: "The Elements of Statistical Learning".

Answer 4

I think the best answer to what I wanted to know was the term "bootstrap aggregating" in the comment by R. Hahn. Thanks!

Answer 5

With a slight variation of the OP's procedure we can obtain the well-known algorithm called RANSAC (random sample consensus).

For each random 10-sample subset from the training set, we fit a 10th-dimensional (9th-order) polynomial, as in the OP's proposal. However, instead of averaging all the resulting polynomial fit predictions, we do the following variation:

For each 10th-dimensional (9th-order) polynomial fit, we check it's prediction of all the other data points in the training set against the actual points using any suitable relevant metric for the problem (such as Euclidean distance). The number of predicted data points (their cardinality) within a given predefined threshold of the relevant metric from the actual data points is calculated. This is called a consensus set.

The 10th-dimensional (9th-order) polynomial fit which has the so-far highest cardinality consensus set is stored. Furthermore, it is customary and beneficial to also store the consensus set, i.e., the locations of the data predictions which fall within the predefined threshold of the relevant metric. (Note that at this stage, we do not know if the other points, whose distance is larger than the threshold, are necessarily outliers, because the model fit could simply be a poor one, i.e., a spurious overfit of the random 10-sample subset.)

After either a predetermined fixed number of random 10-sample subsets have been checked (a fixed number of iterations), or a large enough cardinality consensus set has been reached (a "good enough" fit), the procedure is terminated, i.e., iterating over random 10-sample subsets is terminated. Probabilistic arguments described in the Wikipedia article can be used to determine the probability of estimating the "correct" or sufficiently accurate model fit.

This method has the additional benefit of resilience to a large percentage of outlier measurements in the training set, if such a problem potentially exists in the data.

Addressing the issue of overfit:

• A model fit estimated on the training set, possessing a consensus set with sufficiently high cardinality, directly implies that on the training set, the model discovered does not overfit, i.e., it generalizes well enough from a specific 10-sample subset to a large enough set of unseen data points of the training set.
• It is implicitly assumed that a large enough number of iterations on the training set, or a "good enough" fit on the training set, will indicate good prediction on (generalization to) any held-out test set, whose data points we have not used at all during training.

Although the OP wasn't concerned with the issue of outliers, it deserves mention that typical implementations of the RANSAC method are concerned with outlier detection, so a typical additional final (post-processing) step is to take all points from the best consensus set found at the termination of the procedure, together with the 10-sample subset from the best set (which are considered inliers by definition at the end of the procedure), and use them on the training set with some overdetermined estimation procedure, such as least squares.