半监督学习

1. 给定有标记样本集合 $\mathbb D_l=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_l,y_l)\}$ ，和未标记样本集合 $\mathbb D_u=\{(\mathbf{\vec x}_{l+1},y_{l+1}),(\mathbf{\vec x}_{l+2},y_{l+2}),\cdots,(\mathbf{\vec x}_{l+u},y_{l+u})\}$ ，其中 $l \ll u$ 。

   学习器自动地利用未标记的 $\mathbb D_u$ 来提升学习性能，这就是半监督学习semi-supervised learning。

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

   因此可以通过专家人工标注少量的样本，然后采用半监督学习。

3. 虽然未标记样本集 $\mathbb D_u$ 没有直接包含标记信息，但是如果假设 $\mathbb D_u$ 与带 $\mathbb D_l$ 从同样的数据源独立同分布采样而来，则 $\mathbb D_u$ 所包含的关于数据分布的信息对建立模型是有好处的。

4. 要利用未标记样本，必然需要对未标记样本的分布与已标记样本的分布的关联做出假设。

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

5. 半监督学习可以划分为：纯pure半监督学习和直推学习transduction learning 。

   • 纯半监督学习：假定训练数据中的未标记样本集 $\mathbb D_u$ 并非待预测的数据。

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

   • 直推学习：假定学习过程中考虑的未标记样本集 $\mathbb D_u$ 就是待预测的数据，学习的目标就是在 $\mathbb D_u$ 上获取最优泛化性能。

     直推学习是封闭性的，它学得的模型仅仅是针对学习过程中的未标记样本集 $\mathbb D_u$ 。

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

1. 生成式generative methods 半监督学习方法：直接基于生成式模型的方法。

2. 生成式半监督学习方法假设所有数据（无论是否有标记），都是由同一个潜在的模型生成的。

   • 该假设使得能够通过潜在模型的参数将未标记样本与学习目标联系起来。
   • 未标记样本的标记可以视作模型的缺失参数，通常可以基于EM算法进行极大似然估计求解。

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

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

1. 给定样本 $\mathbf{\vec x}$ ，其真实类别标记为 $y \in \mathcal Y=\{1,2,\cdots,K\}$ 。

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

   $$p(\mathbf{\vec x})=\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)$$

   来产生的。其中：

   • $p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)$ 是样本 $\mathbf{\vec x}$ 的第 $k$ 个高斯混合成分的概率。
   • $\vec \mu_k,\Sigma_k$ 为该高斯混合成分的参数。
   • 混合系数 $\alpha_k \ge 0, \sum_{k=1}^{K}\alpha_k=1$ 。

2. 令 $f(\mathbf{\vec x})\in \mathcal Y$ 为模型 $f$ 对 $\mathbf{\vec x}$ 的预测标记，$\Theta \in \{1,2,\cdots,K\}$ 表示样本 $\mathbf{\vec x}$ 隶属的高斯混合成分。

   根据最大化后验概率，有：

   $$f(\mathbf{\vec x})=\arg\max_{j\in \mathcal Y}p(y=j\mid \mathbf{\vec x})$$

   • 考虑到 $p(y=j\mid \mathbf{\vec x})=\sum_{k=1}^{K}p(y=j,\Theta=k\mid \mathbf{\vec x})$， 则有：

     $$f(\mathbf{\vec x})=\arg\max_{j\in \mathcal Y}\sum_{k=1}^{K}p(y=j,\Theta=k\mid \mathbf{\vec x})$$

   • 由于 $p(y=j,\Theta=k\mid \mathbf{\vec x})=p(y=j\mid \Theta=k,\mathbf{\vec x})\cdot p(\Theta=k\mid \mathbf{\vec x})$， 则有：

     $$f(\mathbf{\vec x})=\arg\max_{j\in \mathcal Y}\sum_{k=1}^{K}p(y=j\mid \Theta=k,\mathbf{\vec x})\cdot p(\Theta=k\mid \mathbf{\vec x})$$

     • $p(\Theta=k\mid \mathbf{\vec x})$ 为已知样本 $\mathbf{\vec x}$ ，则它由第 $k$ 个高斯混合成分生成的后验概率

       $$p(\Theta=k\mid \mathbf{\vec x})=\frac{\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)}{\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)}$$

     • $p(y=j\mid \Theta=k,\mathbf{\vec x})$ 为已知 $\mathbf{\vec x}$ 由第 $k$ 个高斯混合成分生成，则其类别为 $j$ 的概率

