半监督学习

1. 给定有标记样本集合

，和未标记样本集合

，其中

。 学习器自动地利用未标记的

来提升学习性能，这就是半监督学习semi-supervised learning。

1. 半监督学习的现实需求非常强烈，因为现实中往往能够容易地收集到大量未标记样本，但是对其标记需要耗费大量的人力、物力。如：在医学影像分析上，对影像的疾病标记需要专家人工进行。 因此可以通过专家人工标注少量的样本，然后采用半监督学习。
2. 虽然未标记样本集

没有直接包含标记信息，但是如果假设

与带

从同样的数据源独立同分布采样而来，则

所包含的关于数据分布的信息对建立模型是有好处的。

1. 要利用未标记样本，必然需要对未标记样本的分布与已标记样本的分布的关联做出假设。
   • 最常见的假设是聚类假设cluster assumption：假设数据存在簇结构，同一个簇的样本属于同一个类别。
   • 另一种常见假设是流形假设manifold assumption：假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。其中，邻近的程度用相似度来刻画。
   • 流形假设可以看作是聚类假设的推广，但流形假设对于输出值没有限制（可以为类别，也可以为实数），因此比聚类假设的适用程度更广，可用于多类型的学习任务。
   • 无论聚类假设还是流形假设，本质都假设是：相似的样本有相似的输出 。

2. 半监督学习可以划分为：纯pure半监督学习和直推学习transduction learning 。
   • 纯半监督学习：假定训练数据中的未标记样本集

   并非待预测的数据。 纯半监督学习是开放性的，它学得的模型能够适用于额外的未观测数据。

   • 直推学习：假定学习过程中考虑的未标记样本集

   就是待预测的数据，学习的目标就是在

   上获取最优泛化性能。 直推学习是封闭性的，它学得的模型仅仅是针对学习过程中的未标记样本集

   。

一、生成式半监督学习方法

1. 生成式generative methods 半监督学习方法：直接基于生成式模型的方法。
2. 生成式半监督学习方法假设所有数据（无论是否有标记），都是由同一个潜在的模型生成的。
   • 该假设使得能够通过潜在模型的参数将未标记样本与学习目标联系起来。
   • 未标记样本的标记可以视作模型的缺失参数，通常可以基于EM算法进行极大似然估计求解。

3. 生成式半监督学习方法其实是一个算法框架，内部不同算法的主要区别在于生成式模型的假设：不同的假设将产生不同的方法。

1.1 生成式高斯混合半监督学习

1. 给定样本

，其真实类别标记为

。 假设样本由高斯混合模型产生，且每个类别对应一个高斯混合成分。即数据样本是基于概率密度：

来产生的。其中：

是样本

的第

个高斯混合成分的概率。

为该高斯混合成分的参数。

• 混合系数

。

1. 令

为模型

对

的预测标记，

表示样本

隶属的高斯混合成分。 根据最大化后验概率，有：

• 考虑到

， 则有：

• 由于

， 则有：

为已知样本

，则它由第

个高斯混合成分生成的后验概率

为已知

由第

个高斯混合成分生成，则其类别为

的概率

1. 在

中，

需要知道样本的标记

； 而

并不需要样本的标记。因此有标记和无标记的数据均可利用。 因此通过引入大量的未标记数据，对

的估计可以由于数据量的增长而更为准确，于是上式的整体估计可能会更准确。

1. 给定标记样本集

，和未标记样本集

，其中

。 假设所有样本独立同分布，且都是由同一个高斯混合模型

生成的。

• 高斯混合模型的参数

采用极大似然法来估计。

的对数似然是：

• 第一项对数项中，为联合概率

：

• 第二项对数项中，为概率

：

1. 高斯混合模型参数估计可以用EM算法求解。迭代更新步骤为：
   • E步：根据当前模型参数

   计算未标记样本

   属于各高斯混合成分的概率：

• M步：基于

更新模型参数。 令

为第

类的有标记样本数目，则：

以上过程不断迭代直至收敛，即可获得模型参数。

1. 预测过程：根据式子：

来对样本

进行分类。

1.2 性质

1. 如果将上述过程中的高斯混合模型替换成其他模型，则可以推导出其他的生成式半监督学习方法。
2. 生成式半监督学习方法优点：方法简单，易于实现。在有标记数据极少的情况下，往往比其他方法性能更好。 缺点：模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合，否则利用未标记数据反倒会降低泛化性能。 在现实任务中往往很难事先做出准确的模型假设，除非拥有充分可靠的领域知识。

二、半监督 SVM

1. 半监督支持向量机Semi-Supervised Support Vector Machine：S3VM 是支持向量机在半监督学习上的推广。
2. 在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面；在考虑未标记样本之后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。 如下图中，蓝色点为未标记样本，紫色点为正类样本，黄色点为负类样本。

1. 半监督 SVM 的基本假设是：低密度分隔low-density separation。这是聚类假设在考虑了线性超平面划分后的推广。

