Kernel Principal Component Ranking: Robust Ranking on Noisy Data
Evgeni Tsivtsivadze, Botond Cseke, Tom Heskes · Radboud Repository (Radboud University) · 2009
A b s tr a c t.We propose the kernel principal component ranking algo rithm (KPCRank) for learning preference relations.The algorithm can be considered as an extension of nonlinear principal component regres sion applicable to preference learning task.It is particularly suitable for learning from noisy datasets where a lower dimensional data representa tion preserves most expressive features.In many cases near-linear depen dence of regressors (multicollinearity) can notably decrease performance of the learning algorithm, however, KPCRank can effectively deal with this situation.It is accomplished by projecting the data onto p-principal components in the feature space defined by a positive definite kernel and consecutive learning of the ranking function.Despite the fact that the number of the pairwise preferences is quadratic, the training time of KPCRank scales linearly with the number of data points in the training set and is equal to th a t of the principal component regression.We com pare the algorithm to several ranking and regression methods, including probabilistic regression on pairwise comparison data.Our experiments demonstrate th at the performance of KPCRank is better than th at of the baseline methods, when learning to rank from the data corrupted by noise. I n t r o d u c t i o nT he ta sk of learning preference relations (see e.g.[5]) has received significant atte n tio n in m achine learning lite ra tu re .T his p ap e r prim arily concerns th e ta sk of ranking, w hich is a special case of a preference learning task w hen a to ta l order is associated w ith th e set of d a ta points under consideration.B o th the preference learning and th e ranking tasks can be form ulated as th e problem s w here th e aim is to learn a function capable of arranging d a ta points according to a given preference relation.W hen com paring two d a ta points, th e function is able to evaluate w hether th e first p o in t is preferred over th e second one.To learn th is function we propose th e kernel principal com ponent ranking (K P C R ank) algorithm .T he algorithm can be considered as an extension of th e nonlinear principal com ponent regression applicable to th e preference learning task .Sim ilar to the kernel principal com ponent regression (K P C R ) [14], K P C R an k is p articu larly