# Name of “reshuffle trick” (randomly permute the dataset to estimate the bias of an estimator)

Do you know a reference or name for the following way to investigate if a complex modelling technique $T$ is biased?

1. Apply $T$ to the original data set. Measure its performance (e.g. R-squared in regression setting).
2. Randomly permute the response variable to get a new data set. Apply $T$ and measure its performance $P'$. [If the observations are dependent, this step is more complicated.]

If $P'$ is substantially different from zero performance, we conclude $T$ is biased.

Step 2 can be repeated if resources allow, which would lead to the permutation null distribution of the performance measure. But in my application, I cannot do this because of resource problems.

I darkly remember that this "reshuffling" trick was used by someone to investigate the bias of leave-one-out cross-validation (in some setting). I don't know, however, if he was in my situation where he could repeat the whole process just once.

An example in R that shows the "power" of naive backward selection:

# Generate random data set. Only random performance is expected.
n <- 100
p <- 30

set.seed(7567)
y <- rnorm(n)
X <- rnorm(n*p)
dim(X) <- c(n, p)
data <- data.frame(y, X)

# Modelling technique: backward selection with OLS
T <- function(data) {
step(lm(y ~ ., data = data), trace = 0)
}

# Performance: R-squared
P <- function(fit) {
summary(fit)$r.squared } # Step 1: Compute performance on original data. Happily publish high R-squared... P(T(data)) # 0.240405 # Step 2: Your mean colleague reshuffles response and gets also R-squared far away from 0 data$y <- data$y[sample(n)] P(T(data)) # 0.1925726  Conclusion on the example: The chosen modeling technique is extremely prone to overfitting, at least in this specific setting. ### Some background I have once used this reshuffling trick to check if cross-validation of some tedious modelling process was properly implemented by me. Under a random permutation, CV gave an R-squared of essentially 0 (as expected/desired). • This question seems highly relevant: stats.stackexchange.com/questions/192291/… and the reference quoted in it. – Flounderer Oct 18 '17 at 13:48 • Good searching @Flounderer, I've added the link to this question to my answer for those who want further reading (and maybe get amoeba's answer some of the upvotes it deserves) – IWS Oct 18 '17 at 14:29 ## 2 Answers To answer the question in the title, AFAIK this is called a permutation test. If this is indeed what you are looking for though, it does not work as described in the question. To be (somewhat) concise: the permutation test indeed works by shuffling one of the 'columns' and performing the test or calculation of interest. However, the trick is to do this a lot of times, shuffling the data each time. In small datasets it might even be possible to perform all possible permutations. In large datasets you usually perform an amount of permutation your computer can handle, but which is large enough to obtain a distribution of the statistic of interest. Finally, you use this distribution to check whether, for example, the mean difference between two groups is >0 in 95% of the distribution. Simply put, this latter step of checking which part of the distribution is above/below a certain critical value is the 'p-value' for your hypothesis test. If this is wildly different from the p-value in the original sample, I wouldn't say there's something wrong with the test/statistic of interest, but rather your sample containing certain datapoints which specifically influence the test result. This might be bias (selection bias due to including some weird cases; measurement error in specific cases, etc.), or it might be incorrect use of the test (e.g. violated assumptions). See https://en.wikipedia.org/wiki/Resampling_(statistics) for further details Moreover, see @amoeba 's answer to this question If you want to know more about how to combine permutation tests with variable selection. • So it is like a permutation test with one single permutation (because$T$e.g. runs for 10 days) and with focus on the null distribution of the performance statistic (instead of p-values)? – Michael M Oct 18 '17 at 8:31 • The strength of permutation tests (and resampling methods) lies in the distribution of test statistics you obtain. To restate that, obtaining the distribution is mandatory for the test. You will understand that if you only do this once or just a few times, you cannot form a proper distribution of these results. If modelling$T\$ once requires 10 days of runtime, proper permutation tests would indeed take ages. Maybe crossvalidation en.wikipedia.org/wiki/Cross-validation_(statistics) is more applicable? – IWS Oct 18 '17 at 8:41
• @MichaelM The permutation test and the randomization test are the same test. If the statistic takes a long time to compute, the permutation test will take a VERY long time to run. – AdamO Jan 16 '18 at 19:47
• @AdamO: Fully agree about the timing. But the technique is not at all about testing a hypothesis. It is about estimation of a bias (which would go more in the direction of a bootstrap application). But that is the reason why I asked the question! – Michael M Jan 16 '18 at 19:55

I finally found the answer in Frank Harrell's book "Regression Modeling Strategies"  in Section 5.2.4 (Improvements on Data-Splitting: Resampling.).

"The randomization method" is presented as an interesting method to estimate optimism through random permutations of the response, especially in combination with variable selection (as in the example in the OP).

He refers, among others, to  for related ideas.

The method is very simple: Let's say your complicated modelling strategy involves forward-/backward (and sideway) selection and your data set is too small to have a clean train/validation/test split. Furthermore, you might not fully trust cross-validation as it always mean to discard a certain proportion of the data within fold. How can you judge if your R-squared of 0.7 is valid or if it mostly a result of overfitting? The randomization method works as follows (here we talk about R-squared but it can be any performance measure of interest). If your strategy is unbiased, then you would expect the R-squared to be close to 0 if repeated on a data set with randomly permuted response variable. Let's say you get an average R-squared of 0.6 instead of 0 after 20 permutations. So you know that the original R-squared of 0.7 is probably not much more than the result of overfitting. A more honest estimate of the "true" R-squared would be 0.7-0.6 = 0.1 (small). So you have shown how badly your strategy overfits.

• Very simple
• You always use the full data set