高斯均值漂移是期望最大化的算法外文翻译资料

 2022-10-26 10:16:42

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 29, NO. 5, MAY 2007 767

高斯均值漂移是期望最大化的算法

Miguel A. Carreira-Perpintilde;aacute; n, Member, IEEE

摘要——基于Fukunaga的思想和Hostetler [16]提出的均值漂移算法，是一个用于研究被有限混合或核密度估计而定义的数据密度的爬山算法。均值漂移可以作为一种非参数聚类方法。并且，在近些年来的计算机视觉应用如图像分割或跟踪中，均值漂移得到了一定的关注。我们能够表明：当内核为高斯核时，均值漂移是一种期望最大化的算法，当内核是非高斯时，均值漂移则是广义的期望最大化算法。这意味着均值漂移几乎从任何起点收敛，并且在一般情况下，其收敛性遵从线性秩序。通过高斯均值漂移，我们发现：1）在极窄核或极宽核中，线性收敛率十分接近0（超线性收敛）。但在核大约为中间宽度时它往往接近1并且在归并模式下精确到1（亚线性收敛）。2）迭代接近的模式是沿着数据点的凸包内部的数据的局部主成分的。3）收敛域是非凸的并且在断开时表现出不规则行为。我们因此预测出一种基于期望最大化演绎的加速均值漂移方法。

索引：均值漂移算法，高斯混合，核密度估计，期望最大化算法，聚合类

  1. 模式的发现和均值漂移算法

从机器学习的角度讲，p(x)的密度模式十分重要。作为聚类[10][11][16]的一个例子，密度可以表现出在给定问题上数据的分布，从而使这样的密度模式作为聚类集群的代表。作为多值回归的一个例子，p(y|z)的条件分布模式，其中x=(y,z)，可以用来表示一个z到y的多值映射。设计一个算法来找到这种密度模式是必须的。原则上来说，只要使用多起点来尽可能地找到更多的不同模式，任何最大化的算法都可以应用于此，但是，对于一个广泛的类的密度，这是有限的混合——包括核密度估计和高斯混合——一种能派生出一个特别简单的定点算法，均值漂移（描述见下）。均值飘移算法已经被证实在图像分割技术上十分成功[11]。在这里，首先，对图像的像素建立核密度估计，声明它们各自的模式作为一个聚合类的代表。然后，将一个给定的像素，在均值漂移算法的基础上，绑定到它对应的收敛模式下。该方法是确定的（因为均值收敛没有步长）和无参的（由于核密度估计）。关于聚类的形状它没有表现出任何先验假设。在此论文中，我们的主要目标是表明并研究均值漂移算法是广为人知的一类算法的中的一个特例，即期望最大化算法，并研究其收敛率和收敛域方面的问题。

均值漂移算法的派生如下：给定M D-维度的数据点，借助核函数K(t),当tgt;0时，确定一个核密度估计[28]。

当作为点m的权重或混合比率（满足,是正定矩阵的协方差。Zm是一个只取决于的归一化常数。其中是马氏距离，如下例：

为了找出p(x)的模式，我们可以寻找固定点

其中Krsquo;=dK/dt,解出x得定点迭代方案，当

利用同方差估算，可以简化为

在实践中，对于有固定权重和各项同性协方差的同方差估算公式，可以更加简明的表示为：

这样的定点迭代方案被称为均值漂移算法。当矢量f(x)——x是均值漂移。不同于其他优化算法，均值漂移不使用步长参数并且有效地定义了一个从IRD到固定点的映射。通过对每个数据点运用均值漂移算法，我们能探究其收敛模式,，然后将点聚合收敛到同一模式下。聚合类的数量也会因此被算出，即。

当核为高斯形式时，，我们能得到一个简单而优美的算法：

对于各向同性核，这个公式简化为：

当q(m|x)被p(m|x)的值因逆方差和重整化被加权后，对于同方差各向同性核，公式可以简化为：

其中新的点是当前点条件均值下的混合。需注意的是，对于非高斯核，p(m|x)涉及到Krsquo;，通过f(x)可求得Krsquo;。

