Towards Unsupervised Learning of Submodular Functions for Summarization

Thesis (Ph.D.)--University of Washington, 2020In the information age, vast volumes of data are generated daily. There exist a plethora of data sources, including text, videos, and sensor networks. The large size of data can make it difficult to process. Furthermore, the generated data often has considerable redundancy. Therefore, extracting meaningful information from the data can make it easier to process for downstream tasks. Summarization is one way to extract this information. In the past, submodular functions have been successfully used for summarizing data. These functions can be defined based on domain knowledge or can be learned from the data itself. However, supervised learning of submodular functions faces an obstacle as there is often a lack of known good summaries of the data for training. Therefore, it would be beneficial if the functions can be learned in an unsupervised manner. This work proposes an approach towards learning a mixture of submodular functions in an unsupervised manner. It is achieved through a two-part process. First, an autoencoder neural network is trained in a constrained manner. The aim is to produce features such that a larger feature value implies that the input data sample has a larger amount of the corresponding learned property. It is analogous to bag-of-words features, with the ``words'' learned automatically. Next, a mixture of submodular functions is instantiated using the learned features. Each component of the mixture consists of a concave composed with a modular function. The mixture weights are learned through an approach that does not directly utilize supervised summary information. It optimizes a set of meta-objectives, each of which corresponds to a likely necessary condition on what constitutes a good summarization objective. Empirical results on different data modalities show that the proposed two-part process produces functions that perform significantly better than a variety of baseline methods. This work also explores other applications of the proposed features. The focus application is the summarization of video streams on the fly under a memory budget. The aim is to produce running summaries (within a budget) of incoming video streams at each time step. Any video snippet that is not part of a summary at a given time step is dropped to abide by the memory constraints. To this end, this work proposes two algorithms, one each for single-stream and multi-stream summarization. Empirical evaluations demonstrate that the algorithms, instantiated with the proposed features, can outperform the baselines. In addition to these explorations, it is also shown that the proposed constrained training can be used with different flavors of autoencoder architectures and losses. The influence of these different setups is also demonstrated for the task of summarization