TY - GEN

T1 - Ranking with kernels in Fourier space

AU - Kondor, Risi

AU - Barbosa, Marconi

PY - 2010

Y1 - 2010

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=84898074972&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9780982252925

T3 - COLT 2010 - The 23rd Conference on Learning Theory

SP - 451

EP - 463

BT - COLT 2010 - The 23rd Conference on Learning Theory

T2 - 23rd Conference on Learning Theory, COLT 2010

Y2 - 27 June 2010 through 29 June 2010

ER -