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 -