第十三章 半监督学习

目录

一、半监督学习简介

二、生成式方法

三、半监督SVM

四、图半监督学习

五、基于分歧的方法

六、半监督聚类




\bullet 本章假设给定有标记样本集D_{l}=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{l}, y_{l}\right)\right\}和未标记样本集D_{u}=\left\{\boldsymbol{x}_{l+1}, \boldsymbol{x}_{l+2}, \ldots, \boldsymbol{x}_{l+u}\right\}l \ll u, l+u=m

一、半监督学习简介

定义:让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能,就是半监督学习。P294

\bullet 要学习半监督学习,首先我们要了解未标记样本

形式化地看我们有训练样本集D_{l}=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{l}, y_{l}\right)\right\},这l个的类别标记(即是否好瓜)已知,称为“有标记样本”;此外,还有D_{u}=\left\{\boldsymbol{x}_{l+1}, \boldsymbol{x}_{l+2}, \ldots, \boldsymbol{x}_{l+u}\right\} l \ll u,这u个样本的类别标记未知(即不知是否有好瓜),称为“未标记”样本。半监督学习就是将这些未标记样本在构建模型的过程中利用起来。

\bullet 此外半监督学习有多种形式:聚类假设与流形假设、纯半监督学习与直推学习、主动学习。

\bullet 聚类假设与流形假设

事实上,未标记样本虽未直接包含标记信息,但若它们与有标记样本是从同样的数据源独立同分布采样而来,则它们所包含的关于数据分布的信息对建立模型将大有裨益.图13.1(P294)给出了一一个直观的例示.若仅基于图中的一一个正例和一个反例,则由于待判别样本恰位于两者正中间,大体上只能随机猜测;若能观察到图中的未标记样本,则将很有把握地判别为正例。

很明显,依赖未标记样本点的分布可以更有把握地判断正反例。同时这也是一种常见的利用未标记样本的方法:“聚类假设”,即假设数据存在簇结构,同一个簇的样本属于同一个类别,图13.1可以清晰地向我们展示。

流形假设即假设数据分布在一个流形的结构上,邻近的样本拥有相似的输出值。“邻近” 程度常用“相似”程度来刻画,因此,流形假设可看作聚类假设的推广,但流形假设对输出值没有限制,因此比聚类假设的适用范围更广,可用于更多类型的学习任务。

事实上,无论聚类假设还是流形假设,其本质都是“相似的样本拥有相似的输出”这个基本假设。

\bullet 主动学习、纯半监督学习与直推学习

我们可以用D_{l}先训练一个模型,拿这个模型去地里挑一个样本,查询正反例,然后把这个新获得的有标记样本加入D_{u}中重新训练一个模型,再去挑样本...这样,若每次都挑出对改善模型性能帮助大的样本,则只需查询比较少的样本就能构建出比较强的模型,从而大幅降低标记成本.这样的学习方式称为“主动学习”

纯半监督学习与直推学习前者假定训练数据中的未标记样本并非待预测的数据,而后者则假定学习过程中所考虑的未标记样本恰是待预测数据,学习的目的就是在这些未标记样本上获得最优泛化性能。

图13.2(P295)直观地显示出主动学习、纯半监督学习、直推学习的区别。




二、生成式方法

\bullet 生成式方法定义
生成式方法是直接基于生成式模型的方法.此类方法假设所有数据(无论是否有标记)都是由同一一个潜在的模型“生成”的.这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来,而未标记数据的标记则可看作模型的缺失参数,通常可基于EM算法进行极大似然估计求解。

\bullet 优点

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

\bullet 缺点

此类方法有一个关键:模型假设必须准确,即假设的生成式模型必须与真实数据分布吻合;否则利用未标记数据反倒会降低泛化性能。遗憾的是,在现实任务中往往很难事先做出准确的模型假设,除非拥有充分可靠的领域知识。

\bullet 生成式方法生成模型高斯混合模型

数据样本是基于如下概率密度生成的:p(\boldsymbol{x})=\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)(13.1)P296

又由最大化后验概率可知:

