两级邻域采样的孪生网络在流形学习中的应用

徐承志，万 方

湖北工业大学 计算机学院，武汉430068

随着多媒体技术的发展和大数据技术的兴起，数据维度呈爆炸性增长，使得机器学习、图像处理、模式识别等研究领域的数据分析变得越来越困难。为消除上述问题中的维度灾难，降维操作成为数据预处理中的重要手段。流形学习（Manifold Learning）是一类特殊的降维问题[1]，自2000 年Science中被首次提出以来，已成为信息科学领域的研究热点[2-3]。流形学习的观点认为：从局部看，数据具有欧氏空间的性质；从全局看，数据是嵌入在一个更高纬度的流形体上。流形学习要消除冗余的纬度，用较低纬度来表示数据（降维操作）。降维的依据是，局部欧氏空间的性质在低维空间中得以保留。保留欧氏空间性质的一个主要方式就是保持数据间的欧氏距离不变，或者说保持数据间的相对位置不变。

鉴于流形结构的高维嵌入特性，传统的线性降维方法，如PCA算法[4]、LDA算法[5]等，并不适合流形学习，而一些基于局部线性假设的非线性数值解法则能很好处理这类特殊的降维问题，如基于重建邻域线性关系的LLE算法[6]、基于测地距离的Isomap算法[7]、基于重建邻接图的LE算法[8]、基于切空间的LTSA算法[9]，以及它们的众多改进算法[10]。这些算法的理论基础都是基于矩阵数值分析与优化的，但随着深度学习在人工智能领域的兴起，利用神经网络实现降维也成为一种有潜力的研究方向。目前，具有降维效果的神经网络有，用于聚类和分类问题的自组织映射网络SOM[11]，用于词嵌入的跳字模型Skip-gram 和连续词袋模型CBOW[12]，用于特征提取的有损压缩网络自编码器Autoencoder[13]，以及基于共享权值的孪生网络[14]（Siamese Network）。上述神经网络通过不同的方式实现了传统领域内的降维需求，并取得了不错的效果。但是因为流形结构的特殊非线性，鲜有神经网络直接应用于流形学习，本文尝试将孪生神经网络与流形学习相结合，希望为流形学习提供一种新的解决方案。

1 孪生网络

传统的基于逻辑回归的分类网络，适用于存在大量标注样本的情况，但在某些情况下，比如类别数量过多或类别数量不定，且每个类别的样本数量又相对较少时，传统分类网络就不那么有效了，比如判定两幅图片是否属于同一类物品，或两张人脸是否属于同一个人等。为了解决上述问题，Lecun 等人[15]提出了孪生网络模型，用于计算样本间的差异度。孪生网络将数据从样本空间映射到目标空间，同类数据在目标空间中的差异度较小，反之差异度较大。通过计算数据间的差异度，孪生网络可以判断数据是否属于同一类别。一般情况下，孪生网络的输出维度（目标空间维度）要小于输入维度（样本空间维度），所以从这种角度看，孪生网络实现了数据降维。如图1所示，典型的孪生网络包含两条通道，并且两条通道的网络结构相同、权值相同，故称为孪生网络。

图1 孪生网络

图1 中的两个子网Network_1 和Network_2 即为两条通道，它们共享权值，即是两个完全相同的子网。两条通道各自接收样本空间中的一对数据X1和X2，并分别映射为目标空间的GW(X1)和GW(X2)。网络输出的能量值EW(X1,X2) 是一个非负数，等于||GW(X1)-GW(X2)||，相当于两个数据在目标空间中的差异度。孪生网络的另一个输入Y代表X1与X2这对数据的标签，如果两个数据属于同类，则Y为0，并希望EW尽量小，否则Y为1，并希望EW尽量大，当两个数据完全相同时，EW自然为最小值0。为了让同类型数据的差异度小，异类型数据的差异度大，孪生网络的损失函数Loss定义如公式（1）和（2）所示：