2.1 TVSM

1. 半监督支持向量机中最著名的是 TSVM:Transductive Support Vector Machine。 与标准SVM一样，TSVM也是针对二分类问题的学习方法。
2. TSVM试图考虑对未标记样本进行各种可能的标记指派label assignment：
   • 尝试将每个未标记样本分别作为正例或者反例。
   • 然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。
   • 一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

3. 给定标记样本集

，和未标记样本集

，其中

。 TSVM学习的目标是：为

中的样本给出预测标记

使得：

其中：

确定了一个划分超平面。

为松弛向量 ：

对应于有标记样本。

对应于未标记样本。

是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数。

1. TSVM尝试未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解。因此通常情况下，必须考虑更高效的优化策略。 TSVM 采用局部搜索来迭代地寻求上式的近似解。具体来说：
   • 首先利用有标记样本学得一个SVM：即忽略上式中关于

   与

   的项以及约束。

   • 然后利用这个SVM 对未标记数据进行标记指派：即将SVM预测的结果作为伪标记pseudo-label赋予未标记样本。
     • 此时

     得到求解，将其代入上式即可得到一个标准SVM问题。于是求解可以解出新的划分超平面和松弛向量。

     • 注意到此时的未标记样本的伪标记很可能不准确，因此

     要设置为比

     小的值，使得有标记样本所起的作用更大。

   • 接下来， TSVM 找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于上式求解出更新后的划分超平面和松弛向量。
   • 再接下来，TSVM 再找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于上式求解出更新后的划分超平面和松弛向量。
   • ...
   • 标记指派调整完成后，逐渐增大

   以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直至

   达到指定阈值为止。

2. TSVM算法：
   • 算法输入：
     • 有标记样本集

     ，其中

     • 未标记样本集

     ，其中

     • 折中参数

   • 算法输出： 未标记样本的预测结果
   • 算法步骤：
     • 用

     训练一个 SVM_l

     • 用 SVM_l 对

     中样本进行预测，得到

     • 初始化

     ，其中

     • 迭代，迭代终止条件为

     。迭代过程为：

     • 基于

     ，求解下式，得到

     ：

     • 对于所有的一对标记指派为异类且很可能发生错误的未标记样本（其条件为：

     ），执行下列操作：

     • 交换二者的标记：

     。 该操作等价于交换标记，因为

     异号，且其取值为 -1 或者 +1。

     • 基于

     ，重新求解得到得到

     。

     • 更新

     。这里采用简单的倍乘，也可以采用其它增长函数。

     • 迭代终止时，输出

3. 在对未标记样本进行指标指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类。这将对SVM的训练造成困扰。 为了减轻类别不平衡性造成的不利影响，可对上述算法稍加改进：将优化目标中的

项拆分为

和

两项，分别对应基于伪标记而当作正、反例使用的未标记样本。并在初始化时，令：

其中

和

分别为基于伪标记而当作反、正例而使用的未标记样本数。

2.2 性质

1. TSVM 最终得到的SVM 不仅可以给未标记样本提供了标记，还能对训练过程中未见的样本进行预测。
2. 在 TSVM 算法中，寻找标记指派可能出错的每一对未标记样本进行调整，这是一个涉及巨大计算开销的大规模优化问题。
   • 在论文《Large Scale Transductive SVMs》 中，约 2000 个未标记样本，原始TVSM 迭代收敛大约需要 1个小时。
   • 半监督SVM研究的一个重点是如何设计出高效的优化求解策略。由此发展成很多方法，如基于图核函数梯度下降的LDS算法，基于标记均值估计的meanS3VM算法等。

三、图半监督学习

3.1 标签传播算法

1. 给定一个数据集，可以将其映射为一个图，数据集中每个样本对应于图中的一个结点。若两个样本之间的相似度很高（或者相关性很强），则对应的结点之间存在一条边，边的强度正比于样本之间的相似度（或相关性）。 将有标记样本所对应的结点视作为已经染色，而未标记样本所对应的结点尚未染色。于是半监督学习就对应于“颜色”在图上扩散或者传播的过程。这就是标记传播算法label propagation 。
2. 给定标记样本集

，和未标记样本集

，其中

。 基于

构建一个图

。其中

• 结点集

• 边集

的权重可以表示为一个亲和矩阵 affinity matirx

，一般基于高斯函数，其定义为：

其中

是用户指定的高斯函数带宽参数。 可以看到：

，因此

为对称矩阵。

• 图

是全连接的，任意两点之间都存在边。

• 两个点的距离越近，说明两个样本越相似，则边的权重越大；距离越远，说明两个样本越不相似，则边的权重越小。
• 权重越大说明样本越相似，则标签越容易传播。

3.1.1 能量函数

1. 假定从图

学得一个实值函数

， 其对应的分类规则为：

