第十章 半监督学习 Semi-Supervised Learning

协同训练（多视图半监督）、基于图的半监督学习算法、S3VM（TSVM）

半监督学习 SSL 介绍

什么是半监督学习?

半监督学习 Semi-Supervised Learning, SSL

从有标签和无标签的数据中学习 . Examples:

• 半监督分类: $l$ 个有标签样本 ${(x_i,y_i)}_{i=1}^l$ 和 $u$ 无标签样本 $\{x_j{\}}_{j=l+1}^{l+u}$, 并且 $u\gg l$
  目标: 训练更好的分类器 $f$ （好于仅适用有标签数据）。
• 半监督聚类算法: 无标签数据, 有监督信息(supervised information), e.g., must-links, cannot-links.
  目标: 训练更好的聚类算法（好于仅适用无标签数据）。
• 半监督分类算法

动机

标签数据较难获得

• 标签数据需要专家经验
• 标签数据需要特殊设备

无标签数据数量大

无标签数据采集成本低

无标签数据更容易获得

结果必须要有改进

基本概念

输入样本 $x$, 标签 $y$

学习器或分类器 f:X→Y

标签数据 $(X_l,Y_l)=\{(x_{1:l},y_{1:l})\}$

无标签数据 $X_u=\{x_{l+1:n}\}$, 模型训练中已知，一般地 $l\ll n$

测试数据 $X_{t}est=\{x_{n+1:}\}$, 模型训练中未知

无标签数据的作用

当加入无标签数据后，分界面发生改变

半监督学习算法

(1) 自学习 / 自训练算法

第一个半监督学习算法

输入: 标签数据 $\{(x_i,y_i){\}}_{i=1}^l$, 无标签数据 $\{x_j{\}}_{j=l+1}^{l+u}$

初始化： $L=\{(x_i,y_i){\}}_{i=1}^l$ and $U=\{x_j{\}}_{i=l+1}^n$

Repeat

• ①利用有标签数据 $L$ 训练分类器 $f$（有监督学习算法）
• ②利用分类器 $f$ 给无标签数据打标签
• ③将已标记的数据 $S$ 加入到 $L$ 中 $\{(x,f(x))│x\in S\}$ to $L$

Until $U=\varnothing$

半监督例子: KNN算法

Input: labeled data $\{(x_i,y_i){\}}_{i=1}^l$, unlabeled data $\{x_j{\}}_{j=l+1}^{l+u}$

Initialize $L=\{(x_i,y_i){\}}_{i=1}^l$ and $U=\{x_j{\}}_{i=l+1}^n$

Repeat until $U$ is empty:

• ①Select $x=argmi{n}_{x\in U}{\text{min}}_{x^{\prime }\in L}d(x,x^{\prime })$

• ②Set $f(x)$ to the label of $x$’s nearest instance in $L$

• ③Break ties randomly

• ④Remove $x$ from $U$; add $(x,f(x))$ to $L$

KNN算法失效

当出现异常点时，算法产生的错误会逐渐增大

(2) 生成模型

生成模型

标签数据 $(X_l,Y_l)$:

假设每个类别服从高斯分布，分界面的位置？

模型参数: $\theta =\{w_1,w_2,{\mu }_1,{\mu }_2,{\Sigma }_1,{\Sigma }_2\}$

混合高斯模型: $p(x,y│\theta )=p(y│\theta )p(x│y,\theta )=w_{y}N(x;{\mu }_y,{\Sigma }_y)$

分类: $p(y|x,\theta )=\frac{p(x,y|\theta )}{{\sum }_{y^{\prime }}p(x,y^{\prime }|\theta )}$

数据分布以及分界面:

加入无标签数据

加入无标签数据后，数据分布和分界线

数据分布发生变化导致分解线发生改变

半监督学习中的生成模型

原始数据的分布：$p(X_l,Y_l,X_u|\theta )$

新数据的分布：${\sum }_{Y_u}p(X_l,Y_l,X_u,Y_u|\theta )$

$Y_u$：新标签数据

目标：$p(X_l,Y_l,X_u|\theta )={\sum }_{Y_u}p(X_l,Y_l,X_u,Y_u|\theta )$

利用极大似然方法求 $\theta$ 的最优解, Bayesian方法

常见的生成模型

在半监督中常见的生成模型:

• 混合高斯模型(GMM)
  • 图像分类
  • EM优化算法
• 混合多项式模型 (Naive Bayes)
  • 文本分类
  • EM优化算法
• 隐马尔科夫模型 (HMM)
  • 语音识别
  • Baum-Welch优化算法

混合高斯模型 GMM

GMM模型，二分类问题，MLE优化方法.

