Submodularity Cuts and Applications
Submodularity Cuts and Applications
复制标题
DOI：
--
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Y. Kawahara;Kiyohito Nagano;K. Tsuda;J. Bilmes
中科院分区：
文献类型：
--
作者：
Y. Kawahara;Kiyohito Nagano;K. Tsuda;J. Bilmes
机器学习中的几个关键问题，如特征选择和主动学习，可以用子模集函数最大化表示。本文提出了一种在基数约束下最大化子模集函数的新算法-该算法基于割平面方法，并实现为迭代小规模二进制整数线性规划过程。众所周知，该问题是NP-难的，并且贪婪算法所获得的近似因子是多项式时间的理论极限。至于（非多项式时间）的精确算法，在实践中表现合理，在文献中很少，虽然这个问题是相当重要的许多应用。我们的算法是保证找到精确的解决方案，许多迭代，它收敛速度快，在实践中，由于效率的切割平面机制。此外，我们还提供了一种方法，产生连续递减的最优解的上限，而我们的算法提供连续增加的下限。因此，可以在任何点估计当前解的准确性，并且一旦满足期望的容差程度，就可以提前停止算法。我们评估我们的算法在传感器放置和特征选择应用中表现出良好的性能。
Several key problems in machine learning, such as feature selection and active learning, can be formulated as submodular set function maximization. We present herein a novel algorithm for maximizing a submodular set function under a cardinality constraint — the algorithm is based on a cutting-plane method and is implemented as an iterative small-scale binary-integer linear programming procedure. It is well known that this problem is NP-hard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (non-polynomial time) exact algorithms that perform reasonably in practice, there has been very little in the literature although the problem is quite important for many applications. Our algorithm is guaranteed to find the exact solution finitely many iterations, and it converges fast in practice due to the efficiency of the cutting-plane mechanism. Moreover, we also provide a method that produces successively decreasing upper-bounds of the optimal solution, while our algorithm provides successively increasing lower-bounds. Thus, the accuracy of the current solution can be estimated at any point, and the algorithm can be stopped early once a desired degree of tolerance is met. We evaluate our algorithm on sensor placement and feature selection applications showing good performance.