点击下方“计算机书童”卡片，每天获取顶刊论文解读
题目：Convergence Analysis of Mean Shift均值漂移算法的收敛性分析
作者：Ryoya Yamasaki; Toshiyuki Tanaka
摘要
均值漂移（MS）算法寻找核密度估计（KDE）的模态。本研究在相当温和的条件下，借助Łojasiewicz不等式的相关论点，提出了MS算法生成的模态估计序列的收敛保证和收敛速率的评估。我们的发现扩展了现有的分析，涵盖了解析核和Epanechnikov核。这些在覆盖基于KDE的模态估计中渐近统计效率最佳的非负核——双权重核方面具有重要意义。
关键词
双权重核，收敛性，收敛速率，均值漂移，Łojasiewicz不等式
Ⅰ. 引言
均值漂移（MS）算法[1]、[2]、[3]已在计算机视觉、图像处理、模式识别和统计学等多个领域得到广泛应用。其在数据聚类[4]、[5]中的一个流行应用是，MS算法的优势在于它不需要预先指定聚类的数量。与k-means聚类相比，基于MS的聚类不需要适当的聚类中心初始化，并且能够处理任意形状的聚类。MS算法的其他应用包括图像分割[3]、[6]、边缘检测[7]、[8]、目标跟踪[9]、[10]和模态估计[11]、[12]等。
MS算法是一种迭代算法，寻找核密度估计（KDE）的局部最大值。MS算法的应用，如数据聚类和模态估计，需要MS算法生成的模态估计序列的收敛性。因此，从理论上研究MS算法的收敛性质是重要的。然而，正如第III节所回顾的，MS算法的可用理论收敛保证非常有限：由于MS算法的动态行为取决于用于构建KDE的核，收敛性质也应该依赖于核的选择。据作者所知，当使用Epanechnikov核[13]、[14]或解析核[15]时，已证明多维数据的MS算法会收敛。这些结果不包括使用除Epanechnikov核之外的分段多项式核的实际情况。此外，关于MS算法的收敛速率知之甚少。
在本文中，我们在一些通用假设下研究MS算法的收敛性质。从技术角度来看，我们遵循与[15]中类似的路线，该路线专注于Łojasiewicz属性[16]、[17]：该属性确保正在考虑的函数在其临界点附近不会过于平坦，使我们能够将KDE值序列的简单收敛分析转换为模态估计序列本身的收敛分析。更具体地说，我们利用了关于该属性的更高级结果[18]、[19]、[20]，进一步扩展了分析核的收敛分析[15]，以适应以与Łojasiewicz属性相关的次分析性[18]进行表征的核：这种扩展使我们能够获得新的结果，包括模态估计序列的收敛保证（定理1和2）和MS算法的最坏情况收敛速率界限（定理3和4），适用于更广泛的核类。我们的贡献具有重要意义，因为我们在本研究中关注的核类包含了双权重核，已知在基于KDE的非退化模态估计中，非负核的渐近统计效率最佳[12]、[21]。
Ⅱ. MS算法
MS算法的多种应用源于MS算法是寻找KDE局部最大值的优化算法的表征。给定n个数据点，KDE构建为其中和分别称为核和带宽参数。在本文中，对于核，我们采用以下假设，这在MS算法的研究中很常见：假设 1：核是有界、连续、非负、归一化和径向对称的。如[22]、[23]所述，MS算法可以被视为在某种条件下的最小化-最大化（MM）算法的一个例子。MM算法通过迭代地构建所谓的原始目标函数的minorizer并优化minorizer来解决一个困难的原始优化问题。让我们将的右导数和左导数写为对于定义在上的实值函数，在处的次微分定义为满足对于任何的的集合。在假设2下，由于轮廓是凸的，次微分对于任何是非空的，由给出。注意到在假设下也是非空的。由于对于任何，是非空的，可以证明次微分是非减的，即对于，有：实际上，对于任何且，取任意和。从次微分的定义，有和，两者相加得到，得到。参见[24, Section 24]中关于上函数的次微分的这些属性。此外，由于轮廓是非增的，对于任何，有。因此，通过定义的函数在上是非增的、非负的、有界的，因为对于任何，有，这是由假设2保证的。对于任何。我们也有。这些性质意味着，在假设1和2下，是处核的一个minorizer。应该注意的是，在的定义(4)中，当包含多个值时，的值是有任意性的。例如，Epanechnikov核的轮廓由给出，其中，因此。在这种情况下，可以采用区间中的任意值作为。实际上，[13]采用了，而[14]采用了。我们想在这里指出，以下分析不受在这些点的定义方式的影响。给定次估计，MS算法构建KDE在处的minorizer为用它来表示中二次项的系数为。假设2确保了由于的非负性，是非负的。此外，如果，那么(7)右边的所有求和项都是零，因此函数是常数。如果，那么函数是二次的，并且有一个唯一的最大值。和全零向量。MS算法从给定的初始估计开始迭代更新规则(8)，同时增加下标。因此，MS算法可以被视为MM算法的一个实例。这里，当时的更新规则是一个异常处理规则，以避免MS算法由于普通更新规则的分母(即)为零而变得未定义。在假设1和2下，如果，那么KDE的梯度也消失，也就是说，是的一个临界点。因此，异常处理规则确保MS算法在临界点停止。此外，以下命题表明，如果适当选择初始估计，则不会发生这种异常：命题 1：假设假设1和2。设是由MS算法(8)从开始获得的模态估计序列，其中。那么，存在一个常数，使得对于某个依赖于的索引，有，因此对于任何，有。例如，在用MS算法进行数据聚类[4]、[5]时，采用每个数据点作为初始估计，因此额外的假设肯定成立。上述将MS算法构造为MM算法的过程展示了密度估计序列的上升性质，以及由于假设1保证了KDE的有界性，保证了该序列的收敛性：命题 2（[15]中的定理1）：假设假设1和2。对于由MS算法(8)从任何开始获得的模态估计序列，密度估计序列是非减的并且收敛。上述命题保证了由MS算法生成的密度估计序列的收敛性。从应用的角度来看，我们感兴趣的不是密度估计序列的收敛性，而是模态估计序列的收敛性，因为如果存在极限，它将告诉我们模态或聚类中心的位置。这里的困难在于，如果不附加额外的假设，就不能从密度估计序列的收敛性推导出模态估计序列的收敛性。本文的主要兴趣在于，例如MS算法生成的模态估计序列的收敛性质，以及它收敛时的收敛速率。Ⅳ ŁOJASIEWICZ属性的预备知识
如上所述，[15]利用解析核证明了MS算法模态估计序列的收敛性，而不需要考虑带宽参数或数据维度。他们证明的关键是在Łojasiewicz属性/不等式，它为解析函数提供了函数在其临界点附近平坦度的下界。在MS算法的收敛分析中，这个界限反过来允许我们将密度估计序列的收敛性转换为模态估计序列的收敛性。我们遵循与[15]类似的路线，但不是依赖于[16]、[17]，而是依赖于[18]，它为超出解析函数的更广泛类别的函数显示了Łojasiewicz属性，以及利用该属性的更高级收敛分析[19]、[20]。我们这里描述了Łojasiewicz属性，以及具有该属性的重要函数类。我们采用了以下Łojasiewicz属性/不等式/指数的定义，以及相关的概念。其中，，以及任何，那么我们说函数在处具有Łojasiewicz属性，其中按照[36, Remark 4]的约定，。此外，如果在（当时，我们省略“在上”）上可微，并且存在，使得满足不等式(10)，对于，，以及任何使得，，那么我们说在上具有Łojasiewicz属性。而且，在处具有Łojasiewicz属性的最小可能指数（即Łojasiewicz指数）是信息性的。如果在处连续可微，并且如果不是的临界点（即，），那么对于任何，在处显然具有Łojasiewicz属性，与指数，意味着在处“最大地不平坦”。另一方面，如果是的局部最小值，那么对于足够小的，有，意味着在局部最小值处具有Łojasiewicz属性。这些事实表明，定义1主要针对的是描述在其临界点（除了局部最小值）附近的平坦度。当足够光滑时，其在非局部最小值的临界点处的Łojasiewicz指数通常是，而如果在临界点的Hessian是退化的，它可以更大。作为一个更具体的例子，让我们考虑意味着在处具有Łojasiewicz属性，指数。当取更大的时，在处“更平坦”，相应地，Łojasiewicz指数变得更大。另一个例子是，其中是指示函数，如果条件为真，则取值为1，否则为0。那么我们有其中，，基于此，可以展示在处没有Łojasiewicz属性，即在处“过于平坦”，无法被定义1捕获，因为对于任何，我们有对于我们的目的，Łojasiewicz属性的重要性在于，它允许我们在KDE“不太平坦”的情况下，将密度估计序列的收敛性转换为模态估计序列的收敛性，并且当模态估计序列收敛时，该属性可以提供更快的收敛保证，当在极限处“不那么平坦”时，将在第V节讨论。[16]表明解析函数具有Łojasiewicz属性，之后，[18]将该结果推广到函数的更广泛类别（见[37]），特别是包括全局次分析函数：命题 3 ([16], [18])：如果函数在上是解析的，或者如果是全局次分析的，那么具有Łojasiewicz属性。现在我们介绍全局次分析性的定义，以及几个相关的概念，后者作为全局次分析性的充分条件。在补充材料中的讨论中将看到，这些概念在实践中是有用的，因为直接验证全局次分析性可能很困难，而这些充分条件更容易验证。- 被称为次分析的，如果对于每个点，都存在一个的邻域和一个有界的半解析集，，使得。
- 函数在上被称为半代数的（resp. 半解析的，次分析的，全局半解析的，或全局次分析的），如果其图是半代数的（resp. 半解析的，次分析的，全局半解析的，或全局次分析的）的子集。
- 函数在上被称为最大次数为的分段多项式，如果存在一个有限集合的子域，，构成的一个划分（即，对于所有，，对于所有，，有，并且），使得对于任何（即，在上的限制与在上的限制相同）对于每个，并且的最大次数为。
具有广泛实例的半代数函数类别包括：多项式、有理和更一般的分段多项式函数[43]、[44]。正如下一节将讨论的，包括双权重核在内的分段多项式函数类别在本研究的讨论中尤为重要。任何全局半解析函数都是半解析的，任何具有有界图的半解析函数都是全局半解析的[42, 在例1.1.4之前]。任何全局次分析函数都是次分析的，任何具有有界图的次分析函数都是全局次分析的[38, 在定义2.2之后]。同样，半解析函数是次分析的（这可以从定义2中看出），全局半解析函数是全局次分析的[42, 定义1.1.6]，半代数函数是全局次分析的[42, 示例1.1.4]。值得注意的是，解析函数不一定是全局次分析的（当然，反之亦然：全局次分析函数不一定是解析的）。例如，，肯定是解析的，但不是全局次分析的[42, 示例1.1.7]。此外，应该指出的是，半解析/次分析函数（例如，在上定义的正弦函数）和函数不一定是全局次分析的，并且它们并不总是具有Łojasiewicz属性；[17]中的“墨西哥帽”函数（方程(2.8)）和[45]第14页上显示的函数是类别的实例，不是全局次分析的，并且这些函数没有Łojasiewicz属性。这些包含关系在图1中总结。![]()
由于命题3中Łojasiewicz属性的考虑，对于我们的目的重要的是提供KDE是全局次分析的充分条件。因此，上述包含关系中的全局次分析的充分条件，以及全局次分析性在求和下的稳定性[42, 性质1.1.8]，是重要的，总结如下：命题 4：任何半代数或全局半解析函数，任何半解析或具有有界图的次分析函数，以及任何全局次分析函数的求和都是全局次分析的。Ⅴ MS算法的主要结果：收敛定理
A. 收敛到临界点
在本小节中，我们提供了一个充分条件，使得MS算法的模态估计序列收敛到KDE 的一个临界点。我们的结果与现有的使用解析核的MS算法的收敛定理[15]类似，并且进一步扩展了命题3和4，即全局次分析核及其相应的KDE具有Łojasiewicz属性。包括[17]、[19]、[20]、[36]、[40]、[41]在内的几项最近的优化理论研究，利用Łojasiewicz属性来证明各种优化算法的收敛性。通过将诸如[19, 定理 3.2]和[20, 定理 3.1]之类的抽象收敛定理应用于MS算法，我们得到了以下定理：定理 1（收敛保证）：假设假设1和2。设是由MS算法(8)从开始获得的模态估计序列，其中。进一步假设，对于某个，的凸包的闭包
(a1) KDE 在上可微，并且具有Lipschitz连续梯度（即，存在一个常数，使得对于任何，有，其中这样的常数的最小值称为在上的Lipschitz常数），并且
(a2) KDE 在上具有Łojasiewicz属性。那么，模态估计序列具有有限长度轨迹（即，），并且收敛到KDE 的一个临界点。我们接下来讨论如何将假设(a1)和(a2)关于KDE 的假设替换为有关核的假设，以便后者为前者提供了充分条件。让我们首先关注定理1的假设(a1)。如果核具有Lipschitz连续梯度的可微性，则使用核的KDE 显然满足假设(a1)对于任何，因为函数的求和保留了可微性，以及梯度的Lipschitz连续性。因此，对于模态估计序列的收敛保证，我们可以将关于KDE 的假设(a1)替换为以下关于核的假设：假设 3：核是可微的，并且具有Lipschitz连续梯度。接下来讨论如何将定理1的假设(a2)替换为关于核的假设。根据命题3和4，当核是解析的或全局次分析的，很明显相应的KDE 也是如此，并且具有Łojasiewicz属性。我们接下来论证，要求核是次分析的确实足够以满足假设(a2)：在假设1和2，以及条件下，对于的模态估计变成了数据点的一个凸组合，即的加权均值，权重非负，因此它位于的凸包中，这是一个有界集。因此，我们可以在没有问题的情况下将每个核的定义域限制在上。另外，每个核在假设1下是有界的。因此，当核是次分析的，到的限制变成了一个具有有界图的次分析函数，并且由于命题4，它也是全局次分析的，因此具有Łojasiewicz属性。因此，相应KDE的限制也是全局次分析的，由于命题3，具有Łojasiewicz属性。鉴于这种考虑，我们不必要求全局次分析性，要求核是次分析的就足够了，以满足对于任何的假设(a2)。因此，在假设1、2和3以及条件下，我们可以将关于KDE 的假设(a2)替换为以下关于核的假设：因此，以下定理将直接作为定理1的推论得到，它独立于模态估计序列保证了收敛性。定理 2（定理1的推论）：假设假设1、2、3和4。设是由MS算法(8)从开始获得的模态估计序列，其中。那么，模态估计序列具有有限长度轨迹，并且收敛到KDE 的一个临界点。定理2的主要意义在于，它首次揭示了包括双权重和三权重核在内的几种分段多项式核的MS算法的收敛性。具体来说，双权重核在基于KDE的模态估计中，在非负核的渐近统计效率方面是最优的[11]、[12]。更具体地说，对于具有在模态处具有非退化Hessian的真实概率密度函数的模态，一维KDE基础模态估计器的渐近均方误差的主要项与核相关项（）成比例我们称其倒数为渐近统计效率，[21]表明双权重核使这个核相关项最小化。此外，[12]为多维情况获得了类似的结果。三权重核在相同的角度来看也是相对较好的；见表I，我们将核按一维情况下的渐近统计效率顺序（忽略有限数量的不可微点计算）从顶部排列。![]()
B. 收敛速率
在本小节中，我们研究MS算法的收敛速率。正如第III节末尾提到的，关于MS算法收敛速率的研究很少：在[13]和[14]中证明了使用Epanechnikov核的MS算法在有限次迭代中收敛，在[28]中证明了使用高斯核的MS算法在KDE在临界点的Hessian是非退化的情况下表现出线性收敛。我们在这里建立了一个更一般情况下的收敛速率评估，涵盖了更多的核，包括退化情况。暂时假设核是两次连续可微的（即，是类别的），除了假设1和2之外。考虑在临界点处对的泰勒展开，其中是在处的映射的雅可比矩阵。当足够接近时，有一个关系对于足够小的。这个关系表明，如果矩阵是实对称的，并且最远非零特征值的绝对值小于1，那么模态估计序列实现了线性收敛（即，对于足够大的）。简单计算揭示了在处的映射的雅可比矩阵由下式给出它是实对称的。应该指出，右边的分母等于，如果则是正的。由于假设2确保了是非负的，变成了正半定的。另一方面，从和，雅可比矩阵也可以计算为其中是单位矩阵。在局部最大值处变成负半定的事实，以及上面提到的雅可比矩阵的正半定性，意味着在局部最大值处的的特征值在区间内。以下命题，它是[28]中高斯核的一般化到通用核，允许KDE在处二次连续可微，展示了当Hessian 是非退化的情况下的线性收敛。命题 5（非退化情况下的线性收敛）：假设假设1和2，假设由MS算法(8)获得的模态估计序列收敛到，假设存在一个的邻域，其中KDE 是两次连续可微的（当核是类别时成立），并且假设在处的Hessian 是负定的。那么，模态估计序列实现了线性收敛：对于中最大的特征值和任何，存在，使得对于任何，有，其中。命题5告诉我们MS算法的典型收敛速率。此外，我们想指出，这个命题中的线性收敛保证也意味着指数速率收敛（尽管反之则不一定）：将关系递归应用，得到对于，这暗示了。另外，KDE 的二阶泰勒展开在临界点处表明，密度估计序列以指数速率收敛，如在上面的命题中，我们排除了Hessian 退化的情况。当Hessian退化时，雅可比矩阵具有最大特征值等于1，然后基于的一阶泰勒近似的分析不会导致MS算法的（线性）收敛。为了在这种情况下以同样的方式评估收敛速率，可能需要更详细地研究残差项的影响。基于Łojasiewicz属性的讨论使我们能够在对可微性更弱的假设下得出MS算法的收敛速率。具体来说，通过应用[20, 定理 3.5]，我们可以证明以下关于MS算法收敛速率的定理，涵盖了更一般的核，包括退化情况。它提供了由KDE的Łojasiewicz指数决定的收敛速率的上界。定理 3（收敛速率评估）：在定理1或2的同样假设下，进一步假设KDE 在处具有Łojasiewicz指数，对于由MS算法(8)获得的模态估计序列。那么，我们有
(b1) 如果，那么MS算法在有限次迭代中收敛（存在，使得对于任何，有，并且），
(b2) 如果，那么MS算法实现了指数速率收敛（存在，使得，并且），或者
(b3) 如果，那么MS算法实现了多项式速率收敛（，并且）。我们想指出的是，在定理3中出现的三种情况中，的情况可能只会例外地发生。例如，当是KDE的局部最小值时，处的Łojasiewicz指数变为0，意味着收敛到局部最小值应该在有限次迭代中发生。另一方面，通常不会在定理3的假设下发生：考虑KDE 在附近的行为类似于，。对两边进行微分，并且利用梯度的Lipschitz连续性（假设(a1)或假设3），我们得到，其中Lipschitz常数。这意味着，因此。因此，当模态估计序列收敛到一个模态点，如MS算法预期的那样，通常定理3(b2)或(b3)告诉我们收敛速率。值得注意的是，Epanechnikov核不满足假设3，如表I所示，因此定理3仅在满足定理1中的假设(a1)和(a2)的条件下，才适用于Epanechnikov核的MS算法。对于Epanechnikov核，KDE在模态点的Łojasiewicz指数通常是，如果应用定理3是合法的，它表明通过(b2)的指数速率收敛，这比[13]和[14]保证的有限时间收敛性要宽松。然而，收敛速率评估由定理3(b2)和(b3)在其他一般情况中似乎是几乎紧的，如图2所示，其中显示了用高斯核在一维情况下的MS算法的行为，精心选择了数据点的位置，使得KDE在其模态点有退化的Hessian。定理3，以及图2中的实验结果，强烈表明KDE的Łojasiewicz指数具有关于MS算法收敛速率的基本信息。然而，通常计算Łojasiewicz指数是困难的（见[48]中的讨论以获取详细信息）。即使在这种情况下，[49]、[50]、[51]为多项式函数提供了Łojasiewicz指数的界限。基于[50, 命题4.3]，我们可以为具有分段多项式核的KDE提供Łojasiewicz指数的上界。![]()
定理 4（Łojasiewicz指数界限）：假设核是类别的，并且是最大次数的分段多项式。那么，KDE 在任何临界点处的Łojasiewicz指数的上界为前提是对于任何，在任何与的邻域有非空交集的子域上都不是常数。这个Łojasiewicz指数的界限，连同定理3(b3)，给出了使用分段多项式核的MS算法的收敛速率的最坏情况界限。然而，应该注意的是，定理4中提供的界限通常不是紧的，并且可能通过未来的研究改进。最后，我们想对本节的讨论做几点评论：首先，出现在定理3和4中的Łojasiewicz指数是KDE的一个临界点（1）的指数，它不仅取决于核，还取决于数据点和带宽，因此我们关于收敛速率的结果不直接适用于如何选择MS算法中使用的核的问题。核的选择还应受到其他因素的影响，例如输出质量，如双权重核在基于KDE的非退化模态估计方面的渐近统计效率的最优性[11]、[12]、[21]。Ⅵ 结论和未来工作
我们已经展示了使用次分析核的MS算法生成的模态估计序列收敛到KDE的一个临界点（定理2）。我们的证明既不假设KDE有有限数量的临界点或它们是孤立的，也不假设其在收敛点的Hessian是非退化的，也不限制带宽的大小或数据的维度；它利用了KDE的Łojasiewicz属性。这个定理所涵盖的核的类别包括几个分段多项式核，例如在基于KDE的非退化模态估计方面在非负核中渐近统计效率最优的双权重核[12]、[21]。收敛分析结果扩展了现有的分析，涵盖了Epanechnikov核[13]、[14]和解析核[15]。此外，我们不仅为当KDE在收敛点的Hessian是非退化的情况下模态估计序列实现线性收敛提供了一个充分条件（命题5），而且还提供了一个最坏情况下的收敛速率评估（定理3和4），该评估取决于KDE的Łojasiewicz指数，甚至在Hessian退化时也适用。子空间约束MS算法[59]、[60]，另一个MS算法的变体，是估计主曲线和主曲面作为KDE的脊[61]、[62]的方法。它迭代一个更新规则，预计会收敛到KDE的一个脊上的点，而不是其临界点。该算法的收敛性质将与MS算法的收敛性质相关，但仍然是一个开放的问题，使用Łojasiewicz属性的分析可能对它有用。声明
本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。你是否有这样的苦恼：自己辛苦的论文工作，几乎没有任何的引用。为什么会这样？主要是自己的工作没有被更多的人了解。
计算机书童为各位推广自己的论文搭建一个平台，让更多的人了解自己的工作，同时促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 计算机书童 鼓励高校实验室或个人，在我们的平台上分享自己论文的介绍、解读等。
稿件基本要求：
• 文章确系个人论文的解读，未曾在公众号平台标记原创发表，
• 稿件建议以 markdown 格式撰写，文中配图要求图片清晰，无版权问题
投稿通道：
• 添加小编微信协商投稿事宜，备注：姓名-投稿
![]()
△长按添加 计算机书童 小编
