A general model for finite-sample effects in training and testing of competing classifiers

Sergey V. Beiden, Marcus A. Maloof, and Robert F. Wagner

The conventional wisdom in the field of statistical pattern recognition (SPR) is that the size of the finite test sample dominates the variance in the assessment of the performance of a classical or neural classifier. The present work shows that this result has only narrow applicability. In particular, when competing algorithms are being compared, the finite training sample more commonly dominates this uncertainty. This general problem in SPR is analyzed using a formal structure recently developed for multivariate random-effects receiver operating characteristic (ROC) analysis. Monte Carlo trials within the general model are used to explore the detailed statistical structure of several representative problems in the sub-field of computer-aided diagnosis in medicine. The scaling laws between variance of accuracy measures and number of training samples and number of test samples are investigated and found to be comparable to those discussed in the classic text of Fukunaga, but important interaction terms have been neglected by previous authors. Finally, the importance of the contribution of finite trainers to the uncertainties argues for some form of bootstrap analysis to sample that uncertainty. The leading contemporary candidate is an extension of the 0.632 bootstrap and associated error analysis, as opposed to the more commonly used cross-validation.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Paper available in PostScript (gzipped) and PDF.

Beiden, S.V., Maloof, M.A., & Wagner, R.F. (2003). A general model for finite-sample effects in training and testing of competing classifiers. IEEE Transactions on Pattern Analysis and Machine Intelligence 25:1561–1569.

@article{beiden.pami.03,
  author = "Beiden, S.V. and Maloof, M.A. and Wagner, R.F.",
  title = "A general model for finite-sample effects in training
    and testing of competing classifiers",
  journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
  year = 2003,
  volume = 25,
  number = 12,
  pages = "1561--1569",
  annote = {
}}