提出新方法在分配格上高效优化子模函数，避免传统方法的指数膨胀问题。
Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization
- 直接在分配格内操作，不转到布尔格
- 实验显示运行时间显著优于传统方法
- 适合需要高效子模优化的视觉与机器学习场景
子模函数最小化近年来受到广泛关注，尤其在计算机视觉和机器学习中应用广泛。许多应用涉及定义在分配格上的子模函数。当前主流方法是通过扩展到布尔格来处理，但会导致工作空间呈集合大小的指数级增长，严重降低效率。本文提出一种通用框架，直接在分配格上进行优化，无需转换至布尔格。该框架可复用已有的布尔格子模优化算法。实验表明，与传统方法相比，本方法在运行时间上实现巨大提升。
原文摘要 · Abstract (English)
Submodular function minimization has gained a lot of interest in recent years. They are highly applicable in the area of Computer Vision and Machine Learning. Often such applications require to work with submodular functions defined on distributive lattice. Current best way of dealing with it is using a transformation which extrapolates the submodular function for the respective boolean lattice. It makes optimization system too inefficient due to enlargement of the working space. Quantitatively, the expanded space has additional exponential (in set size) number of elements. We propose a generic framework for dealing with distributive lattice which only works within distributive lattice. Our framework allows one to use already established submodular function minimization algorithms for boolean lattice. In our experiment, we show the huge improvement in terms of running time over tranditional methods for handling distributive lattice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。