Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization
J. Andrew Bagnell
arXiv e-Print archive - 2013 via Local arXiv
First published: 2013/08/16 (9 years ago) 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.