Peeking Inside the Black Box, can Feature importance indicate overfit? my basic question is: can permutation feature importance be used to identify overfitting?
when you have a binary classifcation problem with balanced classes (i.e. 70 x yes, 70 x no), when none of the predictors is relevant for the classification task you would expect an accuracy of 50% right?
We have trained an MLP with an Accuarcy of 95%, which indicated that some of the predictors are relevant for the binary classification task. We computed the permutation importance with the IML R-package, and got an permutation importance score (method difference so permutation error - baseline error) of 0.08 for only one relevant predictor. All other predictors had an importance score of 0 (no change when the predictor is shuffled)  
Does this mean we are overfitting? Permutation of the only important predictor results in an decrease of accuracy of 8% we are still at an accuracy of 87% (95% baseline accuracy - 8% of that feature).

Edit - Splitting to validate overfit:
After some helpful comments suggested I need to split the data to be sure about overfit I did. I used 100 observations (72.5% of the Data) for the Training Data in grouped 5-fold CV gave me an accuarcy of 98.04% for the hyperparameter size of 5 (5 Neurons in the single hidden layer). Predictions based on the final caret model about the unseen left 38 observations (27.5% of the Data) resulted in 100% Accuracy.  
However the sum of my permutation feature importance (see below) is still only 6.2%. 3 Predictors are deemed relevant (permutation of them resulted in an increase of error). Yet it is unclear to me how one can interpret this result: Baseline Accuracy 98.04% - 6.2% Error increase for permutation relevant features = still 91.84% when all relevant features are permuted.

Here is my partial code, I am sorry but I cant give out a reproducable example since I dont own the data I am working with.
  # preparation for the contrasting dataset
  df_test <- subset(df,  Class == "Control" | Class == classes[i])
  df_test$Class <- factor(df_test$Class)
  preproc <- select(df_test,-ID,-Class) %>% caret::preProcess(., method = c("center","scale","zv"), verbose = T)
  df.contrast <- predict(preproc, df_test)
  # Splitting: testing for overfit splitting of the contrast ds
    partition = 0.725
    train_ids = sample(unique(df.contrast$ID), size=partition*length(unique(df.contrast$ID)))
    df.train = df.contrast %>% filter(ID %in% train_ids)
    df.test = df.contrast %>% filter(!ID %in% train_ids)
  # train the model and evaluate on test set
    model <- tuneModel.contrast(df.train)
    x.test <- select(df.test,-ID,-Class)
    predictions.testset = caret::predict.train(model, newdata = x.test)
    print(confusionMatrix(predictions.testset, df.test$Class))

  permutation_vip.perclass(df.contrast,classes[i],levels(df.contrast$Class),model)

Here the function used to train the model
allSummary  <- function(data, lev = NULL, model = NULL){
  a1 <- defaultSummary(data, lev, model)
  b1 <- twoClassSummary(data, lev, model)
  c1 <- prSummary(data, lev, model)
  out <- c(a1, b1, c1)
  out
  # return(out)
  }
########################## Hyperparametertuning NeuralNet (MLP) ############################
tuneModel.contrast <- function(contrast_df){
  ############## Caret Preparation ############## 
  set.seed(1337)
  k.folds = 5
  contrast_df.folds <- groupKFold(contrast_df$ID, k = k.folds) 
  contrast_df.control <- trainControl( # k Folds grouped by subject cross validation, repeated 3 times
    method = "repeatedcv", 
    number = k.folds, 
    repeats = 3,
    index = contrast_df.folds,
    savePredictions = T,
    summaryFunction = allSummary,
    classProbs = T
    )
  contrast_df <- select(contrast_df, -"ID")
  contrast_df.tunegrid <- expand.grid(.size=c(1:(ncol(contrast_df)-1)))

  metric <- "Accuracy"
  # metric <- "AUC"
  tic("MLP Contrasting, Hyperparameter Startegy 1: Grid Search")
  mlp <- train(Class~., 
               data=contrast_df, 
               method="mlp", 
               metric=metric, 
               tuneGrid=contrast_df.tunegrid, 
               trControl=contrast_df.control
               # , preProc=c("center", "scale","zv")
               )
  toc()
  print(mlp)
  # M <- mlp$results
  # print(sort(apply(M,2,sd), decreasing = T))
  return(mlp)
}

 A: I don't think permutation feature importance can identify overfitting per se, it could however hint whether a good amount of noise has been modelled (overfitting) when features that you know for a fact to be significant, aren't deemed significant (pretty much your case). If you go with splitting, significantly smaller training error than test error indicates overfit. You could try k-fold the way you suggested, but you could also try leave-one-out cross validation. In both cases you'll get average training and test set errors so you can compare them.
Since your goal is both inference and prediction, it might be best to use a separate model for each (as suggested in Harrell's, Regression Modeling Strategies). To check the statistical significance of your predictors you could use anything from a classic GLM with asymptotic p-values to a Bayesian regression. If you want to combine feature significance with prediction without having to split your data for cross validation, I would suggest permuted Random Forests. 