其中，n是训练的样本总数，(X1i,X2i,Yi)是第i个数据对，LG负责计算同类样本的损失函数，LI负责计算异类样本的损失函数。为了达到同类样本的差异度小，异类样本的差异度大的效果，需要将LG设计成单调递增函数，LI设计成单调递减函数。

孪生网络的通道结构可以根据问题的需要进行不同设计，比如针对回归问题可以选择多层感知机（MLP）[16]、针对图像问题可以选择卷积神经网络（CNN）[17]、针对时序问题又可以选择循环神经网络（RNN）[18]等。同时，差异度的计算方法也可以灵活选择，比如余弦相似度、曼哈顿距离、欧氏距离、汉明距离等。最后，损失函数也可以自由设计，只要保证优化方向符合预期目标就行，比如Lecun[15]就将LG定义为EW的二次项函数（递增函数），把LI定义为EW的负指数幂函数（递减函数）。

2 孪生网络与流形学习

孪生网络可以实现从样本空间到目标空间的降维，但是孪生网络是有监督学习，需要样本标签来引导网络训练，而传统的流形学习是无监督学习，为了将孪生网络应用于流形学习，需要调整网络的使用方法。

2.1 损失函数与子网设计

如众多传统算法认为的，从局部看，流形是线性嵌入在高维空间中的低维结构，通过找出所有局部映射关系，并附加人为约束，最后整体优化，即可实现流形降维，如LLE 算法设定邻域样本的线性组合为当前样本，并以∑Wij=1 为约束进行整合[6]；LE 算法在降维过程中保持邻域内的邻接图关系，并以YTDY=I为约束进行整合[8]；LTSA 是对局部空间进行PCA 映射，并以TTT=I为约束进行整合[9]；而LMDS 则是对局部空间进行MDS 映射，并以YYT=I为约束进行整合[19]。理论上神经网络具有任意复杂的模式分类能力和优良的多维函数映射能力，如果神经网络能够蕴含足够多的局部映射关系，并且实现不同的输入样本激活不同的映射关系，就可以将神经网络引入流形学习。

为了将孪生网络引入流形学习，需要重新设计孪生网络的损失函数。将样本间的空间关系用欧氏距离来表示，并希望映射到低维空间后，样本间尽量保持原空间里的欧氏距离。假设样本所在的原始空间是R，降维后的子空间是P，采用图1 中的孪生网络结构，则样本在原始空间内的欧氏距离表示为dR=||X1-X2||，在子空间内的欧氏距离表示为dP=||GW(X1)-GW(X2)||。网络训练的目标是希望dR与dP的差值尽量小，即降维后空间关系尽量保持，则可以设计网络的损失函数Loss1，如公式（3）～（5）所示：

上述网络训练思路与多维缩放算法（MDS）非常相似[20]，不同的是，MDS 要保证所有数据点在低维空间中的距离等于在高维空间中的距离，而流形学习只需要保证邻域内的样本在低维空间内的距离保持不变。因此在构建训练集时，只需要选择邻域内数据来构建训练样本。确定邻域的方法有两种，第一种是k邻近法[21]，即选择距离当前样本最近的k个样本作为邻域，第二种是ε邻域法[22]，即选择与当前样本的欧氏距离在ε以内的样本作为邻域。传统流形学习算法通常选择第一种方法来创建邻域，因为第一种方法能够产生固定数目的邻域样本，非常适合进行矩阵运算与分析。本文则采用第二种方法，训练集对邻域内样本数目没有限制。确定邻域产生方法后，每个数据与其邻域数据形成一组样本对，汇总所有数据的样本对，并去掉重复后，就形成了孪生网络的训练集。

后续工作是确定孪生网络中的通道结构，即子网结构。孪生网络输入的是高维样本，输出的是低维数据，仅从某侧通道来看，它是一个解决多元多值回归问题的模型，对于简单应用可以直接选择多层感知机（MLP）作为子网结构，如图2所示。

图2 孪生网络的子网结构

