nips nips2009 nips2009-3 nips2009-3-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicolas Vayatis, Marine Depecker, Stéphan J. Clémençcon
Abstract: The purpose of the paper is to explore the connection between multivariate homogeneity tests and AUC optimization. The latter problem has recently received much attention in the statistical learning literature. From the elementary observation that, in the two-sample problem setup, the null assumption corresponds to the situation where the area under the optimal ROC curve is equal to 1/2, we propose a two-stage testing method based on data splitting. A nearly optimal scoring function in the AUC sense is first learnt from one of the two half-samples. Data from the remaining half-sample are then projected onto the real line and eventually ranked according to the scoring function computed at the first stage. The last step amounts to performing a standard Mann-Whitney Wilcoxon test in the onedimensional framework. We show that the learning step of the procedure does not affect the consistency of the test as well as its properties in terms of power, provided the ranking produced is accurate enough in the AUC sense. The results of a numerical experiment are eventually displayed in order to show the efficiency of the method. 1
[1] M.J. Rasch B. Scholkopf A. Smola A. Gretton, K.M. Borgwardt. A kernel method for the two-sample problem. In Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA, 2007.
[2] S. Agarwal, T. Graepel, R. Herbrich, S. Har-Peled, and D. Roth. Generalization bounds for the area under the ROC curve. J. Mach. Learn. Res., 6:393–425, 2005.
[3] G. Biau and L. Gyorfi. On the asymptotic properties of a nonparametric l1 -test statistic of homogeneity. IEEE Transactions on Information Theory, 51(11):3965–3973, 2005.
[4] Y.K. Cheung and J.H. Klotz. The Mann Whitney Wilcoxon distribution using linked list. Statistica Sinica, 7:805–813, 1997.
[5] S. Cl´ mencon, G. Lugosi, and N. Vayatis. Ranking and scoring using empirical risk minimization. In e ¸ P. Auer and R. Meir, editors, Proceedings of COLT 2005, volume 3559 of Lecture Notes in Computer Science, pages 1–15. Springer, 2005.
[6] S. Cl´ mencon, G. Lugosi, and N. Vayatis. Ranking and empirical risk minimization of U-statistics. The e ¸ Annals of Statistics, 36(2):844–874, 2008.
[7] S. Cl´ mencon and N. Vayatis. Ranking the best instances. Journal of Machine Learning Research, e ¸ 8:2671–2699, 2007.
[8] S. Cl´ mencon and N. Vayatis. Empirical performance maximization based on linear rank statistics. In e ¸ Advances in Neural Information Processing Systems, volume 3559 of Lecture Notes in Computer Science, pages 1–15. Springer, 2009.
[9] S. Cl´ mencon and N. Vayatis. Tree-based ranking methods. IEEE Transactions on Information Theory, e ¸ 55(9):4316–4336, 2009.
[10] W.W. Cohen, R.E. Schapire, and Y. Singer. Learning to order things. In NIPS ’97: Proceedings of the 1997 conference on Advances in neural information processing systems 10, pages 451–457, Cambridge, MA, USA, 1998. MIT Press.
[11] C. Cortes and M. Mohri. AUC optimization vs. error rate minimization. In S. Thrun, L. Saul, and B. Sch¨ lkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, o MA, 2004.
[12] C. Ferri, P.A. Flach, and J. Hern´ ndez-Orallo. Learning decision trees using the area under the roc curve. a In ICML ’02: Proceedings of the Nineteenth International Conference on Machine Learning, pages 139– 146, 2002.
[13] Y. Freund, R. D. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933–969, 2003.
[14] S. Kotz and S. Nadarajah. Multivariate t Distributions and Their Applications. Cambridge University Press, 2004.
[15] E.L. Lehmann and J. P. Romano. Testing Statistical Hypotheses. Springer, 2005.
[16] H.B. Mann and D.R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Stat., 18:50–60, 1947.
[17] A. Rachev. Probability Metrics and the Stability of Stochastic Models. Wiley, 1991.
[18] A. Rakotomamonjy. Optimizing Area Under Roc Curve with SVMs. In Proceedings of the First Workshop on ROC Analysis in AI, 2004.
[19] C. Rudin, C. Cortes, M. Mohri, and R. E. Schapire. Margin-based ranking and boosting meet in the middle. In P. Auer and R. Meir, editors, Proceedings of COLT 2005, volume 3559 of Lecture Notes in Computer Science, pages 63–78. Springer, 2005.
[20] R.J. Serfling. Approximation theorems of mathematical statistics. Wiley, 1980.
[21] A.K. van der Vaart. Asymptotic Analysis. Cambridge University Press, 1998.
[22] F. Wilcoxon. Individual comparisons by ranking methods. Biometrics, 1:80–83, 1945.
[23] E. Moulines Z. Harchaoui, F. Bach. Testing for homogeneity with kernel Fischer discriminant analysis. In Advances in Neural Information Processing Systems 20. MIT Press, Cambridge, MA, 2008. 9