- ICML连续次模函数实现强大的预算分配
本文从鲁棒优化的角度重新审视了连续版本的预算分配或二分图影响最大化问题,并利用与连续次模函数的联系以及求解受约束子模最小化问题的方法精确地解决了这个非凸问题。
- Jaccard 距离的三角不等式注释
本文提供了两个简单的证明方式,针对 Jaccard 距离中的三角形不等式,使用非负、单调、次模函数进行讨论。
- 采样优化的限制
本文提出了优化采样函数的新框架 optimization from samples (OPS),并证明了在特定条件下,仍然存在一类函数无法进行有效的优化,但对于一些子模函数,仍然可以进行有效的近似。
- 子模函数:从离散到连续领域
本文研究了次模函数及其在凸优化和概率测度方面的应用,提出了连续化的概率测度拓展方式,利用多重边际最优传送理论对次模集函数情况下的推论进行了拓展,最终给出了离散域中通用次模函数的实际最小化算法及其收敛速率。
- 离散点过程的快速混合
本文研究用于离散点过程的快速混合马尔可夫链蒙特卡罗采样的系统设计机制,探究了设置条件和误差限制的方法,提出了如何使用 Hessian 量来控制分解信息量,指出如果使用自然的相关性衰减概念,可以使用快速混合的 MCMC 方法导出较小的误差上限 - 子模遇上结构化:在指数级结构化项目集中找到多样化子集
通过在组合项集上应用子模函数和高阶潜力,探索用于在结构化输出空间中找到多元解法子集的贪心算法,将贪心增广步骤降低到带有适当构造的高阶潜力的因子图推理中,以实现高效近似最大化。
- 在线玄学最大化下的基合约束与学习分配应用
本文提出了一种能够动态地为信息源进行排序,同时又能保证重复信息的减少不会影响子模函数的最优化问题算法,并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。
- 可分解子模函数最小化的收敛速度
本文介绍一种易用且可并行的用于最小化由 “简单” 子模函数组成的子模函数的算法,并在几何子模多面体的基础上,利用谱图理论结果证明该算法线性收敛,并给出了收敛速率的上下界。
- 弱次模函数
本文研究了弱次模函数的性质及优化问题,其中包括了一些次超模函数,并提出了在均匀和一般性拟阵约束下最大化弱次模函数的优化问题,在此问题中,我们证明了标准贪心算法和简单局部搜索算法的算法近似比分别为 5.95 和 10.22。
- 结构化学习总和子模高阶能量函数
本文介绍了一种基于判别学习的方法来寻找高阶先验,该方法采用了结构化 SVM 和用于求解子模流问题的延伸割算法,说明了如何更好地利用子模函数的表达能力,实现更好的交互式分割技术。
- 子模函数近似
本文研究了 submodular functions 可以被其他简单类别的 submodular functions 逼近的程度和方法,并证明了一些上下界。
- 通过子模最大化扩展印度自助餐流程
使用 Kurihara 和 Welling(2008 年)的极大期望框架进行线性高斯潜在特征模型的近似 MAP 推断,在模型证据的下限上得到一种次模函数。通过使用贪心算法最大化此函数,我们的推理方法与输入数据的规模呈线性比例。
- 关于树重新加权最大乘积消息传递的最优性
本文研究了基于树重加权的最大乘积(TRW)信息传递算法的性质,针对二元变量、成对耦合的情况下,证明满足弱树协议条件的 TRW 解总是能达到全局最优解且总是能够在线性松弛下实现。
- 一个子模 - 超模程序及其在区分性结构学习中的应用
本文通过基于凸凹过程的变分框架方法,提出了一种最小化两个次模函数之间差异的算法。该算法在机器学习中的应用包括生成式结构图模型和特征选择,结果表明使用此算法的判别式图模型分类器可以明显优于使用生成式图模型的分类器。
- 图形模型中近乎最优的非远视信息价值
提出了一种基于子模函数理论的随机算法,可以在多项式时间复杂度下有效地选择具有信息量的变量子集,并在两个复杂实际数据集上表现出良好效果。
- 近似最小化次模函数差的算法及应用
本研究扩展了 Narasimhan 和 Bilmes 的工作,提出了基于子模函数差别最小化的新算法,该算法能有效地解决多种组合约束的问题,并且能够用于许多机器学习问题中,它在性能上优于现有的算法。
- 子模函数学习:凸优化观点
本文从凸分析的角度介绍了子模函数,论述了子模函数最小化与各类凸优化问题的关系,提出了新的高效算法以及多种子模函数在机器学习中的应用。
- 子模最大化问题的对称性和可近似性
研究了使用问题的多线性松弛的优化问题的一些最近结果,提出了一种与对称差相关的不可近似性结果的一般方法,证明了最大化基于 matroid 的非负次模函数问题不存在常数近似算法。
- 通过多线性松弛和竞争解决方案的子模函数最大化
研究了如何在不同的 packing 类型约束下,最大化定义在给定集合上的非负子模函数,提出了一个基于多线性扩展和分数解取整的算法框架,并且解决了其中的一些重要限制问题,开辟了线性和子模函数最大化的新方法。
- 可分解次模函数的高效最小化
本文研究了一类新的子模函数优化问题,提出了一种基于平滑凸优化的算法 SLG,可用于解决具有数万个变量的分解子模函数问题,而且在一些合成基准测试和联合分类和分割任务中优于现有的子模函数优化算法。