make_classification: variances of informative, redundant and useless features differ significantly

In this part of the code for `make_classification`, the informative and redundant features are generated; here is the informative part:
https://github.com/scikit-learn/scikit-learn/blob/9aaed498795f68e5956ea762fef9c440ca9eb239/sklearn/datasets/_samples_generator.py#L233-L246
I generated a classification dataset with some useless features, and noticed that it was obvious which they were, because their variance was so much smaller than that of the informative features.

We can analyse the reason for this.  Let us write $\mathbf{Z}=(Z_1\ Z_2\ \dots\ Z_r)$ for one row of the initial `X_k`, as at line 241, where $r$ is `n_informative` and the $Z_i$ are independent identically distributed standard normal variates, $Z_i\sim \mathrm{N}(0,1)$. Then writing the matrix $A=(a_{ij})$, the corresponding row of the transformed `X_k` (after line 244) is $\mathbf{X}=\mathbf{Z}A = (X_1\ X_2\ \dots\ X_r)$, with
$$X_i = a_{1i}Z_1+a_{2i}Z_2+\dots+a_{ri}Z_r = \sum_{k=1}^r a_{ki}Z_k.$$
Then $\mathrm{E}(X_i)=0$ and $\mathrm{Var}(X_i)=\sum\nolimits_{k=1}^r a_{ki}^2$.  The significant thing here is that the variance is no longer 1, and it depends on the random matrix $A$.

Let us say something about this variance.  Each of the $a_{ki}$ is sampled from a uniform distribution on [-1,1], and so its mean is 0 and its variance is 1/3.  Thus $\mathrm{E}(a_{ki}^2)=1/3$ (taking the expectation over the distribution of random matrices $A$), and so the expected variance (over matrices $A$) of $X_i$ is $r/3$.

On the other hand, the useless entries have a standard normal distribution, so their variance is 1, and this explains the difference in the variances that I observed.

There is another issue with the (expected) variance of $X_i$ being different from 1: the `class_sep` parameter default value of 1.0 has an increasingly insignificant effect as `n_informative` increases: since the standard deviation in each informative variable is around $\sqrt{r/3}$, the separation of classes in that variable is around $2\sqrt{3/r}$ times the standard deviation if the cluster centres differ in that variable (being at +1 and -1).  This means that the classes are less distinguished than the default `class_sep` would suggest.

The same behaviour occurs with the redundant features:
https://github.com/scikit-learn/scikit-learn/blob/9aaed498795f68e5956ea762fef9c440ca9eb239/sklearn/datasets/_samples_generator.py#L248-L253
Since each of the redundant features is a random sum of the $r$ informative features, their expected variance is $r/3$ times the expected variance of the informative features, so is $r^2/9$ by the same reasoning.  (Note that this does not depend on the number of redundant features.)  This makes the redundant features even more obviously different.

What could be done to improve this?

One approach would be to normalise the columns of `A` and `B` so that each column has magnitude 1 (i.e., sum of squares of the entries = 1).  That would mean that each informative and redundant variable would have variance 1.

Another approach would be to allow a little more variability, and so to divide `A` and `B` by $\sqrt{r/3}$, meaning that the expected variance of each variable (over all possible matrices `A` and `B`) would be 1.

As I mentioned in my previous issue, I don't know what guarantees scikit-learn makes for reproducibility across versions.  If that is an issue, this could be addressed by having a `version` or `variant` parameter that controls the behaviour of the function.  Alternatively, one could have something like a `standardize` parameter that defaults to `False` (meaning the current behaviour), and if it is set to `True`, then the new behaviour is used instead.

Thanks for taking the time to read this!

COMMENT:
Perhaps I wasn't clear enough in my report.  There are two related issues here around the variances.

The first is that the variances of different featuers dramatically differ from each other, and this may have a significant impact on experiments.  As a simple example, if there are 27 informative features, then we find the following:

* useless features have a standard deviation of 1
* informative features have a standard deviation of about 3
* redundant features have a standard deviation of about 9

which possibly makes it obvious that these features differ in their nature.  It is entirely possible that classifiers will use this to "short-circuit" the classification problem by recognising that the relative variance gives information about the meaningfulness of the variable.  In other words, this is "information leakage" about the nature of the variables.

The second issue is that the side of the hypercube used (`2 * class_sep`) implicitly assumes that there is a fixed variance of the variables.  Imagine a very simple experiment which tests how the quality of a classifier depends on the number of features used, something like the following pseudocode:

```python
for n_features in range(3, 30, 3):
    X, y = make_classification(n_samples=1000, n_features=n_features, n_informative=n_features, n_redundant=0)
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)
    clf = classifier.fit(X_train, y_test)
    y_pred = clf.predict(X_test)
    print(n_features, get_error(y_test, y_pred))
```

Unknown to the experimenter, there are two competing things affecting the dataset: the number of informative features increases, which should make the task easier, but the separation of the datasets in each variable decreases, which makes the task harder.  They might, therefore, make erroneous conclusions about the quality of the classifier.  To fix this, they would need to use something like the following:

```python
    X, y = make_classification(n_samples=1000, n_features=n_features, n_informative=n_features,
                               n_redundant=0, class_sep=math.sqrt(n_features/3))
```

(and even that would not be perfect, but just an approximation, and this relies on a close reading of the source code of scikit-learn and performing the analysis that I did above).

So for both these reasons, I would suggest reopening this issue.

Labels: Needs Triage