Sparse Passive-Aggressive learning for bounded online kernel methods

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 ov...

Full description

Saved in:
Bibliographic Details
Main Authors: LU, Jing, SAHOO, Doyen, ZHAO, Peilin, HOI, Steven C. H.
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2018
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/3999
https://ink.library.smu.edu.sg/context/sis_research/article/5001/viewcontent/sparse.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5001
record_format dspace
spelling sg-smu-ink.sis_research-50012021-03-26T07:19:11Z Sparse Passive-Aggressive learning for bounded online kernel methods LU, Jing SAHOO, Doyen ZHAO, Peilin HOI, Steven C. H. 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. 2018-02-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/3999 info:doi/10.1145/3156684 https://ink.library.smu.edu.sg/context/sis_research/article/5001/viewcontent/sparse.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Kernel methods Online learning Online multiple-kernel learning Databases and Information Systems Numerical Analysis and Scientific Computing Theory and Algorithms
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Kernel methods
Online learning
Online multiple-kernel learning
Databases and Information Systems
Numerical Analysis and Scientific Computing
Theory and Algorithms
spellingShingle Kernel methods
Online learning
Online multiple-kernel learning
Databases and Information Systems
Numerical Analysis and Scientific Computing
Theory and Algorithms
LU, Jing
SAHOO, Doyen
ZHAO, Peilin
HOI, Steven C. H.
Sparse Passive-Aggressive learning for bounded online kernel methods
description 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.
format text
author LU, Jing
SAHOO, Doyen
ZHAO, Peilin
HOI, Steven C. H.
author_facet LU, Jing
SAHOO, Doyen
ZHAO, Peilin
HOI, Steven C. H.
author_sort LU, Jing
title Sparse Passive-Aggressive learning for bounded online kernel methods
title_short Sparse Passive-Aggressive learning for bounded online kernel methods
title_full Sparse Passive-Aggressive learning for bounded online kernel methods
title_fullStr Sparse Passive-Aggressive learning for bounded online kernel methods
title_full_unstemmed Sparse Passive-Aggressive learning for bounded online kernel methods
title_sort sparse passive-aggressive learning for bounded online kernel methods
publisher Institutional Knowledge at Singapore Management University
publishDate 2018
url https://ink.library.smu.edu.sg/sis_research/3999
https://ink.library.smu.edu.sg/context/sis_research/article/5001/viewcontent/sparse.pdf
_version_ 1770574115819749376