Reverse testing: an efficient framework to select amongst classifiers under sample selection bias

ABSTRACT

One of the most important assumptions made by many classification algorithms is that the training and test sets are drawn from the same distribution, i.e., the so-called "stationary distribution assumption" that the future and the past data sets are identical from a probabilistic standpoint. In many domains of real-world applications, such as marketing solicitation, fraud detection, drug testing, loan approval, sub-population surveys, school enrollment among others, this is rarely the case. This is because the only labeled sample available for training is biased in different ways due to a variety of practical reasons and limitations. In these circumstances, traditional methods to evaluate the expected generalization error of classification algorithms, such as structural risk minimization, ten-fold cross-validation, and leave-one-out validation, usually return poor estimates of which classification algorithm, when trained on biased dataset, will be the most accurate for future unbiased dataset, among a number of competing candidates. Sometimes, the estimated order of the learning algorithms' accuracy could be so poor that it is not even better than random guessing. Therefore,a method to determine the most accurate learner is needed for data mining under sample selection bias for many real-world applications. We present such an approach that can determine which learner will perform the best on an unbiased test set, given a possibly biased training set, in a fraction of the computational cost to use cross-validation based approaches.

REFERENCES

• 1: Wei Fan , Ian Davidson , Bianca Zadrozny , Philip S. Yu, An Improved Categorization of Classifier's Sensitivity on Sample Selection Bias, Proceedings of the Fifth IEEE International Conference on Data Mining, p.605-608, November 27-30, 2005 [doi>10.1109/ICDM.2005.24]
• 2: Heckman, J. (1979). Sample selection bias as a specification error. Econometrica, 47:153--161.
• 3: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 4: McCallum, A. (1998). Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. CMU TR.
• 5: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 6: Moore, A. A Tutorial on the VC Dimension for Characterizing Classifiers, Available from the Website: www.cs.cmu.edu/~awm/tutorials
• 7: Rennie, J. 20 Newsgroups, (2003). Technical Report, Dept C.S., MIT.
• 8: Rosset, S., Zhu, J., Zou, H., and Hastie, T. (2005). A method for inferring label sampling mechanisms in semi-supervised learning. In Advances in Neural Information Processing Systems 17, pages 1161--1168. MIT Press.
• 9: John Shawe-Taylor , Peter L. Bartlett , Robert C. Williamson , Martin Anthony, A framework for structural risk minimisation, Proceedings of the ninth annual conference on Computational learning theory, p.68-76, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238070]
• 10: Andrew Smith , Charles Elkan, A Bayesian network framework for reject inference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014085]
• 11: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: Bianca Zadrozny, Learning and evaluating classifiers under sample selection bias, Proceedings of the twenty-first international conference on Machine learning, p.114, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015425]
• 14: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
classification, cross-validation, sample selection bias, stationary distribution