Scaling Submodular Maximization via Pruned Submodularity Graphs
원문 초록
We propose a new random pruning method (called "submodular sparsification (SS)") to reduce the cost of submodular maximization. The pruning is applied via a "submodularity graph" over the $n$ ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each step, SS prunes a $1-1/\sqrt{c}$ (for $c>1$) fraction of the nodes using weights on edges computed based on only a small number ($O(\log n)$) of randomly sampled nodes. The algorithm requires $\log_{\sqrt{c}}n$ steps with a small and highly parallelizable per-step computation. An accuracy-speed tradeoff parameter $c$, set as $c = 8$, leads to a fast shrink rate $\sqrt{2}/4$ and small iteration complexity $\log_{2\sqrt{2}}n$. Analysis shows that w.h.p., the greedy algorithm on the pruned set of size $O(\log^2 n)$ can achieve a guarantee similar to that of processing the original dataset. In news and video summarization tasks, SS is able to substantially reduce both computational costs and memory usage, while maintaining (or even slightly exceeding) the quality of the original (and much more costly) greedy algorithm.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SD-VSum: A Method and Dataset for Script-Driven Video Summarization
An Egocentric Vision-Language Model based Portable Real-time Smart Assistant
What Is That Talk About? A Video-to-Text Summarization Dataset for Scientific Presentations
Do Language Models Understand Time?
Video Repurposing from User Generated Content: A Large-scale Dataset and Benchmark
Does SpatioTemporal information benefit Two video summarization benchmarks?
토론
이 논문과 연결된 포럼 글이 아직 없습니다.