Back to publications
ICMLJanuary 2013

Knapsack constrained contextual submodular list prediction with application to multi-document summarization

Jiaji Zhou, Stephane Ross, Yisong Yue, Debadeepta Dey, J Andrew Bagnell

International Conference on Machine Learning

PDF

Many prediction domains, such as ad placement, recommendation, trajectory prediction, and document summarization, require predicting a set or list of options. Such lists are often evaluated using submodular reward functions that measure both quality and diversity. We propose a simple, efficient, and provably near-optimal approach to optimizing such prediction problems based on noregret learning. Our method leverages a surprising result from online submodular optimization: a single no-regret online learner can compete with an optimal sequence of predictions. Compared to previous work, which either learn a sequence of classifiers or rely on stronger assumptions such as realizability, we ensure both data-efficiency as well as performance guarantees in the fully agnostic setting. Experiments validate the efficiency and applicability of the approach on a wide range of problems including manipulator trajectory optimization, news recommendation and document summarization.

@article{ross2013learning,
  title={Learning policies for contextual submodular prediction},
  author={Ross, Stephane and Zhou, Jiaji and Yue, Yisong and Dey, Debadeepta and Bagnell, J Andrew},
  journal={International Conference on Machine Learning},
  year={2013}
}