\begin{aligned}
f(\boldsymbol{x}) &=\underset{j \in \mathcal{Y}}{\arg \max } p(y=j | \boldsymbol{x}) \\
&=\underset{j \in \mathcal{Y}}{\arg \max } \sum_{i=1}^{N} p(y=j, \Theta=i | \boldsymbol{x}) \\
&=\underset{j \in \mathcal{Y}}{\arg \max } \sum_{i=1}^{N} p(y=j | \Theta=i, \boldsymbol{x}) \cdot p(\Theta=i | \boldsymbol{x})
\end{aligned}(13.2)P296

不难发现,式(13.2)中估计p(y=j | \Theta=i, \boldsymbol{x})需知道样本的标记,因此仅能使用有标记数据;而p(\Theta=i | \boldsymbol{x})不涉及样本标记,因此有标记和未标记数据均可利用,通过引入大量的未标记数据,对这项的估计可望由于数据量的增长而更为准确,于是式(13.2)整体的估计可能会更准确。由此可清楚地看出未标记数据何以能辅助提高分类模型的性能。

\bullet 高斯混合模型参数估计

高斯混合模型的参数有三个:\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}

用极大似然法来估计高斯混合模型的参数\left\{\left(\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) | 1 \leqslant i \leqslant N\right\}, D_{l} \cup D_{u}的 对数似然是:(13.4)P297

\begin{aligned}
L L\left(D_{l} \cup D_{u}\right)=& \sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l}} \ln \left(\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot p\left(y_{j} | \Theta=i, \boldsymbol{x}_{j}\right)\right) \\
&+\sum_{\boldsymbol{x}_{j} \in D_{u}} \ln \left(\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\right)
\end{aligned}

可见式中有基于有标记样本的有监督项和基于未标记样本的无监督项,因此可用EM算法求解:

\bullet E步:\gamma_{j i}=\frac{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}

\bullet M步:

\begin{aligned}
\boldsymbol{\mu}_{i}=& \frac{1}{\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}+l_{i}}\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \boldsymbol{x}_{j}+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{x}_{j}\right) \\
\boldsymbol{\Sigma}_{i}=& \frac{1}{\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}+l_{i}}\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\mathrm{T}}\right.\\
+&\left.\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\mathrm{T}}\right) \\
\alpha_{i}=& \frac{1}{m}\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}+l_{i}\right)
\end{aligned}

以上过程不断迭代直至收敛,获得模型参数,然后代入式(13.3)和(13.2)以进行样本分类。




三、半监督SVM

\bullet 半监督SVM定义

半监督支持向量机, 简称S3VM,是支持向量机在半监督学习上的推广,在不考虑未标记样时,支持向量机试图找到最大间隔划分超平面,而在考虑未标记样本后,S3VM试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面。书上的图13.3(P298)可以说是十分形象地表示了出来。

\bullet TSVM

定义:半监督支持向量机中最著名的是TSVM 。TSVM试图考虑对未标记样本进行各种可能的标记指派,即尝试将每个未标记样本分别作为正例或反例,然后在所有这些结果中,寻求一个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上间隔最大化的划分超平面,一旦划分超平面得以确定,未标记样本的最终标记指派就是其预测结果。

TSVM的学习目标是为D_{u}中的样本给出预测标记\hat{\boldsymbol{y}}=\left(\hat{y}_{l+1}, \hat{y}_{l+2}, \ldots, \hat{y}_{l+u}\right), \hat{y}_{i} \in\{-1,+1\},使得:

\begin{aligned}
&\min _{w, b, 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}\\
&\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \ldots, l\\
&\hat{y}_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=l+1, l+2, \ldots, m\\
&\xi_{i} \geqslant 0, \quad i=1,2, \dots, m
\end{aligned}

TSVM的算法描述如图13.4(P300):

TSVM采用局部搜索来迭代地寻找式(13.9)的近似解。

具体来说,

1、它先利用有标记样本学得一个SVM,然后,利用这个SVM对未标记数据进行标记指派,即将SVM预测的结果作为“伪标记”赋予未标记样本。

