RI: Medium: Advances and Applications in Submodularity for Machine Learning

子模块性是一个直观的收益递减属性，说明将元素添加到较小的集合比将其添加到较大的集合更有帮助。子模块性允许人们有效地找到离散问题的可证明最优或接近最优的解决方案。 子模最小化已经找到了用途，例如，在图形模型推断和聚类中，尽管已经应用了最大化，例如，变量/特征选择和主动学习。 然而，子模块化在机器学习及其应用中的适用性才刚刚开始。 此外，在组合学和运筹学文献中的子模块优化工作基本上没有意识到机器学习中出现的独特问题。因此，现有的标准算法不利用机器学习中出现的子模块问题的某些结构或变体。因此，研究涉及子模块目标的新机器学习问题可以导致纯组合学文献的进步。 我们建议将机器学习和组合优化的研究结合起来，以解决两个社区都无法单独解决的问题。特别是，我们建议使用机器学习的见解来扩大典型的子模块优化问题的规模（通过关注学习中出现的问题实例）。我们还建议进一步绘制子模块化在机器学习中发挥作用的领域。在本研究中，我们将介绍与子模块性相关的新的子模块结构。我们将介绍机器学习的子模块学习问题。我们将介绍新的带约束的子模优化问题。最后，我们将把这些子模块实例应用到计算机视觉、语音识别和自然语言处理的实际应用中。

Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Submodularity allows one to efficiently find provably optimal or near-optimal solutions to discrete problems. Submodular minimization has found use, e.g., in graphical model inference and clustering, whereas maximization has been applied, e.g., to variable/feature selection and active learning. Submodularity, however, is still only beginning to show applicability in machine learning and its applications. Moreover, work on submodular optimization in the combinatorics and operations research literature has been primarily unaware of unique problems arising in machine learning. Therefore, existing standard algorithms do not exploit certain structures or variants of the submodular problems arising in machine learning. Studying novel machine learning problems involving submodular objectives can thus lead to advances in the pure combinatorics literature. We propose to pursue activities that bring together research in machine learning and combinatorial optimization to solve problems which neither of the communities can solve alone.In particular, we propose to use insights from machine learning to enable scaling up typical submodular optimization problem sizes (by focusing on problem instances arising in learning). We also propose to further chart the territory that submodularity plays in machine learning. In this grant, we will introduce new submodular structures specifically related to submodularity. We will introduce submodular learning problems for machine learning. We will introduce new submodular optimization problems with constraints. And lastly, we will apply these submodular instances to real-world applications in computer vision, speech recognition, and natural language processing.