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

Jiaji Zhou, Stephane Ross, Yisong Yue, Debadeepta Dey, and J. Andrew (Drew) Bagnell
ICML 2013 Workshop on Inferning: Interactions between Inference and Learning , July, 2013.


Download
  • Adobe portable document format (pdf) (380KB)
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
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.

Keywords
List Prediction, Document Summarization, Submodularity

Notes

Text Reference
Jiaji Zhou, Stephane Ross, Yisong Yue, Debadeepta Dey, and J. Andrew (Drew) Bagnell, "Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization," ICML 2013 Workshop on Inferning: Interactions between Inference and Learning , July, 2013.

BibTeX Reference
@inproceedings{Zhou_2013_7450,
   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 = "ICML 2013 Workshop on Inferning: Interactions between Inference and Learning ",
   month = "July",
   year = "2013",
}