半监督判别分析

半监督判别分析摘要线性判别分析（LDA ）已经成为特征提取的常用方法，此方法可保存类可分性。通常投 影向量通过最大化类间协方差，同时最大限度地减少类内协方差的方式获得的。在实践中， 当没有足够的训练样本，每个类的协方差矩阵的估计可能不准确。在本文中，我们提出了一 种新的方法，称为半监督判别分析（SDA）,这种方法既使用的标记样本有使用未标记的样 本。标记的数据点是用来最大化不同类别之间的可分性，而未标记的数据点用来估计数据的 内在的几何结构。具体来说,我们的目标是学习的一个判别函数，使其尽可能平稳地表示数 据流形。单训练图像的人脸识别和相关反馈图像检索的实验结果可以证明我们算法的有效性。1. 介绍 在许多可视化分析应用中，如图像检索、人脸识别等，它们都会遭遇高维数据的问题。然而， 有理由怀疑，自然产生的高维数据可能驻留在一个低维流形。这导致我们去考虑降维方法， 这种方法允许高维数据代表一个较低维空间中的数据。要达到此目的，有两个最流行的方法， 分别是是主成分分析（PCA）和线性判别分析（LDA）。主成分分析法是一种无监督的方法。 该方法是通过将原来的 N 维数据投影到高维的线性子空间的方式来实现降维，而线性子空 间通过数据的协方差矩阵的主要特征向量来跨越。它的目标是找到一组相互正交的基函数， 用于捕获数据中最大方差的方向，因此，成对的欧氏距离可以最好地保存。如果数据被嵌入 在一个线性子空间，主成分分析可以保证挖掘出子空间的维数，并产生一个简洁的表示。 LDA是一种有监督的方法。它搜索项目轴，在该轴上，不同类别的数据点相距很远，同时要 求同一类的数据点彼此接近。当标签信息可获得时，例如，用于分类任务,LDA可以实现的 性能优于PCA。然而，当相对于维度数量没有足够的训练样本的时，每个类的协方差矩阵的 估计可能不准确。在这种情况下，测试样品的泛化能力不能得到保证。一个可行的解决方案 可以应对培训（标记）样本不足的情况，该方法既学习标记得数据又未标记的数据（半监督 和直推式学习）。这种方法既时自然的也是合理的，因为在现实中，我们通常只有一部分的 输入数据被标记，以及大量的未标记的数据。在过去的几十年中，半监督学习（或直推式学习）吸引了越来越多的关注。两个众所周知的 算法分别是直推式支持向量机（TSVM）和协同训练。最近，基于半监督学习算法的图像分 析有相当大的兴趣和成功，这种方法考虑将所有的样本的图形作为前提来指导决策。所有这 些算法考虑的都是分类问题，要么直推法，要么归纳法。在本文中，我们的目标是在半监督的情况下的降维。我们提出了一种半监督降维算法，称为 半监督判别分析（SDA）。SDA的目的是找到一个投影，这个投影代表从标记的数据点中推断 出的判别结构，以及代表从标记和未标记的数据点中推断出的固有的几何结构。具体而言， 这些结合未标记的数据点标记的数据点，被用于建立一个包含数据集邻域信息的图。该图提 供了一个相对于数据流形局部几何的离散的近似值。利用拉普拉斯图的概念，图上的一个平 滑可以纳入目标函数。这样，我们的SDA算法可以优化保留流形结构。本文的其余部分组织如下。在第2节中，我们提供LDA简要回顾。在第三部分中，我们介 绍我们的半监督判别分析（SDA）的降维算法。在第4节，称述实验结果。最后在第5节， 我们总结本文，并为今后的工作提供建议。2. LDA的图视角线性判别分析（LDA）寻求某种方向，再次方向上的不同类别的数据点相距很远，同时要求 同一类的数据点彼此接近。假设我们有一组L样本X X X Rn，属于C类。LDA的目标1, 2, l函数如下：aT S aa 二 arg maxb-opt a aT S aW ，( 1 )，（2）S =才 l C(k)_卩人)一 J bkk=1=1l 任 C)-4)X (k)-4)iik=1 J i=1丿,(3)卩l卩）x（）ki其中， 是总样本的均值向量， 是k类样本数，是第k个类的平均向量，是SS在第k个类的第i个样本。我们称w为类内散布矩阵，称b为类间散布矩阵。S =2 1 （X -卩）（-卩S = S + S确定的总散射矩阵 ti=1 i i,我们有 t w b ，那么公式（1）中 的线性判别分析的目标函数就等于，（ 4 ）aT S a a = arg max i opt aaT S at最佳的a是与本征问题的非零特征值对应的特征向量:S a 二九S abt，（ 5 ）Sb由于 的阶是由CT限制，所以最多的有CT个非零特征值对应的特征向量。卩=01无一般性损失，我们假设 。我们有bkk=1=211 丄 ILx (k) k( i i k=1 k i=1k=1让数据矩阵X = L G,., X （）并且定义一个1 x 1的矩阵J为其中，W财是一个ikxt的矩阵，他的所有元素都等于!ik，同时XX詁, 表示k类的数据矩阵。_W (1)0.0 w=lxl0w (2 ).0( 6)_ 00.W(c)_我们有s = xawa)Q= xw xt(7)blxlk=1因此，在方程式( 4)中线性判别分析的目标函数可以改写为aTS aaT xw xTaa = arg max i = arg max 阳(8)opt aaTS aaaT xxTatLDA 目标函数的公式将对发展我们的算法是非常有帮助的。他第一次被介绍在143. 半监督判别分析LDA 考虑者正寻求完全基于训练集的最优预测。在现实中，获得一个大规模未标记的数据集 是有可能的。在这部分中，我们试图扩展LDA模型去涵盖由未标记的数据表示的流形结构。3.1.目标函数LDA的目的是找到一个投影向量a，以至于aTSa和aTSa之间的比例最大化。当没有足够bt的训练样本时，过拟合将发生。一个防止过拟合的E典型方法来是加强规范化。LDA的规范 化版本的优化问题可以写成如下：maxaaT S aaTS +a J (a )t9)其中，J (a)控制假设群的学习复杂度，而系数a控制模型复杂度与实验误差之间的平衡。一个最流行的正则化是Tiknonov正则化21 J (a )= |2带有Tikhonov正则化的LDA模型通常被称为正则化判别分析(RDA) 8 。正则化项J (a)为我们提供了一定的灵活性，帮助我们吸收特定应用的先验知识。当可获得一组未标记样本时，我们的目标是建立一个结合的流形结构的J C)。半监督学习算法的关键是一致性的先验假设。对于分类，它意味着附近的点有可能有相同的标签 26 。对于降 维，它可以解释为附近的点将有类似的嵌入(低维表示)。给出一组例子 h，我们可以i i =1用一个p最邻近的图G模拟附近的数据点之间的关系。具体来说，如果xi和xj是“关闭” 我们在节点 i 和 j 之间设置一个界限，换言之， xi 和 xj 是近邻之间的相互。让相应的权重矩阵为S,定义为1, ifx e N (x Irx e N (x )S = 0,矩阵X_ +al Xt + pI肯定是非奇异。我们也可以使用光谱谱回归技术来 k I丿 丿解决这个奇异性问题，请参阅 5 。3.3 核心半监督判别分析算法 上面描述的算法是一个线性方法。当数据流形具有高度非线性时，它可能无法发现内在的几 何结构。在这一部分，我们将讨论如何用（RKHS）执行SDA算法，该算法对SDA有很大的 提升。这里所使用的方法基本上 与 13 相似。我们认为，功能空间F中的问题是由一些非线性映射引起。选择合适的内积0，它可以在F上定义，F创造一个所谓的再生核希尔伯特空间（RKHS更 具体地说:），0（y=K（x, y）其中，k（,）是正半确定核函数。几种常用的核函数有：高斯核函数(x,y )= exp-llx-y|x，s 型核函数x,K(x，y给定一个向量集(e f|i = 1,2,.,di此向量是正交的0(x )e f 对i【，vd的投影可以由下式推倒从Rn到欧氏空间的映射yiiv ,v我们找到如此的矩阵（e f|i = 1,2,d 以帮助矩阵i,m）保持数据流的局部几何结构和判别结构。