  K-fold cross validation (CV) is a popular method for estimating the true
performance of machine learning models, allowing model selection and parameter
tuning. However, the very process of CV requires random partitioning of the
data and so our performance estimates are in fact stochastic, with variability
that can be substantial for natural language processing tasks. We demonstrate
that these unstable estimates cannot be relied upon for effective parameter
tuning. The resulting tuned parameters are highly sensitive to how our data is
partitioned, meaning that we often select sub-optimal parameter choices and
have serious reproducibility issues.
  Instead, we propose to use the less variable J-K-fold CV, in which J
independent K-fold cross validations are used to assess performance. Our main
contributions are extending J-K-fold CV from performance estimation to
parameter tuning and investigating how to choose J and K. We argue that
variability is more important than bias for effective tuning and so advocate
lower choices of K than are typically seen in the NLP literature, instead use
the saved computation to increase J. To demonstrate the generality of our
recommendations we investigate a wide range of case-studies: sentiment
classification (both general and target-specific), part-of-speech tagging and
document classification.
