Publication Type
Journal Article
Version
publishedVersion
Publication Date
4-2011
Abstract
Previous studies of Non-Parametric Kernel Learning (NPKL) usually formulate the learning task as a Semi-Definite Programming (SDP) problem that is often solved by some general purpose SDP solvers. However, for N data examples, the time complexity of NPKL using a standard interior-point SDP solver could be as high as O(N6.5), which prohibits NPKL methods applicable to real applications, even for data sets of moderate size. In this paper, we present a family of efficient NPKL algorithms, termed "SimpleNPKL", which can learn non-parametric kernels from a large set of pairwise constraints efficiently. In particular, we propose two efficient SimpleNPKL algorithms. One is SimpleNPKL algorithm with linear loss, which enjoys a closed-form solution that can be efficiently computed by the Lanczos sparse eigen decomposition technique. Another one is SimpleNPKL algorithm with other loss functions (including square hinge loss, hinge loss, square loss) that can be re-formulated as a saddle-point optimization problem, which can be further resolved by a fast iterative algorithm. In contrast to the previous NPKL approaches, our empirical results show that the proposed new technique, maintaining the same accuracy, is significantly more efficient and scalable. Finally, we also demonstrate that the proposed new technique is also applicable to speed up many kernel learning tasks, including colored maximum variance unfolding, minimum volume embedding, and structure preserving embedding.
Keywords
non-parametric kernel learning, pairwise constraints, semi-definite programming, semi-supervised learning, side information
Discipline
Computer Sciences | Databases and Information Systems | Theory and Algorithms
Research Areas
Data Science and Engineering
Publication
Journal of Machine Learning Research
Volume
12
Issue
4
First Page
1313
Last Page
1347
ISSN
1532-4435
Publisher
JMLR
Citation
ZHUANG, Jinfeng; TSANG, Ivor W.; and HOI, Steven C. H..
A Family of Simple Non-Parametric Kernel Learning Algorithms from Pairwise Constraints. (2011). Journal of Machine Learning Research. 12, (4), 1313-1347.
Available at: https://ink.library.smu.edu.sg/sis_research/2289
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://jmlr.csail.mit.edu/papers/volume12/zhuang11a/zhuang11a.pdf