[机器学习]半监督学习

本文档记录了《机器学习》第 13 章半监督学习相关内容

未标记样本

半监督学习

学习器不依赖外界交互、自动的利用未标记样本来提升学习性能。

利用未标记样本的相关假设

本质——相似的样本具有相似的输出。

• 聚类假设：假设数据存在簇结构，同一个簇的样本同属一个类别。
• 流形假设：假设数据的分布在一个流形结构上，邻近的样本具有相似的输出值。

半监督学习的种类

• 纯半监督学习：假定训练数据中的未标记样本并非接下来需要预测的数据。
• 直推半监督学习：假定训练数据中的未标记样本正是接下来需要预测的数据。

生成式方法

• 假设：不论是否有标记，所有数据都是由同一个潜在的模型”生成的“，通过潜在模型的参数将未标记数据（不是对应的标签）与学习目标联系起来，未标记数据的标签可看作是模型的缺失参数。
• 缺陷：模型假设必须准确。

高斯混合模型生成

混合成分与类别一一对应

• 符号标记

  • 标记样本集：$D_l=\{(x_1,y_1),(x_2,y_2),...,(x_l,y_l)\}$
  • 未标记样本集：$D_u=\{x_{l+1},x_{l+2},...,x_{m=l+u}\}$
  • 标签个数：$N$
  • 混合系数：$\sum_{i=1}^{N}\alpha_i=1, \alpha_i\geq0$
  • 高斯混合成分：$\Theta\in\{1,2,...N\}$
  • 样本属于第 $i$ 个高斯混合成分的概率：$p(x|\mu_i,\Sigma_i)$
  • 样本的生成概率：$p(x)=\sum_{i=1}^N\alpha_i\cdot p(x|\mu_i,\Sigma_i)$

  • 样本由第 $i$ 个高斯混合成分生成的后验概率：

    $$p(\Theta=i|x)=\frac{\alpha_i\cdot p(x|\mu_i,\Sigma_i)}{\sum_{j=1}^N\alpha_j\cdot p(x|\mu_j,\Sigma_j)}$$

  • 样本由第 $i$ 个高斯混合成分生成的情况下，类别为 $j$ 的概率：

    $$p(y=j|\Theta=i,x)$$

• 模型预测

  $$f(x)=\text{argmax}_{j\in\mathcal{Y}}\sum_{i=1}^Np(y=j|\Theta=i,x)\cdot p(\Theta=i|x)$$

• 参数更新见 P297 EM算法。

半监督 SVM（二分类）

目标

• 尽可能的将有标记样本分开
• 超平面穿过数据低密度区域划分

Transductive（直推式） SVM

形式化定义

• 参数：
  
  • $C_l/C_u$：用于平衡模型复杂度、有/无标记样本重要程度的折中参数。
  • $\mathbf{\xi}$：松弛向量。

• 目标函数：

  $$\min_{w,b,\hat{y},\xi} \frac{1}{2}\|w\|_2^2+C_l\sum_{i=1}^l\xi_i+C_u\sum_{i=l+1}^m\xi_i$$

• 约束条件：

  • 对有标记样本：$y_i(w^\top x_i+b)\geq 1-\xi_i$
  • 对无标记样本：$\hat{y}_i(w^\top x_i+b)\geq 1-\xi_i$
  • 松弛向量：$\xi_i\geq0$

算法实现

• 输入：
  
  • 标记样本集：$D_l=\{(x_1,y_1),(x_2,y_2),...,(x_l,y_l)\}$
  • 未标记样本集：$D_u=\{x_{l+1},x_{l+2},...,x_{m=l+u}\}$
  • 折中参数：$C_l/C_u$
• 输出：未标记样本的预测结果 $\hat{y}$

• 算法：

  SVM_l = train(D_l) # 有标签数据训练
  y_hat = SVM_l.predicate(D_u) # 无标签数据预测
  C_u.init() << C_l.init()
  while C_u < C_l do
      (w,b),xi = SVM_l.optimize(D_l,D_u,y_hat,C_l,C_u) # 根据目标函数优化模型参数
      # 若存在一对未标记样本 (x_i,x_j)，它们的指派标记不同，且对应的松弛变量之和过大，说明它们的指派标记很可能是错的
      def traverse(y_hat):
          if y_hat[i]*y_hat[j]<0 and xi[i]>0 and xi[j]>0 and xi[i]+xi[j]>2:
              y_hat[i] = -y_hat[i]
              y_hat[j] = -y_hat[j]
              (w,b),xi = SVM_l.optimize(D_l,D_u,y_hat,C_l,C_u)
      C_u = min(2*C_u,C_l)
  end while
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 存在问题：
  
  • traverse(y_hat) 部分计算开销过大。
  • 未标记样本中存在类别不平衡问题：$C_u^+=\frac{u_-}{u_+}C_u^-$

图半监督学习？？？

基于分歧的方法

特点

• 使用多学习器，各个学习器之间的“分歧”对于未标记数据的利用至关重要。
• 学习器之间具有显著差异即可。
• 选择合适的基学习器。
• 不适用于标记样本过少，尤其是不具有多视图的数据。

协同训练与多视图学习

多视图的特点

• “相容互补性”
  
  • 充分：每个视图都包含足以产生最优学习器的信息
  • 条件独立：给定类别标记条件下两个视图独立

协同训练算法

• 主要思想：互相学习，共同进步
  
  1. 在每个视图上基于标记样本训练出一个分类器
  2. 让每个分类器分别挑选自己最有把握的未标记样本赋予伪标记
  3. 将伪标记样本作为新的标记样本给其他学习器训练更新
  4. 循环上述过程
• 算法实现：见 P306

半监督聚类

两种辅助的监督信息：
* 必连集合 $\mathcal{M}$ 和勿连集合 $\mathcal{C}$
* 少量的标记样本信息

约束 k 均值算法

• 主要思想：利用必连集合 $\mathcal{M}$ 和勿连集合 $\mathcal{C}$，在 k-means 的基础上每次更新中心之后，节点重新的归属要满足必连关系和勿连关系。
• 算法实现：见 P307

约束种子 k 均值算法

• 主要思想：利用少量的标记样本信息，首先通过标记样本计算每个簇的中心，然后在 k-means 的基础上对每个点寻找最近的簇并加入其中，此过程不包含标记样本点，仅对未标记样本点执行。此外，每次样本点重新确定中心的过程中要保证标记样本点始终属于标签簇。
• 算法实现：见 P309