弹力理论传播的半监督学习新方法*

刘莹莹，王士同

1.江南大学 数字媒体学院，江苏 无锡 214122

2.江南大学 江苏省媒体设计与软件技术重点实验室，江苏 无锡 214122

1 引言

许多实际的工作中，例如对象识别、多媒体检索和文本分类等任务，标记的示例通常是少量的且需要花费昂贵的代价才能获取，但大量的未标记的示例又是可以利用的。虽然这些大量的未标记示例没有标签，但它们可能提供了数据分布的先验信息，使其在标记示例很少的情况下能够进行准确的分类。半监督学习（semi-supervised learning，SSL）[1-4]就是这样的一种学习策略，目的是利用这些大量的未标记示例来提高学习性能。SSL 已经被许多研究者从不同的角度进行了深入的研究。众所周知，SSL 算法应该在正确的假设下进行，否则未标记的示例可能会显著影响其性能。通常情况基于图形的SSL 算法使用的两个基本假设是聚类假设和流形假设[5]，大多数流行的SSL 算法也都是基于这两个假设之一进行的研究[6-7]。

本文目标是基于流形假设的前提下设计一种新的基于图形的SSL 算法。与现有的基于图形的直接从统计学中推导出来的线性近邻传递（linear neighborhood propagation，LNP）[8]算法不同，本文结合物理学中弹性力理论提出了一种新的SSL 标签传播方案——基于弹力理论传播的半监督学习新方法（novel semi-supervised learning method by elastic-force theory based propagation，EFTP）。EFTP 算法一方面模拟了节点之间的作用力，使得标记节点的标签在传播中扩散。把标记节点可以看作是标签信息高度集中的扩散源，表现在弹力理论中就是标记节点对未标记节点的弹力很大，而对于未标记节点来说它对于其他节点的弹力几乎为0。当扩散过程开始时，标签信息将从标记节点转移到剩余的未标记节点。当传播过程完成后，图中所有的节点都会得到一定量的标签信息，为最终的分类提供基础。另一方面考虑到不同节点被其他节点同化和同化其他节点的能力是不同的，使得EFTP 算法比菲克定律协助传播（Ficks law assisted propagation，FLAP）[9]算法更加逼真。在EFTP 算法中，一个示例接收或者传输标签信息的时间和数量和应该将这些标签传播到哪里，都直接受弹力理论的约束。

本文主要专注于设计弹力理论传播的半监督学习新算法。在人造数据集、图像以及真实数据集上进行实验，EFTP 方法都获得了比LNP、FLAP 更好的效果。

2 理论基础2.1 相关介绍

半监督学习算法的目标是将标记节点的信息传到未标记节点中去，在本文中用如下符号表示：一组标记节点记作，一组未标记的节点记作，xi∈Rm,1 ≤i≤n(n=p+w)且都是从未知的边际分布中取样，1 ≤i≤p，yi从{-1,1}中取值，目的是将标签信息从P传播到W。文献[10]中开发了局部学习稳定器来预测每个样本标签来自其邻居的标签。文献[8]中提出了线性邻域传播（LNP），即假设图上的每一个例子都可以由其邻域进行最优重构。这些算法通常假设邻居对于测试示例的标签是确定的。文献[9]中提出了菲克定律协助传播（FLAP），模拟流体的扩散进行标签传播，设定流体分子的同化与被同化能力是相等的。然而，这些算法中假设并不总是适用于各种数据分布，因此上述方法有时可能会得到不满意的结果。

本文对SSL 方法进行探索，从一个新的角度研究传播的过程。传播是社会生活中一种很常见的现象，举个很常见的例子：在人口迁移中，起初每个人都居住在自己的领域，但是在个人因素和社会因素共同作用下，人们会选择迁徙。这个过程中，人口迁移可以看成是由一系列的“力”引起的。这就是社会学中的著名的人口迁移推拉力模型（参见文献[11-12]）。当然，由于个体的差异性，一个区域对个体的排斥力和吸引力参数都是不同的。这就可以类比成在实际工作中每个节点它的同化与被同化的系数是不一样的。可以把此现象看成人口的流动传播。除此之外，很多社会学家还为推拉理论引入很多量化模型。例如文献[13]把物理学中的重力模型以及统计学中马尔科夫链模型引入迁移理论。目的就是为了使人口迁移的定量分析成为可能。受这种想法的启发，利用弹力模型，使得本文的传播算法更具有兼容性，让本文的标签传播在处理多种数据分布的数据集时更具有鲁棒性。下面将介绍本文所提出的SSL模型——弹力模型。