。 直观上看，相似的样本应该具有相似的标记，于是可以定义关于

的能量函数energy function：

• 两个点距离越远，

平方级的增大，而

指数级下降，因此

下降。 因此能量函数

由距离较近的样本对决定。

• 标签传播算法假定系统能量最小，即

最小。 考虑到

由距离较近的样本对决定，而

是已知的量，因此算法倾向于使得：距离较近的样本具有相近的输出 。

1. 定义对角矩阵

，其中

为矩阵

的第

行元素之和。

的物理意义为：第

个顶点的度（所有与它相连的边的权重之和）。因此

也称作度矩阵。

定义

为函数

在所有样本上的预测结果。 其中：

为函数

在有标记样本上的预测结果。

为函数

在未标记样本上的预测结果。

结合

的定义以及

的对称性，有：

1. 标签传播算法将样本

的标记

视作能量。

• 有标记样本的能量是已知的，未标记样本的能量是未知的。
• 能量在样本之间流动。对于样本

，它流向样本

的能量为

。

表示边的权重，它就是能量流出的比例（类比于管道的大小）。

• 流出的能量可正可负，因为

。

• 注意：能量不能在有标记样本与有标记样本之间流动，也不能从未标记样本流向有标记样本。

• 流经每个未标记样本的能量是守恒的。对未标记样本

：

• 其能量流向其它的所有未标记结点，能量流出为：

。

• 其它所有结点（包括有标记样本）都向其汇入能量，能量流入为：

。

考虑到

，以及

，则有：

。 考虑所有的未标记样本，则有：

• 从每个有标记样本流出的能量也是守恒的。对于有标记样本

，它仅仅流出到未标记样本，因此流出能量为：

。 由于有标记样本只有能量流出，没有能量流入，因此有：

。

• 综合两种能量守恒的情况，有：

即有：

。

1. 标签传播算法假定在满足约束条件的条件下，能量函数

最低。其中约束条件为：

• 标记约束：函数

在标记样本上满足

。

• 能量守恒：定义拉普拉斯矩阵

，则有：

因此标签传播算法就是求解约束最优化问题：

​ .

3.1.2 最优化求解

1. 以第

行第

列为界，采用分块矩阵表示方式：

则：

考虑到

是已知的，因此

完全由

决定。为求得

的最小值，则根据

有：

1. 令:

令：

，则有：

于是，将

上的标记信息作为

代入上式，即可求得未标记样本的预测值

。

矩阵其实为概率转移矩阵：

它表示从节点

转移到节点

的概率。 注意到

，因此

不是对称的。即：节点 i 转移到节点 j 的概率 不等于 节点i 转移到节点 j 的概率 。因此在Label Spreading 算法中，提出新的标记传播矩阵

：

因此有：

，节点 i 转移到节点 j 的概率 等于 节点i 转移到节点 j 的概率 。此时的转移概率是非归一化的概率。

1. 矩阵求逆

的算法复杂度是

。如果未标记样本的数量

很大，则求逆的过程非常耗时。这时一般选择迭代算法来实现。

• 首先执行初始化：

。

• 迭代过程：
  • 执行标签传播：

  。

  • 重置

  中的标签样本标记：

  。

3.2 多类标签传播算法

1. 给定标记样本集

，和未标记样本集

，其中

。 与二类标签传播算法一样，首先基于

构建一个图

，然后定义边的权重矩阵

和度矩阵

。

1. 令

的标记向量为

， 其中

表示

属于类别

的概率。根据概率的定义有：

• 对于标记样本

，

中只有一个值为1 ，其他值为 0。设

的标记为

，即有：

• 对于未标记样本

，

表示一个概率分布，依次是该样本属于各个类别的概率。

1. 当给定

的标记向量

时，样本的分类规则为：

其中

表示模型对样本

的预测输出。

1. 定义非负的标记矩阵为：

即：

的每一行代表每个样本属于各类别的概率。因此

也称为软标记soft label矩阵。 定义非负的常量矩阵

为：

即：

的前

行就是

个有标记样本的标记向量。后

行全为 0 。

3.2.1 Label Propagation

1. Label Propagation 算法通过节点之间的边来传播标记，边的权重越大则表示两个节点越相似，则标记越容易传播。
   • 定义概率转移矩阵

   ，其中：

   它表示标签从结点

   转移到结点

   的概率。

   • 定义标记矩阵

   ，其中：

   即：若

   ，则第

   行的第

   个元素为1，该行其他元素都是 0。

   • 定义未标记矩阵

   ，矩阵的第

   行为样本

   属于各标签的概率。

   • 合并

   和

   即可得到

   。

2. Label Propagation 是个迭代算法。算法流程为：
   • 首先执行初始化：

   。

   • 迭代过程：
     • 执行标签传播：

     。

     • 重置

     中的标签样本标记：

     ，其中

     表示

     的前

     行。

