基于块坐标Frank-Wolfe算法在结构能量最小化问题的MAP推理中的应用方法

1基于块坐标Frank-Wolfe算法Paul SwobodaMPI for Informatics，德国pswoboda@mpi-inf.mpg.de奥地利vnk@ist.ac.at摘要本文提出了一种新的用于结构能量最小化问题的最大后验（MAP）推理的邻近束方法该方法利用拉格朗日分解的特殊结构，采用多平面块坐标Frank-Wolfe方法对原能量最小化问题的拉格朗日松弛进行我们的经验表明，我们的方法优于一些具有挑战性的马尔可夫随机场，多标签离散断层扫描和图形匹配问题的最先进的拉格朗日分解为基础的算法1. 介绍最大后验（MAP）推理，即在离散的标记集合X上最小化能量函数f：X → R，是计算机视觉和机器学习中的核心工具。对于能量f和标记空间X的各种特殊形式，已经提出了许多求解器，参见[11]，了解马尔可夫随机场（MRF）的突出特殊情况的求解器和应用的概述。解算器大致可分为三类：(i)使用搜索技术的精确求解器（例如，分支定界）并且可能依赖于用LP求解器求解下界以加速搜索，（ii）用适合于特定问题的自组织搜索策略找到次优解的原始算法，以及（iii）拉格朗日分解（也称为基于对偶分解）的算法，其将原始问题分解为更小的有效可优化的子问题，并在子问题之间交换拉格朗日乘子，直到子问题之间达成一致除非能量满足特殊假设，否则精确求解器通常不适用，因为计算机视觉中的问题尺寸太大。另一方面，原始算法可能很快，但解决方案的质量不需要很好该作品是在第一作者在IST奥地利时完成的。这项工作得到了欧洲研究委员会根据欧盟第七框架计划（FP 7/2007-2013）/ERC赠款协议616160的支持。也没有给出任何信息来判断它。此外，前两种范式的算法通常是针对特定的优化问题开发的，并且不能轻易地扩展到其他问题。基于拉格朗日分解的算法是一个很好的中间立场，因为它们优化了一个对偶下界，因此可以输出一个显示到最优值的距离的差距，但使用的技术可以扩展到大的问题大小。由于子问题可以很容易地组合在一起，因此将其推广到新问题通常也容易得多已经提出了大量的算法技术来优化MRF的拉格朗日分解，包括（i）消息传递[16，42，38，6]（也称为块坐标上升，置信传播），（ii）一阶近似分裂方法[26，31]和（iii）基于平滑的方法[9，29]，（iv）Nesterov方案[28，10]，（v）镜像下降[22]，（vi）基于次梯度的算法[30，36，18]。在MRF中的MAP推断的情况下，研究[11]已经表明，消息传递技术在很大程度上优于然而，消息传递算法有两个主要的实际缺点：（i）它们不需要收敛到对应于La-grangean分解的松弛的最佳值：虽然设计良好的算法单调地改进对偶下界，但是它们可能卡在次优固定点中。（ii）对于给定的拉格朗日分解中的所有子问题，所谓的最小边际必须是可快速虽然上述问题对于MRF中的大多数MAP推理任务似乎不是问题，但对于其他问题，它们是。在这种情况下，必须使用替代技术。基于次梯度的方法可以在这里提供帮助，因为它们不具有上述缺点：它们收敛到拉格朗日松弛的最优值，并且只需要找到分解的子问题的解，这比它们的最小边缘（如（i）所需），近似步骤（如（ii）所需）或平滑解（如（iii）和（iv）所需）更容易。最简单的基于次梯度的算法是次梯度上升。然而，其收敛通常是缓慢的。Bundle方法存储一系列次梯度来构建待优化函数的局部近似，经验上收敛得更快。1114611147的t1.1. 捐款组织我们提出了一个多平面块坐标版本的Frank-Wolfe方法，以找到最小化方向，近端束框架，见第2节。我们的方法利用了问题的拉格朗日分解的结构我们的方法的应用MRF，离散层析成像和图形匹配的介绍在第3节。在第4节中给出了对这些问题的实验评估，并表明我们的方法优于可比的已建立的方法。所有的证明都在扩展版本中给出[37]。我们的Frank-Wolfe方法的C++实现可在http://pub.ist.ac.at/~vnk/papers/FWMAP.html上获得。在我们的方法之上构建的MRF、离散断层 扫 描 和 图 形 匹 配 求 解 器 可 以 在https://github.com/LPMP/LPMP上获得。1.2. 相关工作据我们所知，Frank-Wolfe方法尚未在我们的一般环境中使用，即。作为结构化能量最小化问题的一般类的邻近束求解器的基础。因此，我们将相关工作细分为(i)次梯度/束能量最小化的方法，（二）特设的方法，使用弗兰克-沃尔夫的特定任务和（iii）近端束方法。基于次梯度的求解器首先被提出，[36]《易经》云：“君子之道，焉可诬也？有始有卒者，其惟圣人乎。更大的子问题。在一般情况下，我们的分解结果在更少的对偶变量优化，每个弗兰克-沃尔夫更新可以预期会得到更大的增益。Frank-Wolfe在[1]中也用于具有Potts相互作用和高斯权重的密集MRF正如我们所做的那样，他们使用Frank-Wolfe来优化MAP推理的近端与我们的工作相比，它们并不优化拉格朗日乘子，而是直接优化原始变量。换句话说，他们在原始中工作，而我们在二元中工作。我们注意到，我们的公式适用于比[33，23，1]更一般的整数优化问题，并且将这些方法应用于我们更一般的设置似乎并不简单，同时只需要访问子问题的MAP-预言机。在[13，21]中引入了近端束方法，加速次梯度下降算法 它们的工作原理是局部地构建对要优化的函数的近似（束），并使用该束来找到下降方向。为了稳定性，增加了二次（近端）项[14]。虽然理论上不能保证，但近端束方法通常比次梯度方法更快。2. 方法原始问题我们考虑最小化布尔变量函数的问题，该函数表示为单个项的总和：Σ[18]《易经》中。这些工作依赖于将MRF分解为树。某些MRF的新分解minx∈{0，1}df（x），f（x）：=t∈Tft（xAt）（1）在[25]中针对最大流子问题和在[32]中针对完美匹配子问题引入并优化。该工作[44]使用树覆盖图，并通过次梯度上升优化重复节点上的附加等式约束。[12，32]提出使用存储一系列次梯度的束方法来构建目标函数的局部近似，用于MRF中的MAP推断。Frank-Wolfe算法是在50年代开发的[4]，最近由[8]推广。 [20]在一个区块中，提出了Frank-Wolfe模型的二次版本，并将其应用于结构支持向量机的训练。进一步的改进是这里的术语t ∈ T由变量At[d]和函数ft：{0，1} At → R {+∞}，|变量|variables.向量xAt∈ R是向量x∈Rd对At的限制.关于 Arity|的t|函数ft可以是任意大，但是我们假设存在一个有效的min-oracle，对于给定的向量λ∈RAt，计算x∈arg min [ft（x）+<$λ，x<$]以及成本ft（x），x∈domft其中domft={x∈ {0，1} At|ft（x）<+∞}=∞是f t的有效域。 为了方便起见，ht（λ）= min [ft（x）+fλ，xf]= minfy， [λ1]f=minfy， [λ1]f在[34，24]中，除其他外，平面的缓存x∈domfty∈Yty∈Yt提出了Frank-Wolfe方法。有几个工作已经将Frank-Wolfe 应 用 于 MAP-MRF 推 理 问 题 ： （ 1 ） [33] 使 用Frank-Wolfe计算MRF的局部多面体松弛中的近似最速下降方向(2)[23]使用Frank-Wolfe来解决一个修改后的问题，该问题通过将严格凸二次函数添加到原始目标（原始或对偶）来获得。与这些作品相比，我们使用Frank-Wolfe近端方法。此外，上述论文使用精细分解成许多小的子问题（对应于能量函数的成对项），而我们将问题分解其中子集Yt，Yt <$[0，1]At<$R定义如下：Yt= {[x ft（x）]：x∈domft}Yt= conv（ Yt）这个假设意味着我们可以有效地计算凹函数ht（λ）在给定λ∈RAt处的超梯度。由于（1）一般是一个NP难问题，我们的目标将可以求解（1）的某个凸松弛，这将等价于（1）的基本LP松弛（BLP）[17]。这种松弛已经在文献中被广泛研究，特别是对于MAP-MRF问题（其中11148y⋆y⋆⋆我⋆Σ.不这种情况通常被称为局部多面体松弛[41，42]）。然而，我们强调，我们的方法与大多数以前的作品不同：在应用BLP松弛之前，我们将目标表示为布尔指示变量的函数。这允许表达复杂的组合约束，例如多标签离散断层扫描和图形匹配问题中的约束（参见第3节）。对于向量y∈ Yt，我们记为第一|的t|当y∈[0，1]At和l aN第一个分量为对于一个中心点μ∈Λ。 近似二次项在μ附近充当信赖域项，使函数强凹，从而使对偶光滑通常使用一个双曲型精化多面体近似[21]来求解（6）。我们开发了一种邻近方法，该方法将在多平面块坐标Frank-Wolfe方法的帮助下最小化（6）和更新邻近中心μ之间交替。y∈R（soN，y=[y<$y<$]）.We也表示Y=t∈TYt2.1. 最大化hµ，c（λ）：BCFW算法并且Y=t∈TYt=conv（Y）. 向量y∈ Y的第t个分量记为yt∈Yt.问题（1）现在可以等价地写为：类似于（6）的目标（没有对λ变量的求和约束）用于训练结构支持向量机（SSVM）。在[20，34，24]，Σ最小ty∈Y， x∈{0，1}d（二）我们使用块坐标Frank-Wolfe算法（BCFW）应用于（6）的对偶，更具体地说，它的多平面yt=xA t∈Tt∈T版本MP-BCFW [34]。（6）的对偶公式如下。我们通过移除非凸约束x∈ {0，1}d来形成（2）的松弛：Σ第二个提案。对于maxλ∈Λhμ，c（λ）的对偶问题是最小ty∈Y， x∈Rd（三）最小fy∈Yµ，c（y），yt=xA t∈Tt∈TΣfµ，c（y）：=maxΣyt，[λt1]Σ1λt−µ t2（七）可以证明，问题（3）等价于BLP（1）见[37]。λ∈Λ2ct∈T我们不会直接优化这种放松，但它的La-定义ν∈ Rd由ν=1Σ（c·yt+μt），其中i∈[d]。我不是|我不是|t∈Tii iGrangean对偶[35].对于每个等式约束y=xAt引入Lagrange乘子λt∈ R At。收集则（7）中的最优λ为λt=c·yt+µt−νA和其中的乘子记为λ∈Nt∈T R At. 的f（y）=c|ν2|ν2dual将在集合 .Σµ，c2⋆t∈T2cii=1Λ=在这里我们表示Σλ：λt=0 i∈ [d]t∈Ti（四）tfµ，c（y） 为[λt1]（8）其中，Wt表示导数w.r.t.变量yt.接下来，我们回顾并适应我们的设置BCFW，Ti={t ∈ T：i ∈ At}。1.提案 （3）w.r.t.等式约束求极小化函数fμ，c（y）或very ∈ Y的MP-BCFW算法我们还将描述对实现的实际改进，即平面的紧凑表示yt=xA是maxh（λ），h（λ）：=Σht（λt）（5）并讨论了二元性缺口的估计问题。BCFW [20]该算法保持可行向量y∈ Y。在每一步BCFW试图减少对象-λ∈Λt∈Ttivefµ，c（y）通过更新所选项t的分量yt，此外，还证明了问题（3）和（5）的最优值是一致的.(This值可以是+∞，这意味着（3）是不可行的，（5）是无界的）。接下来，我们描述如何最大化函数h（λ）。近似项我们在λ中有一个非光滑的凹最大化问题，因此算法需要一个近似项，可分目标函数将不起作用。在近端束方法[14]中，增加了一个额外的近端项。这导致了新的目标不不不D11149（同时保持可行性）。为了实现这一点，它首先通过使用当前点周围的泰勒展开来线性化目标：fµ，c（z）fµ，c（y），z+常数（九）线性化目标的最优解zt∈ Y t是通过调用第t个预言机：zt<$argmintfμ，c（y），ztn来计算的。新矢量y是由zt ∈Ytyt和zt的最佳插值。所有其他组件s=/1秒秒ys，s/=tmaxhµ，c（λ），hµ，c（λ）：=h（λ）−λ∈Λ（6）2ct固定为y，即y（γ）←（1−γ）yt+γzt，s=t。11150ckyt −z t2∆t不算法1BCFW的一次通过输入：向量y∈ Y，而在《易经》中，则是以“卦”为卦。二、1：对于每个t∈T，按随机顺序进行2：设λt=c·yt+µt−νAXt的结构允许更有效地存储和操纵这些例如，在MAP-MRF推理问题中，具有k个可能值的变量可以由单个整数表示，而不是k个指示符变量。阿勒特第三章： 对于λt，调用第t个oracle：zt←argmin<$zt，[λt1]<$.z t ∈Yt即设x←arg min[ft（x）+<$λt，x<$]和zt=[x ft（x）]在我们的实现中，我们假设每个向量x∈domft可以由对象s表示，x∈X t.SYS，ST紧空间Xt. 要指定term ft，用户必须提供数组映射：[|的t|]→[d]确定集合At[d]第四章： 插值y（γ）←（1−γ）yt+γzt，S= t不以自然的方式，指定对象s∈ Xt的大小，并且5：计算γ<$arg minγ∈[0，1]fµ，c（y（γ））：设置γ<$（[λt1]，zt−yt并将γ裁剪为[0，1]⋆⋆c t t实现以下功能：t tF1。一个双射σt：Xt→Xt。6：set νi← νi+|不|（y（γ）i− yi），对于i ∈At和y7：结束←y（γ）F2 对于给定的λt，计算x∈选择步长γ∈[0，1]以最小化目标。最优γ可以很容易地以封闭形式计算（参见[37]中的引理1）。在算法1中总结了BCFW的一次通过。为了避免公式2中计算梯度和步长所需的和ν的昂贵的重新计算，它在算法1中被显式地保持和更新。MP-BCFW [34]在本文中，我们使用BCFW的多平面版本。此方法缓存由返回的平面ztt t targ min[ft（x）+]并返回其紧表达式。x∈domftsentations（即，σt（s）=x）以及成本ft（x）。F3. 计算给定向量λt和对象s∈ Xt的内积的函数。注意，调用第3行中的近似oracle涉及调用（F3）中的函 数 |Y~t|2、一般情 况 下 为O（|Y~t|·siz et）time其中sizet是数组的长度用于存储s∈ Xt。对项ht（λ）= minzt∈Yt <$z，[λ1]<$. 让Y~tt是当前存储在内存中的一组平面，第t个子问题的理论 它定义了项ht（λt）的一个近似h<$t（λt）=minzt∈Y<$t <$z t，[λt1]<$. 注意，对于一个nyλt，ht（λt）≥ht（λt）。MP-BCFW使用精确传递（调用算法1的第3行中ht（λt）的acle）和近似传递（调用一个MP-BCFW迭代由一个精确的通道组成，几次近似传球。通过监测物镜在单位时间内下降也就是说，注1. 高效的平面存储机制在蛋白质折叠MRF数据集上提供了大约25%的单个MP-BCFW通道的加速（参见第3和4节）。此外，它通常导致在每个MP-BCFW遍次之后获得稍微更好的目标值，因为在调用精确遍次之前可以进行更近似的遍次（因为近似遍次由紧凑平面存储加速，所以它们的每单位时间的目标减少更高，因此它们被更频繁地调用）。2.2. 算法f计算比率μ，c（y）−fμ，c（y），其中yμ是MP-BCFW迭代开始时的向量，y是当前向量，而μ t是自MP-BCFW迭代开始以来经过的时间。如果该比率在近似通过之后下降因此，近似传递的次数将取决于精确预言机和近似预言机的相对速度。请注意，近似oracle调用的时间与工作集的大小成比例|Y~t|. 方法[34]使用一种通用策略来控制此大小：从Yt中删除在最后K次迭代期间未使用的平面。 我们使用K=10，这是[34]中的默认参数。平面的紧致表示回想一下，对于某些x∈domft，集合Yt中的平面具有[xft（x）]的形式。{0，1}At。一种天真的方法（特别是在以前works [34，24]）是将它们显式存储为大小|+1。|+ 1. 我们观察到，在某些应用中，回想一下，我们的目标是在λ∈Λ上最大化函数h（λ）;这给出了原始离散优化问题minx∈Xf（x）的下界。现在我们总结我们求解maxλ∈Λh（λ）的算法，并描述我们的参数选择。 为了初始化，我们设置µt= 0，yt←对 于 每 个 t ∈T ， argmaxyt∈Y<$yt ， [µt1]<$ 且Y<$={yt}。然后我们开始主算法。每10次迭代我们更新MP-BCFW的μ←λ（保持向量yt和集合Yt不变），其中λ是迄今为止所见的目标h（λ）的最大值的向量。由于计算h（λ）是一个昂贵的操作，我们对当前向量λ进行计算仅在MP-BCFW的每5次迭代注2（趋同）。如果我们精确地计算MP-BCFW中的内部迭代，我们的方法将相当于收敛的邻近点算法[27]。即使使用非精确评估，也可以证明当近端评估中的误差快速缩小时收敛我11151我IV足够接近零。然而，我们使用了一个更积极的计划，每10次迭代更新的邻近点，并没有约束的不精确的邻近步骤评估。在实验上，我们发现，它给出了良好的结果w.r.t.整体问题（5）。2.3. 估计二元差距为了得到一个好的停止准则，需要在当前目标和最优目标之间的差距h（λ）−h（λ）如果我们有可行的原始解和对偶解，这就很容易做到。不幸的是，在我们的情况下，向量y∈ Y不是问题（3）的可行解这个问题对于一般的图G是NP-难的，但是对于树可以有效地解决。所以，我们用树来选择覆盖G，就像[18]中所做的那样此外，我们寻求少量的树，使得拉格朗日变量的数量保持较小，优化变得更快。一个图的树覆盖称为一个图的最小树覆盖。maltree cover，如果没有覆盖，树树的相关数目称为图我们用[5]布尔编码的方法有效地计算了图 在（1）中，我们通过指示变量对标号x∈X因为它不满足等式约束yt=xA。1xi;a=[xi=a]∈ {0，1}，其中i∈V，a∈Xi，约束条件（即，将无限成本分配给控制器，为了处理对偶性差距，我们建议使用以下量：axi;a= 1不满足该约束的图形）。Ay，λ=埃克塞特yt，[λt1]Σ Σ最大yt−最小yt树覆盖和布尔编码也用于下面有两个问题，我们不作明确评论。t∈Ti=1t∈Ti我t∈Ti我anymore.3号提案考虑对（y，λ）∈Y×Λ。(a) 存在Ay，λ≥0，By≥0，（十）3.2.离散体层摄影术离散层析成像问题是从一组在不同角度拍摄的线性（层析）投影重建图像，其中图像强度值受到限制h（λ<$）−h（λ）≤Ay，λ+By·<$λ<$−λ <$1，∞<$λ<$∈Λ（11）从一组离散的强度中分离出来。 见图1其中，我们将r e记为<$δ<$1，∞=maxi∈[ d]Σt∈Ti |.|.例证这个问题是不适定的，因为线性投影的数量小于像素的数量，(b) 我们有Ay，λ=By=0当且仅当y和λ是问题（3）和（5）的最优解。注意，如果我们知道最优解λ∈maxλ∈Λh（λ）属于某个有界区域，那么我们可以使用（11）来获得对偶间隙的界这样的区域对于某些应用是可以获得的，但是我们没有追求这个方向。3. 应用在本节中，我们将详细介绍这三种重建。因此，我们使用正则化器来惩罚不规则的图像结构。形式上，我们有一个MRFG=（V，E），其中节点集对应于像素网格，边缘连接对应于相邻像素的节点。标签空间为X v ={0，1，. . .，k}对于某些k∈N。另外，标号x∈ X必须满足线性投影Ax=b，其中A∈{0，1} |V|×l. 通常，没有局部信息可用，因此一元势为零：θv<$0（v∈V）。问题是，Σ评估中使用的应用：马尔可夫随机场（MRF），离散断层扫描和图形匹配问题，f（x），f（x）：x∈Xij∈Eθij（xi，xj） （13）莱姆后两者都是MRF的MAP推理问题的扩展本文对这三个问题进行了综述.3.1. 马尔可夫随机场其中X={x∈ {0，1，. . .，k} V：Ax=b}。对于成对势θij 的典型选择是 截 断 L1 范 数 θij （ xi ， xj ）=min（|xi−xj|，c）。每个投影Ax = b的r w构成另一个可分问题m。第i一个MRF由图G=（V，E）和一个图G =（V，E）组成因此，Ax=b的行具有以下形式：v∈V：A=1xv= bi.对于每个v∈V，一个具体的标签集Xv。最大后验概率（MAP）推理的目标是找到标记最近在[19]中考虑了这个问题的有效解决方案。我们遵循他们的递归分解方法求解投影子问题。 细节（xv）v∈V∈潜力：v∈VXv=：X对于下面给出f（x），f（x）：x∈XΣv∈Vθv（xv）+Σuv∈Eθuv（xu，xv）.（ 十二）离散层析成像子问题我们使用[19]的递归分解方法的简化版本，1我们说向量y是（3）的可行（最优）解，如果存在向量x∈Rd使得11152（y，x）是（3）的可行（最优）解。显然，x可以很容易地从可行的y计算出来，所以为了简洁起见省略它有效地求解离散层析成像问题的求和约束Ax=b。下面我们给出相应的细节。令Ax=b的第i行具有以下形式：111531：n对求和变量的 约 束 每当我们有划分时，我们添加约束si：j=sj：k+ sk+1：j。求解（14）我们将提出一种动态规划方法来求解（14）。首先，对于和变量si：j的每个值l，我们存储一个值φi：j（l）∈R。 我们计算φi：j是从左到右递归到根的. 我们计算F或分区i：j=i：kk+1：jφi：j（l）= Minl′=0，.，Lφi：k（l′）+φk+1，j（l−l′）好吧（十五）在计算了φ1：n之后，我们设置sφ=b。随后，委员会注意到，我们从根到叶进行一次传递，以如下计算每个变量si：j的最佳标签和：图1.离散层析成像问题的图示。图像强度值为0（白色）、1（灰色）和2（黑色）。侧面的小箭头表示三个断层摄影投影方向（水平、垂直和对角线）。箭头处的值∗i：k∗k+1：j= minsi：k+sk+1：j=si：jφi：k（si：k）+φk+1：j（sk+1：j）。（十六）表示沿着断层摄影投影的强度值。图2.插图的图形匹配问题匹配鼻子和左/右脚的两只企鹅。左边企鹅上的蓝色节点对应于底层节点集V，而右边企鹅上的蓝色节点对应于标签L。绿线表示匹配。请注意，没有两个标签匹配两次。红色的弹簧表示成对成本θij，它促进了匹配的几何刚性Σ快速动态规划简单计算（15）需要O（（（j-i）·k）2）步。然而，我们使用了一种有效的启发式方法[3]，该方法往往具有次二次复杂度在实践中3.3.图匹配图匹配问题包括在MRFG=（V，E）中找到MAP-解 ， 其 中 每 个 节 点 的 标 签 来 自 公 共 论 域 Xv<$L<$v∈V。额外的匹配约束要求两个节点不能使用相同的标签：xuxv<$u，v∈V，u v.因此，任何可行解都定义了一个到标签集的内射有关说明，请参见图2。问题是minf（x）S.T.xu/=xvu/=v .（ 十七）x∈X我们使用最小成本流求解器来处理匹配-v∈V：Aiv=1xv=bi并且回想一下xv∈{0，1，. . . ，k}。ing约束，参见例如[40，45，39]解释每个这样的断层投影将对应于一个单一的子问题。考虑到拉格朗日乘子λ，我们可以重命名变量并将问题重写为最小成本流求解器构造。4. 实验Σn Σkminx，…x∈{0，.，k}nλi（l）·λxi=ls.t.Σnxi=b我们选择了一个具有挑战性的MRF，离散断层扫描和图形匹配问题的消息传递方法的斗争或不适用的选择。详细1ni=1l=0i=1（十四）这些问题的描述可以在[37]中找到。我们将遵循递归分解方法。到最后，我们引入辅助求和变量si：j=第三条 请注意，在消息传递是Σju=ixu.由于其更快的速度和足够的解决方案的质量，选择的方法，见[11，39]。在这种情况下，可变分区我们对集合 [1，n]进行划分转换为 {x1，. . . ，x<$n<$}和<$$>n<$+1：n=S得双曲余切值.111542使用基于次梯度的求解器的优势，这往往是较慢的。然而，我们选择的评估问题包含2 2 2{xn+1，. . . ，xn}。 我们递归地划分了：一些最具挑战性的MRF和图匹配2 2和n=n+1：n，直到达到单变量。这将产生一棵以n1：n为根的树。问题与相应的拉格朗日分解没有得到满意的解决与消息传递求解器。11155图3.平均下限与蛋白质折叠MRF数据集、离散断层扫描（具有2、4和6个投影的合成图像，具有2、4和6个投影的尺寸为64×64和256×256的绵羊logan图像）和6d场景流图匹配数据集的运行时间图值在数据集的所有实例上平均数据集#我|V||E|FWMAPCBSAMPMRF蛋白质折叠11 33-40528-780-12917.44 -12970.61 -12960.30 -13043.67离散体层摄影术合成2项目合成4项目合成6项目绵羊洛根64×64绵羊洛根256×256999331024102410244096655361984198419848064130560266.12337.88424.36897.184580.06265.89336.33417.76847.874359.24239.39316.61391.09701.93370.63†††††图匹配6D场景流6 48-126 1148-5352-2864.2-2865.61-2867.60-2877.08表1.数据集统计和平均最大下限。 #I表示数据集中的实例数，|V|节点的数量和|E|底层图形模型中的边数。†表示方法不适用。粗体数字表示竞争算法中的最高下限。图4.下限与使用FWMAP和来自（6）的邻近权重c的不同值求解的蛋白质折叠数据集的 实 例 1CKK 上 的 运 行 时间。图5.对于合成的6个项目，来自（10）的对偶间隙量Ay、λ和By随时间的变化。离散断层扫描数据集边界，因此不能直接比较。其次，我们将它们视为互补的求解器，因为当它们应用于已解决的对偶问题时，它们的解质量通常会提高。 我们在Intel i5- 5200U CPU上运行了每个实例10分钟。显示随时间推移的平均下限的每个数据集图见图3。数据集统计和数据集平均的最终下限见表1。每个数据集中每个实例的详细结果可以在[37]中找到。求解器我们的评估重点是能够处理一般的MAP推理问题，其中访问是由min-oracles给出的。FWMAP：我们的求解器，如第2节所述。我们已经从比较中排除了根本不解决与我们的拉格朗日分解相对应的松弛的原始算法。首先，他们不会提供任何低CB：最先进的束方法ConicBun- dle [7]，它不单独处理单个子问题，而是对所有La-进行提升。11156Grangean乘数λ同时。SA：使用Polyak步长规则的次梯度上升此求解器也用于[12]中的MRF。此外，我们测试了最先进的消息传递（MP）求解器版本MP是MAP-MRF问题的流行方法，最近已被应用于图匹配问题[39]。所有求解器优化相同的基本线性规划-明松弛。此外，所有基于次梯度的解算器也使用相同的分解。这确保我们比较相关的求解器方法，而不是松弛或分解之间的差异。我们算法的性能取决于从（6）中选择的邻近权重参数c太大的值将使每个邻近步骤花费很长时间，而太小的值将意味着太多的邻近步骤直到收敛。这种行为可以在图4中看到，在图 4中，我们绘制了MRF问题和FWMAP的下界与时间的关系，其中选择了不同的近似权重c。我们看到，最佳值为100，值越大，性能越差。然而，我们也可以观察到FWMAP的性能对于更大或更小数量级的值是好的，因此FWMAP对c不是太敏感。为这个参数大致选择正确的数量级就足够了我们已经观察到，问题分解（1）中的子问题越多，邻近权重c就应该越小。由于更多的子问题通常在分解中转化为更复杂的依赖关系，因此较小的c值将是有益的，因为它使结果更复杂的邻近步骤更好地被调节。一个好的公式c因此将减少越来越多的子问题|不|. 我们已经从我们评估的50个实例中选取了三个实例，并粗略拟合了一条曲线，该曲线为这三个实例选取了合适的近端权重值，从而得到：4.2. 离散断层扫描。在[19]中，提出了一种基于对偶分解的求解器，用于多标记离散层析成像问题。使用ConicBundle [7]优化分解。不幸的是，对于我们的分解，消息传递求解器不适用。主要问题似乎是由于一元势为零，所有子问题的最小边缘也为零。因此，在消息传递中使用的任何基于最小边际的步骤将导致没有进展。换句话说，初始为零的拉格朗日乘子是消息传递算法的局部不动点因此，我们只与SA和CB进行比较。数据集我们比较了[19]中合成生成的文本图像，由合成表示。这些是随机物体的32×32图像，具有2，4和6个投影方向。并对分辨率为64×64和256×256的经典绵羊logan图像以及分辨率为2，4和6预测4.3. 图形匹配。如[40，45]所示，基于拉格朗日分解的求解器在获得的原始解的质量方面也优于基于原始解析的求解器特别地，[39]提出了一种消息传递算法，该算法是典型的选择方法，并且在大多数问题上优于其他基于消息传递和次梯度的技术我们用MP表示。数据集消息传递有几个问题，到目前为止提出的基于求解器陷入次优固定点这种行为发生在例如。在[39]中的数据集[2]上，我们用图流表示。4.4. 讨论我们的求解器FWMAP在每个实例上都达到了最高下限。它在最困难和最大的问题上有很大的进步，例如。绵羊洛根。虽然消息传递求解器在优化的开始阶段更快（只要适用），但我们的求解器FWMAP在基于次梯度的求解器中是最快的，并且最终c=150万（|不|+22）2 .（十八）实现了比消息传递更高的下界。我们还想提一下，我们的求解器的内存使用量比竞争对手的捆绑求解器低对偶能隙我们从（10）中画出了合成6投影的对偶能隙量Ay，λ和By。图5中的离散断层扫描数据集。4.1. 马尔可夫随机场大多数MRF可以通过消息传递技术[11]有效地解决，例如。用TRWS算法[15]，我们用MP表示。然而，有一些困难的问题，TRWS卡在次优点，一个例子是来自计算生物学的蛋白质折叠CB. 在较大的问题实例中，CB通常会使用我们8 GB机器上的所有可用内存。引用[1] T. Ajanthan，A.德迈松河布内尔湾萨尔茨曼，P.H.S.Torr和M. P. Kumar.密集CRF的有效线性规划。在IEEE计算机视觉和模式识别会议（CVPR），2017。[2] H. A. Alhaija，A. Sellent，D. Kondermann和C.罗瑟通过图匹配的6d大位移场景流。载于2015年全球政策审查11157[3] M. 比西克Hassler，G.J. Woeginger和U.T. 齐默-曼。最大卷积问题的快速算法操作员Res. Let. ，15（3）：133[4] M. Frank和P.沃尔夫二次规划的一个算法海军研究后勤季刊，3：149[5] H. N. Gabow和H. H.韦斯特曼森林、框架和游戏：拟阵和的算法及应用。Algo-rithmica，7（1）：465，Jun1992.[6] A. Globerson和T. S.贾科拉修复max-product：MAP LP松弛 的 收 敛 消 息 传 递 算 法 。 神 经 信 息 处 理 系 统 会 议（NIPS），2007年。[7] C. 赫姆伯格Conicbundle library for convexoptimization v0.3.11. 2011年。https：//www-user.tu-chemnitz.de/~helmberg/ConicBundle/。[8] M. Jaggi重新审视弗兰克-沃尔夫：无投影稀疏凸优化。国际机器学习会议，第427-435页，2013年[9] J. Johnson，D. M. Malioutov和A. S.威尔斯基图模型中地图估计的拉格朗日松弛法。2007年第45届Allerton通信，控制和计算年会[10] V. Jojic，S. Gould和D.科勒MAP推理的加速对偶分解.2010年国际机器学习会议（ICML）[11] J. H.卡佩斯湾Andres，F. A.汉普雷希特角Schnörr，S.Nowozin ， D. 巴 特 拉 、 S. 金 湾 ， 澳 - 地 X. Kausler ，T.Kröger，J.Lellmann，N.科莫达基斯湾Savchynskyy和C.罗瑟结构离散能量最小化问题现代推理技术的比较研究 。 International Journal of Computer Vision ， 115（2）：155[12] J. H. 卡佩斯湾Savchynskyy和C.Schnörr. 用拉格朗日松弛法实现有效MAP推理的束方法在计算机视觉和模式识别（ CVPR） ， 2012 年 IEEE会 议 上 ， 第 1688-1695 页 。IEEE，2012。[13] K. C.基维尔不可微优化的下降法。计算机科学讲义。Springer-Verlag，1985.[14] K. C. 基维尔凸不可微极小化的丛方法中的邻近控制Mathematical Programming，46（1）：105[15] 诉哥洛夫能量最小化的收敛树重加权消息IEEE传输模式分析马赫内特尔，28（10）：1568[16] 科尔莫哥洛夫重新加权消息传递的新视图。 IEEE Trans.模式分析马赫内特尔，37（5）：919[17] V. Kolmogorov，J. Thapper和S.好吧线性规划在一般值csp 问 题 上 的 威 力 。 SIAM Journal on Computing ， 44（1）：1[18] N. Komodakis，N. Paragios和G.齐里塔斯通过对偶分解实 现 MRF 能 量 最 小 化 和 超 越 。 IEEE Transactions onPattern Analysis and Machine Intelligence，33（3）：531[19] J. Kuske，P.Swoboda和S.佩特拉一种新的非二元离散层析成像的凸计算机视觉中的尺度空间和变分方法-第六届国际会议，SSVM 2017，2017，会议记录，第235-246，2017.[20] S. Lacoste-Julien，M. Jaggi，M. Schmidt和P.普莱彻结构支持向量机的块坐标Frank-Wolfe优化。2013年国际机器学习会议（ICML）[21] C.勒马雷夏尔构造凸优化的丛方法。北荷兰数学研究，129：201[22] D. 诉N. Luong，P.Parpas，D.Rueckert，和B.Rustem.用镜像下降法求解MRF最小化问题. Advances in VisualComputing-8th International Symposium ， ISVC 2012 ，Rethymnon，Crete，Greece，July 16-18，2012，RevisedSelected Papers，Part I，pages 587[23] Ofer Meshi，Mehrdad Mahdavi，and Alex Schwing.光滑而结实：线性收敛的MAP推理。神经信息处理系统（NIPS）会议，2015年。[24] A. Osokin，J. B.阿莱拉克岛Lukasewitz，P. K. Dokania，以及S.拉科斯特-朱利安注意结构化支持向量机的块Frank-Wolfe优化的间隙。在2016年的国际机器学习会议（ICML）上[25] A. Osokin和D. P. Vetrov.马尔可夫随机场中推理的次模松 弛 。 IEEE Transactions on Pattern Analysis MachineIntelligence，37（7）：1347[26] P. Ravikumar，A. Agarwal和M. J·温赖特图结构线性程序 的 消 息 传 递 ： 近 似 方 法 和 舍 入 方 案 。 Journal ofMachine Learning Research，11：1043[27] R·泰瑞尔·罗克费勒。单调算子和邻近点算法。SI