2.2 弹力模型

自然界中每个物体在外力作用下都会发生形变。如果撤回这些外力，物体就会恢复原来状态，把这些外力称作“弹力”。在弹性限度内，弹簧发生弹性形变时，弹力的大小跟弹簧形变量成正比。具体表达式如下：

其中，Δx表示弹簧的形变量，k称为弹簧的倔强系数（也称作劲度系数或弹性系数），大小与其自身的性质有关。如弹力理论所描述的形式一样，现在把弹簧形变量Δx类比成标签信息量在节点之间的扩散距离d。倔强系数k大小在本文中除了与节点之间传播时单个节点的输入系数λ1和输出系数γ1有关之外，还与当前时刻互相传播的两个节点标签数值有一定关系。后期会对这两个参数进行适当调整来实现满意的分类结果。因此，在标签传播和力学中弹力理论之间画一个平行关系是很自然的。接下来详细解说节点之间的传播。类比图如图1 所示。

从图1 可以看出标签信息在节点之间的传播过程和结果。颜色偏重的圆类比于较多标签信息的示例。同理具有较少标签信息的示例，则用颜色偏淡的圆来类比。以xw节点为例来分析传播过程。图1中蓝色箭头和绿色箭头分别代表其他节点中的标签信息流向节点xw的过程和节点xw传播自己的标签信息的过程。颜色较重的图形传播的标签信息较多，用重色箭头表示；颜色较浅的图形传播的标签信息较少，用淡色箭头表示。在综合输入输出图之后，画出了最后标签信息的流向用红色箭头表示。红色箭头显示的是xw与外界所有节点标签交流之后的合力方向，也就是标签传播总方向。自然的，设∀v∈{1,2,…,n}，可以用如下弹力模型公式解释标签传播过程：

Fig.1 Elastic force mode图1 弹力模型

这里设置λ1是xw被其他节点传播的系数，形象地说是输入系数。γ1是xw节点对其他节点的同化能力系数，也是其输出系数。除此之外，定义节点xw在t时刻的软标签为。这里软标签意味着l从一个实际范围[-1,1]中取一个值，借助式（1）、式（2）可以变成如下表达式：

式（3）意味着xw在扩散距离dvw=exp(-‖xv-xw‖2/(2σ2))上将其标签信息传播到其他节点和接收其他节点的标签信息。根据牛顿第二定律，粒子运动的加速度等于作用力与粒子质量的比值：

在时间Δt内标签信息的传播距离S有如下表达式：

因此过Δt时间后，结合式（4）、式（5），xw节点在Δt时间段内将标签信息在扩散的过程中散布了一个路径的总信息量。可以得到如下表达式：

式（4）、式（5）中的Δt、m可以简单地设为1，同时令2-1λ1=λ,2-1γ1=γ，为了后续证明，这里令λ1=γ1μ。结合式（3）、式（4）、式（5）、式（6），整个数据集的传播过程用如下式子表达：

考虑到xw的初始状态，式（7）可以变换为：

如果xw分别是一个正的、负的或未标记的例子，那么分别取1，-1 或0。α∈(0,1)是xw从外界接收到的信息以及输出去的标签信息和xw的初始状态之间的平衡系数。式（8）模拟了节点之间的标签传播过程。与最初的弹力定律稍有不同，在实际任务中，如图1 所示xw除了接收其他节点的传播信息之外，同时它也在向其他节点传输标签信息。换句话说，一个节点从数据集中的所有其他节点接收标签信息能力系数和其输出系数是不同的。

式（8）说明数据集中一个节点与另一个节点之间的传播过程，表示未标记节点的接收标签信息可以理解为其他节点发出的信息的集成。

根据前面的介绍，在半监督学习中，将弹力模型应用于无标记和有标记的节点。EFTP 算法允许任意两个节点之间的标签信息交换，而不考虑它们当前的标签值。因此，在传播过程中可以更改节点的标签。幸运的是，文献[9]中定理1 表明被标记的示例的标签在迭代过程之后不会改变，也就意味着被标记示例的原始标签，即1 或-1，不会从1 转成-1。

定理1 被标记节点的标签在迭代过程之后不会改变。