EM求解GMM

混合模型的前提假设：

先验概率 p(y), 条件概率p(x│y) 都是正确的.

启发式算法：

训练一个生成模型, e.g., multiple Gaussian distributions per class

降低无标签数据的权重 0≤λ≤1

$$\log p(X_l,Y_l,X_u|\theta )=\sum _{i=1}\log p(y_i|\theta )p(x_i|y_i,\theta )+\lambda \sum _{i=1+1}^{l+u}\log \left(\sum _{y}p(y|\theta )p(x_i|y,\theta )\right)$$

★(3) 多视图算法

协同训练 Co-training

多视图：图片（ image ）和 文本（ HTML text ）

特征划分：每个样本包含两类特征 $x=[x^{(1)};x^{(2)}]$

• $x^{(1)}$ = 图片特征
• $x^{(2)}$ = 文本特征

协同训练思想：同时训练一个图片分类器和文本分类器，让这两个分类器相互学习。

协同训练正是很好地利用了多视图数据的“相容互补性”，其基本的思想是：首先基于有标记样本数据在每个视图上都训练一个初始分类器，然后让每个分类器去挑选分类置信度最高的样本并赋予标记，并将带有伪标记的样本数据传给另一个分类器去学习，从而共同进步。

协同训练假设数据拥有两个“充分”且“条件独立”视图。

协同训练过程虽简单，但令人惊讶的是，理论证明显示出，若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。

视图的条件独立性在现实任务中通常很难满足，不会是条件独立的，因此性能提升幅度不会那么大, 但研究表明，即使在更弱的条件下，协同训练仍可有效地提升弱分类器的性能。

协同训练优缺点：

基于分歧的方法只需采用合适的基学习器，就较少受到模型假设 、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、适用范围较为广泛。

为了使用此类方法，需能生成具有显著分歧、性能尚可的多个学 习器，但当有标记样本很少、尤其是数据不具有多视图时，要做到这一点并不容易。

协同训练的前提条件

$x^{(1)}$ 和 $x^{(2)}$ 能够独立地训练一个好的分类器

$x^{(1)}$ 和 $x^{(2)}$ 相互独立

协同训练算法

分别利用视图1和视图2的有标签数据 $(X_l^{(1)},Y_l^{(1)})$ 和 $(X_l^{(2)},Y_l^{(2)})$ 训练分类器 $f^{(1)}$ 和 $f^{(2)}$

分别利用分类器 $f^{(1)}$ and $f^{(2)}$ 对无标签数据 $X_u$ 打标签。

将 $f^{(1)}$ 置信度最高的k个标签 $(x,f^{(1)}(x))$ 加入到 $f^{(2)}$ 的标签数据中

将 $f^{(2)}$ 置信度最高的k个标签 $(x,f^{(2)}(x))$ 加入到 $f^{(1)}$ 的标签数据中

重复以上步骤

多视图协同训练

协同训练扩展:

• Loss function: $c(x,y,f(x))\in [0,\infty )$.
  • Squared loss $c(x,y,f(x))=(y-f(x){)}^2$
  • 0/1 loss $c(x,y,f(x))=1$ if $y\ne f(x)$, and $0$ otherwise.

Empirical risk: $\hat{R}(f)=\frac{1}{l}{\sum }_{i=1}^{l}c(x_i,y_i,f(x_i))$

正则项(Regularizer): $\Omega (f)$, e.g., $\Vert f{\Vert }^2$

Regularized risk minimization $f^{\ast }=argmi{n}_{f\in F}\hat{R}(f)+\lambda \Omega (f)$

定义在无标签数据上的正则项 $\Omega (f)$ ，保持不同分类器间的平衡:

$${\mathrm{argmin}}_{f_1,\dots ,f_k}\sum _{\nu =1}^k\left(\sum _{i=1}^{l}c\left(x_i,y_i,f_v(x_i)\right)+{\lambda }_1{\Omega }_{SL}(f_v)\right)+{\lambda }_2\sum _{u,v=1}^k\sum _{i=l+1}^{l+u}c(x_i,f_u(x_i),f_v(x_i))$$

其中 $c(x_i,f_u(x_i),f_v(x_i))=(f_u(x_i)-f_v(x_i){)}^2$

★(4) 基于图的算法

案例：文本分类

分类：天文学和旅游类文章
基于词重叠度计算单词的相似度

标签数据无法计算相似度：没有词组重叠

无标签数据作为桥梁：当使用无标签数据后，可以找到天文学单词和旅游单词的联系

案例：手写体

手写字体识别中，利用欧式距离计算图片的相似度

图半监督学习原理

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高(或相关性很强)，则对应的结点之间存在一条边，边的“强度”(strength)正比于样本之间的相似度(或相关性)。

