What might be the simplest (least flexible, least expressive) model to avoid over-fit?

Question

I need to perform a regression on a data set with a huge noise-to-signal ratio. I am not even sure if there is any "signal" in the data (maybe there is only "noise" in the data), meaning that it might be the case that distribution of targets does not depend on my features at all.

So, in this case I need to work with very simple models but I am afraid that even linear regression is to complex for me. For example, if I have 20 features, I do not believe that I can reliably extract 20+1 parameters from my data.

To simplify my model further, I search a linear function that only depends only on one of my 20 features. However, I am not sure that this is the best way to go.

So, my question is, if there a class of even simpler (less flexible, less expressive) models that are suitable for fitting very very noisy data?

My intuition goes as follows. If we have a logical statement like: "A and B and C", we can simplify it to "A and B" and then we can simplify it to "A". At this point we might think that we cannot say less than just "A" but we are wrong! We can say even less, namely "A or K" or even less: "A or K or L or M".

Answer 1

Use ridge regression. The ridge parameter is a control on the complexity of the model class. Ridge regression is equivalent to fitting a regression model with a constraint on the norm of the weight vector, where the constraint depends on the value of the ridge parameter. If you reduce the ridge parameter slightly, this raises the maximum norm of the weights of the model class slightly, so it can realise any linear function that it could previously realise, and also some more linear functions that require a slightly greater norm. This means ridge regression provides a nested set of model classes of increasing complexity, indexed by the ridge parameter. That is why it is effective in avoiding over-fitting.

I explain the connection between regularisation (as used in ridge regression) and constrained optimisation in my answer to another question.

Answer 2

You can try to apply feature selection. Linear models are already the simplest functional form that you can choose, but techniques like LASSO, non-negative garrote and other penalized/restricted estimation methods try to reduce dimensions, keeping only the most "worthy" covariables of the model. Penalized least squares has the following objective function,

$$g(\beta;\lambda) = ||Y-X\beta||_2^2 + \lambda||\beta||_k$$ $$\hat{\beta}_{PLS} = \arg\min_{\beta\in \mathbb{R}^p} g(\beta,\lambda)$$

such that the model becomes the LASSO when $k=1$ or the ridge regression when $k=2$. There are multiple extensions that apply less common penalties or work with different values of $\lambda$ for each variable, that is also a multitude of side-methods to choose the $\lambda$.

If your data matrix is close to singularity, then ridge ($L^2$ penalty) is a good option. If your interesting in feature selection, then LASSO is the way to go ($L^1$ penalty). Elastic net is a convex combination between penalties and gives better estimates in some cases, $\alpha||\beta||_1 + (1-\alpha)||\beta||_2^2$.

Another option that is similar to the LASSO is the Dantzig selector and I will leave the article by Terence Tao that gives a pretty good explanation:

https://terrytao.wordpress.com/2008/03/22/the-dantzig-selector-statistical-estimation-when-p-is-much-larger-than-n/

EDIT

As I said in the comments, there's a duality between penalties and restrictions over the parameter space of the form $||\beta||_k \leq C$, I'm adding an image that illustrates the $L^p$-balls for various $p$s,

Shrinkage estimation is a huge research area and there are lots of results that show that penalized estimators often have smaller risk (expected loss) than common procedures, specially in high $p$, low $n$ situations. Just for curiosity, take a look at the James-Stein estimator.

If you want a model with only one covarible as you mentioned, you may raise $\lambda$ incrementally until you get only on $\beta\neq 0$.

Other valid methodology is to apply some kind of screening based on correlations, t-tests or other kind of association measures that rank variables according to relevance before estimation.

Answer 3

No overfitting

I search a linear function that only depends only on one of my 20 features

There is not much overfitting when you search for only a linear function

$$y_i = a + b x_{i}$$

Overfitting is not a problem in this case because you do not have hyperparameters that you can tune.

Your problem is more straightforward and only about picking the best feature.

The question of overfitting, and the bias-variance tradeoff, is not relevant here because there is no bias that can make the model less flexible and less variable (except for such techniques as shrinking or Bayesian modeling which could also constrain a one-dimensional model).

---

Overfitting would be more worrisome if you would be fitting more complex functions of your features (e.g. fit polynomial models). In that case, the hyperparameter would be the order of the polynomial and you can change this.

Or, overfitting could occur if you would allow the use of multiple features, in which case the hyperparameter is in the number of features that you include in the model. (but your case seems to have been restricted to only one single feature)

---

So in your case,

You can simply perform the fitting repeatedly with different features $x_i$ and select whichever is the best-performing feature (for this you need to have some measure of performance, and ideally also have an idea about the distribution in order to estimate the significance, or use some part of the data to estimate the significance).

Whether this is a good approach is a different question, but if this is the constraint of your question (find a linear function with only one single feature) then there is not much better solution possible than simply selecting the feature that fits your data the best.

Answer 4

I will assume that you want to avoid overfitting so that your model is the most predictive on new data, rather than being overfit to the training data. Rather than constraining the class of models you are willing to consider at the outset, you may want to fit multiple models and then choose the model that "performs the best" on out-of-sample data. You will need some loss function to assess which "performs the best" out of sample, such as mean squared error. You can estimate how well your model performs on new data by splitting into training and test sets, by using cross validation, or related methods. Candidate models might include those already mentioned, such as ordinary regression, LASSO regression, ridge regression, elastic net etc. but you could also try others. Custom software in R, such as the glmnet package, should make it relatively easy to do a lot of the above.