论文标题：Pointwise manifold regularization for semi-supervised learning（基于点态流形正则化的半监督学习）

期刊：Frontiers of Computer Science

作者：Yunyun WANG, Jiao HAN, Yating SHEN, Hui XUE

发表时间：15 Feb 2021

DOI： 10.1007/s11704-019-9115-z

微信链接：点击此处阅读微信文章

原文信息

标 题：

Pointwise manifold regularization for semi-supervised learning

原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-019-9115-z

引用格式：

Yunyun WANG, Jiao HAN, Yating SHEN, Hui XUE. Pointwise manifold regularization for semi-supervised learning. Front. Comput. Sci., 2021, 15(1): 151303

1导读

在许多实际应用中，未标记的数据可以很容易和廉价地收集，而获取有标记的数据通常是相当昂贵和耗时的，特别是涉及人工工作。例如，在网页推荐中，有大量的网页可用，但很少有用户愿意花时间标记他们感兴趣的网页。在垃圾邮件检测中，可以自动收集大量的电子邮件，但很少有人没有被用户贴上垃圾邮件的标签。因此，半监督学习，它联合利用大量的未标记数据和有限的标记数据进行学习，在过去的几十年里引起了广泛的关注。

半监督分类方法试图利用未标记数据在学习过程中所披露的内在数据分布信息，通常认为这些信息有助于学习。为了利用未标记的数据，需要采用一些假设来进行学习。半监督分类中两个常见的假设是聚类假设和流形假设。前者假设在高密度区域中的类似实例很可能共享相同的类标签，从而通过集群之间的低密度区域引导分类边界。后者假设数据驻留在一些由拉普拉斯图表示的低维流形上，并且相似的实例应该根据图共享相似的分类输出。

对于第二种假设也就是流形假设，流形正则（MR）通常将每个实例对视为一个单一的对象，并约束流形图上的相似实例对应该共享相似的分类输出。因此，它是建立在流形图上的成对平滑性之上的。然而平滑约束在自然界中可以是点态的，也就是说，平滑应该“无处不在”，从而将每个点的行为与其近邻的行为联系起来。实际上，研究者已经研究了学习问题中的点态平滑。而基于聚类假设的方法通常会实现点态平滑。在本文中，作者提出了一种基于点态MR的框架，并将公式推导与基于点对的MR相似，最终优化通过实验进行相关比较。

2主要方法

半监督学习中的流形正则化方法

流形假设是半监督学习中最常用的数据分布假设之一，它假设在流形结构上的相似实例应该共享相似的分类输出。基于流形假设，流形正则化(Mr)近年来已被深入研究且已被应用在不同的领域。

那么给定一个数据集，已标记数据定义为，与之相对应的标签，未标记的数据定义为，其中每个样本且。该流形图在整个数据集上的构造为，其中权重表示所连接实例对和之间的相似性。基于这样的流形图，流形学习的框架可以表述如下式：

(1)

其中，f(x)为决策函数，和均为正则化参数，是损失函数，例如：支持向量机（SVM）：；或者最小二乘分类器的平方损失（RLSC）：，是在再生核希尔伯特空间（ Reproducing Kernel Hilbert Space）中保证平滑性的一个正则项。第三项则保证了流形图上的点对之间的光滑性，即相似的实例应该在流形结构上共享相似的分类输出。它可以进一步写成：

(2)

其中,L是由L=D-W给出的图拉普拉斯矩阵，W是图G的权重矩阵，D是由组成的对角矩阵。由表示定理（Representer theorem），等式（1）的最小值可以有如下形式：

(3)

其中是一个有效核函数（Mercer kernel）。

半监督学习的逐点流形正则化方法(PW_MR)

（1）模型框架

流形学习对实例对采用正则化项，以约束流形图上的相似实例对共享相似的分类输出，从而实际实现了点对之间的平滑性。在本节中，作者介绍了一个依据点态平滑度的逐点流形学习框架。通过逐点实现平滑性约束，可以将PW_MR框架的优化问题表述为：

(4)

其中，表示邻域集中的近邻，表示每个实例周围的局部密度。它可以根据实例与其近邻之间的归一化距离来计算，值越小表示实例周围的分布越密集。但是，当一个实例在类的重叠区域时，那么根据上述的局部密度，周围局部密度将变得很大。因此，在等式（4）的第三项中将受到更重视或更大的处罚，但显然这是意料之中的。因此，在计算局部密度时，这里同时考虑了邻居密度和无监督学习结构，即：

(5)

式中，表示实例与其邻居之间的距离，表示所有实例之间这些距离的和。和描述了集群成员关系，或者在某个无监督学习方法如FCM中，xi属于单个集群的概率。的第一部分考虑每个实例与其近邻之间的归一化距离，值越小表示周围的分布越密集，因此的值越大，最后在等式（4）中的惩罚越大。第二部分考虑了无监督学习方法的结果，因为无监督学习方法通常可以用来检测分布结构的内在边界。的值越大，表示成为非边界实例的概率越大。

不同于等式（1）中的第三项，这是一个正规化项，对实例对有平滑惩罚的正则项，等式（4）中的第三项考虑了在单个本地实例上的平滑性。此外，由于考虑了点态光滑性，PW_MR通过考虑局部密度来引入每个实例的重要性。我们可以在等式（4）中进一步重写第三项为：

