Budgeted Nonparametric Learning from Data Streams
Abstract
We consider the problem of extracting informative exemplars from a data stream. Examples of this problem include exemplar-based clustering and nonparametric inference such as Gaussian process regression on massive data sets. We show that these problems require maximization of a submodular function that captures the informativeness of a set of exemplars, over a data stream. We develop an efficient algorithm, Stream Greedy, which is guaranteed to obtain a constant fraction of the value achieved by the optimal solution to this NP-hard optimization problem. We extensively evaluate our algorithm on large real- world data sets.
Cite
Text
Gomes and Krause. "Budgeted Nonparametric Learning from Data Streams." International Conference on Machine Learning, 2010.Markdown
[Gomes and Krause. "Budgeted Nonparametric Learning from Data Streams." International Conference on Machine Learning, 2010.](https://mlanthology.org/icml/2010/gomes2010icml-budgeted/)BibTeX
@inproceedings{gomes2010icml-budgeted,
title = {{Budgeted Nonparametric Learning from Data Streams}},
author = {Gomes, Ryan and Krause, Andreas},
booktitle = {International Conference on Machine Learning},
year = {2010},
pages = {391-398},
url = {https://mlanthology.org/icml/2010/gomes2010icml-budgeted/}
}