3. Label Propatation 算法：
   • 输入：
     • 有标记样本集
     • 未标记样本集
     • 构图参数

   • 输出：未标记样本的预测结果
   • 步骤：
     • 根据下式，计算

     ：

   • 基于

   构造概率转移矩阵

   。 其中

   ，

   为矩阵

   的第

   行元素之和。

   • 构造非负的常量矩阵

   ：

   • 初始化

   ：

   • 初始化
   • 迭代，迭代终止条件是

   收敛至

   。 迭代过程为：

   ，其中

   表示

   的前

   行。

   • 构造未标记样本的预测结果：
   • 输出结果

3.2.2 Label Spreading

1. Label Spreading 算法也是个迭代算法：
   • 首先初始化

   为：

   ，其中

   表示第 0 次迭代。

   • 然后迭代：

   。其中：

   为标记传播矩阵

   ，其中

   。

   为用户指定的参数，用于对标记传播项

   和初始化项

   的重要性进行折中。

   ，则每次迭代时尽可能保留初始化项

   。最终数据集的分布与初始化项

   非常相近。

   ，则每次迭代时尽可能不考虑

   。最终数据集的分布与

   差距较大。

   迭代直至收敛，可以得到：

。于是可以从

中可以获取

中样本的标记。

1. 由于引入

，因此 Label Spreading 最终收敛的结果中，标记样本的标签可能会发生改变。这在一定程度上能对抗噪音的影响。 如：

意味着有 80% 的初始标记样本的标签会保留下来，有 20% 的初始标记样本的标签发生改变。

1. Label Spreading算法：
   • 输入：
     • 有标记样本集
     • 未标记样本集
     • 构图参数
     • 折中参数

   • 输出：未标记样本的预测结果
   • 步骤：
     • 根据下式，计算

     ：

   • 基于

   构造标记传播矩阵

   。 其中

   ，

   为矩阵

   的第

   行元素之和。

   • 构造非负的常量矩阵

   ：

   • 初始化

   ：

   • 初始化
   • 迭代，迭代终止条件是

   收敛至

   。 迭代过程为：

   • 构造未标记样本的预测结果：
   • 输出结果

3.3 性质

1. 其实上述算法都对应于正则化框架：

其中：

为正则化参数 。当

时，上式的最优解恰好为

• 上式第二项：迫使学得结果在有标记样本上的预测与真实标记尽可能相同。
• 上式第一项：迫使相近样本具有相似的标记。

这里的标记既可以是离散的类别，也可以是连续的值。

1. 虽然二类标签传播算法和多类标签传播算法理论上都收敛，而且都知道解析解。但是：
   • 对二类标签传播算法，矩阵求逆

   的算法复杂度是

   。如果未标记样本的数量

   很大，则求逆的过程非常耗时。

   • 对多类标签传播算法，矩阵求逆

   的算法复杂度是

   。如果样本总数量

   很大，则求逆的过程非常耗时。

   因此标签传播算法一般选择迭代算法来实现。

2. 图半监督学习方法在概念上相当清晰，且易于通过对所涉及矩阵运算的分析来探索算法性质。 缺点：
   • 在存储开销上较大，使得此类算法很难直接处理大规模数据。
   • 由于构图过程仅能考虑训练样本集，难以判断新的样本在图中的位置。因此在接收到新样本时，要么将其加入原数据集对图进行重构并重新进行标记传播，要么引入额外的预测机制。

3.4 标签传播与 PageRank

1. PageRank 算法用于对网页进行排名。它也是利用能量在有向图

中的流动来获得网页的重要性得分。

• 每个网页代表图

中的一个顶点，所有顶点的集合为

。

• 如果存在超链接，该超链接从顶点

对应的网页指向顶点

对应的网页，则存在一条有向边从顶点

指向顶点

。 所有的边的集合为

。

• 每个顶点都存储有能量，能量对应着网页的重要性得分。
• 对每个网页，设其能量为

：

• 用户以概率

选择一个超链接，进入下一个网页。这意味着有

的能量从当前顶点流失，流向下一个网页。

• 用户以概率

随机选择一个网页。这意味着有

的能量从当前顶点流失，流向全局能量池。同时有

的能量流入当前顶点，其中

是系统中所有顶点的总能量，

为顶点数量。 这是因为每个顶点都有

比例的能量流入全局能量池，则全局能量池的流入能量为

。而全局能量池的能量又平均流入到每个顶点中，则每个顶点从全局能量池得到的能量为

。

• 当系统取得平衡时，满足以下条件：
  • 全局能量池的流入、流出能量守恒。
  • 每个顶点的流入、流出能量守恒。
  • 系统所有顶点的总能量为常数。

1. 假设

，即系统所有顶点的总能量恒定为 1 。对给定的顶点

，假设其能量为

。

• 流出能量为：

。

• 流入能量为：

。其中

为能量从顶点

流向顶点

的概率。

则顶点

