Semi-supervised Learning

Semi-supervised Learning 是 半监督学习 的意思。他是指用于训练的数据有一部分是有标签的，一部分数据是无标签的，同时使用这两部分数据进行学习。你可能会有一些疑问，为什么要使用没有标签的数据？没有标签的数据怎么能用来训练？对于第一个问题，是因为现在的机器学习方法大多都是数据驱动的方法，数据的量很大程度上会决定我们训练出的模型的好坏，但是提升数据量又是件不容易的事情，但是需要注意的是获取大量数据其实不难，难的是获取大量有标签的数据。比如图片分类的问题，我们现在有大量的摄像头安装在各种设备上，让他们不停的拍就能得到大量的图片，这是件很容易的事。所以如果这些无标签的数据也能对训练模型产生帮助，那么将是很好的，所以这就是半监督学习存在的意义。但是并不是所有问题都是能够通过使用一些无标签数据来提升有标签数据训练出的模型的，这就来到了第二个问题，没有标签的数据对训练模型有啥用？让我们来看下图这个例子，蓝色的点是标签为猫的数据，橙色是标签为狗的，如果只用有便签数据我们可能训练出的决策边界是竖着的那条红线。但是如果考虑无标签的数据，一种直觉告诉我们，可能斜着的那条红线会有更好的表现，置于会不会真的有更好的表现呢？其实这就取决于你对整个数据分布的假设符不符合实际了。接下来来看有哪些半监督学习的方法。

Semi-supervised Learning for Generative Model

在前面分类的那节课上我们学习过生成模型，他的理念就是训练出每个类别的样本的分布函数，然后使用贝叶斯公式计算一个新的样本属于每个类的概率，最后取概率最大的结果为最终的分类结果。训练的过程就是去用训练集数据求分布函数，采用的方法是极大似然估计。那么在用这种方法进行半监督学习的时候，能够有效提升模型效果的直观上的原因是如下图所示，使用有标签的数据训练出的分布如实线所示，如果数据的分布如图中所示，那么直观上的感受会感觉虚线的分布可能会更适应实际中的数据。所以我们可以使用无标签的数据来改变我们原来训练出的分布函数。

训练的步骤

首先我们不考虑为什么要这么做，只是来看看他是怎么做的。以下是训练的步骤：

第一步：初始化参数，随机生成 θ = { \mu 1 、 \mu 2 、 Σ 、 P ( C 1 ) 、 P ( C 2 ) } \theta=\{\mu^1、\mu^2、\Sigma、P(C_1)、P(C_2)\} θ={\mu 1、\mu 2、Σ、P(C1)、P(C2)}

第二步：计算每个无标签数据的后验概率 P θ ( C 1 ∣ x u ) P_\theta(C_1|x^u) Pθ(C1∣xu) ，即在参数为 θ \theta θ 条件下每个无标签数据属于每一类的概率

第三步：使用以下公式更新 θ \theta θ
P ( C 1 ) = N 1 + ∑ x u P ( C 1 ∣ x u ) N P ( C 2 ) = 1 − P ( C 1 ) \mu 1 = 1 N 1 ∑ x r ∈ C 1 x r + 1 ∑ x u P ( C 1 ∣ x u ) ∑ x u P ( C 1 ∣ x u ) x u \mu 2 = 1 N 2 ∑ x r ∈ C 2 x r + 1 ∑ x u P ( C 2 ∣ x u ) ∑ x u P ( C 2 ∣ x u ) x u Σ = ⋯