由于流形学习是非线性降维，可将子网分为前、中、后三个部分。最前端是包含线性激活函数的升维层（increase dimension layer），中间部分是包含非线性激活函数relu 的过滤层（filter layer），后端是包含线性激活函数的降维层（reduce dimension layer）。升维层目的是为了让样本的特性尽量充分地表达出来，使得训练效果更好。这个过程类似支持向量机（SVM）[23]利用核函数将输入数据映射到高维特征空间的效果。如果输入样本的纬度本来就很高，可以考虑省略这一层。过滤层选择激活函数relu 的原因是，relu 能有效克服梯度消失问题，并且计算速度和收敛速度都很快。更重要的是，relu是单向饱和（负向饱和），当激励小于0时输出为0，当激励大于0 时输出则线性增强。单向饱和的直接效果就是，过滤层会产生大量饱和值为0 的“死结点”，而剩余的“活结点”才能与后续的降维层构成有效输出。整个过程等效于过滤层中的“活结点”与后端降维层一同构成了局部线性映射关系。孪生网络的具体算法如图3所示。

当孪生网络训练到一定的程度后，可任选两条通道中的一条，用作降维映射。图4呈现了孪生网络对于不同曲率的流形结构的降维效果。由于原始空间只有三维，所以子网结构包含1 层线性升维层（100 个结点），2层非线性过滤层（各100个结点）和1层线性降维层（2个结点）。

当流形结构的曲率不大时，如图4（a）所示，孪生网络的降维效果是良好的。但当曲率增加时，如图4（b）所示，会出现子空间内重叠的现象。造成这一问题的原因是，设计损失函数时，只考虑了保持邻近样本间的距离，而没有考虑远离样本间的空间关系，当样本在子空间内重叠时，没有对损失函数产生明显的负面影响。为了让孪生网络具有更好的适应性，必须对损失函数做出改进。

图3 孪生网络算法流程图

图4 不同曲率下的流形学习

2.2 两级邻域的损失函数

要避免降维数据在子空间内重叠，除了确保邻域样本在子空间里依然保持距离，还要确保非邻域样本在子空间里也要互相远离。为了在损失函数中体现样本的远离效果，本研究提出了两级邻域的概念，一级邻域的距离是ε1，二级邻域的距离是ε2(0 ＜ε1＜ε2)，如图5 所示。为此，需要重新引入样本标签Y，样本输入也还原为传统孪生网络的输入形式(X1,X2,Y)。如果X1与X2距离小于等于ε1，Y取值为0，为正样本；如果X1与X2的距离大于ε1且小于等于ε2，Y取值为1，为负样本。正样本要保持欧氏距离不变，而负样本要保证欧氏距离大于ε1。从流形结构的特点来看，当样本远离到一定的程度后，比如超过ε2时，样本间的欧氏距离变得没有意义，所以设置ε2值的时候没有必要太大，可以综合考虑样本间的平均距离和最大距离来设定ε1和ε2。

图5 两级邻域内的正、负样本

为了体现正、负样本各自产生的效果，重新设计损失函数Loss2，如公式（6）所示：

2.3 对比实验

下面将改进后的孪生网络应用到经典的仿真数据（Swiss roll）的降维中。由于Swiss roll 的原始空间仅仅是三维，为了充分表达样本蕴含的信息，即降低网络训练难度，孪生子网的前端设计了150 个结点的升维层，将3 维输入映射到150 维空间中。子网的中部是三层各包含了150 个结点的过滤层，最后是包含2 个结点的降维层。Swiss roll采样了800个数据，数据间的平均欧氏距离为0.68。实验设置一级邻域的ε1设为3.0，二级邻域的ε2设为6.0，Loss2中的λ设为100。训练集中正样本（距离小于等于ε1的数据对）有6 488对，负样本（距离介于ε1和ε2之间的数据对）有17 123 对，网络的学习率为0.001。经过150 个周期（epoch）的训练，孪生网络的学习效果与其他传统的流形学习方法进行对比，如图7所示。

