×

zbMATH — the first resource for mathematics

On kernel methods for covariates that are rankings. (English) Zbl 1409.62090
Support-vector machines (SVM) are among the most powerful supervised learning models and are based on the Vapnik-Chervonenkis theory of statistical learning proposed in late 1960s. Since recently, SVM is also used for data ranking. Reproducing Kernel Hilbert Space (RKHS) is in the heart of SVM theory and enables efficient “rectifying” space construction, ref. the terminology first proposed by M. A. Aĭzerman et al. [Autom. Remote Control 25, 821–837 (1965; Zbl 0151.24701); translation from Avtom. Telemekh. 25, 917–936 (1964)]. The simple linear classifier in RKHS like PCA, ridge regression can be applied after such mapping. This paper focuses on right-invariant Kendall’s and Mallows’ kernels since they are invariant to a re-indexing of the underlying objects. The feature maps and spectral properties of these kernels are analyzed, new kernels based on these kernels’ interpolation are constructed. Eurobarometer and Movielens ratings datasets are used to demonstrate the effectiveness of the proposed novel ranking methods using SVM with both the Kendall and the Mallows kernels using conventional cross-validation for the parameters selection.

MSC:
62G08 Nonparametric regression and quantile regression
62G10 Nonparametric hypothesis testing
62J07 Ridge regression; shrinkage estimators (Lasso)
Software:
Scikit
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Erich L. Lehmann and Howard J.M. D’Abrera., Nonparametrics: Statistical Methods Based on Ranks. Springer New York, 2006. · Zbl 1217.62061
[2] Brian Francis, Regina Dittrich, and Reinhold Hatzinger. Modeling heterogeneity in ranked responses by nonparametric maximum likelihood: How do Europeans get their scientific knowledge?, The Annals of Applied Statistics, 4 :2181–2202, 2010. · Zbl 1220.62158
[3] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs the method of paired comparisons., Biometrika, 39:324–345, 1952. · Zbl 0047.12903
[4] Yunlong Jiao and Jean-Philippe Vert. The Kendall and Mallows kernels for permutations., Proceedings of the International Conference on Machine Learning, 32 :1935–1944, 2015.
[5] George Kimeldorf and Grace Wahba. Some results on Tchebycheffian spline functions., Journal of Mathematical Analysis and Applications, 33:82–95, 1971. · Zbl 0201.39702
[6] Bernhard Schölkopf and Alex J. Smola., Learning with Kernels. MIT Press, Cambridge, MA, 2002.
[7] Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Bharath K Sriperumbudur. Characteristic kernels on groups and semigroups. In, Advances in Neural Information Processing Systems, pages 473–480, 2009.
[8] Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures., Proceedings of the International Conference on Machine Learning, 19:315–322, 2002.
[9] Risi Imre Kondor and Marconi S. Barbosa. Ranking with kernels in Fourier space., Conference on Learning Theory, 23:451–463, 2010.
[10] Risi Imre Kondor. Group theoretical methods in machine learning., unpublished Ph.D. dissertation, Columbia University, 2008.
[11] Persi Diaconis. Group representations in probability and statistics., IMS Lecture Notes-Monograph Series, 11:i–192, 1988. · Zbl 0695.60012
[12] William Fulton and Joe Harris., Representation Theory, volume 129. Springer Science & Business Media, 1991. · Zbl 0744.22001
[13] Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines., The Journal of Machine Learning Research, 2:67–93, 2002. · Zbl 1009.68143
[14] Alfred Müller. Integral probability metrics and their generating classes of functions., Advances in Applied Probability, 29(2):429–443, 1997. · Zbl 0890.60011
[15] Svetlozar T. Rachev, Lev Klebanov, Stoyan V. Stoyanov, and Frank Fabozzi., The Methods of Distances in the Theory of Probability and Statistics. Springer Science & Business Media, 2013. · Zbl 1280.60005
[16] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test., Journal of Machine Learning Research, 13:723–773, 2012. · Zbl 1283.62095
[17] Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. Fourier theoretic probabilistic inference over permutations., Journal of Machine Learning Research, 10:997 –1070, 2009. · Zbl 1235.68234
[18] Bruce Sagan., The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, volume 203. Springer Science & Business Media, 2013. · Zbl 0823.05061
[19] Martin J. Wainwright., High-dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2017. · Zbl 07021501
[20] Song Xi Chen and Ying-Li Qin. A two-sample test for high-dimensional data with applications to gene-set testing., The Annals of Statistics, 38:808–835, 2010. · Zbl 1183.62095
[21] Aaditya Ramdas, Sashank J. Reddi, Barnabas Poczos, Aarti Singh, and Larry Wasserman. Adaptivity and computation-statistics tradeoffs for kernel and distance based high dimensional two sample testing., arXiv preprint arXiv:1508.00655, 2015.
[22] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Brucher Matthieu, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in python., Journal of Machine Learning Research, 12 :2825–2830, 2011. · Zbl 1280.68189
[23] Andreas Christmann and Ingo Steinwart. Universal kernels on non-standard input spaces., Advances in Neural Information Processing Systems, pages 406–414, 2010.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.