的净入能量为：

。 考虑所有顶点，令

，

，

，则系统每个顶点净流入能量组成的向量为：

当系统稳定时，每个顶点的净流入能量为 0 。因此有：

。

1. 考虑到所有顶点的总能量恒定为 1，则有

。 定义矩阵

为：

则有：

。因此有：

。 令

，则有

。此时的

就是对应于

的特征值为 1 的特征向量（经过归一化使得满足的总能量恒定为 1）。

3.5 标签传播与社区发现

1. 设图

，社区发现就是在图

中确定

个社区

，其中满足

。 若任意两个社区的顶点集合的交集均为空，则称

为非重叠社区，此时等价于聚类。否则称作重叠社区，此时一个顶点可能从属于多个社区。

1. 社区划分的好坏是通过考察当前图的社区划分，与随机图的社区划分的差异来衡量的。
   • 当前图的社区划分：计算当前图的社区结构中，内部顶点的边占所有边的比例 ：

   。 其中：

   表示顶点

   与顶点

   之间的边的权重，

   表示图

   中所有边的权重之和

   。

   表示顶点

   所属的社区，

   表示顶点

   所属的社区。

   函数定义为：

   • 因为

   ，因此每条边被计算了两次，所以系数为

   。

   它可以简化为：

   ，其中

   表示社区

   中所有内部边的总权重。

   • 随机图的社区划分：计算随机图的社区结构中，内部顶点的边占所有边的比例的期望。 随机图是这样生成的：每个顶点的度保持不变，边重新连接。 记顶点

   和

   之间的边的期望权重为

   ，则它满足下列条件：

   • 因为每个顶点的度不变，则最终总度数不变。即：

   。

   • 对每个顶点，它的度保持不变。即：

   。其中

   表示顶点

   的度。

   • 随机连边时，一个边的两个顶点的选择都是独立、随机的。因此对于

   ，选到

   的概率与

   有关，选到

   的概率与

   有关。根据独立性有：

   ，其中

   为某个映射函数。

   根据

   ，以及

   有：

   。 由于

   不包含

   ，因此

   与

   是倍乘关系。不妨假设

   ，其中

   为常量。则有：

   考虑到

   ，则有：

   。因此有：

   因此有：

   。 因此随机图的社区结构中，内部顶点的边占所有边的比例的期望为：

2. 定义modularity 指标为

：

它就是：当前网络中连接社区结构内部顶点的边所占的比例，与另外一个随机网络中连接社区结构内部顶点的便所占比例的期望相减，得到的差值。用于刻画社区划分的好坏。

• 第一项：

• 第二项：

因此，经过化简之后为：

其中：

表示社区

中所有内部边的总权重

。

表示社区

中所有顶点的度之和

。

表示社区

的内部顶点的度数之和，占总权重的比例。

也可以表示为：

，其中

表示社区

与其它所有社区之间的边的数量。

的值在 (-1,1) 之间。

• 当社区之间不存在边的连接时，

最大。

• 当每个点都是一个社区时，

最小。

3.5.1 Fast Unfolding

1. Fast Unfolding 算法是基于modularity 的社区划分算法。 它是一种迭代算法，每一步3迭代的目标是：使得划分后整个网络的 modularity 不断增大。
2. Fast Unfolding 算法主要包括两个阶段：
   • 第一阶段称作 modularity optimization：将每个顶点划分到与其邻接的顶点所在的社区中，以使得 modularity 不断增大。 考虑顶点

   ，设其邻接顶点

   位于社区

   中。

   • 未划分之前，顶点

   是一个独立的社区，它对

   的贡献为：

   。因为该社区只有一个顶点，因此所有顶点的度之和就是

   。

   • 未划分之前，社区

   对于

   的贡献为：

   。

   • 划分之后，除了社区

   与顶点

   之外，所有社区、顶点在划分前后保持不变，因此

   的变化为：

   其中

   分别表示划分之后社区

   的所有内部边的总权重、所有顶点的度之和。

   设顶点

   与社区

   相连的边的度数之和为

   （可能

   有多条边与

   相连） ，则有：

   。 由于顶点

   现在成为社区

   的内部顶点，因此

   。 因此有：

   • 如果

   ，则将顶点

   划入到社区

   中。

   • 如果

   ，则顶点

   保持不变。

   • 第二阶段称作 modularity Aggregation：将第一阶段划分出来的社区聚合成一个点，这相当于重新构造网络。

   重复上述过程，直到网络中的结构不再改变为止。

3. Fast Unfolding 算法：
   • 输入：
     • 数据集

   • 输出：社区划分

   。

   • 算法步骤：
     • 构建图：根据

     构建图

     。

     • 初始化社区：构建

     个社区，将每个顶点划分到不同的社区中。 此时每个社区有且仅有一个顶点。

     • 迭代，迭代停止条件为：图保持不变 。迭代步骤为：
       • 遍历每个顶点： 随机选择与其相连的顶点的社区，考察

       。如果

       ，则将该顶点划入到该社区中；否则保持不变。

       • 重复上述过程，直到不能再增大modularity 为止。
       • 构造新的图：将旧图中每个社区合并为新图中的每个顶点，旧社区之间的边的总权重合并为新图中的边的权重。 然后重复执行上述两步。