2、此时\hat{\boldsymbol{y}}成为已知,将其代入式(13.9)即得到一个标准SVM问题,于是可求解出新的划分超平面和松弛向量;注意到此时未标记样本的伪标记很可能不准确,因此D_{u}要设置为比D_{l}小的值,使有标记样本所起作用更大。

3、接下来, TSVM找出两个标记指派为异类且很可能发生错误的未标记样本,交换它们的标记,再重新基于式(13.9)求解出更新后的划分超平面和松弛向量。

4、然后再找出两个标记指派为异类且很可能发生错误的未标记样本, ....标记指派调整完成后,逐渐增大D_{u}以提高未标记样本对优化目标的影响,进行下一轮标记指派调整,直至D_{u} = D_{l}为止。

5、此时求解得到的SVM不仅给未标记样本提供了标记,还能对训练过程中未见的示例进行预测。

\bullet 缺点

搜寻标记指派可能出错的每一对未标记样本进行调整,是一个涉及巨大计算开销的大规模优化问题。因此,半监督SVM研究的一个重点是如何设计出高效的优化求解策略,由此发展出很多方法。




四、图半监督学习

\bullet 图半监督学习定义

给定一个数据集,我们可将其映射为-一个图,数据集中每个样本对应于图中一个结点,若两个样本之间的相似度很高(或相关性很强),则对应的结点之间存在一条边,边的“强度”正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色,而未标记样本所对应的结点尚未染色。于是,半监督学习就对应于“颜色”在图上扩散或传播的过程。

\bullet 优点

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

\bullet 缺点

1、存储开销,若样本数为O\left(m\right),则算法中所涉及的矩阵规模为O\left(m^{2}\right),这使得此类算法很难直接处理大规模数据;

2、由于构图过程仅能考虑训练样本集,难以判知新样本在图中的位置,因此,在接收到新样本时,或是将其加入原数据集对图进行重构并重新进行标记传播,或是需引入额外的预测机制。

\bullet 针对二分类问题的标记传播方法

