chapter 2是标签传播演算法，然后通过高斯随机场和调和函数来再次阐释标签传播。标签传播的解释有很多角度，比如随机行走（random walk）、电压电流网路(Electric Networks)、也可以是图的最小割的soft version。其中作者的Combining Active Learning and Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions论文获得了ICML10年经典论文奖。

---

Chapter 2：标签传播 Label Propagation

我们把问题看成在图上标签传播的形式，根据节点的相近性一个节点的标签传播到它的邻居节点。在这个过程中我们固定已标记数据的标签。因此已标记数据就像源头一样流出通过未标记数据的标签。

2.1 问题设定

设已标记数据为 , ，未标记数据为 ，通常 。设 。 分别表示已标记和未标记数据。假定类别数量 已知，所有的类都在已标记数据中。

直观上我们希望相近的数据点有相同的标签。我们创造一个图，图中节点代表数据点（包括已标记和未标记）。节点 之间的边代表他们的相似程度。我们假设图是全连接的，权重为 , 为控制带宽的超参数。

2.2 演算法流程

我们通过边来传播标签，更大的边允许标签更容易通过。定义一个 概率转移矩阵 :

其中 是从节点 到 的概率。定义一个 标签矩阵 ，第 行是 的一个指示向量。我们计算节点的"软"标签 。 是一个 的矩阵，行可以理解为标签之间的概率分布。 的初始化不重要，整个标签传播演算法过程如下：

1. 传播：Propagate
2. 固定已标记数据：Clamp the labeled data
3. 重复步骤1直到 收敛。

在第一步中所有节点将它们的标签传向它们的邻居。第二步非常关键：我们想从已标记数据那里获得固定持久的标签源，因此不是让初始的标签逐渐减弱消失，而是用 固定它们。有了这个从已标记节点的不变「动力（push）」，类边界就会继续推进通过高密度区域并在低密度间隔处停止。如果用这种结构用来做分类任务，那么这个演算法可以利用未标记数据来学习。

2.3 收敛性

这种演算法最后会收敛到一个简单的解。令 。由于将 固定为了 ，我们只对 感兴趣。我们把P切分为已标记和未标记的子矩阵来表示：

演算法中可以表示为：

即：

其中： 是 的初始值， 。因为 是行规范化的， 是 的子矩阵，因此有：

从而：

因此 收敛到0意味著 。因此初始值 不重要。

显然有： 是一个固定不动的点。因此我么的迭代演算法的解是这个不动点，无需迭代的传播就能直接求得标签传播问题的解。

需要注意当 可逆的时候解是有效的。这个条件满足的话，直观上图中的每个连接组件都至少有一个已标记点。

2.4示例

我们在两个数据集上展现标签传播的性质。图2.1(a)中数据有三个类，每个是横窄带状分布。数据点为均匀的从带中采样而得。开始有三个标记点和178个未标记点。在1NN（1-nearest-neighbor）演算法中，忽略了未标记数据因此得到了2.1(b)结果。标签传播演算法得到的结果为2.1(c),标签沿著横向带状传播。

图2.2是三维螺旋结构的数据集，有两个类。图中有2个已标记数据点和184个未标记数据点。同样1NN的结果不如标签传播。

---

Chapter 3 高斯随机场和调和函数（Gaussian Random Fields and Harmonic Functions）

在这一章我们将基于概率框架的标签传播形式化。不失一般性，假定二分类 , 我们假设给定 权重矩阵 ， 中的项都是对称非负的，但 不一定是半正定的。

4.1 高斯随机场（Gaussian Random Fields）

我们的方法是在图上定义一个连续随机场。首先定义一个实值函数： 。 可以是负的也可以大于1。直观上我们认为相似的未标记点具有相似的标签，从这点考虑可以选择二次能量函数：

显然 可以通过常数函数最小化。但对于已经观测到的点我们设 。通过高斯随机场我们假设函数 的概率分布为

是「温度颠倒」参数，

是配分函数，作用是为了归一化。

我们感兴趣的是推断问题 或者均值 。

分布 非常像离散状态的标准马尔科夫随机场。实际上区别就是具有实值关系。但这个关系可以大大简化推断问题。因为二次能量函数， 都是多维高斯分布。这就是为什么把 称为高斯随机场。边缘分布 是单变数高斯分布，具有闭式解。

4.2拉普拉斯运算元（The Graph Laplacian）

现在我们介绍一个重要的量：combinatorial Laplacian 。设 是度矩阵定义请参考这里其中 是节点 的度。拉普拉斯运算元定义为：

利用拉普拉斯运算元可将能量函数简写，可以证明：

高斯随机场可以写为：

在一个多维高斯分布中扮演精度矩阵的角色。如果 是对称非负的话，就总是半正定的。

4.3调和函数（Harmonic Functions）

不难看出最小化能量函数 是harmonic，也就是说在未标记数据点 上满足 ，在已标记数据点上等于 。我们用 来代表这个调和函数。

调和性质意味著在每个未标记数据点 的值 是它在图中的邻居的平均值：

由于调和函数最大原理（ 如果调和函数不是一个常数，那么它的最大最小值只能在边界上），故 是独一无二的并且满足 ,注意对 有 .

为了计算调和解，我们把矩阵 分解为四块：

由 和约束 可得调和解：

最后一项和等式（2.11）一样，其中 是图上的传播矩阵。chapter2里面的标签传播演算法实际上计算的是调和函数。

调和函数最小化能量是（4.2）的众数，因为（4.2）定义了一个单峰各向同性的高斯分布，众数也是均值。

---

Chapter 5 Active Learning

5.1 结合半监督学习和主动学习（Combing Semi-Supervised and Active Learning）

高斯随机场和调和函数框架允许将半监督啊学习和主动学习结合起来。每次从未标记数据中贪婪选择点查询，按照最小化调和能量最小函数的风险为准则。这个风险是贝叶斯分类器泛化误差的估计，可以通过矩阵的方法计算。基于调和函数 我们定义贝叶斯分类器的真实风险 为：

是贝叶斯决策规则，阈值为0.5，大于0.5为1否则为1. 是未知的真实标签在结点 的分布，因此 是可计算的。假设我们可以用高斯随机场的均值来估计未知分布 :

直观上，在图上一次random walk为1的概率是 ,我们的假设是我们可以近似这个分布，使用在每个结点使用一个有偏硬币，正面朝上的概率为 。有了这个假设可以计算估计风险：

如果查询一个未标记结点 ，就会得到一个结果 。把这个点加入训练集中重新训练，高斯随机场和均值函数也会改变。设新的调和函数为 。估计风险也会变为：

因为我们不知道 的真实标记，我们再一次假设 。查询过结点 之后的期望估计风险为：

这里我们使用的选择防范是最小化期望估计风险的贪婪选择：

在这个过程中，我们在把 加入到当前已标记训练集中后需要计算调和函数 。这是一个重复训练问题并且通常需要密集计算。但对于高斯随机场和调和函数存在一个有效的方法。已知调和函数的解为：

如果我们固定结点 的值 解会是什么？这和给定值 计算所有未标记数据条件分布相同。在高斯场中，未标记数据的条件是多维高斯分布 。一旦固定 ，条件均值为（参考原论文的附录A）：

是未标记数据的Laplacian逆矩阵的第k列， 是其第k个对角元素。当计算调和函数 的时候这两项已经计算过了。

主动学习演算法流程如下图：

推荐阅读：

相关文章