Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

6-2009

Abstract

Previous studies of Non-Parametric Kernel (NPK) learning usually reduce to solving some Semi-Definite Programming (SDP) problem by a standard SDP solver. However, time complexity of standard interior-point SDP solvers could be as high as O(n6.5). Such intensive computation cost prohibits NPK learning applicable to real applications, even for data sets of moderate size. In this paper, we propose an efficient approach to NPK learning from side information, referred to as SimpleNPKL, which can efficiently learn non-parametric kernels from large sets of pairwise constraints. In particular, we show that the proposed SimpleNPKL with linear loss has a closed-form solution that can be simply computed by the Lanczos algorithm. Moreover, we show that the SimpleNPKL with square hinge loss can be re-formulated as a saddle-point optimization task, which can be further solved by a fast iterative algorithm. In contrast to the previous approaches, our empirical results show that our new technique achieves the same accuracy, but is significantly more efficient and scalable.

Discipline

Computer Sciences | Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning: Montreal, Canada, June 14-18

First Page

1273

Last Page

1280

ISBN

9781605585161

Identifier

10.1145/1553374.1553537

Publisher

ACM

City or Country

New York

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1145/1553374.1553537

Download

Share

COinS