机器学习-半监督学习

半监督学习

推荐 https://www.huaxiaozhuan.com/统计学习/chapters/12_semi_supervised.html ，太强了，太强了

啥是半监督学习（Semi-supervised Learning）

让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习，现实生活中，我们很容易收集无标签数据，但有标签数据并不容易收集，所以我们需要一种模型，以少量标签数据作为参照，利用大量无标签数据进行训练，得到一个更高效的学习器。

也可以这样理解，半监督学习就是监督学习和无监督学习的折中版，而监督学习的核心就是回归，无监督学习的核心是分类，半监督学习一般的目标是找到一个函数迎合（也就是回归任务），然后用分类任务的信息去优化回归函数。

给定有标记样本集合 $\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。
半监督学习的现实需求非常强烈，因为现实中往往能够容易地收集到大量未标记样本，但是对其标记需要耗费大量的人力、物力。如：在医学影像分析上，对影像的疾病标记需要专家人工进行。
因此可以通过专家人工标注少量的样本，然后采用半监督学习。
虽然未标记样本集 $\mathbb D_u$ 没有直接包含标记信息，但是如果假设 $\mathbb D_u$ 与带 $\mathbb D_l$ 从同样的数据源独立同分布采样而来，则 $\mathbb D_u$ 所包含的关于数据分布的信息对建立模型是有好处的。
要利用未标记样本，必然需要对未标记样本的分布与已标记样本的分布的关联做出假设。
- 最常见的假设是聚类假设cluster assumption：假设数据存在簇结构，同一个簇的样本属于同一个类别。
- 另一种常见假设是流形假设manifold assumption：假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。其中，邻近的程度用相似度来刻画。
- 流形假设可以看作是聚类假设的推广，但流形假设对于输出值没有限制（可以为类别，也可以为实数），因此比聚类假设的适用程度更广，可用于多类型的学习任务。
- 无论聚类假设还是流形假设，本质都假设是：相似的样本有相似的输出 。
半监督学习可以划分为：纯pure半监督学习和直推学习transduction learning 。
- 纯半监督学习：假定训练数据中的未标记样本集 $\mathbb D_u$ 并非待预测的数据。
  纯半监督学习是开放性的，它学得的模型能够适用于额外的未观测数据。
- 直推学习：假定学习过程中考虑的未标记样本集 $\mathbb D_u$ 就是待预测的数据，学习的目标就是在 $\mathbb D_u$ 上获取最优泛化性能。
  直推学习是封闭性的，它学得的模型仅仅是针对学习过程中的未标记样本集 $\mathbb D_u$ 。

一般，半监督学习算法可分为：self-training（自训练算法）、Graph-based Semi-supervised Learning（基于图的半监督算法）、Semi-supervised supported vector machine（半监督支持向量机，S3VM）。简单介绍如下：

1.简单自训练（simple self-training）：用有标签数据训练一个分类器，然后用这个分类器对无标签数据进行分类，这样就会产生伪标签（pseudo label）或软标签（soft label），挑选你认为分类正确的无标签样本（此处应该有一个挑选准则），把选出来的无标签样本用来训练分类器。

2.协同训练（co-training）：其实也是 self-training 的一种，但其思想是好的。假设每个数据可以从不同的角度（view）进行分类，不同角度可以训练出不同的分类器，然后用这些从不同角度训练出来的分类器对无标签样本进行分类，再选出认为可信的无标签样本加入训练集中。由于这些分类器从不同角度训练出来的，可以形成一种互补，而提高分类精度；就如同从不同角度可以更好地理解事物一样。

3.半监督字典学习：其实也是 self-training 的一种，先是用有标签数据作为字典，对无标签数据进行分类，挑选出你认为分类正确的无标签样本，加入字典中（此时的字典就变成了半监督字典了）

4.标签传播算法（Label Propagation Algorithm）：是一种基于图的半监督算法，通过构造图结构（数据点为顶点，点之间的相似性为边）来寻找训练数据中有标签数据和无标签数据的关系。是的，只是训练数据中，这是一种直推式的半监督算法，即只对训练集中的无标签数据进行分类，这其实感觉很像一个有监督分类算法…，但其实并不是，因为其标签传播的过程，会流经无标签数据，即有些无标签数据的标签的信息，是从另一些无标签数据中流过来的，这就用到了无标签数据之间的联系

5.半监督支持向量机：监督支持向量机是利用了结构风险最小化来分类的，半监督支持向量机还用上了无标签数据的空间分布信息，即决策超平面应该与无标签数据的分布一致（应该经过无标签数据密度低的地方）（这其实是一种假设，不满足的话这种无标签数据的空间分布信息会误导决策超平面，导致性能比只用有标签数据时还差）

半监督学习的方法大都建立在对数据的某种假设上，只有满足这些假设，半监督算法才能有性能的保证，这也是限制了半监督学习应用的一大障碍。

事实上，未标记样本虽未直接包含标记信息，但若他们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建立模型将大有裨益。

下图给出了一个直观的示例。若仅基于图中的一个正例和反例，则由于待判别样本恰位于两者正中间，大体上只能随机猜测；若能观察到图中的为标记样本，则将很有把握的判别为正例。

让学习器不依赖外界交互、自动地利用为标记样本来提升学习性能，就是半监督学习（semi-supervised learning）。

半监督学习还可细分为纯（pure）半监督学习和直推学习，前者假定训练数据中的为标记数据并非待预测数据，而后者则假定学习过程中所考虑的为标记样本恰是待预测数据。下图直观的显示出主动学习、纯监督学习和直推学习的区别。

半监督学习要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记想联系的假设，其本质是 “相似的样本拥有相似的输出”

半监督学习的假定

平滑性假定

如果两个点在高密度区域中（数据分布的概率密度比较大），且这两个点距离很近，那么他们的输出也会十分的接近。

聚类假定

即假设数据存在簇结构, 同一个簇的样本属于同一个类别，也就是说，如果两个点在相同的聚类中，那么他们趋向于被分成同一类。

流形假定

即假设数据分布在一个流形结构上, 邻近的样本拥有相似的输出值.

高维的数据一般都会处于一个低维的流形中。那么问题来了，这个流形是什么呢？

流形是局部具有欧几里得空间性质的空间，在数学中用于描述几何形体。用更简单的实例表述，就是：

假设一个三维空间 R3，那么在这个三维空间的低维分布，或者说低维嵌入，比如曲面函数 $z^2=x^2+y^2$ 是一个流形，再往下，三维空间中的一维分布也是流形，这个函数的方程为： $x=e^{-0.1*z}*cos⁡(z)$ , $x=e^{-0.1*z} *sin⁡(z)$ 。图像如下：

以此类推，高维空间中的低维分布就是我理解中的流形。

“邻近”程度常用 “相似” 程度来刻画, 因此, 流形假设可看作聚类假设的推广, 但流形假设对输出值没有限制, 因此比聚类假设的适用范围更广, 可用于更多类型的学习任务, 事实上, 无论聚类假设还是流形假设, 其本质都是 “相似的样本拥有相似的输出” 这个基本假设.

引自李宏毅深度学习笔记
假设现在做分类任务，建一个猫和狗的分类器。有一大堆猫和狗的图片，这些图片没有 label。
假设只考虑有 label 的猫和狗图片，要画一个边界，把猫和狗训练数据集分开，可能会画一条如上图所示的红色竖线。假如未标注数据的分布如上图灰色点，可能会影响你的决定。未标注数据虽然只告诉我们 input，但它们的分布可以告诉我们一些信息。
比如加入灰色点后，你会把边界画成红色斜线。
半监督学习使用未标注数据的方式，往往伴随着一些假设，所以有没有用取决于假设符不符合实际。你可能觉得左下的灰点是猫，但是可能是狗，因为两张图片的背景看起来很像。

生成式方法

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

通常可基于 EM 算法进行极大似然估计求解。EM（Expectation Maximization）算法也叫期望最大化算法，在西瓜书第七章有过介绍。该算法的核心思想是通过 E 步来对未知变量进行估算，然后通过估算出来的变量在 M 步使用极大似然估计法（在第七章也有介绍）对模型参数进行估算。在反复迭代 E, M 步骤的过程中使预估的参数收敛到局部最优解。

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

给定样本 $\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$ 。
令 $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$ 的概率
在 $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})$ 的估计可以由于数据量的增长而更为准确，于是上式的整体估计可能会更准确。
给定标记样本集 $\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)$
高斯混合模型参数估计可以用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)$
以上过程不断迭代直至收敛，即可获得模型参数。
预测过程：根据式子：
$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}$ 进行分类。

特点

优点：方法简单，易于实现。在有标记数据极少的情况下，往往比其他方法性能更好。

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

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