基于有标记样本和未标记样本的并集构建一个图G=(V, E),常基于高斯函数定义为:(\mathbf{W})_{i j}=\left\{\begin{array}{ll}
\exp \left(\frac{-\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{2}^{2}}{2 \sigma^{2}}\right), & \text { if } i \neq j \\
0, & \text { otherwise }
\end{array}\right.

假定从图中学得一个实值函数:f: V \rightarrow \mathbb{R},然后可定义关于此实值函数的“能量函数”:

利用此函数可以求得实值函数在有标记样本和未标记样本上的预测结果f_{l}=\left(f\left(\boldsymbol{x}_{1}\right) ; f\left(\boldsymbol{x}_{2}\right) ; \ldots ; f\left(\boldsymbol{x}_{l}\right)\right), \quad \boldsymbol{f}_{u}=\left(f\left(\boldsymbol{x}_{l+1}\right)\right.\left.f\left(\boldsymbol{x}_{l+2}\right) ; \ldots ; f\left(\boldsymbol{x}_{l+u}\right)\right)

采用分块矩阵表示方式:\mathbf{W}=\left[\begin{array}{cc}
\mathbf{W}_{l l} & \mathbf{W}_{l u} \\
\mathbf{W}_{u l} & \mathbf{W}_{u u}
\end{array}\right]\mathbf{D}=\left[\begin{array}{cc}
\mathbf{D}_{l l} & \mathbf{0}_{l u} \\
\mathbf{0}_{u l} & \mathbf{D}_{u u}
\end{array}\right],公示经过运算可

重写为:\boldsymbol{f}_{u}=\left(\mathbf{D}_{u u}-\mathbf{W}_{u u}\right)^{-1} \mathbf{W}_{u l} \boldsymbol{f}_{l}(式13.15)P302,

\mathbf{P}_{u u}=\mathbf{D}_{u u}^{-1} \mathbf{W}_{u u}, \mathbf{P}_{u l}=\mathbf{D}_{u u}^{-1} \mathbf{W}_{u l},则式13.15可重写为式13.17:

于是将D_{l}上的标记信息作为\boldsymbol{f}_{l}=\left(y_{1} ; y_{2} ; \ldots ; y_{l}\right)带入式13.17,即可利用求得的f_{u}对未标记样本进行预测。

\bullet 适用于多分类问题的标记传播方法

继承二分类问题标记传播的图G=(V, E),定义一个非负标记矩阵\mathbf{F}=\left(\mathbf{F}_{1}^{\mathrm{T}}, \mathbf{F}_{2}^{\mathrm{T}}, \ldots, \mathbf{F}_{l+u}^{\mathrm{T}}\right)^{\mathrm{T}},将其初始化:

有迭代计算式:\mathbf{F}(t+1)=\alpha \mathbf{S} \mathbf{F}(t)+(1-\alpha) \mathbf{Y}

迭代至收敛可得:\mathbf{F}^{*}=\lim _{t \rightarrow \infty} \mathbf{F}(t)=(1-\alpha)(\mathbf{I}-\alpha \mathbf{S})^{-1} \mathbf{Y}

\mathbf{F}^{*}可得未标记样本中的样本标记。

算法描述如图13.5(P303):




五、基于分歧的方法

\bullet 多视图数据

每个属性集可看作一个视图。对一部电影来说图像画面、声音信息、字幕等等都是一个属性集对应一个视图,暂且仅考虑图像画面属性集所构成的视图和声音属性集所构成的视图。于是,一个电影片段可表示为样本\left(\left\langle\boldsymbol{x}^{1}, \boldsymbol{x}^{2}\right\rangle, y\right),其中{x}^{i}是样本在视图i中的示例,即基于该视图属性描述而得的属性向量,不妨假定{x}^{1}为图像视图中的属性同量,{x}^{2}为声音视图中的属性向量;y是标记,假定是电影的类型,例如“动作片”、“爱情片” 等。 \left(\left\langle\boldsymbol{x}^{1}, \boldsymbol{x}^{2}\right\rangle, y\right)这样的数据就是多视图数据。

\bullet 相容互补性

仍以电影为例,某个片段上有两人对视,仅凭图像画面信息难以分辨其类型,但此时若从声音信息听到“我爱你”,则可判断出该片段很可能属于“爱情片”;另一方面,若仅凭图像画面信息认为“可能是动作片”,仅凭声音信息也认为“可能是动作片”,则当两者一起考虑时就有很大的把握判别为“动作片”。显然,在“相容性”基础上,不同视图信息的“互补性”会给学习器的构建带来很多便利。

\bullet 协同训练

协同训练正是很好地利用了多视图的“相容互补性”。

可用一个简单的办法来利用未标记数据:

\bullet 首先在每个视图上基于有标记样本分别训练出一个分类器;

\bullet 然后让每个分类器分别去挑选自己“最有把握的”未标记样本赋予伪标记,并将伪标记样本提供给另-一个分类器作为新增的有标记样本用于训练更新....

\bullet 这个“互相学习、共同进步”的过程不断迭代进行,直到两个分类器都不再发生变化,或达到预先设定的迭代轮数为止。

算法描述如图13.6(P306):

\bullet 优点

[1] 即便在更弱的条件下,协同训练以然可以有效地提升弱分类器的性能。

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

\bullet 缺点

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




六 半监督聚类

\bullet 作用

聚类是一种典型的无监督学习任务,然而在现实聚类任务中我们往往能获得一些额外的监督信息, 于是可通过半监督聚类来利用监督信息以获得更好的聚类效果。

\bullet 两种监督信息

聚类任务中获得的监督信息大致有两种类型.第一种类型是“必连”与“勿连”约束,前者是指样本必属于同一个簇,后者是指样本必不属于同一个簇;第二种类型的监督信息则是少量的有标记样本.

\bullet 约束k均值算法

约束k均值算法是利用第一类监督信息(即“必连”和“勿连”)的代表。算法描述如图13.7(P307):


\bullet 约束种子k均值算法

利用少量有标记样本:

直接将它们作为“种子”,用它们初始化k均值算法的k个聚类中心,并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系.这样就得到了约束种子k均值算法。

其算法描述如图13.9(P309):

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,456评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,370评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,337评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,583评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,596评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,572评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,936评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,595评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,850评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,371评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,951评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2 342

推荐阅读更多精彩内容