\begin{aligned} P(C_1) &= \frac {N_1+\sum_{x^u}P(C_1|x^u)} {N} \\ P(C_2) &= 1-P(C_1) \\ \mu^1 &= \frac {1} {N_1} \sum_{x^r \in C_1}x^r+\frac {1} {\sum_{x^u}P(C_1|x^u)} \sum_{x^u} P(C_1|x^u)x^u \\ \mu^2 &= \frac {1} {N_2} \sum_{x^r \in C_2}x^r+\frac {1} {\sum_{x^u}P(C_2|x^u)} \sum_{x^u} P(C_2|x^u)x^u \\ \Sigma&= \cdots \end{aligned} P(C1)P(C2)\mu 1\mu 2Σ=NN1+∑xuP(C1∣xu)=1−P(C1)=N11xr∈C1∑xr+∑xuP(C1∣xu)1xu∑P(C1∣xu)xu=N21xr∈C2∑xr+∑xuP(C2∣xu)1xu∑P(C2∣xu)xu=⋯
其中， x r x^r xr 表示有标签数据， x u x^u xu 表示无标签数据。上面的更新其实是在说，我现在已经根据了概率分布得到了每个无标签样本属于每个类的概率，假设分别是 P 1 、 P 2 、 ⋯ P_1、P_2、\cdots P1、P2、⋯ （如果这有两个类别的话就没有后面的 ⋯ \cdots ⋯），那么我就把这个样本给拆开来看，他的 P 1 P_1 P1 属于类别 C 1 C_1 C1 ，他的 P 2 P_2 P2 属于类别 C 2 C_2 C2 ，当然所有 P P P 加起来是 1 1 1 的。然后再和那些有标签的数据去来更新在这种样本条件下的极大似然估计情况下的概率分布（就是用上面的式子更新那些参数）。上面计算 P ( C 1 ) 、 \mu 1 P(C_1)、\mu^1 P(C1)、\mu 1 的式子中，前半部分是有标签的数据项，后半部分是无标签的数据项，有标签的数据项属于哪个类是确定的（标签告诉我们了）所以不用拆开，后半部分我们不知道属于哪个类，所以根据算出来的概率拆开。

然后不断重复迭代步骤二和三，直到参数收敛。通常参数是可以收敛的，和梯度下降一样，初始值的位置会决定最终收敛的位置落入不同的局部极小值点。

为什么这么训练？

在只使用有标签数据进行训练的时候，我们是去求解这些数据被采集到的条件下的概率最大的时候的概率分布的参数值，即极大似然的想法，我们的似然函数是：
log ⁡ L ( θ ) = ∑ x r log ⁡ ( P θ ( x r , y ^ r ) ) \log L(\theta) = \sum_{x^r}\log(P_\theta(x^r,\hat y^r)) logL(θ)=xr∑log(Pθ(xr,y^r))
其中 P θ ( x r , y ^ r ) P_\theta(x^r,\hat y^r) Pθ(xr,y^r) 是在类别为 y ^ r \hat y^r y^r 的概率分布上取到一个特制为 x r x^r xr 的样本的概率， P θ ( x r , y ^ r ) = P θ ( x r ∣ y ^ r ) P ( y ^ r ) P_\theta(x^r,\hat y^r)=P_\theta(x^r|\hat y^r)P(\hat y^r) Pθ(xr,y^r)=Pθ(xr∣y^r)P(y^r) 。这个时候任何一个样本只可能出现在一个样本的概率分布上，因为标签已经告诉我们了。那么再考虑加入无标签的数据时，我们不知道它属于那个类别，所以我们就允许他同时出现在所有类别的分布函数上，可以算出他在某一个类 C i C_i Ci 上出现的概率为 P = P θ ( x u ∣ C i ) P ( C i ) P = P_\theta(x^u|C_i)P(C_i) P=Pθ(xu∣Ci)P(Ci) ，所以他能被采到的概率就是在所有类别上被采到的概率的和，所以我们极大似然的方向就是希望这个无标签的样本能够被采集到，这个条件就比有标签的弱，在有标签的数据上，我们不仅要求他被采到，还要求他是要在标签所在的那个分布上采到。无标签就无所谓他在哪个分布上被采到，能被采到就行。所以被采到的概率为 P θ ( x u ) = P θ ( x u ∣ C 1 ) P ( C 1 ) + P θ ( x u ∣ C 2 ) P ( C 2 ) 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) 。似然函数变为：
log ⁡ L ( θ ) = ∑ x r log ⁡ ( P θ ( x r , y ^ r ) ) + ∑ x u P θ ( x u ) \log L(\theta) = \sum_{x^r}\log(P_\theta(x^r,\hat y^r)) + \sum_{x^u}P_\theta(x^u) logL(θ)=xr∑log(Pθ(xr,y^r))+xu∑Pθ(xu)
而上面那个训练步骤就是在对这个式子进行迭代求解（可能这个式子是一个超越方程，无法进行公式求解，只能迭代进行数值求解）