我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点则尚未染色。于是，半监督学习就对应于**“颜色”在图上扩散**或传播的过程。

由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。

监督信息大致有两种类型

• 必连与勿连约束：必连指的是两个样本必须在同一个类簇，勿连则是必不在同一个类簇。
• 标记信息：少量的样本带有真实的标记。

图半监督学习优缺点

图半监督学习方法在概念上相当清晰, 且易于通过对所涉矩阵运算的分析来探索算法性质。

但此类算法的缺陷也相当明显：

• 首先是在存储开销高；
• 另一方面，由于构图过程仅能考虑训练样本集，难以判知新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制。

基于图的半监督学习算法

图中包括标签数据和无标签数据，当两个节点的标签一致时，这两个节点有一条权重较大的边（ heavy edge ）相连。

节点: $X_l\bigcup X_u$

边: 利用节点特征计算相似度权重, 例如,

• k-nearest-neighbor graph, unweighted (0, 1 weights)
• fully connected graph, weight decays with distance $w=exp(-\Vert x_i-x_j{\Vert }^2/{\sigma }^2)$

目标: 利用网络中的路径计算节点间的相似度

Mincut算法

The graph mincut problem:

Fix $Y_l$, find $Y_u\in \{0,1{\}}^{n-l}$ to minimize $∑{ij}w{ij} |y_i-y_j | $

Equivalently, solves the optimization problem

$$\underset{Y\in \{0,1{\}}^n}{\min }\infty \sum _{i=1}^l(y_i-Y_{li}{)}^2+\sum _{ij}{w}_{ij}{\left(y_i-y_j\right)}^2$$

Combinatorial problem, but has polynomial time solution

Mincut computes the modes of a Boltzmann machine. There might be multiple modes. One solution is to randomly perturb the weights, and average the results.

调和函数

将标签离散值转化为实数集中(R)的连续值, 调和函数 f满足：

$f(x_i)=y_i$ for $i=1,\dots ,l$

$F$ minimizes the energy ${\sum }_{i\sim j}{w}_{i}j(f(x_i)-f(x_j){)}^2$

The mean of a Gaussian random field

Average of neighbors $f(x_i)=\frac{{\sum }_{j\sim i}{w}_{i}jf(x_j)}{{\sum }_{j\sim i}{w}_{i}j},\forall x_i\in X_u$

An electric network interpretation 电网解释

Edges are resistors with conductance $w_{i}j$

1 volt battery connects to labeled points y=0,1

The voltage at the nodes is the harmonic function f

Implied similarity: similar voltage if many paths exist

A random walk interpretation 随机游动解释

Randomly walk from node i to j with probability $\frac{w_{ij}}{{\sum }_k{w}_{ik}}$

Stop if we hit a labeled node

The harmonic function $f=Pr(\text{hit label }1|\text{start from }i)$

An algorithm to compute harmonic function

One way to compute the harmonic function is:

This can be viewed as a special case of self-training too.

★(5) 半监督支持向量机 S3VM / TSVM

半监督支持向量机 = 半监督SVMs (S3VMs)

Transductive SVMs (TSVMs)

对于半监督学习，S3VM则考虑超平面需穿过数据低密度的区域。

TSVM是半监督支持向量机中的最著名代表，其核心思想是：尝试为未标记样本找到合适的标记指派，使得超平面划分后的间隔最大化。

TSVM采用局部搜索的策略来进行迭代求解，即首先使用有标记样本集训练出一个初始SVM，接着使用该学习器对未标记样本进行打标，这样所有样本都有了标记，并基于这些有标记的样本重新训练SVM，之后再寻找易出错样本不断调整。

最大化 “unlabeled data margin”

标准软间隔SVMs

最大化标签数据的间隔

S3VM的目标函数

The hat loss on unlabeled data

S3VM算法

Computational difficulty

• SVM objective is convex
• Semi-supervised SVM objective is non-convex
• Optimization approaches: 𝑺𝑽𝑴^{𝒍𝒊𝒈𝒉𝒕}, 𝜵𝑺𝟑𝑽𝑴, continuation S3VM, deterministic annealing, CCCP, Branch and Bound, SDP convex relaxation, etc.

Entropy regularization 熵正则化

当最大间隔假设错误

SVM error: 0.26 ± 0.13
S3VM error: 0.34 ± 0.19

Theory of SSL 半监督算法理论分析

SSL的缺陷

当假设错误，SSL往往差于SL!

A PAC Bound for Semi-Supervised Learning

略

Online SSL 在线半监督学习算法

略

Multimanifold SSL 高维多流形SSL

略