Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityDocument SummarizationMulti-Document SummarizationSimilar Papers 제목 키워드 기반
Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and $k$-System Constraints
In this paper, we study the non-monotone adaptive submodular maximization problem subject to a knapsack and a $k$-system constraints. The input of our problem is a set of items, where each item has a particular state dra…
2kSubmodular Optimization with Submodular Cover and Submodular Knapsack Constraints
We investigate two new optimization problems — minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound c…
DiversitySubmodular Optimization with Submodular Cover and Submodular Knapsack Constraints
We investigate two new optimization problems -- minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound …
DiversityFast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring …
MarketingSubmodular Maximization Through Barrier Functions
In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves the running time for constrained submodul…
Movie Recommendation