3. 在 $f(\mathbf{\vec x})=\arg\max_{j\in \mathcal Y}\sum_{k=1}^{K}p(y=j\mid \Theta=k,\mathbf{\vec x})\cdot p(\Theta=k\mid \mathbf{\vec x})$ 中，$p(y=j\mid \Theta=k,\mathbf{\vec x})$ 需要知道样本的标记 $y$ ； 而 $p(\Theta=k\mid \mathbf{\vec x})$ 并不需要样本的标记。因此有标记和无标记的数据均可利用。

   因此通过引入大量的未标记数据，对 $p(y=j,\Theta=k\mid \mathbf{\vec x})$ 的估计可以由于数据量的增长而更为准确，于是上式的整体估计可能会更准确。

4. 给定标记样本集 $\mathbb D_l=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_l,y_l)\}$ ，和未标记样本集 $\mathbb D_u=\{ \mathbf{\vec x}_{l+1}, \mathbf{\vec x}_{l+2} ,\cdots, \mathbf{\vec x}_{l+u} \}$，其中 $l \ll u,\quad l+u=N$ 。

   假设所有样本独立同分布，且都是由同一个高斯混合模型 $p(\mathbf{\vec x})=\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)$ 生成的。

   • 高斯混合模型的参数 $\{(\alpha_k,\vec \mu_k,\Sigma_k), k=1,2,\cdots,K\}$ 采用极大似然法来估计。

   • $\mathbb D_l \bigcup\mathbb D_u$ 的对数似然是：

     $$\mathcal L=\sum_{(\mathbf{\vec x}_i,y_i)\in \mathbb D_l}\log\left(\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x}_i;\vec \mu_k,\Sigma_k)\cdot p(y_i\mid\Theta=k,\mathbf{\vec x}_i)\right) \\ +\sum_{\mathbf{\vec x}_i \in \mathbb D_u}\log\left(\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x}_i;\vec \mu_k,\Sigma_k)\right)$$

     • 第一项对数项中，为联合概率 $p(\mathbf{\vec x}_i,y_i)$ ：

       $$p(\mathbf{\vec x}_i,y_i)=p(y_i\mid \mathbf{\vec x}_i)p(\mathbf{\vec x}_i)=\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x}_i;\vec \mu_k,\Sigma_k)\cdot p(y_i\mid \Theta=k,\mathbf{\vec x}_i)$$

     • 第二项对数项中，为概率 $p(\mathbf{\vec x}_i)$ ：

       $$p(\mathbf{\vec x}_i)=\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x}_i;\vec \mu_k,\Sigma_k)$$