Low-density Separation

低密度分离是一个 “非黑即白” 的思想进行半监督学习的，他和上面不同，不接受无标签数据可以有一部分是一个类别，另一部分是另外一个类别。

Self-training

Self-training 的做法非常简单，首先用有标签的数据训练一个分类模型，然后把无标签的数据进行分类，然后取其中的一部分数据加入到有标签数据中，再重新训练模型。置于如何选数据，并没有一个确定的方法，你可以自己觉得，对于加入到训练集的无标签的数据，还可以给他们权重，来调整他们对模型的影响。

这是一种 hard-label 的方式，还有 soft-label 的方式，在 self-training 中，soft-label 是不会有效果的，因为加入到训练集的数据并不会影响最优时的损失值。

Entropy-based Regularization

上面那种方法其实是在制造新的有标签的数据来改变模型，而这个方法则是通过调整损失函数来改变模型。调整的思想是，我们就把无标签的数据看成是运用到实际中所输入到模型的数据，那么我们肯定会期望模型在进行分类的时候，每个数据属于某一个类别的概率很大，属于其他类别的概率很小（虽然也有可能分错了），而不希望模型告诉我输入的样本输入每个类的概率基本是相同的。所以我们可以基于这一点来调整我们的损失函数，当我们的模型让无标签的样本分类时所有类别的概率都差不多时有一个很大的损失，而只有一个类概率很大，其他都很小时损失很小。所以我们可以计算熵来衡量我们的模型能否做到尽可能的只让一个类别的概率很大，计算公式如下：
E ( x u ) = − ∑ m = 1 M y m u ln ⁡ y m u E(x^u)=-\sum_{m=1}^{M}y_m^u\ln{y_m^u} E(xu)=−m=1∑Mymulnymu
其中， M M M 是类别个数， y m u y_m^u ymu 是输入为 x u x^u xu 时，模型输出的该样本属于 m m m 类的概率，如果各个类别概率差不多时， E E E 会比较大，否则则很小，最小为 0 0 0 。那么我们的损失函数就可以在原来的后面加上这一项，这个有点类似于我们为了模型更平滑而加上正则项，为了调整是更希望模型在训练集上的准确率更高，还是在无标签样本上更能给出明确的分类结果，引入一个权重参数 λ \lambda λ 来平衡两者的关系，损失函数变为：
L = ∑ x r C ( x r , y ^ r ) + λ ∑ x u E ( x u ) L=\sum_{x^r}C(x^r,\hat y^r) + \lambda\sum_{x^u}E(x^u) L=xr∑C(xr,y^r)+λxu∑E(xu)

Smoothness Assumption

上面那个采用的是先做分类，再把分类好的无标签数据加入到有标签数据的方式进行半监督学习。接下来这类方法类似于先做聚类再用聚类的结果训练。即把无标签的数据标记为和他属性相类似的有标签的数据，并且这种类似是可以传递的，即被标签后的数据可以作为其他没标签的数据标记类别时的参考。使用这种方法有一个前提假设，要求同一类的数据在分布上是集中的，密度比较大，而不同数据在分布上较为分散。这样，有标签的数据就可以在同一个密度簇中传播标签，最终使整个簇被标记为同一个标签。比如下图， x 1 、 x 2 x^1、x^2 x1、x2 在同一个密度簇中，但距离较远，而 x 3 x^3 x3 在另一个簇中，虽然可能 x 3 x^3 x3 离 x 2 x^2 x2 更近一些，但是由于他两之间没有较为稠密的路径可以相连，所以不会被看作同一类，但 x 1 x^1 x1 可以不断感染周围的数据，最终影响传播到 x 2 x^2 x2 ，使其被标记为同一类。

这么做在实际中也是有合理的依据的，例如下图这个数据集，最右边的 2 2 2 其实和最左边的 2 2 2 通过比较同一个位置的像素可能算出来的距离并不是很近，可能还没有和那个 3 3 3 近，但是如果中间还有一些数据集是这两种 2 2 2 的过渡形式的话，那么就可以做到正确标记。

