Sequential Facility Location: Approximate Submodularity and Greedy Algorithm
Sequential Facility Location: Approximate Submodularity and Greedy Algorithm
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Ehsan Elhamifar
中科院分区：
文献类型：
--
作者：
Ehsan Elhamifar
结合数据的动态模型，提出并分析了一种新的效用函数和序列数据子集选择的快速优化算法。我们提出了一种基数约束的顺序设施选址函数，它找到固定数量的代表，其中代表的序列与动态模型兼容，并且对数据进行了很好的编码。由于这种新目标函数的极大化是NP困难的，我们提出了一种基于子模极大化的快速贪婪算法。与传统的设施选址不同，在我们的情况下，边际收益的计算不能通过对每个项目的独立操作来完成。我们利用问题的序列结构，开发了一种基于动态规划的高效算法，该算法可以精确地计算边际收益。研究了效用函数为(ε-近似)次模时动态模型的条件，从而保证了贪婪算法的性能。通过在人工数据和教学视频中的过程学习问题上的实验表明，该框架显著地缩短了计算时间，获得了更好的目标函数值，并获得了更一致的摘要。
We develop and analyze a novel utility function and a fast optimization algorithm for subset selection in sequential data that incorporates the dynamic model of data. We propose a cardinalityconstrained sequential facility location function that finds a fixed number of representatives, where the sequence of representatives is compatible with the dynamic model and well encodes the data. As maximizing this new objective function is NPhard, we develop a fast greedy algorithm based on submodular maximization. Unlike the conventional facility location, the computation of the marginal gain in our case cannot be done by operations on each item independently. We exploit the sequential structure of the problem and develop an efficient dynamic programming-based algorithm that computes the marginal gain exactly. We investigate conditions on the dynamic model, under which our utility function is (ε-approximately) submodualr, hence, the greedy algorithm comes with performance guarantees. By experiments on synthetic data and the problem of procedure learning from instructional videos, we show that our framework significantly improves the computational time, achieves better objective function values and obtains more coherent summaries.