5. 高斯混合模型参数估计可以用EM算法求解。迭代更新步骤为：

   • E步：根据当前模型参数 $\{(\hat \alpha_k,\hat{\vec \mu_k},\hat \Sigma_k), k=1,2,\cdots,K\}$ 计算未标记样本 $\mathbf{\vec x}_i$ 属于各高斯混合成分的概率：
   $$\gamma_{i,k}=\frac{\hat \alpha_k p_k(\mathbf{\vec x}_i;\hat {\vec \mu_k},\hat \Sigma_k)}{\sum_{k=1}^{K}\hat \alpha_k p_k(\mathbf{\vec x}_i;\hat {\vec \mu_k},\hat\Sigma_k)}$$

   • M步：基于 $\gamma_{i,k}$ 更新模型参数。

     令 $l_k$ 为第 $k$ 类的有标记样本数目，则：

   $$\hat{\vec \mu_k}=\frac{1}{\sum_{\mathbf{\vec x}_i\in \mathbb D_u}\gamma_{i,k}+l_k}\left(\sum_{\mathbf{\vec x}_i\in \mathbb D_u} \gamma_{i,k}\mathbf{\vec x}_i+\sum_{(\mathbf{\vec x}_i,y_i)\in \mathbb D_l \;and\; y_i=k} \gamma_{i,k}\mathbf{\vec x}_i\right)\\ \hat \Sigma_k=\frac{1}{\sum_{\mathbf{\vec x}_i\in \mathbb D_u}\gamma_{i,k}+l_k}\left(\sum_{\mathbf{\vec x}_i\in \mathbb D_u} \gamma_{i,k}(\mathbf{\vec x}_i-\hat{\vec \mu_k})(\mathbf{\vec x}_i-\hat{\vec \mu_k})^{T}+\\ \sum_{(\mathbf{\vec x}_i,y_i)\in \mathbb D_l \;and\; y_i=k} \gamma_{i,k}(\mathbf{\vec x}_i-\hat{\vec \mu_k})(\mathbf{\vec x}_i-\hat{\vec \mu_k})^{T}\right)\\ \hat \alpha_k=\frac 1N\left(\sum_{\mathbf{\vec x}_i\in \mathbb D_u}\gamma_{i,k}+l_k\right)$$

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

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

   $$f(\mathbf{\vec x})=\arg\max_{j\in \mathcal Y}\sum_{k=1}^{K}p(y=j\mid \Theta=k,\mathbf{\vec x})\cdot p(\Theta=k\mid \mathbf{\vec x})\\ p(\Theta=k\mid \mathbf{\vec x})=\frac{\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)}{\sum_{k=1}^{K}\alpha_k p_k(\mathbf{\vec x};\vec \mu_k,\Sigma_k)}$$

   来对样本 $\mathbf{\vec x}$ 进行分类。

1.2 性质

1. 如果将上述过程中的高斯混合模型替换成其他模型，则可以推导出其他的生成式半监督学习方法。

2. 生成式半监督学习方法优点：方法简单，易于实现。在有标记数据极少的情况下，往往比其他方法性能更好。

   缺点：模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合，否则利用未标记数据反倒会降低泛化性能。

   在现实任务中往往很难事先做出准确的模型假设，除非拥有充分可靠的领域知识。

二、半监督 SVM

1. 半监督支持向量机Semi-Supervised Support Vector Machine：S3VM 是支持向量机在半监督学习上的推广。

2. 在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面；在考虑未标记样本之后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。

   如下图中，蓝色点为未标记样本，紫色点为正类样本，黄色点为负类样本。

   

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

2.1 TVSM

1. 半监督支持向量机中最著名的是 TSVM:Transductive Support Vector Machine。

   与标准SVM一样，TSVM也是针对二分类问题的学习方法。

2. TSVM试图考虑对未标记样本进行各种可能的标记指派label assignment：

   • 尝试将每个未标记样本分别作为正例或者反例。
   • 然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。
   • 一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

3. 给定标记样本集 $\mathbb D_l=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_l,y_l)\}$ ，和未标记样本集 $\mathbb D_u=\{ \mathbf{\vec x}_{l+1}, \mathbf{\vec x}_{l+2} ,\cdots, \mathbf{\vec x}_{l+u} \}$，其中 $l \ll u,\; l+u=N,\;y_i \in \{-1,+1\},i=1,2,\cdots,l$ 。

   TSVM学习的目标是：为 $\mathbb D_u$ 中的样本给出预测标记 $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T},\hat y_i \in \{-1,+1\},i=l+1,l+2,\cdots,N$ 使得：

   $$\min_{\mathbf{\vec w},b,\hat{\mathbf{\vec y}},\vec\xi} \frac 12 ||\mathbf{\vec w}||_2^{2}+C_l\sum_{i=1}^{l}\xi_i+C_u\sum_{i=l+1}^{N}\xi_i\\ s.t.\; y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=1,2,\cdots,l\\ \hat y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=l+1,l+2,\cdots,N\\ \xi_i \ge 0,\quad i=1,2,\cdots,N$$

   其中：

   • $(\mathbf{\vec w},b)$ 确定了一个划分超平面。

   • $\vec \xi$ 为松弛向量 ：

     • $\xi_i ,i=1,2,\cdots,l$ 对应于有标记样本。
     • $\xi_i ,i=l+1,l+2,\cdots,N$ 对应于未标记样本。

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