4. 对于顶点

，在考察

时，可以遍历与其相连的所有顶点所属的社区，然后选择最大的那个

。

1. 上述算法是串行执行：逐个选择顶点，重新计算其社区。在这个过程中其它顶点是不能变化的。 事实上可以将其改造为并行算法，在每一步迭代中同时更新多个顶点的信息。
2. Fast Unfolding 算法的结果比较理想，对比LPA 算法会更稳定。另外Fast Unfolding 算法不断合并顶点并构造新图，这会大大减少计算量。

3.5.2 LPA

1. Usha 等人于2007年首次将标签传播算法用于社区发现。 不同于半监督学习，在社区发现中并没有任何样本的标注信息，这使得算法不稳定，可能得到多个不同的社区划分结果。
2. 标签传播算法在迭代过程中，对于顶点

，会根据它的邻居顶点更新

的社区。更新规则为：

的邻居顶点中，哪个社区出现最多，则顶点

就属于哪个社区。 如果多个社区出现的次数都是最多的，则随机选择一个。

1. 标签传播算法：
   • 输入：
     • 数据集

   • 输出：社区划分

   。

   • 算法步骤：
     • 构建图：根据

     构建图

     。

     • 初始化：为每个顶点指定一个唯一的标签。
     • 迭代，迭代停止条件为社区划分收敛。迭代步骤为：
       • 随机打乱顶点的顺序。
       • 遍历每个顶点

       ，设置顶点

       的标签为：

       其中

       表示顶点

       的邻居顶点集合，

       表示顶点

       的标签，

       表示示性函数。

       • 判断是否收敛。收敛条件为：遍历每个顶点

       ，满足：

       即：顶点

       的邻居顶点集合中，标签为

       的点的个数最多。 之所以取 = 是因为：可能出现个数一样多的情况，这时也是满足条件的。

2. 标签传播算法的优点是：简单、高效、快速。缺点是每次迭代结果不稳定，准确率不高。
3. 标签传播算法中，顶点的标签有同步更新和异步更新两种方式。
   • 同步更新（假设更新次数为

   ）：

   同步更新方法在二分图中可能出现震荡的情况，如下图所示。

   • 异步更新：

   为顶点

   的最新的标签值。如果它最近的更新是在第

   轮，则

   ；如果它最近的更新是在第

   轮，则

   。 异步更新可以保证收敛，因此标签传播算法采用异步的策略更新顶点的标签，并在每次迭代之前对顶点重新进行随机排序从而保证顶点是随机遍历的。

4. 标签传播算法的时间复杂度为

，空间复杂度为

。因此标签传播算法具有线性的时间复杂度并且可以很好地适应大规模社区的检测。 它既不需优化预定义的目标函数，也不需要关于社区的数量和规模等先验信息。

3.5.3 SLPA

1. SLPA 由Jierui Xie 等人于 2011 年提出，它是一种重叠型社区发现算法。通过设定参数，也可以退化为非重叠型社区发现算法。
2. SLPA 与LPA 的重要区别：
   • SLPA 引入 Listener 和 Speaker 的概念。其中Listener 就是待更新标签的顶点， Speaker 就是该顶点的邻居顶点集合。 在LPA 中，Listener 的标签由 Speaker 中出现最多的标签决定。而SLPA 中引入了更多的规则。
   • SLPA 会记录每个顶点的历史标签序列。假设更新了

   次，则每个顶点会保存一个长度为

   的序列。 当迭代停止之后，对每个顶点的历史标签序列中各标签出现的频率作出统计，按照某一给定的阈值

   过滤掉那些频率小的标签，剩下的就是该顶点的标签，通常会有多个标签。

3. SLPA 算法：
   • 输入：
     • 数据集
     • 迭代步数
     • 标签频率阈值
     • Speaker rule
     • Listener rule

   • 输出：社区划分

   。

   • 算法步骤：
     • 构建图：根据

     构建图

     。

     • 初始化：为每个顶点分配一个标签队列；为每个顶点指定一个唯一的标签，并将标签加入到该顶点的标签队列中。
     • 迭代

     步。迭代步骤为：

     • 随机打乱顶点的顺序。
     • 遍历每个顶点

     ，将顶点

     设置为Listener， 将顶点

     的邻居顶点都设置为Speaker 。

     • Speaker 根据Speaker rule 向Listener 发送消息。 Speaker rule为发送规则，如：Speaker 从它的标签队列中发送最新的标签、或者Speaker 从它的标签队列中随机选择一个标签发送（标签选择的概率等于标签队列中各标签出现的频率）。
     • Listener 接收消息，并根据Listener rule 更新标签，并将最新的标签加入到它的标签队列中。 Listener rule 为接收规则。如：Listener 选择接受的标签中出现最多的那个作为最新的标签。
     • 遍历每个顶点

     ，将顶点

     的标签队列中，标签出现频率低于

     的标签丢弃。标签队列中剩下的标签就是顶点

     的标签（可能有多个）。

