jmlr jmlr2011 jmlr2011-69 jmlr2011-69-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Philippe Rigollet, Xin Tong
Abstract: Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss ϕ. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with high probability: (i) its ϕ-type I error is below a pre-specified level and (ii), it has ϕ-type II error close to the minimum possible. The proposed classifier is obtained by minimizing an empirical convex objective with an empirical convex constraint. The novelty of the method is that the classifier output by this computationally feasible program is shown to satisfy the original constraint on type I error. New techniques to handle such problems are developed and they have consequences on chance constrained programming. We also evaluate the price to pay in terms of type II error for being conservative on type I error. Keywords: binary classification, Neyman-Pearson paradigm, anomaly detection, empirical constraint, empirical risk minimization, chance constrained optimization
P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. J. Amer. Statist. Assoc., 101(473):138–156, 2006. A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2009. G. Blanchard, G. Lee, and C. Scott. Semi-supervised novelty detection. J. Mach. Learn. Res., 11: 2973–3009, 2010. S. Boucheron, O. Bousquet, and G. Lugosi. Theory of classification: A survey of some recent advances. ESAIM Probab. Stat., 9:323–375, 2005. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004. G. C. Calafiore and M. C. Campi. The scenario approach to robust control design. IEEE Trans. Automat. Control, 51(5):742–753, 2006. A. Cannon, J. Howse, D. Hush, and C. Scovel. Learning with the Neyman-Pearson and min-max criteria. Technical Report LA-UR-02-2951, 2002. A. Cannon, J. Howse, D. Hush, and C. Scovel. Simple classifiers. Technical Report LA-UR-030193, 2003. D. Casasent and X. Chen. Radial basis function neural networks for nonlinear fisher discrimination and neyman-pearson classification. Neural Networks, 16(5-6):529 – 535, 2003. L. Devroye, L. Gy¨ rfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition, Volume 31 of o Applications of Mathematics (New York). Springer-Verlag, New York, 1996. W. Feller. An Introduction to Probability Theory and Its Applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971. M. Han, D. Chen, and Z. Sun. Analysis to Neyman-Pearson classification with convex loss function. Anal. Theory Appl., 24(1):18–28, 2008. V. Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. ´ ´ e Ecole d’Et´ de Probabilit´ s de Saint-Flour XXXVIII-2008. Lecture Notes in Mathematics 2033. e Berlin: Springer. ix, 254 p. EUR 48.10 , 2011. 2854 N EYMAN -P EARSON C LASSIFICATION C. M. Lagoa, X. Li, and M. Sznaier. Probabilistically constrained linear programs and risk-adjusted controller design. SIAM J. Optim., 15(3):938–951 (electronic), 2005. E. L. Lehmann and J. P. Romano. Testing Statistical Hypotheses. Springer Texts in Statistics. Springer, New York, third edition, 2005. A. Nemirovski and A. Shapiro. Convex approximations of chance constrained programs. SIAM J. Optim., 17(4):969–996, 2006. A. Pr´ kopa. Stochastic Programming, volume 324 of Mathematics and its Applications. Kluwer e Academic Publishers Group, Dordrecht, 1995. R. T. Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original, Princeton Paperbacks. R. Schapire. The strength of weak learnability. Machine learning, 5(2):197–227, 1990. C. Scott. Comparison and design of Neyman-Pearson classifiers. Unpublished, 2005. C. Scott. Performance measures for Neyman-Pearson classification. IEEE Trans. Inform. Theory, 53(8):2852–2863, 2007. C. Scott and R. Nowak. A Neyman-Pearson approach to statistical learning. IEEE Transactions on Information Theory, 51(11):3806–3819, 2005. E. V. Slud. Distribution inequalities for the binomial law. Ann. Probability, 5(3):404–412, 1977. 2855