Kernel Regression with Order Preferences

Abstract

We propose a novel kernel regression algorithm which takes into account order preferences on unlabeled data. Such preferences have the form that point x1 has a larger target value than that of x2, although the tar-get values for x1, x2 are unknown. The order pref-erences can be viewed as side information or a form of weak labels, and our algorithm can be related to semi-supervised learning. Learning consists of formu-lating the order preferences as additional regularization in a risk minimization framework. We define a linear program to effectively solve the optimization problem. Experiments on benchmark datasets, sentiment analy-sis, and housing price problems show that the proposed algorithm outperforms standard regression, even when the order preferences are noisy.