Learning Mixtures of Submodular Functions for Image Collection Summarization

Sebastian Tschiatschek, Rishabh K. Iyer, Haochen Wei, Jeff A. Bilmes

Introduction

We are living in an era of "visual overload." With hundreds of millions of images uploaded daily to platforms like Instagram and Flickr, managing these massive visual repositories is increasingly difficult. Whether dealing with a personal vacation album or a massive security feed, users frequently need a "summary"—a small, representative subset of images that captures the essence of the entire collection.

Example of a dense image collection requiring summarization.

A high-quality summary must balance two conflicting goals:

  1. Fidelity (Coverage): It should represent all the major concepts present in the collection. For instance, a vacation summary should include both the beach and the mountains if both were visited.
  2. Diversity: It should minimize redundancy, avoiding ten nearly identical photos of the same sunset.

Because "importance" is inherently subjective, previous methods relying on fixed algorithms (like standard clustering) often fail to adapt to diverse collection types. This paper introduces a supervised learning framework to automatically summarize large image collections by training a "mixture" of submodular functions, effectively learning how to summarize directly from human examples.

Methodology

The authors utilize submodular functions as the mathematical backbone of their approach. Submodularity naturally models the economic law of "diminishing returns": adding a specific image to a small, sparse summary provides significantly more new information than adding that same image to a large, already comprehensive summary.

Key Innovations

  • Mixtures of Functions: Rather than relying on a single, rigid algorithm, the researchers combine 594 different "component" functions into a weighted mixture. These components range from graph theory-based metrics to deep learning feature extractors.
  • Structured Prediction: The team employs a large-margin framework to learn the optimal weights for these components. The objective is to ensure that human-generated summaries consistently receive higher scores than any other possible subset of images.
  • V-ROUGE (Visual ROUGE): Inspired by the ROUGE metric used in text summarization, the authors developed V-ROUGE to evaluate visual summaries. It measures the overlap of "visual words" between a machine-generated summary and a human ground-truth summary. These visual words are extracted using color histograms, super-pixels, and the OverFeat deep convolutional neural network.
  • Optimization: The study found that using non-submodular optimization techniques—specifically the submodular-supermodular procedure—to handle the loss function during training yielded the most effective submodular models.

Datasets

To train and evaluate their models, the authors introduced a new benchmark dataset comprising 14 real-world collections. Each collection contains 100 images sourced from personal holiday trips.

To establish a human ground truth, they utilized Amazon Mechanical Turk to collect multiple summaries for each collection. Recognizing the variability in crowdsourced work, they also developed an automated pruning algorithm to filter out low-quality summaries that performed no better than random selection.

Key Results

The authors evaluated their method using 14-fold cross-validation, training on 13 collections and testing on the remaining one.

Performance comparison of the proposed methods against baselines across 14 datasets.
  • Beating the Baseline: Their best method, utilizing the $\ell_{1-R}$ loss function (based on $1 - V-ROUGE$), achieved an average score of 1.13. In this scoring system, 1.00 represents average human performance, and 0.00 represents random selection. This indicates the model often exceeds average human curation.
  • Superiority over Standard Methods: The learned mixture approach significantly outperformed common baselines. For example, K-Medoids (kM) scored 0.71, and Maximal Marginal Relevance (MMR) scored just 0.21.
  • Upper Bound: In "cheating" experiments—where the model was trained and tested on the same data to determine its theoretical maximum potential—the system reached a score of 1.42, suggesting significant headroom for finding mathematically "perfect" summaries.

Limitations and Future Work

While the results are promising, the authors note several limitations:

  • Scalability: The current study focused on collections of 100 images. Scaling the algorithm to handle 10,000+ images presents a significant computational challenge, as does collecting reliable human ground truth for such massive sets.
  • Subjectivity: Although V-ROUGE correlates well with human judgment, summarization remains subjective. Future iterations could focus on personalizing summaries based on specific user preferences.
  • Complexity: Utilizing 594 component functions is computationally intensive. Identifying a "minimal set" of highly effective components could streamline the system, making it viable for real-time, consumer-facing applications.

Summary updated

Abstract

We address the problem of image collection summarization by learning mixtures of submodular functions. We argue that submodularity is very natural to this problem, and we show that a number of previously used scoring functions are submodular — a property not explicitly mentioned in these publications. We provide classes of submodular functions capturing the necessary properties of summaries, namely coverage, likelihood, and diversity. To learn mixtures of these submodular functions as scoring functions, we formulate summarization as a supervised learning problem using large-margin structured prediction. Furthermore, we introduce a novel evaluation metric, which we call V-ROUGE, for automatic summary scoring. While a similar metric called ROUGE has been successfully applied to document summarization [14], no such metric was known for quantifying the quality of image collection summaries. We provide a new dataset consisting of 14 real-world image collections along with many human-generated ground truth summaries collected using mechanical turk. We also extensively compare our method with previously explored methods for this problem and show that our learning approach outperforms all competitors on this new dataset. This paper provides, to our knowledge, the first systematic approach for quantifying the problem of image collection summarization, along with a new dataset of image collections and human summaries.
BibTeX
@inproceedings{tschiatschek2014learning,
  author = {Sebastian Tschiatschek and Rishabh K. Iyer and Haochen Wei and Jeff A. Bilmes},
  title = {{Learning Mixtures of Submodular Functions for Image Collection Summarization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure