Learning Policies for Contextual Submodular Prediction

Stephane Ross, Jiaji Zhou, Yisong Yue, Debadeepta Dey, and J. Andrew (Drew) Bagnell
The 30th International Conference on Machine Learning (ICML 2013), July, 2013.


Download
  • Adobe portable document format (pdf) (521KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
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 no-regret 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.

Keywords
list prediction, submodular optimization, online learning

Notes

Text Reference
Stephane Ross, Jiaji Zhou, Yisong Yue, Debadeepta Dey, and J. Andrew (Drew) Bagnell, "Learning Policies for Contextual Submodular Prediction," The 30th International Conference on Machine Learning (ICML 2013), July, 2013.

BibTeX Reference
@inproceedings{Ross_2013_7449,
   author = "Stephane Ross and Jiaji Zhou and Yisong Yue and Debadeepta Dey and J. Andrew (Drew) Bagnell",
   title = "Learning Policies for Contextual Submodular Prediction",
   booktitle = "The 30th International Conference on Machine Learning (ICML 2013)",
   month = "July",
   year = "2013",
}