Is generating training data for a classifier mathematically valid? I have an application with a class imbalance problem: A lot of positive data points, but very few (comparatively) negative points.
One colleague recommended that I train a generative model on the limited subset of the negative data I have, and then generate data from that model to use for training my classifier.
I have the feeling that this shouldn't work, after all the generative model will only have access to the small sample of negative data, and not the true population.
Is there a way to formally claim this? I was thinking something along the lines of Computational learning theory or the no free lunch theorem.
 A: Let say the you have a data set D and hypothesis class H.
You can use D to find the subset of H that is consistent with it (assume prefect consistency fro simplicity).
The will enable you to learn P(h|D), the likelihood of hypothesis h given the data.
Of course, you can also use P(h), the probability of the hypothesis. There you can use prior assumptions on properties of the data, MDL, and so on.
Now let's consider that you simulate some data S.
You will make some assumptions on the data in order to decide how to simulate it.
If you could make these assumptions formal and clear, you could just add them into P(h). Since your simulation will be a result of these assumptions and D, consistency with S, P(h|S), shouldn't give you more information over P(h) and P(h|D).
This argument shouldn't be taken as a justification of never using simulated data. In computer vision it is very common to generate samples using rotation, splitting and other operations on the original image. We know that if there is a cat in a picture we can consider a slightly rotated picture to have a cat too. However, since we don't have clear and formal ways to characterize picture with cats, we do benefit from the simulated data.
In the field of NLP and sentence classification, it is usually hard to define manipulations of the data that will respect the concept of interest. If you can find such manipulations, you might benefit since this is another area in which it is hard to define well the hypothesis prior. 
A: Whenever we fit or train a model, there are several assumption which are made. One of the major assumptions made is that the data belongs to a certain distribution (Normal/Poisson/Binomial). Moreover, the noise present in the dataset is also assumed to follow a certain distribution.
If you really want to generate new data, fit a distribution on the negative data. Pick random points from the distribution and add random noise following the distribution to each point.
Having said the above, generating new data just to have class balance has very little advantage. This is due to the fact that class imbalance does not effect regression models like logistic regression: International Journal of Forecasting. "Instance sampling in credit scoring: An empirical study of sample size and balancing". Moreover, in ML methods like Support Vector Machines which only look at the boundary training examples, the added data does not really improve anything. Finally even if you are able to generate data by either the method you mentioned above or the method I mentioned, it would still contain the information present in the data you already had, and will follow the same distribution as the data you already had. Hence this new data will not improve the performance of the your model.
A: As per @Frobot's comment, in a parametric setting let $X=\{(\textbf{x}_1,t_1) \dots (\textbf{x}_n,t_n) \}$ be the negative examples in question. We can build a generative model $p(t|\textbf{x},\textbf{w})$ by finding the optimal weights by minimizing a cost function $J$
$$\text{argmin}_{\textbf{w}}\{J(X; \textbf{w})\}$$
If we draw samples $S=\{(\textbf{x}_i,t_i) \dots (\textbf{x}_n,t_n) \}$ from $p(t|\textbf{x},\textbf{w})$ we will of course discover that as $|S| \to \infty$ the minimization of $J(S;\textbf{w*})$ will find $\textbf{w*} = \textbf{w}$.
Therefore you will gain no new information by generating more negative samples. The case for non-parametric methods can be similarly argued. 