4. TSVM尝试未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解。因此通常情况下，必须考虑更高效的优化策略。

   TSVM 采用局部搜索来迭代地寻求上式的近似解。具体来说：

   • 首先利用有标记样本学得一个SVM：即忽略上式中关于 $\mathbb D_u$ 与 $\hat{\mathbf{\vec y}}$ 的项以及约束。

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

     • 此时 $\hat{\mathbf{\vec y}}$ 得到求解，将其代入上式即可得到一个标准SVM问题。于是求解可以解出新的划分超平面和松弛向量。
     • 注意到此时的未标记样本的伪标记很可能不准确，因此 $C_u$ 要设置为比 $C_l$ 小的值，使得有标记样本所起的作用更大。

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

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

   • ...

   • 标记指派调整完成后，逐渐增大 $C_u$ 以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直至 $C_u$ 达到指定阈值为止。

5. TSVM算法：

   • 算法输入：

     • 有标记样本集 $\mathbb D_l=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_l,y_l)\}$ ，其中 $y_i \in \{-1,+1\},i=1,2,\cdots,l$
     • 未标记样本集 $\mathbb D_u=\{ \mathbf{\vec x}_{l+1}, \mathbf{\vec x}_{l+2} ,\cdots, \mathbf{\vec x}_{l+u} \}$ ，其中 $l \ll u,\quad l+u=N$
     • 折中参数 $C_l,C_u$

   • 算法输出： 未标记样本的预测结果 $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T},\hat y_i \in \{-1,+1\},i=l+1,l+2,\cdots,N$

   • 算法步骤：

     • 用 $\mathbb D_l$ 训练一个 SVM_l

     • 用 SVM_l 对 $\mathbb D_u$ 中样本进行预测，得到 $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T}$

     • 初始化 $\tilde C_u$ ，其中 $\tilde C_u \ll C_u,\tilde C_u \gt 0$

     • 迭代，迭代终止条件为 $\tilde C_u \ge C_u$ 。迭代过程为：

       • 基于 $\mathbb D_l,\mathbb D_u,\hat{\mathbf{\vec y}},C_l,\tilde C_u$ ，求解下式，得到 $(\mathbf{\vec w},b),\vec \xi$：

         $$\min_{\mathbf{\vec w},b,\hat{\mathbf{\vec y}},\vec\xi} \frac 12 ||\mathbf{\vec w}||_2^{2}+C_l\sum_{i=1}^{l}\xi_i+\tilde C_u\sum_{i=l+1}^{N}\xi_i\\ s.t.\; y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=1,2,\cdots,l\\ \hat y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=l+1,l+2,\cdots,N\\ \xi_i \ge 0,\quad i=1,2,\cdots,N$$

       • 对于所有的一对标记指派为异类且很可能发生错误的未标记样本（其条件为：$\hat y_i\hat y_j \lt 0 \;\text{and}\; \xi_i \gt 0\;\text{and}\; \xi_j \gt 0 \;\text{and}\; \xi_i+\xi_j \gt 2$），执行下列操作：

         • 交换二者的标记：$\hat y_i=-\hat y_i,\quad \hat y_j=-\hat y_j$ 。

           该操作等价于交换标记，因为 $\hat y_i\hat y_j$ 异号，且其取值为 -1 或者 +1。

         • 基于 $\mathbb D_l,\mathbb D_u,\hat{\mathbf{\vec y}},C_l,\tilde C_u$，重新求解得到得到 $(\mathbf{\vec w},b),\vec \xi$ 。

       • 更新 $\tilde C_u= \min(2\tilde C_u,C_u,)$ 。这里采用简单的倍乘，也可以采用其它增长函数。

     • 迭代终止时，输出 $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T}$

