Online Summarization via Submodular and Convex Optimization
Online Summarization via Submodular and Convex Optimization
复制标题
DOI：
10.1109/cvpr.2017.197
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Ehsan Elhamifar;M. Clara De Paolis Kaluza
中科院分区：
文献类型：
--
作者：
Ehsan Elhamifar;M. Clara De Paolis Kaluza
我们考虑的问题，子集选择在线设置，数据到达增量。我们提出了一个增量子集选择框架，而不是在整个数据集上存储和运行子集选择，该框架在每个时刻使用先前选择的代表集和新的一批数据来更新代表集。我们将问题转换为整数二进制优化，通过由选定项目的数量正则化的代表来最小化数据的编码成本。由于所提出的优化是，在一般情况下，NP-难和非凸的，我们研究了基于无约束子模块优化的贪婪方法，也提出了一个有效的凸松弛。我们表明，在适当的条件下，我们提出的凸算法的解决方案实现的非凸问题的全局最优解。我们的研究结果还解决了传统的问题，在离线设置的子集选择，作为一个特殊的情况。通过对视频摘要问题的大量实验，我们证明了我们提出的在线子集选择算法在真实的数据上表现良好，捕获视频中的各种代表性事件，同时获得接近离线设置的目标函数值。
We consider the problem of subset selection in the online setting, where data arrive incrementally. Instead of storing and running subset selection on the entire dataset, we propose an incremental subset selection framework that, at each time instant, uses the previously selected set of representatives and the new batch of data in order to update the set of representatives. We cast the problem as an integer binary optimization minimizing the encoding cost of the data via representatives regularized by the number of selected items. As the proposed optimization is, in general, NP-hard and non-convex, we study a greedy approach based on unconstrained submodular optimization and also propose an efficient convex relaxation. We show that, under appropriate conditions, the solution of our proposed convex algorithm achieves the global optimal solution of the non-convex problem. Our results also address the conventional problem of subset selection in the offline setting, as a special case. By extensive experiments on the problem of video summarization, we demonstrate that our proposed online subset selection algorithms perform well on real data, capturing diverse representative events in videos, while they obtain objective function values close to the offline setting.