论文标题
适用于合作建模的鲁棒性最小化
Robust Submodular Minimization with Applications to Cooperative Modeling
论文作者
论文摘要
在机器学习应用中，强大的优化变得越来越重要。本文研究了鲁棒性下最小化的问题。在几种应用中，诸如图像分割中的合作剪辑，图像对应中的合作匹配等几种应用中都会产生限制的下二次最小化。这些模型中的许多模型都定义在数据点的聚类中（例如图像中的像素），对于这些模型对数据的稳健和数据非常重要。尽管几篇现有的论文研究了强大的下管最大化，但我们的作品是在广泛的组合约束下研究最小化版本的第一项工作，包括基数，背包，矩形以及基于图的约束，例如剪切，路径，匹配和树木。在每种情况下，我们都提供可扩展的近似算法并研究硬度界限。最后，我们从经验上证明了我们算法在合成和现实世界数据集上的实用性。
Robust Optimization is becoming increasingly important in machine learning applications. This paper studies the problem of robust submodular minimization subject to combinatorial constraints. Constrained Submodular Minimization arises in several applications such as co-operative cuts in image segmentation, co-operative matchings in image correspondence, etc. Many of these models are defined over clusterings of data points (for example pixels in images), and it is important for these models to be robust to perturbations and uncertainty in the data. While several existing papers have studied robust submodular maximization, ours is the first work to study the minimization version under a broad range of combinatorial constraints including cardinality, knapsack, matroid as well as graph-based constraints such as cuts, paths, matchings, and trees. In each case, we provide scalable approximation algorithms and also study hardness bounds. Finally, we empirically demonstrate the utility of our algorithms on synthetic and real-world datasets.
