我已经有两年 ML 经历，这系列课主要用来查缺补漏，会记录一些细节的、自己不知道的东西。

已经有人记了笔记（很用心，强烈推荐）：https://github.com/Sakura-gh/ML-notes

本节对应笔记：http://htmlpreview.github.io/?https://github.com/Sakura-gh/ML-notes/blob/master/ML-notes-html/15_Semi-supervised-Learning.html

本节内容综述

1. 介绍，见小细节。包括什么是半监督学习？其分类？为什么做这个？如何起到作用？
2. 本节课 Outline ：Semi-supervised Learning for Generative Model，Low-density Separation Assumption，Smoothness Assumption，Better Representation。
3. Semi-supervised Learning for Generative Model，见小细节。讲解了基于高斯分布与似然估计的半监督学习基础理论。
4. Low-density Separation Assumption，一个经典的假设，认为这个世界是非黑即白的。见小细节。还拓展了Entropy-based Regularization与Semi-supervised SVM。
5. Smoothness Assumption，基本精神是近朱者赤，近墨者黑。见小细节。提及了聚类、建图等归类方法。最后基于图，让smoothness也成为了训练中的一个优化目标。
6. Better Representation，基本精神是去芜存菁，化繁为简，将在Supervised Learning中展开。

小细节

Introduction

对于监督学习：训练数据中，都有x与标签y。

但是对于半监督学习：

• 训练中，部分数据没有标签，只有输入x；
• 通常，无标签的数据量远大于有标签的。

半监督学习可以分为两种情况：

• Transductive Learning：unlabeled data is the testing data，把testing data当做无标签的training data使用（这个是没有问题的，因为在比赛中，所有已有的数据都可以使用，当然包括测试数据的特征值）；
• Inductive Learning：unlabeled data is not the testing data，事先无法获取testing data，并且无法使用。

为什么使用半监督学习？

• 我们不缺数据，但是缺有标签的数据；
• 人类一直在做“半监督学习”。

半监督学习如何起作用？

如上图，我们可以通过未标记的数据，获取一些信息，如分布等（通常伴随一些假设）。

Semi-supervised Learning for Generative Model

Supervised Generative Model

如上，在监督学习中，我们假设了数据服从高斯分布，并且依次做了许多拓展。

Semi-supervised Generative Model

如上，在有了未标记数据后，直观上可以影响我们对高斯分布的拟合。

其在数学上推导如下。

如上：

• 首先初始化参数；
• step1利用model计算每个未标记数据$x^u$xu计算其属于第1类的概率$P_\theta(C_1|x^u)$Pθ​(C1​∣xu)；
• step2更新model，这些未标记数据其一部分属于第1类，一部分属于第2类。

$P(C_1)=\frac{N_1+\sum_{x^u}P(C_1|x^u)}{N}$P(C1​)=NN1​+∑xu​P(C1​∣xu)​

对于均值，也要在原有式子中加上$x^u$xu的影响：

$u_1=\frac{1}{N_1}\sum\limits_{x^r\in C_1} x^r+\frac{1}{\sum_{x^u}P(C_1|x^u)}\sum\limits_{x^u}P(C_1|x^u)x^u$u1​=N1​1​xr∈C1​∑​xr+∑xu​P(C1​∣xu)1​xu∑​P(C1​∣xu)xu

接着循环上两步。上述的step1就是EM algorithm里的E，step2则是M。

理论上，可以收敛，但是其值与初始值有很大关系。

上述的理论基础在于，我们以往做极大似然估计的式子的基础上，再增加一个拟合目标：

$logL(\theta)=\sum\limits_{x^r} logP_{\theta}(x^r, \hat{y}^r)+\sum\limits_{x^u}logP_{\theta}(x^u)$logL(θ)=xr∑​logPθ​(xr,y^​r)+xu∑​logPθ​(xu)

而$x^u$xu这一项，我们将其视为可以划分的，用成为各类先验概率乘上这个类别的概率，如下式。

$P_{\theta}(x^u)=P_{\theta}(x^u|C_1)P(C_1)+P_{\theta}(x^u|C_2)P(C_2)$Pθ​(xu)=Pθ​(xu∣C1​)P(C1​)+Pθ​(xu∣C2​)P(C2​)

Low-density Separation Assumption

认为在数据密度低的地方，其有一条绝对的分界线。

Self-training

low-density separation最经典简单的方法是self training：

• 先用有标签数据去训练一个model $f^*$f∗；
• 然后用$f^*$f∗对未标记数据打上label，$y^u=f^*(x^u)$yu=f∗(xu)，叫做Pseudo-label；
• 从未标记数据中拿出一些data加到labeled data里，至于选取谁需要自己设计算法来挑选；
• 回头再去训练$f^*$f∗，循环即可。

注意，这一招在 Regression 上没有用。

与前面的Semi-supervised Learning for Generative Model对比：这个用的是Hard label，之前的用的是Soft label。

如图，对于一个神经网络来讲，使用 Self-training （Hard label）才会有用。

Entropy-based Regularization

这个方法描述的是，希望各个类别的数据都处于高密度分布。

这个方法即把标记数据的正确率与未标记数据的信息熵作为优化目标。

Semi-supervised SVM

如图，Semi-supervised SVM穷举了所有的可能性，然后去用 SVM 拟合，最后找出让 margin 最大又有error最小的方案。

Smoothness Assumption

基本精神：近朱者赤，近墨者黑。

如上，其假设是：

• x的分布不平均的；
• 如果两个x处于同一个 high density 区域，那么其标签是相同的。

这么做其实是有道理的：不是通过单纯的特征值相似，而是通过其所处区域。

如上，属于同一类的数据，可能不相似。但是其中间存在许多数据，可以过度到。

此外，这招在文件分类上也是有用的。

cluster and then label

如何实现呢？

有一种方法是，先进行聚类，接着打标签。

Graph-based Approach

如图，根据连通图，进行类别的划分。

对于有些数据，其图是很自然就建立成的，如网页；有些则需要我们自己建立图。

如上，图的好坏直接影响模型最终表现，但建立图是一件需要凭借直觉来做的事：

• 比如基于 auto-encoder 提取特征值来做相似度计算；
• 相似度计算完成，就可以建立图了：
• • 可以使用 k nearest neighbor ;
• • 可以使用 e-neighborhood （设定连接阈值）。

此外，还可以给边特殊的权重，比如与相似度成正比，建议使用 RBM function （蛮必要的）：$s(x^i,x^j)=e^{-\gamma||x^i-x^j||^2 }$s(xi,xj)=e−γ∣∣xi−xj∣∣2；

• 加上 exp ，可以提升性能；
• 只要距离远一点，权重就会下降很大；
• 这样避免了跨区域相连。

如图，建图的意义在于“传播”。

smoothness

$S=\frac{1}{2}\sum\limits_{i,j} w_{i,j}(y^i-y^j)^2$S=21​i,j∑​wi,j​(yi−yj)2

我们希望smoothness 这个值越小越好。如上，左边在直觉上也要平滑许多。

此外，上式还可以化简，如下图。

D是W每一行的和。

因此，如上，在优化目标中加上一个对 Smoothness 的优化。

Better Representation

Better Representation 的精神：去芜存菁，化繁为简。

我们观察到的世界很复杂，但是背后蕴含的规律很简单——因此我们需要看破真相。

将在 Supervised Learning 中介绍。