# Why does machine learning work for high-dimensional data($n \ll p$)?

Consider the high dimensional data with which the number of features $$p$$ is much larger than the number of observations $$n$$. Machine learning algorithm is trained with the data.

My first thought is that a learning algorithm trained with the high dimensional data would have large model variance and so poor prediction accuracy.

To construct a model, we need to decide the parameters of models and the number of parameters gets larger when the number of features increases. And for the wide data, we would not have enough observations to decide all the parameters reliably. I think that the parameters of the model will change sensitively with the change of train samples. The instability of the model parameters indicates that there would be large model variance which will worsen the prediction performance.

However, I read that the machine learning models trained with high-dimensional data can make good predictions. I am curious about what is the underlying reason ML works for the prediction of the high-dimensional data($$n \ll p$$).

• Some ML algos can indeed be used to fit models on wide data. Whether these models are good is another question. – Michael M Jun 12 at 7:11
• "Wide" data is not the best name for describing p > n, since "wide" and "narrow", or "tall" is already used for naming the format how the data is stored. – Tim Jun 12 at 8:07
• @Tim Thanks, I didn't know about the table types. Could you suggest a name instead of the 'wide'? – kevin012 Jun 12 at 8:50
• @kevin012 I'm not sure is there is a name, people usually just say that it is a data where "$n \ll p$" – Tim Jun 12 at 8:56
• I think we need a name for that. I was searching it a while ago (for LDA), and "n < p" doesn't help on google – carlo Jun 12 at 10:31

## 3 Answers

Most of the machine learning models use some kind of regularization (see other questions tagged as ). In simple words, what regularization does it forces the model to be more simple then it can be. To give few examples:

• LASSO forces pushing regression parameters towards zero, so practically removing them from the model.
• Dropout that turns on and off different parts of the neural network, so that it needs to learn how to work with smaller sub-networks, instead of using all parameters, what makes it more flexible.
• When using bagging, you train multiple models using different, random, subsamples of the data, usually subsampling also the columns, and then aggregate them. So the individual models in your ensemble will need to learn how to use different features, and aggregating multiple models would "cancel out" scenarios where the individual model overfit.

Moreover, some recent results show that even without explicit regularization, neural networks, but also some other models, are able to work well in scenarios where they have many more parameters then datapoints, so in cases where they could literally memorize the whole data and overfit. Apparently, that is not the case and the models seem to regularize themselves, but the mechanism is still not known to us. This would suggest that we may not understand why this happends well enough yet.

One word: regularization. The complexity of a model is indeed more or less proportional to the number of predictors (this depends on the model), but ML algorithms use regularization to split the predictive burden between the different preductors, and finally yield a cautious outcome.

This works so well that, even when p is small, you can use a kernel method to embed your data to a infinite-dimensional space and trough regularization effectively learn a generalizable model from there.

You can't apply kernel methods to ordinary linear regression, that would be instable. But you can apply them to ridge regression, because it includes regularization.

• Thanks, carlo. But I'm not quite sure about the kernel methods of solving the problem in the infinite-dimensional space. Could you give me a link to any material on the approach? – kevin012 Jun 29 at 12:23
• more like the kernel trick creates the problem of a higher (even infinite) dimensional space. this is why kernel methods always include regularization: it is to it to solve the problem of high (or even infinite) dimensional space. I learned kernel methods on the book by Geron: hands-on machine learning, which explains them very well (but really, there is so much more about it). a good thing about kernel methods is that they scale linearly on p, but unfortunately they scale very badly with n and they are too slow overall. – carlo Jun 30 at 9:11

The description in the second paragraph of OP's question describes the phenomenon where regression coefficients cannot be uniquely determined when the design matrix is not full rank.

To construct a model, we need to decide the parameters of models and the number of parameters is proportional to the number of predictors. And for the wide data, we don't have enough data to decide all the parameters reliably. I guess with the wide data, the parameters of the model will change all the time with the small change of data. There would not be any stable solution for the model. And the instability indicates that there would be large model variance which will worsen the prediction performance.

The answer to this is two parts.

1. Not all machine learning models involve estimating a coefficient vector for a matrix-vector product. For example, random forest can find a best binary split for some data even when $$n \ll p$$ because finding a split doesn't involve solving a linear system.

2. For machine learning models that do involve a matrix-vector product (e.g. OLS or logistic regression), the addition of a penalty term can make the optimization problem strongly convex, and therefore identify a unique minimum of the loss function. See: Why does ridge estimate become better than OLS by adding a constant to the diagonal? Three common examples of penalized regression are , regression, and regression. This penalty is a form of regularization, because it limits the flexibility of the model.

The other answers are correct that regularization is why machine learning models can do well in terms of prediction when $$n \ll p$$, but they don't quite connect that concept to the rank deficiency component of your question.