Adapting Kernel Representations Online Using Submodular Maximization

Matthew Schlegel, Yangchen Pan, Jiecao Chen, Martha White
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3037-3046, 2017.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-schlegel17a, title = {Adapting Kernel Representations Online Using Submodular Maximization}, author = {Matthew Schlegel and Yangchen Pan and Jiecao Chen and Martha White}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3037--3046}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/schlegel17a/schlegel17a.pdf}, url = {https://proceedings.mlr.press/v70/schlegel17a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Adapting Kernel Representations Online Using Submodular Maximization %A Matthew Schlegel %A Yangchen Pan %A Jiecao Chen %A Martha White %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-schlegel17a %I PMLR %P 3037--3046 %U https://proceedings.mlr.press/v70/schlegel17a.html %V 70 %X 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.
APA
Schlegel, M., Pan, Y., Chen, J. & White, M.. (2017). Adapting Kernel Representations Online Using Submodular Maximization. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3037-3046 Available from https://proceedings.mlr.press/v70/schlegel17a.html.

Related Material