四、基于分歧的方法

1. 基于分歧的方法disagreement-based methods使用多个学习器，学习器之间的分歧disagreement对未标记数据的利用至关重要。 协同训练co-traning是此类方法的重要代表。它最初是针对多视图multi-view数据设计的，因此也被视作多视图学习multi-view learning的代表。

4.1 数据视图

1. 在不少现实应用中，一个数据对象往往同时拥有多个属性集attribute-set。每个属性集就构成了一个视图。
2. 假设数据集为

， 其中

。属性集合

。假设属性集合划分为

，其中：

即将属性划分为两个属性集，前

个属性为第一个属性集，后

个属性属于第二个属性集。

• 原始样本

被划分为两个属性向量

，它们分别属性这两个属性集。

这样的数据就是多视图数据，每个属性集都是一个视图。

如： <身高、体重、年龄、学历、爱好、工作> 可以划分为两个属性集： <身高、体重、年龄>以及<学历、爱好、工作> 。

1. 假设不同视图具有相容性compatibility：即其所包含的关于输出空间

的信息是一致的。 令

为从第一个属性集判别的标记空间，

为从第二个属性集判别的标记空间，则有

。 注意：这里仅要求标记空间相同，并没有要求每个标记相同。

4.2 协同训练算法

1. 协同训练充分利用了多视图的相容互补性。
2. 假设数据拥有两个充分且条件独立视图。
   • 充分：指每个视图都包含足以产生最优学习器的信息。
   • 条件独立：指在给定类别标记条件下，两个视图独立。

   此时，可以用一个简单的办法来利用未标记数据：

   • 首先在每个视图上，基于有标记样本，分别训练出一个分类器。
   • 然后让每个分类器分别去挑选自己最有把握的未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新。
   • 该“ 互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或者到达指定的迭代轮数为止。

   注意：

   • 如果在每轮学习中都考察分类器在所有未标记样本上的分类置信度，则会有很大的计算开销。因此在算法中使用了未标记样本缓冲池。
   • 分类置信度的估计因基学习算法而异。

3. 协同训练算法：
   • 输入：
     • 有标记样本集
     • 未标记样本集
     • 缓冲池大小
     • 每轮挑选的正例数量
     • 每轮挑选的反例数量
     • 基学习算法
     • 学习轮数

   • 输出：未标记样本的预测结果
   • 步骤：
     • 从

     中随机抽取

     个样本构建缓冲池

     • 从

     中分别构建：

     分别表示第一视图有标记数据集、第二视图有标记数据集：

     • 开始迭代，迭代终止条件是：迭代收敛或者迭代次数达到

     。迭代过程为：

     • 从

     中分别构建（其中

     为其元素个数）：

     分别表示第一视图缓冲数据集、第二视图缓冲数据集：

     • 考察视图一：
       • 利用

       训练

       得到分类器

       。

       • 然后考察

       在

       上的分类置信度。挑选

       个正例置信度最高的样本

       、 挑选

       个反例置信度最高的样本

       。

       • 然后将

       的视图二标记为正例，将

       的视图二标记为反例：

     这里并没有简单的将

     标记为正例、

     标记为反例。而是标记它们对立的那个视图，帮助对方视图增加标记数据。

     ，更新

     。此时

     会缩小，因为有部分样本从视图一中获得了标记信息。

     • 考察视图二：
       • 利用

       训练

       得到分类器

       。

       • 然后考察

       在 上

       的分类置信度。挑选

       个正例置信度最高的样本

       、 挑选

       个反例置信度最高的样本

       。

       • 然后将

       的视图一标记为正例，将

       的视图一标记为反例：

     。

     • 如果

     在训练前后，均未发生改变，则迭代收敛。否则继续向下执行。

     如何判断是否发生改变？通常可以考察它们的预测结果是否一致

     • 更新

     ：

     • 补充

     ：从

     中随机抽取

     个样本加入

     ，同时

     中移除这

     个样本。 这意味着：

     越来越大、

     越来越小。

   • 最终得到分类器

   。将这两个分类器用于

   即可得到未标记样本的预测结果：

   。

4.3 性质

1. 协同训练过程虽然简单，但是理论证明：若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。
   • 不过视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度没有那么大。
   • 但研究表明，即便在更弱的条件下，协同训练仍可以有效提升弱分类器的性能。

