SCIENCE@home

Learning Policies for Contextual Submodular Prediction

S. Ross,Jiaji Zhou,Yisong Yue,Debadeepta Dey,J. Bagnell

Published 2013 in International Conference on Machine Learning

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 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.

PUBLICATION RECORD

  • Publication year

    2013

  • Venue

    International Conference on Machine Learning

  • Publication date

    2013-05-11

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1305.2532
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-27 of 27 references · Page 1 of 1

CITED BY

Showing 1-34 of 34 citing papers · Page 1 of 1