Ranking with Kernels in Fourier Space
Abstract
In typical ranking problems the total number n of items to be ranked is relatively large, but each data instance involves only k << n items. This paper examines the structure of such partial rankings in Fourier space. Specifically, we develop a kernel--based framework for solving ranking problems, define some canonical kernels on permutations, and show that by transforming to Fourier space, the complexity of computing the kernel between two partial rankings can be reduced from O((n-k)!2) to O((2k)2k+3).
Cite
Text
Kondor and Barbosa. "Ranking with Kernels in Fourier Space." Annual Conference on Computational Learning Theory, 2010.Markdown
[Kondor and Barbosa. "Ranking with Kernels in Fourier Space." Annual Conference on Computational Learning Theory, 2010.](https://mlanthology.org/colt/2010/kondor2010colt-ranking/)BibTeX
@inproceedings{kondor2010colt-ranking,
title = {{Ranking with Kernels in Fourier Space}},
author = {Kondor, Risi and Barbosa, Marconi S.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2010},
pages = {451-463},
url = {https://mlanthology.org/colt/2010/kondor2010colt-ranking/}
}