2. 协同训练算法本身是为多试图数据而设计的，但此后出现了一些能在单视图数据上使用的变体算法。
   • 它们或是使用不同的学习算法，或是使用不同的数据采样，甚至使用不同的参数设置来产生不同的学习器，也能有效利用未标记数据来提升性能。
   • 后续理论研究表明，此类算法事实上无需数据拥有多试图，仅需弱学习器之间具有显著的分歧（或者差异），即可通过相互提供伪标记样本的方式来提升泛化性能。 而不同视图、不同算法、不同数据采样、不同参数设置等，都是产生差异的渠道，而不是必备条件。

3. 基于分歧的方法只需要采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、使用范围较为广泛。
   • 为了使用此类方法，需要能生成具有显著分歧、性能尚可的多个学习器。
   • 但当有标记样本较少，尤其是数据不具有多试图时，要做到这一点并不容易，需要巧妙的设计。

五、半监督聚类

1. 聚类是一种典型的无监督学习任务，然而在现实聚类任务中，往往能够获取一些额外的监督信息。 于是可以通过半监督聚类semi-supervised clustering来利用监督信息以获取更好的聚类效果。
2. 聚类任务中获得的监督信息大致有两种类型：
   • 第一类是必连must-link与勿连cannot-link约束：
     • 必连：指样本必属于同一个簇。
     • 勿连：指样本必不属于同一个簇。

   • 第二类是：少量的有标记样本。

5.1 约束 k 均值算法

1. 约束

均值算法Constrained-k-means 是利用第一类监督信息的代表。

1. 给定样本集

， 以及必连关系集合

和勿连关系集合

，则：

， 表示

与

必属于同簇。

， 表示

与

必不属于同簇。

约束

均值算法是

均值算法的扩展，它在聚类过程中要确保

与

中的约束得以满足，否则将返回错误提示。

1. 约束

均值算法：

• 输入：
  • 必连关系集合
  • 勿连关系集合
  • 聚类簇数

• 输出：聚类簇划分

• 算法步骤：
  • 从

  中随机选取

  个样本作为初始均值向量

  • 迭代：
    • 初始化每个簇 ：
    • 对每个样本

    ， 执行下列操作：

    • 初始化可选的簇的集合为
    • 计算

    与各均值向量的距离

    • 找出

    且

    最小的

    ，设此时

    ，即

    最小，则考察将

    划入簇

    是否会违背

    与

    中的约束：

    • 若不违背，则

    划入簇

    ：

    • 若违背，则从

    中移除

    ， 继续找出

    且

    最小的

    。

    • 重复上述考察，直到

    或者

    划入簇

    不会违背

    与

    中的约束。 如果

    ，则返回错误提示。这意味着

    与所有的簇都发生冲突。

    • 更新均值向量：
  • 若更新均值向量前后，均值向量变化很小，则迭代结束。
  • 根据最新的均值向量划分

  ， 获得聚类簇划分

  。

5.2 约束种子 k 均值算法

1. 约束种子 k 均值Constrained Seed k-means算法是利用第二类监督的代表。
2. 给定样本集

。 假定少量的有标记样本为

，

为隶属于第

个聚簇的样本。 直接将

中的样本作为种子，用它们初始化

均值算法的

个聚类中心，并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系，这样就得到了约束种子

均值算法。

1. 约束种子

均值算法：

• 输入：
  • 少量有标记样本
  • 聚类簇数

• 输出：聚类簇划分

• 算法步骤：
  • 利用有标记样本集合

  初始化均值向量：

• 迭代：
  • 初始化每个簇：
  • 将有标记样本集合

  中的每个样本

  分别添加到对应的簇中

  。

  • 对未标记样本集合

  中的每个样本

  ，将它划分为距离该样本最近的簇中。其中的距离是样本和簇均值向量的距离。

  • 更新簇均值向量：

• 若更新均值向量前后，均值向量变化很小，则迭代结束。

• 根据最新的均值向量划分

， 获得聚类簇划分

。

六、 总结

1. 各种半监督学习算法的比较：
   • 生成式半监督学习方法需要充分可靠的领域知识才能确保模型不至于太坏。
   • 非监督SVM目标函数非凸，因此有不少工作致力于减轻非凸性造成的不利影响。
   • 图半监督学习方法，图的质量极为重要。
   • 基于分歧的方法将集成学习与半监督学习联系起来。
2. 半监督学习在利用未标记样本后并非必然提升泛化性能，在有些情况下甚至会导致性能下降。
   • 对生成式方法，原因通常是模型假设不准确。因此需要依赖充分可靠的领域知识来设计模型。
   • 对半监督SVM，原因通常是训练数据中存在多个“低密度划分”，而学习算法可能做出不利的选择。 S4VM通过优化最坏情况下性能来综合利用多个低密度划分，提升了此类技术的安全性。
   • 更一般的安全半监督学习仍然是未决的难题。 安全是指：利用未标记样本后，能确保返回性能至少不差于仅利用有标记样本。