Big Data Summarization Using Submodular Functions
Baharan Mirzasoleiman · Repository for Publications and Research Data (ETH Zurich) · 2017
Data summarization, a central challenge in machine learning, is the task of finding a representative subset of manageable size out of a large dataset.It has found numerous applications, including image summarization, document and corpus summarization, recommender systems, and non-parametric learning, to name a few.A general recipe to obtain a faithful summary is to turn the problem into selecting a subset of data elements optimizing a utility function that quantifies "representativeness" of the selected set.Often times, the choice of utility functions used for summarization exhibit submodularity, a natural diminishing returns property.In words, submodularity implies that the added value of any element from the dataset decreases as we include more data points to the summary.Thus, the data summarization problem can be naturally reduced to that of a constrained submodular maximization, or a submodular cover problem.Although, there are efficient centralized algorithms for the aforementioned problems, they are highly impractical for massive datasets, as sequentially selecting elements on a single machine is heavily constrained in terms of speed and memory.Hence, in order to solve the above submodular optimization problems at scale, we need to make use of MapReduce-style parallel computation models, or resort to streaming algorithms.In this Thesis, we develop large scale algorithms for submodular summarization.In particular, we present a simple, parallel protocol, called G reeD i for distributed (notnecessarily monotone) submodular maximization subject to cardinality, and other general types of constraints, including matroid and knapsack constraints.In addition, we develop a distributed algorithm, D isC over, for the submodular cover problem, as well as a fast distributed algorithm, FastCover, that enables us to solve the more general problem of covering multiple submodular functions in one run of the algorithm.We then consider the streaming setting, where at any point of time, the algorithm iii