nips nips2013 nips2013-358 nips2013-358-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Assaf Glazer, Michael Lindenbaum, Shaul Markovitch
Abstract: In this paper we introduce a novel method that can efficiently estimate a family of hierarchical dense sets in high-dimensional distributions. Our method can be regarded as a natural extension of the one-class SVM (OCSVM) algorithm that finds multiple parallel separating hyperplanes in a reproducing kernel Hilbert space. We call our method q-OCSVM, as it can be used to estimate q quantiles of a highdimensional distribution. For this purpose, we introduce a new global convex optimization program that finds all estimated sets at once and show that it can be solved efficiently. We prove the correctness of our method and present empirical results that demonstrate its superiority over existing methods. 1
[1] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines, 2001.
[2] Yixin Chen, Xin Dang, Hanxiang Peng, and Henry L. Bart. Outlier detection with the kernelized spatial depth function. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(2):288–305, 2009.
[3] G. Fasano and A. Franceschini. A multidimensional version of the Kolmogorov-Smirnov test. Monthly Notices of the Royal Astronomical Society, 225:155–170, 1987.
[4] A. Glazer, M. Lindenbaum, and S. Markovitch. Learning high-density regions for a generalized Kolmogorov-Smirnov test in high-dimensional data. In NIPS, pages 737–745, 2012.
[5] John A Hartigan. Clustering Algorithms. John Wiley & Sons, Inc., 1975.
[6] V. Hodge and J. Austin. A survey of outlier detection methodologies. Artificial Intelligence Review, 22(2):85–126, 2004.
[7] Roger Koenker. Quantile regression. Cambridge university press, 2005.
[8] Gyemin Lee and Clayton Scott. Nested support vector machines. Signal Processing, IEEE Transactions on, 58(3):1648–1660, 2010.
[9] Youjuan Li, Yufeng Liu, and Ji Zhu. Quantile regression in reproducing kernel hilbert spaces. Journal of the American Statistical Association, 102(477):255–268, 2007.
[10] D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 3rd edition, 2008.
[11] A. Munoz and J.M. Moguerza. Estimation of high-density regions using one-class neighbor machines. In PAMI, pages 476–480, 2006.
[12] W. Polonik. Concentration and goodness-of-fit in higher dimensions:(asymptotically) distribution-free methods. The Annals of Statistics, 27(4):1210–1229, 1999.
[13] B. Sch¨ lkopf, A.J. Smola, R.C. Williamson, and P.L. Bartlett. New support vector algorithms. o Neural Computation, 12(5):1207–1245, 2000.
[14] Bernhard Sch¨ lkopf, John C. Platt, John C. Shawe-Taylor, Alex J. Smola, and Robert C. o Williamson. Estimating the support of a high-dimensional distribution. Neural Computation, 13(7):1443–1471, 2001.
[15] R. Serfling. Quantile functions for multivariate analysis: approaches and applications. Statistica Neerlandica, 56(2):214–232, 2002.
[16] Ingo Steinwart, Don R Hush, and Clint Scovel. A classification framework for anomaly detection. In JMLR, pages 211–232, 2005.
[17] Ichiro Takeuchi, Quoc V Le, Timothy D Sears, and Alexander J Smola. Nonparametric quantile estimation. JMLR, 7:1231–1264, 2006.
[18] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, New York, 2nd edition, 1998.
[19] R. Vert and J.P. Vert. Consistency and convergence rates of one-class svms and related algorithms. The Journal of Machine Learning Research, 7:817–854, 2006.
[20] W. Zhang, X. Lin, M.A. Cheema, Y. Zhang, and W. Wang. Quantile-based knn over multivalued objects. In ICDE, pages 16–27. IEEE, 2010.
[21] Yijun Zuo and Robert Serfling. General notions of statistical depth function. The Annals of Statistics, 28(2):461–482, 2000. 9