聚完簇标记完标签，就可以按照常用的方法训练分类器了。

Graph based Approach

我个人感觉，上面的聚类方法其实有点类似密度聚类的思想，接下来的基于图的聚类方法其实感觉和上面使用的密度聚类也很相似，在上课中没有细想这两部分内容是并列的关系还是递进的关系，现在感觉应该是递进的关系，即接下讲的是具体的实际操作方法。

基于图的方法其实可以分为两步，第一步是把每个样本看作是一个点，然后采用一定的放在在一些相似的点之间建立边，最终所有的点构成了图，不过并不是所有点之间都是两两连通的，如下图所示，会形成多条连通的图。第二步就是根据每个连通的图内的有标签的点，标记其他的无标签的点，要是同一个连通图上的所有有标签的点都是同一类的，那就很容易了，直接把所有能连接的点都标记成这一类就好了。如果存在多种类别的点在同一个连通图的话，则需要使用一种规则来标记其他点了。

Graph Structure

接下来先将怎么建立点与点之间的变变成图。首先我们需要定义点与点之间距离的计算方法，进而计算他们的相似度 s ( x i , x j ) s(x^i,x^j) s(xi,xj) ，可以使用例如欧氏距离等多种计算方式。

第一步就是建立点与点之间的边，将不同点连起来了。第一种方法是 K 邻近连接法，即把一个点和他最近的 K 个点相连。第二种是 e e e 密度连接法，即把一个点和他周围距离小于 e e e 的所有点相连，有多少连多少，没有就不连。每个边也都会有权重，权重值和距离有关，我们希望距离越远权重越小，所以可以使用下面的函数来计算边的权重 s s s ，同时也可以理解为相似度。
s ( x i , x j ) = e − γ ∣ ∣ x i − x j ∣ ∣ 2 s(x^i,x^j) = e^{-\gamma||x^i-x^j||^2} s(xi,xj)=e−γ∣∣xi−xj∣∣2

Label based on structure

写到这里我意识到可能我前面理解的和老师讲解的不太一样了，我原来的理解是接下来用下面的方法计算出把一个为标记的样本标记为某一类的代价，然后使用代价最小的标签方法来标未标签的数据，然后再拿去用常规的方法训练分类器。但其实老师在课上讲的意思并不只看这个代价，而是把这个代价当做损失函数的一项，类似于正则化的思想，还是要先用训练好的数据训练一个分类器，然后再分类为标签的数据，然后再根据上面的图的结构使用后面说的方法去计算那一项损失。这一项损失体现了标签的平滑成都，计算公式为：
S = 1 2 ∑ i , j w i , j ( y i − y j ) 2 S = \frac {1} {2} \sum_{i,j}w_{i,j}(y^i-y^j)^2 S=21i,j∑wi,j(yi−yj)2
其中 y i − y j y^i-y^j yi−yj 是两个相邻的点的标签，一样就是 0 ，不一样就是 1 ， w i , j w_{i,j} wi,j 是这两个点的边权，前面的系数应该是为了上面那个式子可以用更简洁的形式表示。Smooth” 的结果。

使用线性代数矩阵表示上面那个式子，可以表示为：
S = y T L y S=\boldsymbol y^T \boldsymbol L \boldsymbol y S=yTLy
其中， y \boldsymbol y y 是所有数据的标签构成的向量， y = [ ⋯ , y i , ⋯ , y j , ⋯ ] T \boldsymbol y = [\cdots,y^i,\cdots,y^j,\cdots]^T y=[⋯,yi,⋯,yj,⋯]T 。 L = D − W \boldsymbol L = \boldsymbol D - \boldsymbol W L=D−W ，是两个矩阵的差，矩阵 W \boldsymbol W W 是图的边权的邻接矩阵，矩阵 D \boldsymbol D D 是对角线各行元素为矩阵 W \boldsymbol W W 各行的和的对角矩阵。所以最后总的损失函数就是：
L = ∑ x r + λ S L=\sum_{x^r}+\lambda S L=xr∑+λS