3 弹性理论传播算法3.1 算法传播进程介绍

弹力理论传播的半监督学习新方法需要对样本中的每个节点进行传播，随着时间的推移，越来越多的节点加入传播行列，进行反复迭代计算，直至收敛。在传播过程中同时更新所有示例的标签，用标签向量来表示，初始状态用向量y=(y1y2…yn)T来表示。各个示例的标签值用如下公式表示：

把迭代矩阵D定义为：

由式（9）可知，一个示例的标签是其初始状态与包括其自身在内的所有示例标签的线性组合。迭代计算式（9）直到其收敛，收敛判定由如下公式表示：

式中，δ是预定义的一个极小的正数。通过迭代过程可得到收敛向量L*。给定一个硬阈值0，若则确定xw为正（是L*向量中的第w个元素），否则为负数。

虽然式（9）是为二元分类推导出来的，但是可以通过将标签向量L和初始状态向量y替换为标签向量矩阵L和初始状态矩阵Y，式（9）可以直接扩展到多类分类。具体表达式如下：

式（12）中矩阵L和Y的规格是n×m，m表示类别的总数。若xw被标记，则yw=m1那么。反之如果xw没有标记，那么=0 (1 ≤m1≤m)，最后xw属于种类。

由文献[14-15]中定理2 可知式（12）以线性速率收敛。定理2 的内容直接适用于式（9）。

定理2 由式（12）生成的序列{L(t)},t=1,2,…最终收敛到如下式子：

此时也对标签传播的停止准则进行了相应的修改：

这里‖· ‖L表示范数。因为式（12）是一个根据示例之间的相似性传递标签信息的传播算法，所以它可以处理任何类型的数据分布。此外，EFTP 是一种基于图形的算法，可以有效地利用隐藏在数据集中的流形结构[16-17]，因此它总能得到满意的分类结果。

3.2 算法收敛性证明

为了直观地比较EFTP、FLAP、LNP，并显示其优越性，在经典正则化理论背景下重新构造了EFTP 算法，具体表达式如下：

式中，Dkj是矩阵D中的第(k,j)个元素。式（15）右侧的第一项形成了特定的先验知识，使示例标签在L中平稳变化。这表明类似示例的软标签之间不应该有太大的差别。第二个拟合项表示所确定的标签应与示例原始标签状态保持一致。而正则化参数φ＞0控制平滑项和拟合项之间的权衡。

定理3 正则式(15)是一个凸优化问题。

证明Q(L)对L进行求导的过程步骤如下：

在式（17）中Q(L)对L求导后变成如下形式：

将式（17）右边设为0，因此式（18）可以被重新表述如下：

变形得到与式（13）相同的闭合式，表达式如下：

因此式（15）是式（9）的迭代结果，在式（15）中迭代矩阵D可变换成如下形式：

为了保证D是非负随机矩阵以及D1每行和为1，设置。

从文献[14]中的Gerschgorin 圆定理得到D1所有特征值都在范围内，这表明D1是正定矩阵。

而对于对角矩阵D2其特征值就是对角线，为使得其为正定矩阵设置u＞1。

根据正定矩阵的性质可知正定矩阵的和仍是正定矩阵。由此可以证明本文的迭代矩阵D也是正定矩阵。因此，式（15）是凸优化问题，收敛结果也是全局的最优的。 □

定理3 表明，EFTP 算法式（15）的收敛点对应全局最优解。这些处理方式差异使得EFTP的收敛精度更高。至此以上内容即为本文所提算法的主要内容。

4 实验分析

本章采用不同形状的人造数据、图像数据以及真实数据分别对EFTP、LNP、FLAP 算法进行评估。重点讨论这三个算法中的两个问题：（1）对每个数据集只给出很少的标记示例的情况下，算法对未标记示例的分类精度；（2）算法的稳定性。实验软硬件环境为Intel Corei3-2130 3.4 GHz CPU，4.0 GB RAM，Windows 7，Matlab R2016b。

4.1 参数设置和评价标准

本节将说明实验中的参数设置情况和使用的评价标准。

两个参数k、u是EFTP 算法获得令人满意结果的关键。k控制一个既定的稀疏图，u在平衡算法准确性和稳定性中起着重要的作用。