其中，W是邻域相似度矩阵，，是一个单位矩阵。P∈R^(n×是一个对角矩阵且对角分量。

（2）逐点流形正则最小二乘法（PW_LapRlsc）

对于公式（4），我们利用平方损失函数，PW_LapRlsc可以写作：

(6)

同理，在应用了表示定理（Representer theorem）后，公式（6）的最小值有如下表示形式：

(7)

因此，最优化函数为：

(8)

其中，是拉格朗日乘子的向量。和

是核矩阵，其中和分别表示标记的和整个数据集。是标记数据的类标签向量。关于α的偏导数在等式最小的时候等于零，因此：

(9)

由此可以得出：

(10)

（3）逐点流形正则支持向量机（PW_LapSVM）

利用铰链损失函数，计算出了PW_LapSVM公式如下：

(11)

进一步公式（11）可以表示为：

(12)

在应用了代表者定理之后，可以得到：

在应用了拉格朗日乘子法进行优化后，可以得到下式：

(13)

其中是拉格朗日乘数。进一步优化可以得到：

(14)

因此，我们可以进一步减少如下式：

(15)

其中是一个矩阵，其中为单位矩阵(假设第一个点将被标记)且。

进而：

(16)

因此：

(17)

将其替换回等式（16）中的简化拉格朗日量，可以得到：

(18)

其中：

(19)

3实验

实验设置

对所采用的数据集的描述见表1。每个数据集被随机分成两部分，一个用于训练，另一部分用于测试，训练集分别随机选择10个和100个标记实例。但是，如果训练能力小于100，我们只需要为标记的样本选择一半的训练样本。数据划分和训练过程重复20次，并报告平均精度和标准偏差。

表1. 对13个UCI和基准数据集的描述

在本文的实验中，作者使用高斯核来进行比较。在逐对的MR和逐点的MR的图构造中的邻域数k都被简单地设置为10。当标记10个实例时，记录了所有最佳性能的正则化参数组合，当标记100个实例时，通过5折交叉验证选择正则化参数。参数和C_2的值范围为{0.01、0.1、1、10、100}，内核参数的值范围为{0.01、0.1、1、10、100}×d，其中d为实例之间的平均差值。

文章将其逐点Mr方法与逐对的Mr方法进行了比较，包括成对的LapRlsc和LapSVM，以及基于聚类假设的方法TSVM，并将有监督的SVM实验结果作为基准线。

实验结果

表2和表3分别给出了10个和100个标记实例的比较结果。每一行给出了每个数据集上的结果，最后一行给出了每个方法在所有数据集上的平均性能。此外，在每一行中，粗体值表示在每个数据集上的最佳性能，斜体值表示PW_LapRlsc/PW_LapSVM的性能优于LapRlsc/LapSVM。

表2. 10个标记实例的结果比较

表3. 100个标记实例的结果比较

其次邻居k的数量对于逐对MR和逐点MR的性能都很重要文章还展示了以监督学习SVM实验结果为基准线，具有不同值的LapRlsc和PW_LapRlsc的性能。每个数据集只包含10个带标记的实例。采用高斯核，k的值范围为{5、10、15、20、25}。对于其他参数，文章展示了最佳的结果。最后，计算结果如图1所示：

图1. 以SVM为基准，从{5、10、15、20、25、} 中选择不同数量的邻居结点数k,LapRlsc和PW_LapRlsc在数据集(a) australian (b) g241c (c) heart (d) house (e) isolet (f) optdigits上的实验表现

从图1中，我们可以发现：

• 邻域数k是构造流形图的一个重要参数。然而，通常很难选择它的值。从上图中可以看出，对于不同的k值，PW_LapRlsc的性能是相对稳定的，因此它对被选择的邻居的数量不那么敏感。其原因可能是在平滑度约束中使用了邻域均值。

• 不同的k值下，PW_LapRlsc的性能通常优于LapRlsc，说明PW_LapRlsc的强更优越的性能。因此，对于一个适当的k，PW_LapRlsc有望提供更优越的分类性能。此外，即使k固定为10，逐点Mr的表现已经比逐对Mr具有竞争力。

4 文章的主要贡献

作者将点态平滑性运用到了流形正则中来，作者试图通过约束单个局部实例来开发一个点态MR(简称PW_MR)的半监督学习，这样，就保持了平滑性的点态性质。而且，通过考虑单个实例而不是实例对时，就可以引入单个实例的重要性。特别是在学习中存在异常值时，每个实例的重要性可以通过其对正确预测的贡献或局部密度来描述。本文以单个实例的局部密度为例，对于解决该问题，PW_MR的公式可以推导的与MR的相似，因此优化过程也将是相似的。最后，实验结果表明，PW_MR与MR相比具有竞争力。

摘要

Manifold regularization (MR) provides a powerful framework for semi-supervised classification using both the labeled and unlabeled data. It constrains that similar instances over the manifold graph should share similar classification outputs according to the manifold assumption. It is easily noted that MR is built on the pairwise smoothness over the manifold graph, i.e., the smoothness constraint is implemented over all instance pairs and actually considers each instance pair as a single operand. However, the smoothness can be pointwise in nature, that is, the smoothness shall inherently occur “everywhere” to relate the behavior of each point or instance to that of its close neighbors. Thus in this paper, we attempt to develop a pointwise MR (PW_MR for short) for semi-supervised learning through constraining on individual local instances. In this way, the pointwise nature of smoothness is preserved, and moreover, by considering individual instances rather than instance pairs, the importance or contribution of individual instances can be introduced. Such importance can be described by the confidence for correct prediction, or the local density, for example. PW_MR provides a different way for implementing manifold smoothness. Finally, empirical results show the competitiveness of PW_MR compared to pairwise MR.

解读：徐 宁 东南大学

审核：张 琨 合肥工业大学

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中13种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn