论文标题
分量最大覆盖问题的变分优化
Variational Optimization for the Submodular Maximum Coverage Problem
论文作者
论文摘要
我们检查\ emph {subsodular最大覆盖范围问题}（SMCP），这与广泛的应用有关。我们基于Nemhauser差异为此问题提供了第一个变化近似，并证明可以使用变分优化有效地解决它。该算法在两个步骤之间交替：（1）E步骤估计一个变分参数以最大化参数化\ emph {modular}下限； （2）通过解决局部近似问题来更新解决方案的M步骤。我们提供有关拟议方法及其曲率依赖性近似因素的性能的理论分析，并在许多公共数据集和几个应用程序任务上对其进行经验评估。
We examine the \emph{submodular maximum coverage problem} (SMCP), which is related to a wide range of applications. We provide the first variational approximation for this problem based on the Nemhauser divergence, and show that it can be solved efficiently using variational optimization. The algorithm alternates between two steps: (1) an E step that estimates a variational parameter to maximize a parameterized \emph{modular} lower bound; and (2) an M step that updates the solution by solving the local approximate problem. We provide theoretical analysis on the performance of the proposed approach and its curvature-dependent approximate factor, and empirically evaluate it on a number of public data sets and several application tasks.