u选择：u对EFTP 算法性能的影响是双重的。直观上，从式（3）观察到u代表从xv同化xw的效果，xv同化xw的概率越大，u的值就越大，xw的标签就越容易受到xv的影响。并且在第3 章中证明此算法的收敛性是在u>1 的情况下。但是u的取值并不是无限大，因为在一个数据集之中不同类的数据可能会相似，所以u的取值要在一定的范围内。同时为了此算法可以适用于大样本高维的数据集，对数据集选取一定的代表点以此来反映数据集的整体情况。在这种情况下用文献[18]中的参数寻优方法找到合适的u。利用最优的u带入到原数据集中得到最高的分类精度。

简而言之，u>1 会收敛，在保证收敛的情况下，趋于无限大时或者取值太小都会降低算法稳定性和精度。因此，u的选择应该在保证其准确性和稳定性前提下作一个适中的权衡。下面的参数敏感性实验信息图将阐述这一点。在Wine 数据集中通过固定L=18，EFTP 的精度和稳定性的变化如图2（a）和图2（b）。显然在Wine 数据集里，设置u=1.4 精度相对较高，该设置下的稳定性也是可以接受的。

Fig.2 Sensitivity test analysis diagram of parameter u图2 参数u 的敏感性实验分析图

k选择：一个合适的图形对提高算法性能非常重要，k是决定已建立图的邻域数目和稀疏性的一个关键参数。在DS1、DS2、DS3、DS4 数据集上让k从小到大取值。一般情况下，如果图太稀疏（例如k=2），EFTP 达不到令人满意的性能。然而，当k在某值（k=6）左右取值时，EFTP 分类性能就是正常的，效果令人满意。综合实验表明k的选择对稳定性和精度影响不大，很容易调优。具体参数敏感性实验分析如图3 所示。

Fig.3 Sensitivity test analysis diagram of parameter k图3 参数k 的敏感性实验分析图

为了公平比较，下列所有实验中EFTP 参数设置为a=0.99,，η设置在[0,1]内。在FLAP 中a也设置为0.99。为所有算法构造了相同的K近邻（K-NN）图。σ、u在不同数据集中会进行相应调整，以达到最佳性能。

采 用NMI（normal mutual information）、RI（rand index）[19]指标对算法进行评估。NMI 与RI 的定义如下：

首先给出包含n个对象的数据集，X定义了已知标签的原始数据，Y定义了对已知标签原始数据的聚类效果，a定义了X、Y任意两个具有相同类标签并且属于同一个样本的个数，b定义了X、Y中任意两个具有不同标签并且属于不同类样本的个数。两种指标对算法进行评估，指标越高，说明聚类效果越好。

4.2 人造数据集实验

本节使用人造平面数据集DS1、DS2、DS3、DS4将EFTP、FLAP 以及LNP 三种算法的传播过程可视化，以此来进行三种算法的验证和比较。由于LNP与FLAP 算法的分类效果相近，限于篇幅，LNP 的分类效果可视图不再给出。算法中所用到的四个数据集为了在精度和稳定性上形成对比，都采用了较多数据点。除此之外，为了证明EFTP 算法的鲁棒性，本节的数据集的选取也具有不同的类别形式，数据量由简单到复杂，覆盖面较为广泛，具体信息如表1所示。

Table 1 Synthetic datasets表1 人造数据集

DS1、DS2 数据集与使用双月数据集进行实验的文献[7]和文献[20]相比，减少了类间距离。分别让两个类尽可能地镶嵌与靠近，使月、正方、圆形态不规则增加分类难度。DS3、DS4 数据样本量大于10 000的数据集也分别进行EFTP、FLAP、LNP 算法实验。本节依次在图4、图5、图6、图7 中给出了其原图、代表点图以及运行FLAP 及EFTP 算法后的图解。

Fig.4 Original graph and experimental graph of DS1图4 DS1 原图及实验图

Fig.5 Original graph and experimental graph of DS2图5 DS2 原图及实验图

Fig.6 Original graph and experimental graph of DS3图6 DS3 原图及实验图

Fig.7 Original graph and experimental graph of DS4图7 DS4 原图及实验图

从图4～图7 中可以看出，相对于FLAP 算法，EFTP 算法对于各种形状数据集传播分类的效果都非常好。为了在DS1、DS2、DS3、DS4 数据集上更好地实现分类效果，为EFTP 算法构建了5-NN、6-NN、8-NN 和10-NN 图。