基于分歧的方法

基于分歧的方法disagreement-based methods使用多个学习器，学习器之间的分歧disagreement对未标记数据的利用至关重要。

协同训练co-traning是此类方法的重要代表。它最初是针对多视图multi-view数据设计的，因此也被视作多视图学习multi-view learning的代表。

数据视图

在不少现实应用中，一个数据对象往往同时拥有多个属性集attribute-set。每个属性集就构成了一个视图。
假设数据集为 $\mathbb D=\{(\mathbf{\vec x}_1,y_1),(\mathbf{\vec x}_2,y_2),\cdots,(\mathbf{\vec x}_N,y_N)\}$ ，其中 $\mathbf{\vec x}_i=(x_{i,1},x_{i,2},\cdots,x_{i,d})^{T}$ 。属性集合 $\mathbf x=\{x_1, x_2,\cdots, x_d\}$ 。假设属性集合划分为 $\mathbf x= \mathbf x^{(1)}\bigcup \mathbf x^{(2)}$ ，其中：
$\mathbf x^{(1)}=\{x_1, x_2,\cdots, x_{d_1}\},\quad \mathbf x^{(2)}=\{x_{d_1+1}, x_{d_1+2},\cdots, x_{d}\}$
即将属性划分为两个属性集，前 $d_1$ 个属性为第一个属性集，后 $d-d_1$ 个属性属于第二个属性集。
- 原始样本 $\mathbf{\vec x}_i$ 被划分为两个属性向量 $<\mathbf{\vec x}_i^{(1)},\mathbf{\vec x}_i^{(2)}>$ ，它们分别属性这两个属性集。
- $(<\mathbf{\vec x}_i^{(1)},\mathbf{\vec x}_i^{(2)}>,y_i)$ 这样的数据就是多视图数据，每个属性集都是一个视图。
如： <身高、体重、年龄、学历、爱好、工作> 可以划分为两个属性集： <身高、体重、年龄>以及<学历、爱好、工作> 。
假设不同视图具有相容性compatibility：即其所包含的关于输出空间 $\mathcal Y$ 的信息是一致的。
令 $\mathcal Y^{1}$ 为从第一个属性集判别的标记空间， $\mathcal Y^{2}$ 为从第二个属性集判别的标记空间，则有 $\mathcal Y=\mathcal Y^{1}=\mathcal Y^{2}$ 。
注意：这里仅要求标记空间相同，并没有要求每个标记相同。

自学习self-training

Self-training 是最简单的半监督方法之一，其主要思想是找到一种方法，用未标记的数据集来扩充已标记的数据集。算法流程如下：

首先，利用已标记的数据来训练一个好的模型，然后使用这个模型对未标记的数据进行标记。
然后，进行伪标签的生成，因为已训练好的模型对未标记数据的所有预测都不可能都是完全正确的，因此对于经典的 Self-training，通常是使用分数阈值（confidence score）过滤部分预测，以选择出未标记数据的预测标签的一个子集。
其次，将生成的伪标签与原始的标记数据相结合，并在合并后数据上进行联合训练。
整个过程可以重复 n 次，直到达到收敛。

Self-training 最大的问题在就在于伪标签非常的 noisy，会使得模型朝着错误的方向发展。此后文章大多数都是为了解决这个问题。

简单解释一下：

将初始的有标签数据集作为初始的训练集 $(X_{train},y_{train})=(X_{l},y_{l})$ ，根据训练集训练得到一个初始分类器 $C_{int}$ 。
利用 $C_{int}$ 对无标签数据集 $X_u$ 中的样本进行分类，选出最有把握的样本 $(X_{conf},y_{conf})$
从 $X_u$ 中去掉 $(X_{conf},y_{conf})$
将 $(X_{conf},y_{conf})$ 加入到有标签数据集中， $(X_{train},y_{train})\leftarrow(X_{l},y_{l})\cup(X_{conf},y_{conf})$
根据新的训练集训练新的分类器，重复步骤 2 到 5 直到满足停止条件（例如所有无标签样本都被标记完了）最后得到的分类器就是最终的分类器。

Self-training 的主要缺点是模型无法纠正自己的错误。如果模型对自己的分类结果很有 “自信”，但这是盲目自信，分类结果是错的，那它就会在训练中放大误差。此外，如果数据集 $U$ 和数据集 $L$ 的重合度很低，标签集 $C$ 并不能覆盖 $U$ 的所有类别，这种不良影响就更严重了。在这种情况下，模型的性能注定会很差。