均值漂移算法是如此的简单以至于它可能已经被发现过数次。在1975年，Fukunaga和Hostetler[16]有可能是第一次提出并介绍“均值漂移”的人。从1981年起，这个算法在统计学中被独立地提出并被称为“均值漂移算法”（见[29,p.167ff]和参考文献）。Fukunaga和Hostetler在不证实收敛性的情况下，通过研究可变步长下的logp(x)的梯度上升，二人为Epanechnikov核得出这种算法（为了方便计算和，并且Epanechnikov核提供有限支持）。他们当时所得的版本是不同于我们现在得到的版本的：他们建议直至收敛前，每个数据点在每次迭代时，基于均值漂移公式，都应该移动。这个版本被Cheng[10]称为“模糊化进程”。正是这位Cheng研究了这个版本的均值漂移算法并且建议舍弃数据点的移动过程（如现在讨论的版本）。

而后，Carreira-Perpintilde; aacute;n[3]，被寻找高斯混合模式这个问题所驱使，又独立地重新研究了一种用于高斯核的算法并证明了其在任意协方差矩阵上的收敛性[5]。Comaniciu and Meer[11]给出了一种不同的对于普通各向同性核的收敛性证明，囊括了高斯核和Epanechnikov核（后者在有限次数下的迭代取决于其自身的有限次的支持）。他们将均值漂移算法用于图像过滤和分隔，因此掀起了一阵关于机器视觉应用算法的热情，如追踪（e.g.,[12][13][30]）。Fashing和Tomasi[15]将针对于各向同性同方差的核与均值漂移算法相关联以优化，并且证明当Krsquo;为分段常数时，这个算法和Newton方法是重合的。类似的均值漂移算法曾用于尺度空间聚类[9],[25],[32],[33],聚类的确定性锻炼和基于内核方法的原象查找。

本文的贡献如下：首先，我们表明了高斯均值漂移(5)算法是期望最大化(EM)算法并且非高斯均值飘移(2)是广义的期望最大化算法(第三小节)。这意味着，在两种情况下，每个起始点都被确定具有收敛性。过去，收敛性证明[11],[15]是不基于与期望最大化的连接、并且要严格遵守同方差各向同性情况（公式在此）。我们的证明把握了原有基础，即每个组件都拥有自身的所有协方差的情况。期望最大化算法同样引起了高斯均值漂移迭代中两个分离步骤的注意：事后几率的计算(E step)和数据的加权均值(M step)。然后，我们着眼于高斯均值漂移算法在各向同性核上的应用。在第四小节，我们通过核宽度函数描述了收敛性速度并且证明：1）收敛性是线性的，并且如同期望最大化算法一样，可以变得十分缓慢。2）收敛性在非常宽或非常窄的核中会变得超线性，在合并模式中会变为亚线性。3）迭代接近的模式是沿着数据点的凸包内部的数据的局部主成分的。在第五小节，我们展示出收敛域是广义非凸的，并且能被断开且具有显著的分形性。我们通过对基于其视图的均值漂移算法作为一个期望最大化算法的加速得出结论。

  1. 高斯均值漂移作为期望最大化算法

在此我们表明，高斯均值漂移算法可以派生为期望最大化算法[14][18]。这个证明的想法是由出现在参考文献[5][8]的作者——爱丁堡大学的Chris Williams提出的。这个想法包括定义一个极大似然问题当1）由原核密度估计给出的高斯混合模型（因此，核心已由被高斯均值漂移应用过的数据集给出）但这个混合可以被刚性移动（因此该模型有单一参数，即位移矢量v）2）该样例适用于包含一个单一点x=0的模型。然后我们就能证明对位移矢量的任何极大似然估计是原核密度估计的一个模式并且说明期望最大化算法和高斯均值漂移算法的一致性。

假定是一个满足(1)(5)的高斯均值漂移问题的高斯混合参数。当为定值且参数v=(V1,hellip;,VD)T,考虑如下对关于

的模型：

即当m具有固定混合比例m时，x|v是一个D-维度的高斯混合，均值矢量(是定值)，且协方差矩阵为定值。动值v导致了整个混合整体的刚性转化而不是内部各个独立成分的分别变化。现在，考虑拟合由数据集产生的极大似然模型并且派生出一个期望最大化算法来估计变量v。数据集在这个阶段是任意的，然后我们从原点将它特例化到一个点上。需要注意的是此时的数据已经不同于在均值漂移问题中收集到的核心数据。令zn{1,hellip;M}（未知）为混合成分指数，由此生成数据点xn,然后：

E step：

整体数据对数似然，好像为已知，假定数据为

并且它的当前后验分布的加权期望如下：

其中，并且C与v相互独立。

M step：