6. 在对未标记样本进行指标指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类。这将对SVM的训练造成困扰。

   为了减轻类别不平衡性造成的不利影响，可对上述算法稍加改进：将优化目标中的 $C_u$ 项拆分为 $C_u^{+}$ 和 $C_u^{- }$ 两项，分别对应基于伪标记而当作正、反例使用的未标记样本。并在初始化时，令：

   $$C_u^{+}=\frac{u_-}{u_+}C_u^{- }$$

   其中 $u_-$ 和$u_+$ 分别为基于伪标记而当作反、正例而使用的未标记样本数。

2.2 性质

1. TSVM 最终得到的SVM 不仅可以给未标记样本提供了标记，还能对训练过程中未见的样本进行预测。

2. 在 TSVM 算法中，寻找标记指派可能出错的每一对未标记样本进行调整，这是一个涉及巨大计算开销的大规模优化问题。

   • 在论文《Large Scale Transductive SVMs》 中，约 2000 个未标记样本，原始TVSM 迭代收敛大约需要 1个小时。
   • 半监督SVM研究的一个重点是如何设计出高效的优化求解策略。由此发展成很多方法，如基于图核函数梯度下降的LDS算法，基于标记均值估计的meanS3VM算法等。

    

三、图半监督学习

3.1 标签传播算法

1. 给定一个数据集，可以将其映射为一个图，数据集中每个样本对应于图中的一个结点。若两个样本之间的相似度很高（或者相关性很强），则对应的结点之间存在一条边，边的强度正比于样本之间的相似度（或相关性）。

   将有标记样本所对应的结点视作为已经染色，而未标记样本所对应的结点尚未染色。于是半监督学习就对应于“颜色”在图上扩散或者传播的过程。这就是标记传播算法label propagation 。

2. 给定标记样本集 $\mathbb D_l=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_l,y_l)\},y_i\in \{-1,+1\}$ ，和未标记样本集 $\mathbb D_u=\{ \mathbf{\vec x}_{l+1}, \mathbf{\vec x}_{l+2} ,\cdots, \mathbf{\vec x}_{l+u} \}$，其中 $l \ll u,\quad l+u=N$ 。

   基于 $\mathbb D_l \bigcup \mathbb D_u$ 构建一个图 $\mathcal G=(\mathbb V,\mathbb E)$ 。其中

   • 结点集 $\mathbb V=\{\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_l, \mathbf{\vec x}_{l+1}, \mathbf{\vec x}_{l+2} ,\cdots, \mathbf{\vec x}_{l+u}\}$

   • 边集 $\mathbb E$ 的权重可以表示为一个亲和矩阵 affinity matirx $\mathbf W=(w_{i,j})_{N\times N}$，一般基于高斯函数，其定义为：

     $$w_{i,j}=\begin{cases} \exp\left(-\frac{||\mathbf{\vec x}_i-\mathbf{\vec x}_j||_2^{2}}{2\sigma^{2}}\right),& i \ne j\\ 0,&i=j \end{cases},\quad i,j\in \{1,2,\cdots,N\}$$

     其中 $\sigma \gt 0$ 是用户指定的高斯函数带宽参数。

     可以看到：

     • $w_{i,j}=w_{j,i}$ ，因此 $\mathbf W$ 为对称矩阵。
     • 图 $\mathcal G$ 是全连接的，任意两点之间都存在边。
     • 两个点的距离越近，说明两个样本越相似，则边的权重越大；距离越远，说明两个样本越不相似，则边的权重越小。
     • 权重越大说明样本越相似，则标签越容易传播。