协同训练算法

协同训练正是很好地利用了多视图数据的 “相容互补性”，其基本的思想是：首先在每个视图上基于有标记样本分别训练一个初始分类器，然后让每个分类器去挑选分类置信度最高的未标记样本并赋予标记，并将带有伪标记的样本数据传给另一个分类器作为新增的有标记样本用于训练更新，这个 “互相学习、共同进步” 的过程不断迭代进行，直到两个分类器都不再发生变化，或达到预先设定的轮数为止。

协同训练充分利用了多视图的相容互补性。
假设数据拥有两个充分且条件独立视图。
- 充分：指每个视图都包含足以产生最优学习器的信息。
- 条件独立：指在给定类别标记条件下，两个视图独立。
此时，可以用一个简单的办法来利用未标记数据：
- 首先在每个视图上，基于有标记样本，分别训练出一个分类器。
- 然后让每个分类器分别去挑选自己最有把握的未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新。
- 该 “互相学习、共同进步” 的过程不断迭代进行，直到两个分类器都不再发生变化，或者到达指定的迭代轮数为止。
注意：
- 如果在每轮学习中都考察分类器在所有未标记样本上的分类置信度，则会有很大的计算开销。因此在算法中使用了未标记样本缓冲池。
- 分类置信度的估计因基学习算法而异。
协同训练算法：
- 输入：
  - 有标记样本集 $\mathbb D_l=\{(<\mathbf{\vec x}_1^{(1)},\mathbf{\vec x}_1^{(2)}>,y_1),(<\mathbf{\vec x}_2^{(1)},\mathbf{\vec x}_2^{(2)}>,y_2),\cdots,(<\mathbf{\vec x}_l^{(1)},\mathbf{\vec x}_l^{(2)}>,y_l)\}$
  - 未标记样本集 $\mathbb D_u=\{<\mathbf{\vec x}_{l+1}^{(1)},\mathbf{\vec x}_{l+1}^{(2)}>, <\mathbf{\vec x}_{l+2}^{(1)},\mathbf{\vec x}_{l+2}^{(2)}>,\cdots, <\mathbf{\vec x}_{l+u}^{(1)},\mathbf{\vec x}_{l+u}^{(2)}> \},l+u=N$
  - 缓冲池大小 $s$
  - 每轮挑选的正例数量 $p$
  - 每轮挑选的反例数量 $n$
  - 基学习算法 $f$
  - 学习轮数 $T$