新的参数估计出是从旧参数通过获得的。为了验证其是最大的，我们使Q梯度加权变化，范围为v到0。

作为一个关于v的方程，是的高斯均值密度以及协方差，由此得到：

解方程(10)得到：

如果我们现在选择只含有原点的数据集（如N=1且x1=0），令m=z1、，我们可以得到改写后的M step：

这与方案(5)的迭代形式完全相同。

其中对数似然为：

总之，当试图以样例的原点适配时，高斯均值漂移迭代方案(5)相当于期望最大化算法的高斯混合模型(8)。高斯混合下的期望最大化算法的广义特性告诉我们，几乎所有的从起点开始的收敛都是线性的[14][18][24][34]，具体而言，在每一次迭代中，迭代方案(11)要么增加其对数似然程度，要么不改变。相应地，迭代方案(5)仅会单调地增加p(x)的密度值或者不改变。我们能直接指出（广义期望最大化算法的派生形式，在此我们使用p而不是q仅做阐明，不代表）：

在此我们使用了1）Bayes定理2）Jensen不等式 3）可使最大化的事实。而且，运用Jensen不等式，当时，对数似然度的增加是严格正向的。

原则上来说，收敛可以发生在一个鞍点或者一个最小值而不是一个模式（通常在非常不可能的情况下，初始值是非常小的，方案会始终停留在这里）由于鞍点和最小值对于最大化来说都不稳定，一个小小的随机扰动都会造成期望最大化算法的偏离。因此，实际收敛性几乎总是一个模式。

这里有一个很有趣的关于Fashing和Tomasi[15]的研究结果，他们考虑了均值漂移的各向同性同方差情况，这显示出均值漂移的迭代过程最大限度地提高了在上的二次低结合。对于高斯核来说，它们的二次低结合由(15)[15]给定，如下：

当恒有agt;0时，这个结合验证了和。

期望最大化算法也使用了二次低结合但是它使用了而不是。

定义如下：

当恒有a1gt;0时，从(12)我们可以得到和。虽然这两类结合不同，但它们都是二次的且最大化时都为。对于非高斯核，[15]中的结合仍然是二次的，尽管这时方程Q已经不再是二次的了（见下节）。

也可以将高斯均值漂移算法（在同方差各向同性的情况下）视为一个有连续变量和连续曲线的动力系统，并且证明其收敛（见附录A）。

  1. 非高斯均值漂移作为一种广义期望最大化算法

对于任意的核K(t)，当t大于或等于0时，我们定义

类似于(8)。这个期望最大化算法的派生延续了(10)中的高斯式。但现在

考虑之前的情况，N=1且x1=0，用p()代替q()，重命名变量之后，我们得到了如下公式：

此处我们通过Bayes定理使用了表达式

在高斯核情况下，，并且我们能够通过解出v的方法重写(11),但在非高斯核情况下，我们不能解出具体的v值。此时我们有两个选择：

1）精确的M step方法：我们可以为采用如下的定点迭代方案

此时

因此最终的期望最大化算法含有两个嵌套循环。其中外部循环是关于的普通迭代，内部循环是关于和定值的迭代。其中内部循环会一直运行直到大概呈现出收敛性。

2）不精确的E step方法：使内部循环只循环数次，在呈现出收敛性之前就停止。这就是广义的期望最大化算法（GEM）。在广义期望最大化算法中，在M step我们简单地使u增加Q而不是最大化它。从(12)可以明显看出，只要v的迭代每次增加Q，其收敛性在期望最大化算法[14][18]中就能得到保证。

如果在(14)中我们选择初始化u0=，且只做单一的一步，我们可以得到表达式，这与均值漂移迭代(2)是重合的。

因此，对于非高斯核的原生均值漂移算法是一种广义的期望最大化算法。

令内层循环的，运行内层循环直至内存循环收敛至，我们可以定义一个广义期望最大化算法版本。这满足了两种极限情况下的连续化：

和我们由此获得了精确的M step。同时，当I=1时，我们可以得到均值漂移算法。我们用这个做过实验并且已经发现，通过一系列的和I的值的变化，均值漂移在整体上边的更快。这意味着我们可以通过仅完成少量内层循环迭代来减少外层循环迭代的次数，但是内存循环迭代的总数仍很高。由于内层循环迭代对机器的消耗量更高一点，均值漂移算法总是表现的更快一些。表一是一个具有代表性的例子。

表一<!--

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153939]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章