# Training set size for neural networks considering curse of dimensionality

I'm learning the ropes of neural networks. Recently, I read stuff about the curse of dimensionality and how it might lead to overfitting (e.g. here).

If I understand correctly, the number of features (dimensions) d of a given dataset with n data points is very important when considering the size t of the training set.

QUESTIONS

(...not sure if all my questions are really connected to the curse of dimensionality)

1. How do I choose the correct training size t considering d and n? Is t a function of d and n?
2. Do I have to consider d for regularization?
• By "size t of the training set" are you referring to cross validation? Are you planning to use any particular scheme? Jul 17, 2015 at 17:52
• Yes, for example for cross validation. What do you mean by scheme? Jul 17, 2015 at 18:24
• 10 fold CV, leave one out CV, bootstrap CV, etc. Jul 17, 2015 at 18:28
• let's say 10 fold CV. sorry that I'm not so familiar with the terms yet Jul 17, 2015 at 18:50

A neural net is a linear model in derived variables. Take the regression case, because it is a little bit simpler: $$\begin{array}{l} y = \alpha + V_1\beta + \epsilon\\ V_1 = a(\gamma_1 + V_2\Gamma_1)\\ V_2 = a(\gamma_2 + V_3\Gamma_2)\\ \vdots \\ V_L = a(\gamma_L + X\Gamma_L)\\ \end{array}$$ where $X$ is your data (i.e.: your features), $\Gamma$ are matrices of weights, $\gamma$ are "biases", and $\beta$ are your weights connecting the topmost hidden layer to the output. You see that it is nothing more than a linear model, but in nonlinear functions of $X$.

Just like in a linear model, you can overfit when you have too many parameters. A typical strategy for avoiding overfit is regularization. Rather than solving $$\underset{\hat\beta}{argmin}\left(y-X\hat\beta\right)^2$$ you instead solve $$\underset{\hat\beta}{argmin}\left(\left(y-X\hat\beta\right)^2 + \lambda\hat\beta^T\hat\beta\right)$$ in ridge regression, for example. Selecting $\lambda$ by cross-validation, you're effectively letting the data tell you how much to use your many dimensions.

This generalized directly to neural nets, except that there is no closed form solution to the minimization problem, as there is in ridge regression. You'll overfit if you do

$$\underset{\hat\beta, \Gamma_{1:L}}{argmin}\left(y-\hat{f}(X, \hat\beta, \hat\Gamma)\right)^2$$ so instead you do

$$\underset{\hat\beta, \Gamma_{1:L}}{argmin}\left(\left(y-\hat{f}(X, \hat\beta, \hat\Gamma)\right)^2 + \lambda\hat\theta^T\hat\theta\right)$$ where $\theta$ is a concatenated vector of all of your weights.

Note that the quadratic penalty here isn't the only form of regularization. You could also do L1 regularization, or dropout regularization.

But the idea is the same: build a model that will overfit the data, and then find a regularization parameter (by some variant of cross validation) that will constrain the variability such that you don't overfit.

One of the rules of thumb is to have at least 10x more data points as the number of dimensions. Using some intelligent prior information (e.g. good kernel in SVMs), you might even learn a good machine with less data points as dimensions.

The lecture about VC dimension from Yaser Abu-Mostafa [link] motivates this 10x rule with some nice charts. If you are not familiar with VC dimension concept, it is about the capacity of learning. The higher the dimension, the more complex problem we are trying to solve. For example, classical Perceptron has d+1 VC dimensions. Some problems have infinite VC dimensions, such problems are impossible to learn.

• Thanks for the rule of thumb and the link. do you also have a source for the statement "you might even learn a good machine with less data points as dimensions"? Jul 22, 2015 at 10:04