Publication Type

Journal Article

Version

acceptedVersion

Publication Date

2-2018

Abstract

One critical deficiency of traditional online kernel learning methods is their unbounded and growing number of support vectors in the online learning process, making them inefficient and non-scalable for large-scale applications. Recent studies on scalable online kernel learning have attempted to overcome this shortcoming, e.g., by imposing a constant budget on the number of support vectors. Although they attempt to bound the number of support vectors at each online learning iteration, most of them fail to bound the number of support vectors for the final output hypothesis, which is often obtained by averaging the series of hypotheses over all the iterations. In this article, we propose a novel framework for bounded online kernel methods, named "Sparse Passive-Aggressive (SPA)" learning, which is able to yield a final output kernel-based hypothesis with a bounded number of support vectors. Unlike the common budget maintenance strategy used by many existing budget online kernel learning approaches, the idea of our approach is to attain the bounded number of support vectors using an efficient stochastic sampling strategy that samples an incoming training example as a new support vector with a probability proportional to its loss suffered. We theoretically prove that SPA achieves an optimal mistake bound in expectation, and we empirically show that it outperforms various budget online kernel learning algorithms. Finally, in addition to general online kernel learning tasks, we also apply SPA to derive bounded online multiple-kernel learning algorithms, which can significantly improve the scalability of traditional Online Multiple-Kernel Classification (OMKC) algorithms while achieving satisfactory learning accuracy as compared with the existing unbounded OMKC algorithms.

Keywords

Kernel methods, Online learning, Online multiple-kernel learning

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

ACM Transactions on Intelligent Systems and Technology

Volume

9

Issue

4

First Page

45:1

Last Page

27

ISSN

2157-6904

Identifier

10.1145/3156684

Publisher

Association for Computing Machinery (ACM)

Copyright Owner and License

LARC and Authors

Additional URL

https://doi.org/10.1145/3156684

Download

Share

COinS