1组合问题拉格朗日分解的对偶上升框架Paul Swoboda1，Jan Kuske2，Bogdan Savchynskyy31ISTAustria，2Univ ersit aütHeidelber g，3TUDresdenpswoboda@ist.ac.at摘要我们提出了一个一般的对偶上升框架的La- grangean分解的组合问题。虽然这种类型的方法已经显示出它们对许多问题的效率在这项工作中，我们提出了这样一个通用的算法。它取决于几个参数，可用于优化其在每个特定设置中的性能我们证明了我们的方法在图匹配和多割问题上的有效性，它优于最先进的求解器，包括基于次梯度优化和现成的线性规划求解器。1. 介绍计算机视觉和机器学习产生了许多强大的计算模型。这是典型的，在这些模型中的推理减少到非平凡的组合优 化问题。对于 一些模型，如 条件随机场（CRF），开发了强大的专业求解器，如[48，49，12，52]一般来说，无论如何，人们必须求助于现成的整 数 线 性 规 划 （ ILP ） 求 解 器 ， 如 CPLEX [2] 或Guidelines [36]。尽管这些求解器在过去的十年中取得了巨大的进步，但它们可以解决的问题的大小仍然是许多潜在应用的限制因素，因为运行时间在问题大小上呈超线性这项工作的目标是部分填补实际需求和现有的计算方法之间的差距。这是一个古老的观察，许多重要的优化ILP可以有效地分解成容易解决的组合子问题[32]。由这些子问题通过线性约束耦合组成的凸松弛被称为拉格朗日分解或对偶分解[31，50]。 尽管这种技术可以有效地用于各种场合，以找到组合问题的近似解，但它有一个主要缺点：在最一般的设置中，只有基于慢（子）梯度的技术[51，57，50，42，61]可用于优化相应的凸松弛。然而，在条件随机场领域， 众所周知[41]，消息传递或双（块坐标）上升算法（例如，TRW-S [48]）显著优于（次）梯度方法。在[59]中，对于约束最短路径问题进行了更早的类似观察虽然对偶上升算法被提出用于许多组合问题（参见下面的相关工作概述），但是没有一般框架，其将（i）给出关于此类算法的性质的一般化视图，并且更重要的是（ii）提供工具来容易地构造用于新问题的此类算法。我们的工作提供了这样一个框架。对偶上升算法优化对偶问题并保证对偶目标的计算机视觉中最著名的例子是块坐标上升（也称为消息传递）算法，如TRW-S [48]或MPLP [28]，用于条件随机场中的最大后验推理[41]。据我们所知，第一个求解整数线性规划的对偶上升算法属于Bilde和Krarup [11]（1967年Danish的相应技术报告）。在这项工作中，解决了一个无能力的设施选址问题一个类似的问题（sim-在[30]中，使用相同类别的算法解决了多个工厂位置）。1980年，Fisher和Hochbaum [22]为计算机网络中的数据库定位问题构造了一个基于对偶上升的算法，该算法被用于优化互联网的前身Arpanet [1]的拓扑结构在[23]中，广义线性分配问题由相同类型的算法解决。作者考虑了将该问题的拉格朗日分解为多个背包问题，并在每次迭代中求解在[34]中提出了该算法的改进版本。在[25]中，还针对最小成本流提出了有效的基于双上升的求解器，15961597（µ1. . .µ）。K2[24]中的覆盖和集合划分问题以及[35]中的资源约束最小加权树形问题工作[33]描述了构造对偶上升算法的基本原理。虽然作者提供了几个例子，但他们并没有超越这一点，并坚持认为这些方法是结构依赖的和特定于问题的。工作[18]建议使用最大产品信念一个集合X<$Rn的定义为conv（X）。不相交的并集用“不相交并集”表示。2. 整数松弛成对可分线性规划形式为minx∈Xθ（x）的组合问题，其中X{0，1}n是二进制向量，通常具有分解-Σk[73]第73话最大的问题可表示为minxi∈Xii =1，…Ki=1<$θi，xi<$，对于Xi<$然而，他们的算法既不是单调的，也不是单调的。总体上是非常严谨的在计算机视觉中，针对多目标跟踪[8]、图匹配（二次分配）问题[78]和条件随机场中的推理[48，49，28，74，75，62，37，56，72，39]，提出了用于组合问题的拉格朗日分解的从后者来看，TRW-S算法[48]是根据[41]的成对条件随机场的最有效算法之SRMP算法[49]概括了{0，1}di是二进制向量的集合，通常对应于X的坐标的子集。 在一组线性约束条件A（i，j）xi=A（j，i）xj下，该分解问题等价于原问题，这保证了所考虑的分量的相互一致性。通过用凸壳conv（Xi）代替Xi，我们将二元向量转换为实值向量，得到了问题的凸松弛。它说：ΣkTRW-S到任意阶条件随机场从某种意义上说，我们的框架可以看作是一种泛化minμ∈ΛG i=1其中ΛG定义为（1）的SRMP到一个广泛的类组合问题。.ΛG：=.. µi∈conv（Xi）i∈F. A（i，j）µi=A（j，i）µj<$ij∈EΣ.（ 二）贡献提出了一种新的基于对偶上升的组合优化计算框架。为此，我们：(i) 定义一类问题，称为整数松弛成对可分线性规划（IRPS-LP），我们的框架可以用于。我们的定义捕获了许多已知的离散优化问题的拉格朗日分解（第2节）。(ii) 给出了求解IRPS-LP的一般单调收敛的消息传递算法，特别是它包含了几个已知的条件随机场的求解器（第4节）。(iii) 给出了我们的al-tax m的不动点的一个特征，它包含了诸如弱树一致性[48]和弧一致性[74]等著名的不动点特征（第5节）。我们通过在IRPS-LP的两个著名的特殊情况下优于最先进的求解器来证明我们的方法的效率，这两个特殊情况在计算机视觉中得到了广泛的应用：多割和图匹配问题。（第6节）。包含上述求解器和实验中使用的数据集的C++框架可以在https://github.com/pawelswoboda/LP_MP 上获得。我们在补充材料中给出了所有的证明这里F：={1.，的。 . Σ。，k}被称为分解的因子F行动与行动2对应于耦合约束。无向图G=（F， E）称为因子图。我们将使用变量名µ来强调µi∈conv（Xi）和x，只要xi∈Xi，i∈F。定义1（IRPS-LP）。 假设对于每个边ij ∈ E，耦合约束A（i，j），A（j，i）的矩阵使得A（i，j）∈{0，1}K×di和A（i，j）xi ∈ {0，1}K对S∈K∈N，n ∈ xi ∈ Xi，对A（j，i） 也是 如 此. 问题minμ∈ΛGi∈F<$θi，μi<$称为整数-R 松弛P-气-S可分线性规划，简称IRPS-LP.下面，我们给出几个IRPS-LP的例子。为了区分IRPS- LP的因子图的符号，我们坚持使用粗体字母（如G，F，E），我们将使用直字体（如G，V，E）用于示例中出现的图形。实施例1（CRF的MAP推断）。一个条件随机域是由图G=（V，E），离散标号空间X=u∈VXu，一元θu：Xu→R和成对代价θuv：Xu×Xv→R（u∈V，uv∈E）构成的.我们也记为Xuv：=Xu×Xv。相关的最大后验如下：记法。 无向图记为d。byG=min Σθu（xu）+u∈VΣθuv（xuv），（3）uv∈E（V，E），其中V是有限节点集，E是V是x∈X边集v∈V的相邻节点集w.r.t.图G记为NG（v）：={u：uv∈E}。凸包其中xu和xuv分别表示对应于节点u∈V和边uv∈E的分量。知名1598+stec=局部多面体松弛[74]可以通过设置F=V∈E被视为IRPS-LP，即与每个节点v∈V和每个边uv∈E关联一个因子，并为图形模型的每个边引入两个耦合约束，即E={{u，uv}，{v，uv}：uv∈E}。为了便于记法，我们假设每个标号s∈ Xu与一个单位vector（0，. . .，0，1，0。. .，0），维数等于v{，}S标签总数|X u|而第s个位置上为1。节点u∈V，其可以被分配标签s和附加的虚拟节点#。虚拟节点#表示标签s的未分配，并且是必要的，因为不是每个标签必须要有。与示例1中一样，我们将单位二进制向量与集合Xs的每个元素相关联，并且conv（Xs）表示此类向量的凸包因子集变为F=VstecEstecL，其中集合E={{u，uv}，{v，uv}：因子图的uv∈E}<${{u，l}：u∈V，l∈Xu}边缘.得到的IRPS-LP公式如下：因此，符号conv（Xu）作为凸所有这些向量的外壳在对一个N维min Σθu，µuΣ紫外线（UV）Σ电子邮件：info@martina.com单形为<$N：={µ∈RN：放松阅读Ni=1 i= 1}结果µ，µu∈Vµ∈LGuv∈Es∈Lminµ∈LGΣθ，µu∈V，µuΣUV+UVθuv∈E，µuv中国（4）μs∈conv（Xs），s∈Lμu（s）=μs（u），s∈Xu.在过完备表示[71]中，LG被定义为：我们在这里介绍（i）辅助变量μs（u），用于所有vari。µu∈conv（X u）：µ u∈|Xu|，u∈V表μu（s）和（ii）辅助节点成本θs<$0s∈L，其在优化过程中可以取其它值Facc-µuv∈conv（Xuv）：µuv∈|XUV|，uv∈ EA µ=AΣµ：µ（x，x）=µ（x），与向量μu和μuv相关的向量对应于（uv，u）uv（u，uv）uUVuvxv∈Xvu中文（简体）图G的节点和边（节点和边因子），如uv∈ E，（xu，xv）∈Xuv，u ∈ uv，xu ∈ Xu.这里，µu（xu）和µuv（xu，xv）表示向量µu和µuv的坐标，分别对应于标签xu和标签对（xu，xv）。示例2（图形匹配）。 图匹配问题，也称为二次分配[13]或特征匹配-并且以相同的方式偶联此外，与向量μs相关联的因子确保标签s最多可以被获取一次。这些标签因子与节点因子相结合（（7）中的最后一行）。实施例3（多切割）。无向加权图G=（V，E）的多割 问 题 （ 也 称 为 相 关 聚 类 ） 是 找 到 一 个 划 分（V1，. . .，k），i V，ing，可以看作是CRF的MAP推理问题（如VKi=1图顶点的最小值，使得总成本在实施例1中）配备有附加约束：的G的标号集属于一个论域L，即Xu<$L <$u∈V，且每个标号s∈ L最多只能被赋值一次。总的问题是最小化连接不同组件的边的数目分量的数量k不是固定的，而是由算法确定的。图示见图1。虽然这个问题在计算机视觉中有许多应用[4，5，minXΣu∈Vθu（xu）+Σuv∈Eθ uv（x u，x v）s.t.xu/=xvuv.（六）6，77]和[7，60，14，15]之外，没有可扩展的求解器，可以提供最优性边界。现有的方法要么是有效的原始算法[66，58，27，19，20，9，10]图匹配是许多计算机视觉应用中的一个关键步骤，其中包括跟踪和图像配准，其目的是找到图像点之间的一一对应关系。出于这个原因，在计算机视觉界已经提出了大量的求解器[18，76，78，70，53，69，63，29，79，38，54，16]。之间基于拉格朗日分解的两种最近的方法[70，78]显示出优越的性能，并提供了其解的下限。然而，我们下面描述的分解与[70，78]中提出的分解不同我们用于图匹配的IRPS-LP表示由两个块组成：（i）CRF本身（进一步分解为具有变量（μu）u∈V的节点和边子问题）和（ii）跟踪节点的附加标签因子，如-或组合的分支-定界/分支-切割/列生成算法，基于现成的LP求解器[43，44，47，77]。移动决策算法不提供下限，因此，不能判断其解决方案的质量或采用它们在分支定界程序。另一方面，现成的LP求解器超线性地扩展，限制了它们在大规模问题中的应用。而不是直接优化分区（它有许多对称性，使优化难以在线性规划设置），我们遵循[17]并在边缘域中制定问题。设θe，e∈E表示图G的所有圈的集合。属于不同组件的每条边称为切边。multicut问题是指签了标签。我们对每个标号s∈ L引入这些标号因子。该1599因子Xs：={u∈V：s∈Xu}<${#}的可能配置集由以下各项minx ∈{0，1}|E|Σθe xe， S.T. Ce∈EΣx e≥x e′。（八）e∈C1600uUV我我我i∈F我我这里xe=1表示切割边缘，并且不等式迫使每个循环没有切割边缘或至少有两个切割边缘。公式（8）具有指数形式的许多约束。然而，众所周知，只考虑无弦周期[17]就足以代替（8）中的集合C此外，可以通过添加具有零权重的附加边来对图进行三角剖分，因此无弦循环的集合减少为边的三倍。在文献[26]中，这种三角测量被称为弦线完成三元组的数量是立方的，这对于实际效率来说仍然太大，因此违反的约束通常以切割平面的方式迭代地添加到问题中[43，44]。为了简化描述，我们将忽略下面的这个事实，并考虑所有图1. 实施例3的说明。由三个连通分支输入 101 、 102 、 103 （绿色）。红色虚线边表示切割边xe= 1。最大化其对偶下界。对偶IRPS-LP（1）w.r.t.耦合约束为Σ这些周期一次。假设一个三角形图，将C重新定义为所有无弦循环（三元组）的集合，最大φ D（φ）：=S.T.θφ：=θi+i∈F minx∈X<$θφ，xi<$A. φ（i，j）<$i∈F（十一）考虑多切割问题1的以下IRPS-LP松弛：Σ Σ Σ˜ij：ij∈E（i，j）φ（i，j）=−φ（j，i）<$ij∈E这里φ（i，j）∈RK，A（i，j）∈{0，1}K×di，其中K∈N.minµ，µe∈Eθeµe+c∈Ce∈cθe，cµe，c，s.t.（九）函数D（φ）称为下界，在φ中是凹的。修改后的原始成本θφ称为重新参数化µe∈conv({0,1})=[0,1], e∈E∀c∈C,e∈c:µc：=（µe，c）e∈c∈conv（{0，1}3|埃雷∈c：Σ µe，c≥µe′，c）势θ。 我们通过引入φ（i，j）：=−φ（j，i）来对称化符号来复制对偶变量。在e∈c\{e′}{0，0，0}，{0，1，1}，{1，0，1}，{1，1，0}，{1，1，1}}µe=µe，c（十）在实践中，只存储一个副本，另一个在苍蝇注意，在该双符号中，来自实施例1的CRF的重新参数化的节点和边缘电势为Σ为了便于记法，我们缩短了一个可行集def-θφ（xu）=θu（xu）+v：uv∈Eφu，uv（xu）initionµ∈conv（µ′ ∈{0，1}n：对μ′的约束）到θφ（xu，xv）=θuv（xu，xv）+φuv，v（xv）+φuv，u（xu）nv（{0，1}n：对n的约束）。在这里，是重新-φu，uv=−φuv，u对应于xe的laxed（可能是非整数）变量。变量μe，c是μ e的一个系数y，它对应于环c。因此，每个µe得到的拷贝数为µe，c，这是众所周知的CRF的可行解的成本是不变的下重新参数化。我们将其推广到IRPS-LP-情况。无弦周期C包含边缘E。对于每个循环，的二元向量满足循环不等式。Σ1.提案Σi∈F<$θi，µi<$=无论何时，对于一个有3条边的循环，这个集合可以明确地写成（10）。除了复制µe，e∈E，我们还复制相应的成本θe，并为每个包含边缘e的循环c。在优化过程中，成本θe将在θe本身和它的副本θe，c，c∈C之间重新分配。IRPS-LP的因子与每个边缘（变量μe）和每个无弦（变量μc）相关。耦合约束将边缘因子与那些循环因子连接起来，因子，其包含相应的边（参见（10）中在[67]中可以找到对具有更严格松弛的多割问题的消息传递的深入讨论3. 对偶问题与容许消息由于我们的技术可以被看作是一个双重上升，我们将不直接优化原始问题（1），而是1可以证明，这种松弛与多割问题的标准LP松弛一致[17]。1601µ1，. . . ，μ k服从耦合约束。虽然命题1保证了原始问题在重新参数化下是不变的，但对偶下界D（φ）不是。我们的目标是找到φ使得D（φ）是最大的。通过线性规划对偶，D（φ）将等于原始（1）的最优值。首先，我们将考虑我们的未来al-tax的一个基本步骤，并表明它是在对偶对象的非减。这一性质保证了整个算法的单调性。设θφ为问题的任意重参数化，D（φ）为相应的对偶值。 让我们考虑用一个向量来改变因子i的重新参数化，该向量只具有非零分量（i，j）和（j，i）。这将改变耦合因子j的重新参数化（使得ij∈E），因为<$（i，j）= −<$（j，i）。下面的引理陈述了φ（i，j）的性质，这些性质足以保证相应的对偶值D（φ+φ）的改进：1602我u我我我我我我u uu我我我引理1（单调性条件）。设ij∈E是一对与耦合常数有关的因子，φ（i，j）为对应的对偶向量。设x ∈ argmin <$θ φ，x i<$，消息传递更新步骤为了最大化D（φ），我们将迭代地访问所有因子并调整与之相关的消息φ，单调地增加下限（11）。n（i，j）满足.≥ 0，v（s）= 1我我xi∈X i∗这样的基本步骤由过程1定义。过程1被定义到向量δ，.（1）（4）（1）①的人。所有y，δ（s）=1、xx（s）= 1（i，j）（s）≤0，ν（s）= 0其中v：=A（i，j）xi.（十二）我-1，x（s）= 0是个不错的选择。虽然δ则x∈argmiin <$θφ+<$，xi<$蕴涵D（φ）≤D（φ+<$）.xi∈X i实施例4. 让我们将引理1应用于示例1。 让ij对应于{u，uv}，其中u∈ V是一个节点，uv∈E是它的任一条入射边。则x=可能会导致我们的框架的不同效率，实现-（14）的部分足以证明其收敛性。重新参数化调整问题（15）服务于将尽可能多的松弛从因子i移动到其相邻因子J的直观目标。例如，对于例4的设置，其解为u，uv（s）=θ φ（x）-θ φ（s）。根据所选的δ，它可能对应于maxi-局部最优标签xu ∈arg mins∈Xuθu（s），v（s）=<$s=x（s）。 因此，我们可以分配u，uv（s）在以下定义的方向上实现双重目标：u个可容许的重参数化最大化（15）从[0，θu（xu）−θu（s）]到任何值。 这确保满足公式（20），并且在重新参数化，即使在Xu中存在多个最优解。引理1可以直接推广到两个以上的因子必须同时重新参数化的情况。就示例1而言，这可以对应于图形节点一次向多个事件边发送消息的情况定义2.设i∈F是一个因子，J={j1，. . . ，jl}<$N∈G（i）是其近邻的子集证明我们的方法的收敛性是不必要的（如我们下面所示，证明只需要（15）的可行解），（i）它导致更快的收敛;（ii）对于CRF的情况（如示例1），它使我们的方法等同于TRW-S [48]和SRMP [49]等成熟的技术，如第4.1节所示。下面的命题陈述了由过程1定义的基本更新步骤可以有效地执行也就是说，重新参数化调整问题（15）的大小随着因子i及其附加消息：博尔斯设θi =θ i+j∈J⊤（i，j）<$（i，j），<$（i，j）（=−<$（j，i））对于所有j ∈ J和命题2的所有其他坐标，满足（20）。 设conv（Xi）={µi：Ai µi≤bi}，其中都是零 如果存在x<$∈ argminx∈X <$θ i，则x i满足ai ∈Rn×m. 让问题（15）中的消息具有大小我我我如果x<$∈argminx∈X <$θ<$，xi <$，则称对偶向量<$为n1，. . . ，n|J|. 则（15）是一个线性规划，其时间复杂度为O（n + n1+n）。我我我可接受的 容许向量的集合表示为：AD（θ i，xθ i，J）.引理2.设φ ∈ AD（θ φ，xφ，J），则D（φ）≤ D（φ + φ）.. . . +n|J|时间复杂度为O（m+n1+. . . +n|J|）约束。4. 消息传递算法现在我们将消息传递更新合并到算法2中。它访问因子图的每个节点并执行过程1：消息传递更新步骤。1输入：因子i∈F，相邻因子J={j1，. . . ，j l}<$NG（i），对偶变量φ计算x∈arg minx∈X<$θφ，xi<$（13）以下两个操作：（i）接收消息，当从相邻因子的子集接收消息时，以及（ii）发送消息，当计算到一些相邻因子的消息并通过ω重新加权时。权重ω的分布可以影响算法2的效率，就像它影响用于选择δ∈Rdis.t. δ（s） . >0，xx=1< 0，x（s）= 0（十四）一1603我（i，J）CRF（见[49]）。我们在第4.1节中提供了 典 型 设置。通常，因子以某种给定的先验顺序在向前和向后方向交替遍历，如2 最大化到J的可接受消息：[48]第49话，我们参考[49]，了解这种计算时间表的动机∗（i，J）∈ argmaxθ∈AD（θφ，xθ，J）δ，θφ+θφ（15）我们将讨论算法2的参数（因子参数）。我我3输出：输出。排序{Ji}，权重wJi）就在定理说明之后任何参数的单调性。定理1. 算法2单调地增加对偶下界（11）。∆1604（j，{i}）（j，{i}）uuuemax{|−E|、|E（i，J）（i，J）uuu|c ∈ C：e∈ c|算法二：消息传递的一次迭代1，对于i∈F，按某种顺序，2接收信息：3选择关联因子（i）第一次出现S [48]用于成对CRF）。补充中给出的其他设置可能会将其转换为其他流行的消息传递技术，如MPLP [28]或最小和扩散[64]。我们对节点因子进行排序，并根据此排序对它们进行排序自然定义了传入的E+和出E−边，每个节点u∈V。这里u u4对于j∈J，接收do5计算时间程序1。uv∈E对于u是传入的，如果v< u，并且如果v > u是传出的。每个节点u∈V接收来自所有传入边的消息6设φ=φ + φ。也就是J接收=NG （u）=E+。发送消息7端89发送信息：到所有外接边缘。算法2的第10行中的分区中的每个边uv∈E由单独的集合表示 也就是说，分区读为stece∈E−{e}。八个字是分开的10选择分区J1分区。 . . （i）在第（1）款中，一致且等于w={1u+|} }，e∈ E−.11对于J ∈ {J1，. . . ，Jl} do12用程序1计算时间。13端部14选择权重ωJ1，. . . ，ωJl≥0，使得ωJ1+。 . . +ωJl≤1。15对于J ∈ {J1，. . . ，Jl} do[16]设φ = φ + ω Jφ。17端部月18日结束4.1. 算法2的参数选择在每次外部迭代之后，当所有节点都被处理时，顺序被颠倒并且过程重复。我们参考[49]以证实这些参数。示例2的参数，图形匹配。除了节点和边缘因子之外，对应的IRPS-LP还具有标签因子（7）。为此，所有节点系数均如例1所示。每个节点因子u∈V接收来自所有输入边因子和标签因子的 消息 ，并将它们发送到所有输出边和标签因子。对应的分区读作<$stecf∈NG（u）\E+{f}<$stecXu。重量是分散的一致地，wf={1−+ {\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F} 标签factors算法2中有以下自由参数：(i)F的遍历因子的顺序;（ii）对于每个因子，从其接收消息的相邻因子（i）JN（i）;（iii）Jstec. . . （i）1+max{|Eu|、|Eu|}在访问了所有节点因子之后进行处理。每个标签因子从所有连接的节点因子接收消息并且也发送消息回来：Jreceive（s）={u∈V：接收G1lGs∈X{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}我们使用相同的一组来发送消息，发送消息的因素，以及（iv）相关权重uωJ，.. . ，ωJ留言。即J1= J接收。在每次迭代之后，我们反转因子一升订单。尽管对于这些参数的任何选择，算法2单调地增加对偶下界（如定理1所述），其效率可以显著地取决于它们的值。下面，我们将描述实施例1-3的参数，我们根据经验发现这些参数是最有效的。通过某个因素发送消息自动意味着通过另一个耦合因素接收该消息。因此，在算法2中，通常不需要对所有的因子进行遍历. 保证所有耦合约束都由过程1更新通常就足够了。形式上，我们总是可以通过设置J receive和J i，i=1，. . .，l到空集。相反，我们将解释性地指定哪些因子在下面的例子中的算法2实施例1的参数，CRF中的MAP推断。成对CRF具有节点因子仅与边因子耦合的特点这意味着在算法2中仅处理节点因子就足够了。下面，我们描述将算法2转换为SRMP [49]的参数（这取决于与TRW等效的实现细节实施例3的参数，多切割。类似于示例1，在算法2的循环中仅遍历所有边缘因子就足够了，因为每个耦合约束恰好包含一个循环和一个边缘因子。 每个边 缘 因 子 e 接 收 来 自 所 有 耦 合 的 循 环 因 子 Jreceive=NG（{c∈C：e∈c}）的消息，并将它们发送到相同的因子。 如在示例1中，每个循环因子在算法2的第10行中的划分中形成平凡集，该划分读作：权重均匀分布其中，W=1.每次迭代后，因素顺序颠倒。4.2. 获得无菌溶液最终我们要得到（1）的原始解x∈X，而不是重新参数化θφ。我们不知道任何舍入技术，将同样适用于所有可能的情况下，IRPS-LP问题。根据我们的经验，最1605有效的舍入是针对具体问题的。下面，我们描述我们对实施例11606uv我我（i，j）我v例1与[48]中建议的舍入一致：假设我们已经计算了所有v u的原始整数解x，我们想计算x。在每次迭代的基础上，计算次梯度比使用算法2更便宜，因为仅需要计算（13），而算法2需要另外求解（15）怎么-v u为此，就在Algo的消息接收步骤对于i=u，我们分配公式2 Σ对于MAP推理，研究[41]表明，基于子梯度的算法收敛比像TRWS [48]这样的消息传递算法慢得多。 第6节中x∈argminθu（xu）+xuv u：uv∈Eθ uv（x u，x）。（十六）对于图匹配问题，我们也证实了这一点。这种大的经验差异的原因是次梯度算法的一次迭代仅更新那些协梯度。实施例2的修约是相同的，除了我们将受电流影响的对偶变量φ的坐标选择最好的标签xu其中，没有极小标号x∈argminxi∈Xixθ φ，x iφ（即坐标为了满足唯一性约束：natesk：（Ax（k=1），而在算法2中，所有cor-x∈argminΣθφ（xu）+θ φ（x u，xφ）。（ 十七）φ的二进制数被考虑在内。 消息传递隐式地选择步长以便实现单调性，uxu：xuxuvu紫外线v u：uv∈E在算法1中，算法1是收敛的，而基于次梯度的算法必须依赖于一些步长规则。舍入为例如3 .第三章。我们 使用有效[45]在[46]中实现的Kernighan Lin启发式[45]成本用于舍入的是重新参数化的边缘电势。5. 不动点及其与地基法算法2不一定收敛到（1）的最优。相反，它可能会卡在次优点，类似于示例1中CRF中的“弱树一致性下面我们将精确地描述这些不动点。定义3（边际一致性）。给定一个重新参数化θφ，令对于每个因子i∈Fa给定非空集 SiQ∈gminxi∈Xi <$θφ ，xi<$，i∈F.定义S=i∈FS i。我们称S在ij ∈ E上的重新参数化θφ为边际相容的，如果A（i，j）（S i）= A（j，i）（S j）.（十八）如果θφ对S在所有ij∈E上是边际相容的，我们称θφ与S几乎一致。请注意，边际一致性是必要的，但不足以使松弛（1）最优。这可以在CRF（示例1）的情况下看到，其中它完全对应于弧一致性。后者只是必要的，但不是最优性的充分条件[74]。定理2. 如果θφ是边际相容的，则对偶下界D（φ）不能通过算法2改进。比较到次梯度法分解IRPS-LP和更一般的可以通过以下方式解决：次梯度法[50]。与算法2类似，它对对偶变量φ进行操作，并通过顺序访问每个因子来操纵它们。与算法2相反，次梯度算法收敛到最优。此外，委员会认为，16076. 实验评价我们的实验的目的是说明所提出的技术的适用性，他们不是一个详尽的评估。所提出的算法只是基本的变种，可以进一步改进和调整所考虑的问题。这两个问题都在专门研究中得到了解决[68，67]。尽管如此，我们表明，所提出的基本变量已经能够在具有挑战性的数据集上超越最先进的专业求解器6.1. 图匹配解算器我们比较了两种最先进的算法：（i）基于次梯度的对偶分解求解器[70]（缩写为DD）和（ii）最近的“匈牙利信念传播”消息传递算法[ 78 ]（缩写为HBP）。虽然[78]的作者将他们的求解器嵌入到分支定界例程中以产生精确的解，但我们重新实现了他们的消息传递组件，但没有使用分支定界来使组件公平。DD和HBP两种算法在发表时都优于其他求解器[18，76，53，69，63，29，79，38，54，16]，因此我们没有对它们进行测试。我们称之为求解器AMP。数据集。我们选择了三个具有挑战性的数据集。前两个是标准的基准数据集car和motor，都在[55]中使用，包含30对汽车和20对摩托车，关键点以1：1匹配。这些图像来自VOC PASCAL 2007挑战赛[21]。成本是根据[55]中的特征计算的图是具有20第三个是新的蠕虫数据集[40]，包含来自生物成像的30个问题这些问题由稀疏连接的图组成，最多有600个节点和1500个标签。据我们所知，蠕虫数据集包含最大1608能源10310210110310210110510410310−1 100101运行时间车10010−1 100 101运行时间电机10210−1 100 101 102运行时间蠕虫图2.比较汽车、发动机和蠕虫图形匹配数据集上的平均log（原始能量-双重下限）值的曲线图两个轴都是对数的。-4，000人-4，200-4，400-4，600-2。71-2。72-2。73·104-7。6-7。8·104-4，800-5，000人10−2 10−1100运行时间Knott-3D-150-2。74-2。7510−1 100 101 102运行时间Knott-3D-300−810−1100 101 102运行时间Knott-3D-450图3.比 较 三个knott-3d-{150| 300| 450}多切割数据集。值是数据集中所有实例的平均值X轴是对数的。连续线是对偶下界，而相应的虚线表示通过舍入获得的原始解。图匹配的情况下曾经考虑在文献中。运行时图显示了每个数据集的所有实例上的平均对数二、结果我们的求解器AMP始终优于HBP和DDw.r.t.原始/对偶间隙和任意时刻性能在最大的蠕虫数据集上最明显的是，基于子梯度的算法DD努力减小原始/对偶间隙，而AMP给出合理的结果。6.2. 多刀解算器我们将其与OpenGM [41]库中实现的最先进的多割算法进行比较，即(i)利用ILP求解器CPLEX [2]的基于分支和切割的求解器MC-ILP[44这些求解器被证明优于其他多切割算法[9]。Al-出租MC-ILP提供了上限和下限，而CC-Fusion和CGC是纯粹的原始算法。我们称之为我们的消息传递求解器与循环约束添加在一个切割平面时尚MP-C。数据集。我们有选择三 数据集Knott-3d-{150|300|450}从OpenGM[41]。问题来自脑组织的电子显微镜，我们希望获得神经元分割。每个数据集包含8个实例，分别具有≤972，5896和17074个节点和≤5656，36221和107060条边。结果关于显示对偶边界和原始解决方案目标随时间变化的图，请参见图3。我们的算法MP-C结合了基于LP的技术和原始算法的优点：它比MC-ILP更快地提供高双下界。它具有快速的原始收敛速度，并提供原始解决方案可比/优于CGC7. 致谢作者感谢Vladimir Kolmogorov进行了有益的讨论。第一作者由欧洲研究理事会根据欧盟七框架计划（FP7/2007-2013）/ERC资助协议编号616160提供支持，第二作者由DFG Grant GRK 1653提供支持，最后一作者由欧洲研究理事会根据欧盟地平线2020研究和信息计划 提 供 支 持 （ 授 权 协 议 号 647769 ） 和 DFGGrant“ERBI”SA 2640/1-1。引用[1] https://en.wikipedia.org/wiki/ARPANET网站。1AMPHUNGARIAN-BPDDMP-CCGCMC-ILPCC-Fusion-RWSCC-Fusion-RHClog（能量下限）log（能量下限）log（能量下限）1609[2] IBM ILOG CPLEX Optimizer。http://www-01.ibm的网站。com/software/integration/optimization/cplex-optimizer/. 1、8[3] 边 际 稠 度 ： 交 换 半 环 上 的 上 界 配 分 函 数 。 IEEETPAMI，37（7）：14557[4] A. Alush和J.戈德伯格突破和征服：有效的相关聚类图像分割.在大肠R. Hancock和M. Pelillo，编辑，SIMPAD，计算机科学讲义第7953卷，第134-147页。Springer，2013. 3[5] B. Andres，J.H. Kappes，T.Beier，U.Koïthe和F.A. 火腿酱。具有封闭性约束的概率图像分割。In D. N.梅塔克萨斯湖Quan、紫菀A. Sanfeliu，以及L. J. V. Gool，editors，ICCV，pages 2611-2618. IEEE计算机协会，2011年。3[6] B. Andres ， T.Kr oger ， K.L. Briggman ， W.Denk ，N.Korogod，G. 诺特U K oïthe和F. A. 汉普雷希特用于连接组学的全局最以. W. Fitzgibbon，S. Lazebnik，P. Perona，Y. Sato和 C. Schmid ， editors ， ECCV （ 3 ） ， Volume 7574ofLecture Notes in Computer Science ， pages 778-791.Springer，2012. 3[7] A. 阿拉苏角R和D。苏丘使用重复数据删除功能进行具有约束的大规模重复数据删除耶氏酵母中E. Ioannidis，D. L. Lee和R.T. Ng，editors，ICDE，pages 952IEEE计算机学会，2009年。3[8] C. Arora和A.格罗伯森高阶匹配一致多目标跟踪。在IEEE计算机视觉国际会议论文集，第177- 184页2[9] T. Beier、F. A. Hamprecht和J. H.卡佩斯融合移动相关聚类。在CVPR中，第3507IEEE计算机学会，2015年。三、八[10] T. Beie r，T. Kr oger，J. H. 卡佩斯大学 Koïthe和F. A.火腿酱。切割，粘合切割：多切割分区的快速近似求解器。在CVPR中。会议记录，2014年。三、八[11] O. Bilde和J.克拉鲁普简单工厂选址问题的精确下界与有效算法。Annals of Discrete Mathematics，1：79-97，1977. 1[12] Y. 博伊科夫岛Veksler和R.扎比通过图切割的快速近似IEEETransactions onpatternanalysisandmachineintelligence，23（11）：1222-1239，2001. 1[13] R. E. Burkard，E. C.Chelela，P. M. Pardalos和L. S. 皮苏利二次分配问题，第1713-1809页。Springer US，Boston，MA，1999年。3[14] Y. Chen，S. Sanghavi和H.徐聚类稀疏图。在公共图书馆Bartlett，F. C. N.佩雷拉角，巴西-地J. C.伯吉斯湖Bottou和K.Q. Weinberger，编辑，NIPS，第22133[15] F. Chierichetti，N.Dalvi，和R.库玛mapreduce中的相关第20届ACM SIGKDD知识发现和数据挖掘国际会议集，KDD'14，第641-650页，美国纽约州
我的内容管理
展开
