英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
图形嵌入和扩展：降维的统一框架
严水成，IEEE会员，徐东，张本禹，张红江，IEEE会员，杨强，IEEE高级会员，StephenLin
摘要：在过去的几十年中，一大类源于统计学或几何理论的算法，无论是监督的还是无监督的，都被设计成降维问题的解决方案。虽然这些算法的设计目的各不相同，但在本文中我们将这些算法统一在图形嵌入这一通用的框架中。在图形嵌入领域，每个算法可以被认为是描述特定本征图的直接嵌入或其线性、核方法、张量化，它们描述了数据集的某些期望的统计或几何属性，而来自比例归一化或惩罚图的约束则代表应该避免的统计或几何属性。此外，图形嵌入框架可以当做开发新降维算法的通用平台。利用这个统一框架，我们提出了一种新的监督降维算法，称为边界Fisher分析，在这个算法中本征图描述了类内紧致性，并将每个数据点与同类的相邻点连接起来，而惩罚图通过连接边际点描述了类间可分性。我们发现，由于数据分布假设和可用的投影方向的理论，MFA有效地克服了传统线性判别分析算法的局限性。人脸识别实验验证了MFA比LDA更具优越性，也显示了相应的核方法和张量化的联系。
索引术语 降维，流形学习，子空间学习，图形嵌入框架。
- 引言
计算机视觉和模式识别领域的科学家对于在有监督或无监督学习任务中的降维技术[1]非常重视。 其中，线性算法主成分分析（PCA）[11]，[14]，[22]和线性判别分析（LDA）[8]，[14]，[32]，[33] 因其相对简单和有效性成为两种最常用的算法。另一种在降维领域提出的理论是被称为局部保持投影（LPP）[10]的线性技术，它保留了数据集内的局部关系并揭示数据本质的流形结构。ISOMAP [20]，LLE [18]和Laplacian Eigenmap [3]是最近开发的三种对位于较低维上或附近的数据集进行非线性降维的算法。另外，核技巧[16]通过核映射函数在高维甚至无限维特征上执行线性运算，可以把线性降维算法扩展为非线性降维算法，从而获得广泛应用。最近，提出了很多对矩阵或任意顺序的张量进行降维的算法[25], [26], [27], [29], [30], [31]。
在本论文中，我们提出了两个相互关联又有创新性的降维方法。首先，我们提出图形嵌入的通用框架，以及它的线性化、核方法和张量化版本，就像前文提到的一样，这个框架实现了理解和解释许多流形的降维算法的统一。直接图嵌入的目的是用保持顶点对间相似性的低维向量表示图中的每个点，其中相似性是通过表达数据特定的统计或几何特征的图相似矩阵来测量的。这些表示顶点的向量可以从具有约束条件的图的拉普拉斯矩阵的主特征值所对应的特征向量中获取。虽然直接图嵌入仅提供训练集中图像顶点的映射，但其张量为原始特征空间中的所有样本提供了映射，例如新测试数据。图形嵌入的线性化理论用图顶点的原始特征向量表示每个顶点向量的线性投影，并且图形核嵌入使用线性图形嵌入核技巧算法处理非线性分布的数据。最后，在图形嵌入张量化过程中，用任意顺序的一般张量编码原始顶点，基于张量表示，多元线性代数方法被应用于扩展多元直接图嵌入。正如上文提到的算法，比如PCA, LDA, LPP,ISOMAP, LLE，拉普拉斯特征映射以及最近提出的基于张量的算法都可以在这个通用的框架里重新配置。在图形嵌入领域，不同的降维方法，现有的或新的，潜在的优缺点由内在的设计、惩罚图和数据嵌入类型揭示。
我们的第二个贡献是表明图形嵌入框架可以成为开发新的降维算法的通用平台。我们通过具体动机设计图形从而完成这项任务。我们尤其重视使用图形嵌入制作LDA变体。虽然LDA算法在很多应用中取得成功，但是我们意识到它使用范围有限，毕竟理论上要求可用的投影方向的数量要小于类的数量。此外，LDA中的类间差异取决于类间和类内散点图，所以只有当每一类的数据近似于高斯分布时才能取得最优结果，然而在实际应用中不可能总是满足这一条件。虽然有很多努力[32]，[33]，包括流行的零子空间算法[24]都致力于改善LDA，但理论上LDA的基本问题和局限性仍未解决。
使用图形嵌入框架作为平台，我们开发了具有创新性的新算法——边界Fisher分析（MFA），它可以克服LDA的局限性。在MFA中，本征图用来描述类内紧致性，惩罚图用来描述类间可分性。在本征图中，如果一个顶点是其他顶点的k1个同类近邻样本点，那么这两个顶点构成一个顶点对并有边连接。在惩罚图中，每一个顶点和k2个不同类的近邻点构成一个顶点对。基于图形嵌入框架，我们开发了MFA,MFA核方法和张量MFA，保留本征图的特征同时也限制惩罚图的特征。和LDA相比，MFA有以下优点：1）可用的投影方向比LDA大得多，2）没有任何数据分布假设，因此更适用于判别分析，3）在没有对数据分布进行预先假设的情况下，类间边界比LDA类间散度更有效地表示不同类别的差异。
本文的其他部分结构如下：我们在第二部分介绍统一图形嵌入公式以及一般降维的线性化、核方法和张量化。在第三部分，我们把图形嵌入框架作为通用平台，设计边界Fisher分析及其核方法和张量化。在第四部分，我们通过一系列的人脸识别和合成的数据实验来评估提出的方案。最后，我们在第五部分给出结束语并讨论发展前景。
2 图形嵌入：降维的一般框架
目前，已经有很多降维的方法。虽然现存算法的动机各不相同，但是它们的目标是一致的，即提取低维表示并促进后续的分类工作。那么是否可以在一个统一的框架里重新配置以及这个框架是否有助于设计新算法，这个问题就自然而然地产生了。在这一部分，我们给出了这些问题的肯定回答。我们提出图形嵌入线性化、核方法和张量化的创新理论，提供了理解现存算法和设计新算法之间关联性的共同视角。
2.1 图形嵌入
对于一般分类问题，模型训练样本可以用矩阵X表示，即X=[X1,X2,hellip;hellip;,XN],Xi，其中N是样本数量，m是特征维数。为了方便监督学习，假设样本Xi类别标签为,其中Nc是类别的数量。同时我们分别使用pi;c和nc表示第c类样本的索引和数目。
在实际情况中，特征维数m通常很高，因此将数据从原始高维空间映射到低维空间是减少维数灾难[8]必要且有益的方法。所以降维的本质是找到映射函数F：x，将转化成期待的低维表示。当在mgt;gt;mrsquo;时：
=F(x) (1)
函数F可以是显性或隐性，也可以是线性或非线性的。图1是不同类型数据，如矢量、矩阵和一般张量降维的直观说明，后文将会做详细的介绍。
图1.数据降维的不同形式
请注意，三阶张量数据是Gabor滤波图像
现在我们从图形嵌入的新视角介绍降维问题。设G={X,W}是顶点集X和相似矩阵W的无向加权图。实对称矩阵W的每一个元素度量了每一个顶点对的相似度，相似度可能为负值。可以通过不同的相似性准则构建相似度矩阵，例如参考文献[3]中的欧几里得距离的高斯相似度，参考文献[18]中的局部邻域关系，以及在参考文献[14]中的监督学习算法中的先验类信息。图G的对角矩阵D和拉普拉斯矩阵L被定义为
在这项工作中，图G的图形嵌入被定义为一种算法：在G的顶点中寻找期望的低维向量表示，它最有效地表示G中顶点对之间的相似性关系。方便起见，我们用一维例子来解释这个问题并用向量 y=表示顶点的低维表示，其中是的低维表示。我们定义本征图是本身的图G和惩罚图为，其顶点X和G相似，但其边缘权重矩阵和在降维特征空间中被抑制的相似性相关联。对于降维问题，我们需要一个本征图G和可选的惩罚图作为输入。图形保存的标准如下：
其中d是常数，B是为避免目标函数的平凡解而定义的约束矩阵。B通常是比例正则化的对角矩阵，也有可能是惩罚图的拉普拉斯矩阵。也就是说，B==-，其中是（2）中定义的对角矩阵。当是多维时，我们注意到类似的图形保存标准可以用比例正则化=d或者惩罚图=d的约束代替。
图形保存标准所保持的相似性有双重解释。当样本和相似性较大（正相似）时，为了使目标函数最小，和之间的距离应尽量小。类似地，当和相似性较小（负相似）时，和之间的距离应尽量大才能使目标函数最小。
图形保存标准为所有顶点提供直接图形嵌入。为了在整个特征空间进行数据点的映射，我们提出三种方案。
线性化。假设顶点的低维线性表示可以通过类似y=w线性投影获得，其中w是单位投影向量，那么（3）中的目标函数变为
注意，在线性化的情况下，低维表示的比例正则化可以转化成（4）中的投影方向。
一般而言，图形嵌入的线性化扩展在计算投影向量学习和最终的分类都是有效的，但是在处理非线性分布的数据时，性能可能会降低，下面我们将引入图形嵌入的核方法来处理非线性分布的数据。
核方法。将线性投影扩展到非线性领域时，可以直接使用核技巧[16]。核方法的技巧就是像Phi;：xF，将数据从原始输入空间映射到另一个更高维的希尔伯特空间，然后在新空间中执行线性算法。这种方法非常适合只计算数据对内积k（,）=Phi;() Phi;()的算法。假设映射方向w= Phi;(),K是=Phi;() Phi;()的核Gram矩阵，从（4）中我们有以下目标函数：
其中表示核Gram矩阵K的第i列向量。
通过求解广义特征值分解问题[6]，我们可以得到（3），（4），（5）的解。
其中，, XL或者KLK, ,B,K,XB,或者KBK.那么（3）中的问题有一个平凡解：所有元素都相同并且对应的拉普拉斯矩阵L的特征值为0.就像（3）中一样，我们通常省略它。
张量化。上文中提到的图形嵌入的线性化和核方法都考虑使用向量表示顶点。但是，从目标中提取的特征可能有更高维的结构。例如，图像是二维张量，即矩阵，用于事件分析的时序数据序列，如视频序列是三维张量。数据分析中为研究数据底层结构，大多数算法将输入数据转化成向量的做法是不合适的，这忽略了数据的高维结构，往往会导致维数灾难。因此，上述图形嵌入的线性化和核方法更有效的做法是将顶点用任意次序编码为一般张量形式，并进行降维。
在介绍图形嵌入张量化之前，我们先回顾张量操作的一些术语[23]。同维的向量A,B，且A，B则A,B的內积定义为
张量A的模是，张量A,B之间的距离是.在二阶张量的情况下，这个范数被称为Frobenius范数，记为.记矩阵U,张量A的k模积定义为B=A,其中,j=1,hellip;,.在本文中，大写粗体字母表示一般张量，大写斜体字母表示矩阵，小写斜体字母表示向量，纯文本小写字母表示标量。
我们用张量形式如{}表示训练样本集.和图形嵌入的线性化类似，我们假设顶点的低维表示是一个尺寸较小的张量，它是用投影矩阵在原始张量上投影得到的。一维情况可以表示为：
那么，目标函数（3）表示为
在上述公式中，如果矩阵B是通过比例正则化计算得到的，那么
如果B来源于惩罚图，即,那么
在很多情况下，目标函数（8）没有封闭解。然而对每个投影向量，如果（）已知，假如我们设，那么目标函数就和（4）的目标函数一样。因此，我们可以通过固定其他的投影向量的封闭形式获得解，而且通过迭代优化不同投影向量可以获得目标函数（8）的局部最优解。
与图形嵌入的线性化相比，每次张量迭代要考虑的特征维数要小很多，从而有效地避免了维数灾难，同时也显著地降低了计算成本。
2.2 降维的一般框架
在这一部分，我们将证明前文所提到的降维算法可以在提出的图形嵌入框架中重构。这些算法的区别在于计算图的相似矩阵以及约束矩阵的选择。图2说明了图形嵌入的框架，还列出了不同类型图形嵌入的示例算法。
图2. 图形嵌入及其线性化、核方法、张量化：降维的统一框架。第一行是图形嵌入类型，第二行是相应的目标函数，第三行是示例算法。
PCA[11],[12]是利用最大方差寻找投影方向的算法。也即是说，PCA算法找到并移除方差最小的投影方向，即
其中，e是N维向量，I是单位矩阵，C是协方差矩阵，是所有样本的均值。很明显，PCA遵循图形嵌入的线性化：本征图连接所有具有相同权重的数据对，并通过投影向量的比例正则化进行限制。图3即PCA算法的本征图。KPCA[16]在PCA的基础上使用核技巧，因此是基于核的图形嵌入方法。2DPCA[29]是简化的PCA二阶张量化，只优化了一个投影方向，参考文献[30]和[25]给出了PCA二阶张量化的完整形式。请注意，[10]中定性地指出，PCA可以通过连接如图3a所示的图与LPP相关联。然而，这没有完全正式地证明PCA是LPP框架的一个特例，因为PCA使用最大化标准，而LPP是基于最小化。在图形嵌入的情况下，本征图描述了需要被发现且丢弃的投影方向的特征，即PCA中的小方差方向。
图3 PCA和LDA的邻接图。 （a）PCA的约束图和本征图。（b）LDA的惩罚图和本征图。
LDA[14]通过最小化类内和类间散点图的比率来寻找最有效的辨别方向：
其中，第c类的均值，是N维向量，当c=时，，其他情况时为0.请注意，（12）的第一行，只有当d时，才能保证第二个等式相等。当d=0时，最小化/d对w是有效的，并通过最小化得到最优解，这种情况下仍然相等。
我们可以观察到LDA遵循图形嵌入的线性化，在这个过程中本征图连接具有同类标签的所有对，而权重与对应的样本大小成反比。PCA的本征图被用作LDA的惩罚图。请注意，虽然参考文献[10]讨论了LDA和LPP中B=D的关系，但是这并不意味着LDA是LPP算法的特例。相反，利用（4）中的图形嵌入公式和惩罚图的约束，LDA可以很自然的在图形嵌入框架中重构。图3b展示了LDA的这两种图。核判别分析（KDA）[9]算法是LDA的核
全文共11299字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12451]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
