Adapting Kernel Representations Online Using Submodular Maximization
- Matthew Schlegel
- Yangchen Pan
- Jiecao Chen
- Martha White, University of Alberta
Kernel representations provide a nonlinear representation, through similarities to prototypes, but require only simple linear learning algorithms given those prototypes. In a continual learning setting, with a constant stream of observations, it is critical to have an efficient mechanism for sub-selecting prototypes amongst observations. In this work, we develop an approximately submodular criterion for this setting, and an efficient online greedy submodular maximization algorithm for optimizing the criterion. We extend streaming submodular maximization algorithms to continual learning, by removing the need for multiple passes—which is infeasible—and instead introducing the idea of coverage time. We propose a general block-diagonal approximation for the greedy update with our criterion, that enables updates linear in the number of prototypes. We empirically demonstrate the effectiveness of this approximation, in terms of approximation quality, significant runtime improvements, and effective prediction performance.
Citation
M. Schlegel, Y. Pan, J. Chen, M. White. "Adapting Kernel Representations Online Using Submodular Maximization". International Conference on Machine Learning (ICML), (ed: Doina Precup, Yee Whye Teh), pp 3037-3046, August 2017.Keywords: | |
Category: | In Conference |
Web Links: | PMLR |
BibTeX
@incollection{Schlegel+al:ICML17, author = {Matthew Schlegel and Yangchen Pan and Jiecao Chen and Martha White}, title = {Adapting Kernel Representations Online Using Submodular Maximization}, Editor = {Doina Precup, Yee Whye Teh}, Pages = {3037-3046}, booktitle = {International Conference on Machine Learning (ICML)}, year = 2017, }Last Updated: February 25, 2020
Submitted by Sabina P