How to assess if my training examples are too similar? I have a dataset containing 30 million rows and 500 columns. A simple 32x32 MLP appears to overfit the data, in that the training error goes down nicely but the test error goes up. Given that my training set is so large, I suspect the overfitting is occurring because my training examples are too similar to each other. How would I go about confirming this? e.g. what techniques are out there for finding similar examples or assessing the variance of my training set? Or how would I increase the heterogeneity of the dataset?
I should say that my data was captured as a time series, so adjacent examples would naturally be quite similar if nothing happened between the two timestamps, but each training example has context, i.e. contains information about what happened in a certain time window around the current time. Right now I'm shuffling the data and trying to do classification.
 A: The data in your training and test sets can be modeled as h(x) + noise. In this context, the noise is the variability in your training and test data that is not explained by some common (theoretically optimal) model h(x). The important thing here is that, for example, if your training and test sets are sampled from entirely different distributions, then ALL of your data is noise, even if on their own, both training and test set data are very well structured. In this case, even a model with 1 or 2 parameters will be overfitting right away - regardless of how many data points you have in your training set!
In other words - the greater the amount of noise in your data, the easier it is to overfit and the simpler model you are restricted to using. With, say, gaussian noise, increasing the amount of data in your training set increases the data-to-noise ratio, reducing overfitting. If your training and test data are from (slightly) different distributions, increasing the amount of data will do nothing to reduce this source of noise! The data-to-noise ratio will stay the same. Only other sources of noise will be eliminated (e.g. measurement noise, if applicable).
I highly suspect this is your problem, given that you are dealing with time series. With 30 million rows, I would attempt to reduce the amount of noise from your data as it is fairly unlikely that your data does not cover the feature space relatively well.
