残差扩展算法：非凸最小二乘问题的快速全局优化

1残差扩展算法：非凸最小二乘问题的快速有效优化Daiki Ikami Toshihiko Yamasaki Kiyoharu Aizawa日本东京大学{ikami，yamasaki，aizawa}@ hal.t.u-tokyo.ac.jp摘要我们提出了残差扩展（RE）算法：非凸最小二乘问题的全局（或近全局）优化方法。与大多数现有的非凸优化技术不同，RE算法不是基于随机或多点搜索;因此，它可以实现快速的全局优化。此外，RE算法易于实现，在高维优化问题上取得了成功.RE算法在k-均值聚类、点集配准、最优乘积量化和盲图像去模糊等方面表现出1. 介绍计算机视觉和机器学习中的许多问题都如果我们可以将一个问题表示为凸优化问题，那么我们可以通过凸优化技术（如基于梯度的方法）来解决它。然而，大多数优化问题都是非凸的，往往存在许多局部最小值。在这些情况下，凸优化技术只能找到局部极小值。非凸问题的全局优化在大多数情况下是NP-难问题.因此，启发式方法通常用于找到全局（或近全局）最优解。主要有两种方法：良好的初始化和随机优化。如果我们能获得一个好的初始猜测，前者是快速有效的[2];然而，许多优化问题没有提供这一点。 后者是随机搜索或多点搜索，以模拟退火（SA）[13]，粒子群优化（PSO）[12]和遗传算法（GA）[19]为代表。虽然这些方法对于低维优化问题是有效的此外，这些方法通常需要过多的计算时间来获得良好的解决方案。第在本文中，我们提出了一种快速，有效的优化，(a) 全局最优结果。（b）局部最小值结果。图1：具有不同RE收敛的K均值聚类结果。灰色圆圈表示原始数据点，红色、蓝色和绿色圆圈表示来自每个聚类中心的α扩展数据点图图1（a）显示α RE收敛，α= 1 ;然而，图1（a）显示α RE收敛，α = 1。1（b）没有说明这一点。在这种情况下，具有较大RE常数的解实现全局最优。RE收敛和RE常数的细节在第3节中描述。最后，本文提出了一种非凸最小二乘（LS）问题的最小化方法，如k-均值聚类和点集配准。首先，我们提出了一种称为RE收敛的新收敛度量：这表示在收敛条件下我们可以沿着数据点的剩余方向扩展数据点多远。图1显示了k均值结果和扩展的数据点。图1（a）描绘了扩展数据上的收敛，而图1（b）描绘了扩展数据上的收敛。图1（b）示出了不收敛的情况我们证明了RE收敛与全局收敛相联系事实上，我们可以证明，在一个大的扩展是稳定的解决方案是一个一维的四次最小化问题的情况下的全局最优。此外，我们提出了一个启发式算法，找到一个解决方案，是稳定的大的扩展，我们称之为剩余扩展（RE）算法。该算法既不基于多点搜索，也不基于随机搜索，因此可以实现快速计算。我们的贡献如下：1. 我们提出了一个新的收敛概念，RE con，58195820¨F¨F¨¨¨聚散给出了RE收敛与全局最优解之间的关系。2. 我们提出的RE算法，它可以适用于任何非凸LS问题。我们表明，RE算法是快速，有效的，易于实现。3. 我们展示了RE算法2. 相关作品2.1. 非凸最小二乘问题我们专注于非凸LS问题，其中许多存在。在本文中，我们研究了计算机视觉和机器学习中的以下四个重要问题。其中R ∈ SO（3）是旋转矩阵，t ∈ R3是平移向量，Z =[z1，. . . ，zn] ∈ Rk×n是一个分配矩阵. I是单位矩阵，1是所有1的向量。迭代最近点（ICP）算法[3]是一个很好的-已知的交替优化方法：它修正Z并更新R，t，然后修正R，t并更新Z。 为了获得全局最小值，一些研究采用随机优化，如GA [24]，PSO [27]和SA [18]。最近，Yanget al.提出了Go-ICP[29]，它通过使用分支定界算法来保证全局最优性然而，它需要大量的计算时间.2.1.3优化产品量化优化乘积量化（OPQ）[9，22]是乘积量化（PQ）的扩展，是一种有效的快速近似最近邻搜索方法。OPQ中的优化问题描述为：2.1.1K-means聚类K-means聚类是最流行的聚类之一，¨¨1ΣN ¨C（1）z。¨(1)¨我是mini−R.¨（三）具有各种应用的方法，例如量化-[11]，特征学习[8]，分割[1]。 K型意味着聚类分配数据向量x1，. . .，xn∈Rd至R、C、Z2（m）¨i=1？¨¨（m）C（M）¨（男）I2⊤最近的代表性集群。 优化问题-S.T.z¨ij={0，1}，？zi<$=1，R1R = I，LEM可以公式化为1minC、Z2第1002章：（1）其中X、C、Z具有与第2.1.1节中相同的含义，R是旋转矩阵。方程的优化问题（3）可以通过S.T. zij={0，1}，zi1= 1，其 中 X=[x1 ， . . . ， xn]∈Rd×n 是 一 个 数 据 矩 阵 ，C=[c1 ， . . .， ck] ∈Rd×k 是 簇 质 心 矩 阵 ， Z=[z1，. . . ，zn] ∈ Rk×n是一个分配矩阵.最 流 行 的 优 化 方 法 是 LloydHartigan 算法[10]比Lloyd算法实现了更好的聚类，因为Hartigan算法的局部最小值集R、C和Z的交替优化[9，22]。 Ge等人也提出了一种参数优化方法，假设数据遵循参数高斯分布[9]。2.1.4盲图像去模糊图像盲去模糊一直是计算机视觉领域的一个具有挑战性的问题从一幅模糊图像B∈Rh×w，我们估计出一幅原始图像I∈Rh×w和模糊核k∈Rk×k，通过最小化以下成本函数：Rithm是Lloyd算法的子集[26，25]。 为良好的初始化，k-means++[2]经常使用，因为它的效率和有效性。minI，kI22.1.2点集配准点集配准是计算机视觉中的一个基本问题这里我们考虑刚性3D点集配准问题：给定源点集X=[x，. . .，x ] ∈其中RI（I）和Rk（k）是正则化项，并且表示卷积算子。对于RI（I），L0-范数（或近似L0-范数）[28，23]或L1/L2函数[15]以增强原始图像的锐利边缘。对于Rk（k），常用L2-范数[28，23]或L1-范数[15]。我们参考了最近比较的论文[16]R3×n1以及目标点集Y=[y1，. . .，ymn]∈R3×m，图像盲去模糊研究我们可以将Eq。（4）通过交替优化我们估计最佳刚性变换参数。在本文中，我们考虑以下具有点对点成本函数的优化问题：我和K。为了快速有效的优化，通常采用粗到细的策略[7，15，28，23]最小值1RX+t1−YZ2（二）2.2. 非凸优化技术R，t，Z22z1⊤5821S.T. zij={0，1}，zi1=1，RFR =I，大多数非凸优化技术都是基于随机优化，包括GA[19]， PSO[12]，5822E（3）E，1（3）E，第2（3）段E，第3（3）段E（3）E，1（3）E，第2（3）段E，第3（3）段3312我我12αθ θθ∗⊤∗ ∗∗2SA [13]。这些方法通常不能很好地工作，或者需要大量的计算时间用于高维优化问题。几项研究[4，14，18，27，24]已经将这些非凸优化技术应用于我们在第2.1节中描述的目标问题;然而，这些这些方法在实践中并不经常使用。$美元我们的方法与渐进非凸性3 3相关(GNC)[5]，它首先解决一个简化的优化问题，然后逐渐将问题转化为原始的非凸问题。Gradu的基本概念（a）θ及其扩展目标（b）θ及其扩展目标函数。 功能图2：具有不同局部最小值的扩展目标函数Eα（θ），θ和θ。红色虚线表示不同最佳化方法是消除局部极小值1 2使用一个凸化的目标函数，然后逐渐α-扩展目标函数Eα（θ），其中α1<α2<α3。θ仍然是Eα（θ）的局部最小值，而θ不是。将目标函数转换为原始函数。我们231[20]《明史》卷120：“明史”为《明史》卷120。mization与GNC相反，我们的方法是通过使用一个大大扩展的目标函数，然后逐渐将其转换为原始函数，从而明确地摆脱糟糕的局部极小值，如第4节所述。3. 残差展开收敛首先，我们描述RE收敛，这表明我们如何沿着其残差方向扩展数据RE con-3.1. 无约束可微问题我们考虑最简单的情况之一：无约束可微LS问题给定一个局部最优值θ，我们可以得到α- e扩展的目标函数Eα（θ）在θ处的一阶和二阶导数为：∗ ⊤ ∗ ∗Eα（）=（1 +α）J（）（y−f（））= 0，（8）ΔEα（θ）= J（θ）J（θ）+（1+α）S（θ）。（九）其中J是雅可比矩阵，S（θ）是聚合度是衡量聚合深度的一个指标，我们的所提出的算法是基于这个概念。我们展示了全局最优和RE转换之间S（θ）=2f（θ）（y我∗-f（θε））。（十）gence.我们讨论了一个非凸最小二乘（LS）优化问题，其目标函数由下式给出：当量（8）表示θ总是Eα（θ）的驻点。因此，θθ是E（θ）的局部极小值，当且仅当Eα（θ）是一个半正定（PSD）矩阵。如果S是12不是PSD矩阵，存在α≥0满足以下事实E（θ）=2<$y −f（θ）<$2。（五）我们的定义如下。定义3.1（剩余膨胀）。设θ_i为方程的局部极小点.（五）、我们定义α-扩展目标函数Eα（θ）：E（θ）=1<$y<$−f（θ）<$2。（六）α22证明了θ2Eα（θ）不是PSD矩阵。图2显示了α-扩展目标函数的示例选项。残差展开使目标函数在θ θ附近升高，如果α足够大，那么它不再是局部最小值。一维四次最小化：在这里，我们考虑一个四次最小化问题，特别是一个可以用公式表示为LS问题的问题：其中，通过在剩余分量中扩展y来构造reyα的大小为∗1 .一、.E（θ）=2y1−θ 2Σ2Σ+（y2−θ）2 .（十一）y=y+α（y−f（θ）），（7）我们考虑Eq. （11）有两个局部极小值我们把构造α-展开对象的运算称为-θ 1和θ 2。下面的定理成立：函数残差展开式（带α）。定义3.2（α RE收敛）。如果存在一个常数α≥0，使得θ仍是Eα（θ）的局部最优解，则称θ θ为α RE收敛.特别地，最大（或上确界）常数被称为RE常数1。我们假设α-RE常数越大。如第3.1.1节所述，该1.若在所有α ≥ 0下，θ∈ Eα（θ∈）总是局部极小值，则定义RE常数为∞。英英我5823定理1. 设θ1和θ2是方程的局部极小点。（11），RE常数分别为α1和α2。如果α1> α2，则θ 1是全局极小点，否则θ2是全局极小点。证据 请参阅补充材料。3.2. αRE收敛与全局最优解的一般关系当我们的假设，即，具有较大RE常数的解更接近全局最优解是有效的。不幸的是，我们很容易找到一个反例5824¨¨1-1-3-113(a) K-means聚类结果1-1-3-113(b) K-means聚类结果算法1残差扩展算法。输入：展开参数α（t）→0，动量p（t）。初始化：t=0，y=y，r（0）=0一曰： 而不收敛2：通过E更新θ。Q. （十二）、（或Eq. （2Σ可怜的最小值。全局最小值3：r（t+1）=p（t）y−fθ（t+1）+1 −p（t）r（t）图3：k=2时不同的k-means聚类结果。结果（a）的RE常数为α=∞;然而，这是一个较差的局部最小值。另一方面，结果（b）具有有限RE常数;然而，这是全局最小值。4：y（t+1）=y+α（t）r（t+1）5：t=t+16：endwhile输出：θ= 1 = 2= 3图4：RE算法的概念视图该算法迭代参数更新和残差扩展，提高了当前解的目标函数。在k-means聚类中，如图所示。3.第三章。然而，我们的算法，其目的是找到一个解决方案，一个大的RE常数，从经验的角度来看，在许多非凸LS问题。分歧，如后所述。RE算法通过最小化Eq.（12）和Eq.的残差扩展（13）和Eq. （14）。我们最初使用大的α（0）来找到具有大RE常数的解。然后我们逐渐减小α（t）以达到收敛，类似于SA中的温度我们总结了在Alg. 1.一、4.1. 收敛参数设置对于每次迭代，RE算法具有两个参数α和p 为了收敛，我们将α（t） 当α=0时，不存在剩余展开，RE算法保证收敛，如果原LS问题一种保证收敛的算法然而，α和p的参数不足会导致不稳定的优化。我们考虑r（t+1）的范数。可以得出对当代"2“。.ΣΣ¨2？r（t+1）？=？py−fθ（t+1）+（1−p）r（t）<$4. 残差展开算法¨ ¨ ¨2¨2¨ ¨2在本节中，我们提出了RE算法，其目的是找到具有大RE常数的解。因为它很难-<$（1−p−αp）2<$r（t）<$.Σ2.（十五）为了精确地找到具有最大RE常数的解我们用fθ（t+1）最后一次近似的最后一次近似我们采用启发式策略。RE算法分为两步：参数更新和残差扩展。我们在图中展示了算法的直观说明。4.第一章对于残差扩展步骤，我们沿着残差方向扩展数据。这导致在当前解附近提升目标函数，如图1所示。二、对于参数更新步骤，代替最小化原始函数Eq. （5），我们在每次迭代中最小化以下扩展目标函数：E（θ）=1<$y<$（t）−f（θ）<$2，（12）t22其中，y=（t）是扩展的数据向量：y（t）=y+α（t）r（t），（13）r（t）=p（t）（y-f（θ（t）+（1-p（t））r（t-1）. 其中α和0

下载后可阅读完整内容，剩余1页未读，立即下载