Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization - Robotics Institute Carnegie Mellon University

Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization

Workshop Paper, ICML '13 Workshop on Inferning: Interactions between Inference and Learning, June, 2013

Abstract

We study the problem of predicting a set or list of options under knapsack constraint. The quality of such lists are evaluated by a submodular reward function that measures both quality and diversity. Similar to DAgger (Ross et al., 2010), by a reduction to online learning, we show how to adapt two sequence prediction models to imitate greedy maximization under knapsack constraint problems: CONSEQOPT (Dey et al., 2012) and SCP (Ross et al., 2013). Experiments on extractive multi-document summarization show that our approach outperforms existing state-of-the-art methods.

BibTeX

@workshop{Zhou-2013-7739,
author = {Jiaji Zhou and Stephane Ross and Yisong Yue and Debadeepta Dey and J. Andrew (Drew) Bagnell},
title = {Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization},
booktitle = {Proceedings of ICML '13 Workshop on Inferning: Interactions between Inference and Learning},
year = {2013},
month = {June},
keywords = {List Prediction, Document Summarization, Submodularity},
}