- 输出：未标记样本的预测结果 $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T},\hat y_i \in \{1,2,\cdots,K\},i=l+1,l+2,\cdots,l+u$
- 步骤：
  - 从 $\mathbb D_u$ 中随机抽取 $s$ 个样本构建缓冲池 $\mathbb D_s$
  - $\mathbb D_u=\mathbb D_u-\mathbb D_s$
  - 从 $\mathbb D_l$ 中分别构建： $\mathbb D^{(1)},\mathbb D^{(2)}$ 分别表示第一视图有标记数据集、第二视图有标记数据集：
    $\mathbb D_l^{(1)}=\{( \mathbf{\vec x}_1^{(1)} ,y_1),( \mathbf{\vec x}_2^{(1)}, y_2),\cdots,( \mathbf{\vec x}_l^{(1)} ,y_l)\}\\ \mathbb D_l^{(2)}=\{( \mathbf{\vec x}_1^{(2)} ,y_1),( \mathbf{\vec x}_2^{(2)}, y_2),\cdots,( \mathbf{\vec x}_l^{(2)} ,y_l)\}$
  - 开始迭代，迭代终止条件是：迭代收敛或者迭代次数达到 $T$ 。迭代过程为：
    - 从 $\mathbb D_s$ 中分别构建（其中 $m$ 为其元素个数）： $\mathbb D_s^{(1)},\mathbb D_s^{(2)}$ 分别表示第一视图缓冲数据集、第二视图缓冲数据集：
      $\mathbb D_s^{(1)}=\{\mathbf{\vec x}_{s1}^{(1)} , \mathbf{\vec x}_{s2}^{(1)},\cdots,\mathbf{\vec x}_{sm}^{(1)} \}\\ \mathbb D_s^{(2)}=\{\mathbf{\vec x}_{s1}^{(2)} , \mathbf{\vec x}_{s2}^{(2)},\cdots, \mathbf{\vec x}_{sm}^{(2)} \}$
    - 考察视图一：
      - 利用 $\mathbb D_l^{(1)}$ 训练 $f$ 得到分类器 $f_1$ 。
      - 然后考察 $f_1$ 在 $\mathbb D_s^{(1)}$ 上的分类置信度。挑选 $p$ 个正例置信度最高的样本 $\mathbb D_p^{(1)} \subset \mathbb D_s$ 、挑选 $n$ 个反例置信度最高的样本 $\mathbb D_n^{(1)} \subset \mathbb D_s$ 。
      - 然后将 $\mathbb D_p^{(1)}$ 的视图二标记为正例，将 $\mathbb D_n^{(1)}$ 的视图二标记为反例：
      $\tilde {\mathbb D}_p^{(2)}=\{(\mathbf{\vec x}_i^{(2)},1)\mid \mathbf{\vec x}_i^{(1)} \in \mathbb D_p^{(1)} \}\\ \tilde {\mathbb D}_n^{(2)}=\{(\mathbf{\vec x}_i^{(2)},-1)\mid \mathbf{\vec x}_i^{(1)} \in \mathbb D_n^{(1)} \}$
      这里并没有简单的将 $\mathbb D_p^{(1)}$ 标记为正例、 $\mathbb D_n^{(1)}$ 标记为反例。而是标记它们对立的那个视图，帮助对方视图增加标记数据。
    - $\mathbb D_s=\mathbb D_s-(\mathbb D_p^{(1)}\bigcup \mathbb D_n^{(1)})$ ，更新 $\mathbb D_s^{(2)}$ 。此时 $\mathbb D_s^{(2)}$ 会缩小，因为有部分样本从视图一中获得了标记信息。
    - 考察视图二：
      - 利用 $\mathbb D_l^{(2)}$ 训练 $f$ 得到分类器 $f_2$ 。
      - 然后考察 $f_2$ 在上 $\mathbb D_s^{(2)}$ 的分类置信度。挑选 $p$ 个正例置信度最高的样本 $\mathbb D_p^{(2)}\subset \mathbb D_s$ 、挑选 $n$ 个反例置信度最高的样本 $\mathbb D_n^{(2)} \subset \mathbb D_s$ 。
      - 然后将 $\mathbb D_p^{(2)}$ 的视图一标记为正例，将 $D_n^{2}$ 的视图一标记为反例：
    $\tilde {\mathbb D}_p^{(1)}=\{(\mathbf{\vec x}_i^{(1)},1)\mid \mathbf{\vec x}_i^{(2)} \in \mathbb D_p^{(2)} \}\\ \tilde {\mathbb D}_n^{(1)}=\{(\mathbf{\vec x}_i^{(1)},-1)\mid \mathbf{\vec x}_i^{(2)} \in \mathbb D_n^{(2)} \}$
    - $\mathbb D_s=\mathbb D_s-(\mathbb D_p^{(2)}\bigcup \mathbb D_n^{(2)})$ 。
    - 如果 $f_1,f_2$ 在训练前后，均未发生改变，则迭代收敛。否则继续向下执行。
    如何判断是否发生改变？通常可以考察它们的预测结果是否一致
    - 更新 $\mathbb D_l^{(1)},\mathbb D_l^{(2)}$ ：
    $\mathbb D_l^{(1)}=\mathbb D_l^{(1)}\bigcup(\tilde {\mathbb D}_p^{(1)}\bigcup \tilde {\mathbb D}_n^{(1)})\\ \mathbb D_l^{(2)}=\mathbb D_l^{(2)}\bigcup(\tilde {\mathbb D}_p^{(2)}\bigcup \tilde {\mathbb D}_n^{(2)})$
    - 补充 $\mathbb D_s$ ：从 $\mathbb D_u$ 中随机抽取 $2p+2n$ 个样本加入 $\mathbb D_s$ ，同时 $\mathbb D_u$ 中移除这 $2p+2n$ 个样本。
      这意味着： $\mathbb D_s$ 越来越大、 $\mathbb D_u$ 越来越小。
- 最终得到分类器 $f_1,f_2$ 。将这两个分类器用于 $\mathbb D_u$ 即可得到未标记样本的预测结果： $\hat{\mathbf{\vec y}}=(\hat y_{l+1},\hat y_{l+2},\cdots,\hat y_{l+u})^{T}$ 。

