Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function
Submodular maximization with the greedy algorithm has been studied as an effective approach to extractive summarization. This approach is known to have three advantages: its applicability to many useful submodular objective functions, the efficiency of the greedy algorithm, and the provable performance guarantee. However, when it comes to compressive summarization, we are currently missing a counterpart of the extractive method based on submodularity. In this paper, we propose a fast greedy method for compressive summarization. Our method is applicable to any monotone submodular objective function, including many functions well-suited for document summarization. We provide an approximation guarantee of our greedy algorithm. Experiments show that our method is about 100 to 400 times faster than an existing method based on integer-linear-programming (ILP) formulations and that our method empirically achieves more than 95{\%}-approximation.
Code (0)
등록된 구현이 없습니다.
Tasks
Document SummarizationExtractive SummarizationInformation RetrievalSimilar Papers 제목 키워드 기반
Lazier Than Lazy Greedy
Is it possible to maximize a monotone submodular function faster than the widely used lazy greedy algorithm (also known as accelerated greedy), both in theory and practice? In this paper, we develop the first linear-time…
ClusteringData SummarizationNon-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approxima…
Video SummarizationFast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning
Compressive Sensing Approaches for Autonomous Object Detection in Video Sequences
Video analytics requires operating with large amounts of data. Compressive sensing allows to reduce the number of measurements required to represent the video using the prior knowledge of sparsity of the original signal,…
Compressive Sensingobject-detectionObject DetectionThe Power of Subsampling in Submodular Maximization
We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set, and use simple combinatoria…
Movie RecommendationVideo Summarization