error of permutation feature importance Feature importance can be calculated by permuting features. But it seems to suffer from instability. To be more accurate about the feature importance, chap 5.5.1 in interpretable machine learning suggests repeating the permutation many times to get the permutation error. Also, the author's  R package iml makes the error plot using the percentile of the permutations.  
My question is when I permute the features, should I sample with replacement or without replacement? 
If I sample with replacement, it would be more like bootstrap rather than permutation, then is it safe to use bootstrap’s approach to calculate the confidence interval? 
If I sample without replacement, how do I interpret the percentile of permutations? It somehow has a connection to the confidence interval but I could not find a reference to support this connection.
 A: In the following answer I assume that we compute the feature importance for one feature $x_j$ and compute the importance as the difference in model error after permutation (the alternative would be the ratio).
In the paper about model-agnostic feature importance by [1], the authors suggest splitting the dataset into two random halves and swap the values of feature $x_j$. This is the equivalent to sampling without replacement.
Sampling Without Replacement
Sampling is random and will yield different results when repeated. That's why I would recommend repeating the feature importance estimate multiple times and see how large the variance is.
We compute the feature importance $FI_j$ of feature $x_j$ as the difference in model error increase when feature j is permuted:
$FI_j = \sum_{i=1}^n L(y^{(i)}, f(x^{(i)})) - \sum_{i=1}^n L(y^{(i)}, f(x^{(i)}_{perm:j}))$
where $L$ is a loss function, e.g. squared difference: $(y - f(x))^2$ and $x^{(i)}_{perm:j}$ is the i-th instance from the data with the j-th feature replaced by a randomly drawn value from another data instance.
There is a connection with confidence intervals and hypothesis tests. By resampling without replacement, we perform a permutation test, with the Null-hypothesis that the feature importance of feature $x_j$ is zero:
$$H_0: FI_j = 0$$ 
By resampling $x_j$ without replacement, we generate samples under this Null-hypothesis. 
When the feature is really not important, we should observe values for $FI_j$ that vary around 0.
Permutation tests are a framework to generate confidence intervals and p-values from resampling. 
Imagine you would repeat the $FI_j$-estimate 100 times, i.e. we get 100 $FI_j$ estimates.
Then we order the importances by increasing value.
The 90%-confidence interval would range from the 5-th to the 95-th value of the (ordered) feature importances.
Sampling with Replacement
I asssume you mean that you would sample for each instance the feature $x_j$ from the training data with replacement, i.e. you allow the $x_j$ of an instance to be drawn repeatedly (or not at all). 
I think that should work as well, but I would recommend sampling without replacement since than we can rely on the framework of permutation tests. 
[1] Fisher, Aaron, Cynthia Rudin, and Francesca Dominici. "Model Class Reliance: Variable Importance Measures for any Machine Learning Model Class, from the" Rashomon" Perspective." arXiv preprint arXiv:1801.01489 (2018).