性质

协同训练过程虽然简单，但是理论证明：若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。
- 不过视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度没有那么大。
- 但研究表明，即便在更弱的条件下，协同训练仍可以有效提升弱分类器的性能。
协同训练算法本身是为多试图数据而设计的，但此后出现了一些能在单视图数据上使用的变体算法。
- 它们或是使用不同的学习算法，或是使用不同的数据采样，甚至使用不同的参数设置来产生不同的学习器，也能有效利用未标记数据来提升性能。
- 后续理论研究表明，此类算法事实上无需数据拥有多试图，仅需弱学习器之间具有显著的分歧（或者差异），即可通过相互提供伪标记样本的方式来提升泛化性能。
  而不同视图、不同算法、不同数据采样、不同参数设置等，都是产生差异的渠道，而不是必备条件。
基于分歧的方法只需要采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、使用范围较为广泛。
- 为了使用此类方法，需要能生成具有显著分歧、性能尚可的多个学习器。
- 但当有标记样本较少，尤其是数据不具有多试图时，要做到这一点并不容易，需要巧妙的设计。

Tri-training（三体训练法）

这是周志华等人于 2005 提出的一种算法，也是迄今为止所有多视图训练算法中知名度最高的一种，它会训练三个独立模型，然后用三者的一致性减少对不含标签数据的预测偏差。

Tri-training 的一个主要前提是初始模型必须是多样的，这和 Democratic Co-learning 一样，但后者实现的方法是使用不同的的架构，而前者则是从原始训练数据 L 中用 Bootstrap 采样机制获得不同变体 $S_i$ 。在这些采样变体上分别训练出 $m_1$ 、 $m_2$ 、 $m_3$ 三个模型后，它们无需计算置信度，只需按照 “少数服从多数” 的做法筛选出标签。例如对于预测标签，模型 $m_j$ 和 $m_k$ 表示强烈同意，但模型 $m_i$ 不置可否，那么算法会为样本生成多数同意的伪标签，然后把它放入 $m_i$ 的训练集。

其他阅读推荐：一文概览能生成代理标签的半监督学习算法

其中介绍了
Self-training
Multi-view training
Co-training
Democratic Co-learning
Tri-training
Tri-training with disagreement
Asymmetric tri-training
Multi-task tri-training
Self-ensembling
Ladder networks
Virtual Adversarial Training
Π model
Temporal Ensembling
Mean Teacher
相关工具和领域
Distillation
Learning from weak supervision
Learning with noisy labels
Data augmentation
Ensembling a single model

半监督 SVM

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

TVSM

半监督支持向量机中最著名的是 TSVM:Transductive Support Vector Machine。与标准SVM一样，TSVM也是针对二分类问题的学习方法。
TSVM试图考虑对未标记样本进行各种可能的标记指派label assignment：
- 尝试将每个未标记样本分别作为正例或者反例。
- 然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。
- 一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。
给定标记样本集 $\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$ 是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数。
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$ 达到指定阈值为止。

`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}$

在对未标记样本进行指标指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类。这将对SVM的训练造成困扰。
为了减轻类别不平衡性造成的不利影响，可对上述算法稍加改进：将优化目标中的 $C_u$ 项拆分为 $C_u^{+}$ 和 $C_u^{- }$ 两项，分别对应基于伪标记而当作正、反例使用的未标记样本。并在初始化时，令：
$C_u^{+}=\frac{u_-}{u_+}C_u^{- }$
其中 $u_-$ 和 $u_+$ 分别为基于伪标记而当作反、正例而使用的未标记样本数。

性质

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

图半监督学习

标签传播算法

给定一个数据集，可以将其映射为一个图，数据集中每个样本对应于图中的一个结点。若两个样本之间的相似度很高（或者相关性很强），则对应的结点之间存在一条边，边的强度正比于样本之间的相似度（或相关性）。
将有标记样本所对应的结点视作为已经染色，而未标记样本所对应的结点尚未染色。于是半监督学习就对应于 “颜色” 在图上扩散或者传播的过程。这就是标记传播算法label propagation 。
给定标记样本集 $\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$ 是全连接的，任意两点之间都存在边。
  - 两个点的距离越近，说明两个样本越相似，则边的权重越大；距离越远，说明两个样本越不相似，则边的权重越小。
  - 权重越大说明样本越相似，则标签越容易传播。

能量函数

假定从图 $\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]$