图7（a）为Swiss roll 在原始三维空间中形状，图7（b）～（e）分别是采用LLE、Hessian、LTSA 和Isomap 方法降维后的效果，图7（f）是孪生网的降维效果。通过降维后的比例尺可以看出，Isomap 和孪生网络在降维时，有效保留了流形结构在高维空间内的真实跨度（比例），而其他传统方法则是附带人为约束的优化问题（见2.1节），这种约束造成了各维度间的不成比例的压缩，如图7（b）～（d）所示，LLE、Hessian 和LTSA 方法将Swiss roll压缩在一个长宽大约都为0.2 的矩形区域内。需要注意，各维度不成比例的压缩，将造成样本在子空间内各维度上的疏密程度不能真实反应高维流形的局部空间关系，最终导致低维数据整体的变形与失真。虽然Isomap 方法在全局尺度上可以较好地保持数据在空间中的跨度，但是因为采用近似测地距离作为计算的依据，所以在局部结构上会存在变形，特别是当数据分布不均或存在采样空洞的情况下，变形将更为明显。与Isomap不同，孪生网络是将高维空间中的欧氏距离尽可能地映射到低维空间中，所以对数据分布或采样空洞不敏感，使得Swiss roll的流形结构在降维后的空间中得以真实地保留。

图6 改进后的孪生网络算法流程图

图7 Swiss roll降维效果对比

3 可视化手写数据集

流形学习主要用于流形结构的降维、特征提取或可视化等目的，本章将孪生网络用于实际数据的可视化处理中。文献[24]分析了字符的旋转和缩放数据集，证明字符是嵌入高维空间内的流形结构，本章对scikit-learn手写数字集[25]进行二维可视化操作。

Scikit-learn 手写数字集是8×8 的图像，样本空间是64维，具有较高维度，可以省略升维层，而直接添加过滤层和降维层。孪生网络的子网结构是包含64个结点的输入层、两层各包含200 个结点的过滤层和包含2 个结点的降维层。从手写数据集中选择0～5这六种数字，并对每种数字随机选择50个样本，共300个原始样本。原始样本归一化后，设置一级邻域的ε1为2.0，二级邻域的ε2为3.0，产生3 795个正样本和15 006个负样本。Loss2中的λ设为10，网络的学习率为0.005。经过250 个周期的训练，孪生网络的二维可视化效果与其他传统方法对比，如图8所示。

图8 手写数字集降维可视化效果对比

从图8的实验结果来看，LLE、Hessian和LTSA方法虽然有明显的聚类效果，但是类别的边界较模糊，个别类别有明显的重叠现象。相对的，Isomap和孪生网络也有明显的聚类效果，类别边界较为清晰。整体来看，经过孪生网络可视化后，数据在空间内的分布更加均匀，没有明显空间压缩的痕迹，空间关系的辨识度较高，这为后续的数据分析打下了良好的基础。

4 结束语

本文为流形学习提供了一种新的研究思路，即通过孪生网络的“样本对”训练方法，实现能够保持原有的空间关系的降维映射。同时，针对孪生网络的通道设计，提出了升维、过滤和降维的三层结构，以及两级邻域采样的概念，并设计了包含正、负样本对的损失函数Loss2。将该方法运用在仿真数据（Swiss roll）的流形降维和真实数据（handwritten digits）的二维可视化上，都取得了良好的效果。该方法的优点有：（1）对流形结构没有凸包要求、空洞限制；（2）对数据的均匀采样要求不高；（3）降维设计避免了复杂的数值分析和添加额外约束；（4）降维过程没有维度压缩、还原度高。

同时，用孪生网络进行流形学习也存在局限性与不足：（1）随着训练集增大、流形结构曲率增加，网络结构也更加复杂，训练难度也在加大；（2）与传统方法类似，如果数据集中引入过多的新数据，则需要重新进行学习，才能达到较好的效果。针对前一种局限性，可以考虑优化训练集的产生方式，控制训练集的规模，同时根据具体的应用，给出子网结构的优化方案。针对后一种局限性，可以考虑迁移学习，即在原有训练好的网络基础上继续进行新的数据集的训练。