3.1.1 能量函数

1. 假定从图 $\mathcal G=(\mathbb V,\mathbb E)$ 学得一个实值函数 $f:\mathbb V\rightarrow \mathbb R$， 其对应的分类规则为： $y_i=\text{sign}(f(\mathbf{\vec x}_i)), y_i \in \{-1,+1\}$。

   直观上看，相似的样本应该具有相似的标记，于是可以定义关于 $f$ 的能量函数energy function：

   $$E(f)=\frac 12 \sum_{i=1}^{N}\sum_{j=1}^{N}w_{i,j}\left(f(\mathbf{\vec x}_i)-f(\mathbf{\vec x}_j)\right)^{2}\\ =\frac 12 \sum_{i=1}^{N}\sum_{j=1}^{N} \left[w_{i,j}f(\mathbf{\vec x}_i)^{2}+w_{i,j}f(\mathbf{\vec x}_j)^{2}-2w_{i,j}f(\mathbf{\vec x}_i)f(\mathbf{\vec x}_j)\right]\\ = \frac 12\left[\sum_{i=1}^{N}\left(f(\mathbf{\vec x}_i)^{2}\sum_{j=1}^{N}w_{i,j}\right)+\sum_{j=1}^{N}\left(f(\mathbf{\vec x}_j)^{2}\sum_{i=1}^{N}w_{i,j}\right)-2\sum_{i=1}^{N}\sum_{j=1}^{N}w_{i,j}f(\mathbf{\vec x}_i)f(\mathbf{\vec x}_j)\right]$$

   • 两个点距离越远， $(f(\mathbf{\vec x}_i)-f(\mathbf{\vec x}_j))^{2}$ 平方级的增大，而 $w_{i,j}$ 指数级下降，因此 $w_{i,j}\left(f(\mathbf{\vec x}_i)-f(\mathbf{\vec x}_j)\right)^{2}$ 下降。

     因此能量函数 $E(f)$ 由距离较近的样本对决定。

   • 标签传播算法假定系统能量最小，即 $E(f)$ 最小。

     考虑到$E(f)$ 由距离较近的样本对决定，而 $w_{w,j}$ 是已知的量，因此算法倾向于使得：距离较近的样本具有相近的输出 。

2. 定义对角矩阵 $\mathbf D=\text{diag}(d_1,d_2,\cdots,d_N)$ ，其中 $d_i=\sum_{j=1}^{N}w_{i,j}$ 为矩阵 $\mathbf W$ 的第 $i$ 行元素之和。

   $d_i$ 的物理意义为：第 $i$ 个顶点的度（所有与它相连的边的权重之和）。因此 $\mathbf D$ 也称作度矩阵。

   $$\mathbf D=\begin{bmatrix} d_1&0&0&\cdots&0\\ 0&d_2&0&\cdots&0\\ 0&0&d_3&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&d_N\\ \end{bmatrix}$$

   定义 $\mathbf{\vec f}=(f(\mathbf{\vec x}_1),\cdots,f(\mathbf{\vec x}_l),f(\mathbf{\vec x}_{l+1}) ,\cdots,f(\mathbf{\vec x}_{N}))^{T}$ 为函数 $f$ 在所有样本上的预测结果。 其中：

   • $\mathbf{\vec f}_l=(f(\mathbf{\vec x}_1),f(\mathbf{\vec x}_2),\cdots,f(\mathbf{\vec x}_l))^{T}$ 为函数 $f$ 在有标记样本上的预测结果。
   • $\mathbf{\vec f}_u=(f(\mathbf{\vec x}_{l+1}) ,f(\mathbf{\vec x}_{l+2}),\cdots,f(\mathbf{\vec x}_{l+u}))^{T}$ 为函数 $f$ 在未标记样本上的预测结果。

   结合 $\mathbf D$ 的定义以及 $\mathbf W$ 的对称性，有：