在运行EFTP 算法时，各数据集的代表点数为525、750、812 和1 250，其传播分类结果与直接使用FLAP、LNP 算法精确度都有显著提升。为了进行定量比较，本文通过更多实验对比三种算法分类精度，具体情况如表2 所示。

在实验中，由于选标记示例点时存在随机的情况，则会造成每次实验结果出现小范围内波动。为此，实验数据则选取均值作为数据结果。以上每组实验所记录数据都是在运行数十次之后计算均值得到。从实验数据可以明显看出，同预想一样，本文提出的EFTP 算法同FLAP、LNP 算法相比较，在标记示例很少的情况下都能取得较高的精度。当然，随着标记示例l逐渐增大，算法的分类精度也会相应提高。从以上实验结果来看，本文算法在精度、稳定性方面都有了很大的提升，完全达到预期目标。

4.3 图像分割实验

本文选取4 幅图像（http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench）用于图像分割实验中，名称分别是Horse、Elephant、Sky、Grassland，每幅图的分辨率均为320×320 像素。限于版面，本文的示意图都进行了一定比例的缩放，如图8 所示。

本节为了说明EFTP 的有效性，与FLAP、LNP 算法分类结果进行对比。4 幅图的类别数分别为2、2、3、3，图9、图10 分别为本文算法和FLAP 算法的图像分割效果，LNP 与FLAP 的分类效果相似，不再给出。本实验采用NMI、RI[19]指标进行评估，目的是为了可以定量地分析图像分割的效果。该指标进行评估之前首先要对像素点划分类标，方法见文献[19]。EFTP 算法分别在4 幅图片上运行10 次，求得平均NMI、RI指标记录在表3、表4 中。

从实验结果中可以看出：在Horse、Elephant 中，两种算法的指标相近，都能有效地分割出目标物体。但是在Sky、Grassland 图片中，EFTP 明显优于FLAP、LNP 算法，因此EFTP 更具有实用性。

Table 2 Experimental results on synthetic datasets表2 人造数据集的实验结果

Fig.8 Images used in segmentation图8 分割实验的图像

4.4 真实数据集

采用4 个UCI（http://archive.ics.uci.edu/ml/datasets.html）数据集Iris、Wine、BreastCancer 以及National Clas-sification of Economic Activities-9 (CNAE-9)来比较EFTP 与FLAP、LNP 算法的分类精度。数据集具体信息如表5 所示。

Table 3 NMI of 3 algorithms on 4 images表3 3 类算法在4 幅图片上的NMI

Table 4 RI of 3 algorithms on 4 images表4 3 类算法在4 幅图片上的RI

Fig.9 Segmentation results of EFTP on each image图9 EFTP 算法在图像上的分割效果

Table 5 Real datasets表5 真实数据集

本节中对标记集L在不同大小下的分类精度进行了实验。算法在每个L下独立实现10次，随机选取标记示例，表6 列出了10 次运行输出的精度平均值以及方差。请注意，在生成标记集时，每个类中至少保证有一个标记示例。分别为Iris、Wine、Breast Cancer和CNAE-9 构建了10-NN、6-NN、7-NN 和10-NN 图。

从表6 可以看出，当L由小变大时，EFTP 一般可以达到比较算法中最高的精度。可以看出，在大多数情况下，EFTP 算法的效果优于FLAP 和LNP 算法。因此本文提出的算法EFTP的结果是满足期望的。

Fig.10 Segmentation results of FLAP on each image图10 FLAP 算法在图像上的分割效果

5 结束语

采用物理力学中弹力基本理论，本文提出了用于SSL 标签传播的EFTP 算法。EFTP 也可以在传统正则化理论的背景下推导出来，将EFTP 算法与已有的算法相联系，意味着EFTP 的收敛点是全局最优的。同时也证明了参数u在决定分类性能和稳定性方面扮演了重要的角色。综合实验结果表明，与FLAP、LNP 算法相比，EFTP 具有很大优势。

与大多数标签传播算法相似，直接将EFTP 应用于大数据问题在计算上并不容易，这是因为图结构的复杂度是O(n3)。然而，超图技术的最新发展，如文献[21]和文献[22]，可以解决这个问题。并且EFTP 算法所提出的模型在u＞1 情况下进行，u＜1 是否依旧收敛找到优解是今后拟探讨的课题。

Table 6 Experimental results on real datasets表6 真实数据集的实验结果