Data Summarization at Scale: A Two-Stage Submodular Approach

Marko Mitrovic, Ehsan Kazemi, Morteza Zadimoghaddam, Amin Karbasi
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3596-3605, 2018.

Abstract

The sheer scale of modern datasets has resulted in a dire need for summarization techniques that can identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. We focus on a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions (drawn from the same distribution) over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper, we develop the first streaming and distributed solutions to this problem. In addition to providing strong theoretical guarantees, we demonstrate both the utility and efficiency of our algorithms on real-world tasks including image summarization and ride-share optimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-mitrovic18a, title = {Data Summarization at Scale: A Two-Stage Submodular Approach}, author = {Mitrovic, Marko and Kazemi, Ehsan and Zadimoghaddam, Morteza and Karbasi, Amin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3596--3605}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/mitrovic18a/mitrovic18a.pdf}, url = {https://proceedings.mlr.press/v80/mitrovic18a.html}, abstract = {The sheer scale of modern datasets has resulted in a dire need for summarization techniques that can identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. We focus on a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions (drawn from the same distribution) over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper, we develop the first streaming and distributed solutions to this problem. In addition to providing strong theoretical guarantees, we demonstrate both the utility and efficiency of our algorithms on real-world tasks including image summarization and ride-share optimization.} }
Endnote
%0 Conference Paper %T Data Summarization at Scale: A Two-Stage Submodular Approach %A Marko Mitrovic %A Ehsan Kazemi %A Morteza Zadimoghaddam %A Amin Karbasi %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-mitrovic18a %I PMLR %P 3596--3605 %U https://proceedings.mlr.press/v80/mitrovic18a.html %V 80 %X The sheer scale of modern datasets has resulted in a dire need for summarization techniques that can identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. We focus on a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions (drawn from the same distribution) over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper, we develop the first streaming and distributed solutions to this problem. In addition to providing strong theoretical guarantees, we demonstrate both the utility and efficiency of our algorithms on real-world tasks including image summarization and ride-share optimization.
APA
Mitrovic, M., Kazemi, E., Zadimoghaddam, M. & Karbasi, A.. (2018). Data Summarization at Scale: A Two-Stage Submodular Approach. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3596-3605 Available from https://proceedings.mlr.press/v80/mitrovic18a.html.

Related Material