半监督学习笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  主要记录下半监督学习的一些方法,包括生成式方法,半监督SVM,图半监督学习,基于分歧的方法和半监督聚类。

半监督学习(Semi-supervised Learning)

  我们经常会有一些数据集中部部分样本被标记了,部分样本没有标记。直觉上,我们可以利用已经标记的样本训练出一个模型,再用这个模型去挑选一个样本,人工再标记这个样本,然后再训练模型。这便是主动学习(Active Learning),需要注意的是,主动学习不是从样本总体中随机地挑选样本进行学习,而是会挑选那些比较难分类的样本,那些当前分类器分类效果不理想的样本进行训练。

比较难分类的样本,拿二分类问题来说,就是在分类“线”周围的那些样本。

  主动学习虽然比人工标记全部未标记的样本工作量要小,但也依然需要人工标记,引入了额外的专家知识,通过与外界的交互来将部分未标记样本转变为标记样本,若不引入额外的专家知识,便用到了半监督学习。
  半监督要利用未标记样本,需要做一些将未标记样本所揭示的数据分布信息与 类别标记相联系的假设,通常有两种常见的假设:

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

  事实上,无论聚类假设还是流形假设,其本质都是“相似的样本拥有相似的输出” 这个基本假设。
  半监督学习可进一步划分为纯(pure)半监督学习和直推学习(transductive learning):

  • 纯(pure)半监督学习:假定训练数据中的未标记样本并非待预测的数据,希望学得模型能适用于训练过程中未观察到的数据。
  • 直推学习(transductive learning):假定学习过程中所考虑的未标记样本恰是待预测数据,学习的目的就是在这些未标记样本上获得最优泛化性能,仅试图对学习过程中观察到的未标记数据进行预测。

生成式方法(Generative Methods)

  生成式方法是直接基于生成式模型的方法。此类方法假设所有数据(无论是否有标记)都是由同一个潜在的模型生成的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来,而未标记数据的标记则可看作模型的缺失参数,通常可基于EM算法进行极大似然估计求解.此类方法的区别主要在于生成式模型的假设,不同的模型假设将产生不同的方法。
  给定样本\(\boldsymbol{x}\),其真实类别标记为\(y \in \mathcal{Y}\)\(\mathcal{Y}=\{1,2, \ldots, N\}\)为所有可能的类别。假设样本由高斯混合模型生成,且每个类别对应一个高斯混合成分,数据样木是基于如下概率密度生成: \[ p(\boldsymbol{x})=\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \quad (\alpha_{i} \geqslant 0, \sum_{i=1}^{N} \alpha_{i}=1) \]   \(p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\)是样本\(\boldsymbol{x}\)\(i\)个高斯混合成分的概率。
  令\(f(\boldsymbol{x}) \in \mathcal{Y}\)表示模型\(f\)\(\boldsymbol{x}\)的预测标记,\(\Theta \in\{1,2, \ldots, N\}\)表示样本\(\boldsymbol{x}\)隶属的高斯混合成分,由最大化后验概率可知: \[ \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} \]   其中后验概率为: \[ p(\Theta=i | \boldsymbol{x})=\frac{\alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \]   \(p(y=j | \Theta=i, \boldsymbol{x})\)\(\boldsymbol{x}\)由第\(i\)个高斯混合成分生成且其类别为\(j\)的概率,由于假设每个类别对应一个高斯混合成分,因此\(p(y=j | \Theta=i, \boldsymbol{x})\)仅与样本\(\boldsymbol{x}\)所属的高斯混合成分\(\Theta\)有关,可用\(p(y=j | \Theta=i)\)代替。不失一般性,假定第\(i\)个类别对应于第\(i\)个高斯混合成分,即\(p(y=j | \Theta=i)=1\)当且仅当\(i=j\),否则\(p(y=j | \Theta=i)=0\)
  估计\(p(y=j | \Theta=i, \boldsymbol{x})\)需知道样本的标记,因此仅能使用有标记数据。而\(p(\Theta=i | \boldsymbol{x})\)不涉及样本标记,因此有标记和未标记数据均可利用,通过引入大量的未标记数据,对这一项的估计可望由于数据量的增长而更为准确\(f(\boldsymbol{x})\)整体的估计可能会更准确.由此可清楚地看出未标记数据何以能辅助提高分类模型的性能。
  给定有标记样本集\(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\),假设所有样本独立同分布,且都是由同一个高斯混合模型生成的。用极大似然法来估计高斯混合模型的参数\(\left\{\left(\alpha_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) | 1 \leqslant i \leqslant N\right\}, D_{l} \cup D_{u}\)对数似然是: \[ \begin{aligned} L L\left(D_{l} \cup D_{u}\right)=& \sum_{\left(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}, \mathbf{\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}, \mathbf{\Sigma}_{i}\right)\right) \end{aligned} \]   高斯混合模型参数估计可用EM算法求解,迭代更新式如下:

  • E步:根据当前模型参数计算未标记样本\(\boldsymbol{x}_{j}\)属于各高斯混合成分的概率。 \[ \gamma_{j i}=\frac{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \mathbf{\Sigma}_{i}\right)}{\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \]
  • M步:基于\(\gamma_{j i}\)更新模型参数,其中\(l_i\)表示第\(i\)类的有标记样本数目。 \[ \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}}+ \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} \]   以上过程不断迭代直至收敛,即可获得模型参数。然后由\(f(\boldsymbol{x})\)\(p(\Theta=i | \boldsymbol{x})\)就能对样本进行分类。
      将上述过程中的高斯混合模型换成混合专家模型、朴素贝叶斯模型等即可推导出其他的生成式半监督学习方法。此类方法简单,易于实现,在有标记数据极少的情形下往往比其他方法性能更好。然而,此类方法有一个关键:模型假设必须准确,即假设的生成式模型必须与真实数据分布吻合;否则利用未标记数据反倒会降低泛化性能。遗憾的是,在现实任务中往往很难事先做出准确的模型假设,除非拥有充分可靠的领域知识

半监督SVM(Semi-Supervised Support Vector Machine,S3VM)

  半监督支持向量机是支持向量机在半监督学习上的推广,在不考虑未标记样本时,支持向量机试图找到最大间隔划分超平面,而在考虑未标记样本后,S3VM试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面,下图是一个例子。

TSVM(Transductive Support Vector Machine)

  半监督支持向量机中最著名的是TSVM,与标准SVM一样,TSVM也是针对二分类问题的学习方法。TSVM试图考虑对未标记样本进行各种可能的标记指派(label assignment)。即尝试将每个未标记样本分别作为正例或反例,然后在所有这些结果中,寻求个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上问隔最大化的划分超平面一旦划分超平面得以确定,未标记样本的最终标记指派就是其预测结果。令\(y_{i} \in\{-1,+1\}\),TSVM的学习目标是为\(D_u\)中的样本给出预测标记\(\hat{\boldsymbol{y}}=\left(\hat{y}_{l+1}, \hat{y}_{l+2}, \dots, \hat{y}_{l+u}\right)\),使得: \[ \min _{\boldsymbol{w}, b, \boldsymbol{\hat{y}}, \boldsymbol{\xi}} \frac{1}{2}\|\boldsymbol{w}\|_{2}^{2}+C_{l} \sum_{i=1}^{l} \xi_{i}+C_{u} \sum_{i=l+1}^{m} \xi_{i} \\ s.t. \quad \begin{array}{l}{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, \ldots, m}\end{array} \]   其中\((\boldsymbol{w},b)\)确定了一个划分超平面,\(\boldsymbol{\xi}\)为松弛向量,\(\xi_{i}(i=1,2, \dots, l)\)对应于有标记样本,\(\xi_{i}(i=l+1, l+2, \dots, m)\)对应于未标记样本。\(C_l\)\(C_u\)是由用户指定的用于平衡模型复杂度、有标记样本与未标记样本重要程度的折中参数。
  显然,尝试未标记样本的各种标记指派是一个穷举过程,仅当未标记样本 很少时才有可能直接求解。对于样本很多时,显然不可行,因此TSVM采用局部搜索来迭代地寻找上式的近似解。具体来说,它先利用有标记样本学得一个SVM,忽略上式中\(C_u\)\(\boldsymbol{\hat{y}}\)的项和约束。然后,利用这个SVM对未标记数据进行标记指派,即将SVM预测的结果作为伪标记(pseudo-label)赋予未标记样本。此时\(\boldsymbol{\hat{y}}\)成为已知,将其代入上式即得到一个标准SVM问题,于是可求解出新的划分超平面和松弛向量。此时未标记样本的伪标记很可能不准确,因此\(C_u\)要设置为比\(C_l\)小的值,使有标记样本所起作用更大。接下来,TSVM找出两个标记指派为异类且很可能发生错误的未标记样本,交换它们的标记,再重新基于上式求解出更新后的划分超平面和松弛向量,然后再找出两个标记指派为异类且很可能发生错误的未标记样本,不断迭代,标记指派调整完成后,逐渐增大\(C_u\)以提高未标记样本对优化目标的影响,进行下一轮标记指派调整,直至\(C_u=C_l\)为止。此时求解得到的SVM不仅给未标记样本提供了标记,还能对训练过程中未见的示例进行预测。TSVM的伪代码如下所示:

  第6行的松弛变量满足\(\xi_i+\xi_j \gt 2\),意味着\(\hat{y}_i\)\(\hat{y}_j\)很可能是错误的,需对二者进行交换后重新求解。
  在对未标记样本进行标记指派及调整的过程中,有可能出现类别不平衡问题,即某类的样本远多于另一类,这将对SVM的训练造成困扰。为了减轻类别不平衡性所造成的不利影响,可对伪代码中的算法改进:将优化目标中的\(C_\)项拆分为\(C_u^+\)\(C_u^-\)两项,分别对应基于伪标记而当作正、反例使用的未标记样本,并在初始化时令其中\(u_+\)\(u_-\)为基于伪标记而当作正、反例使用的未标记样本数。
  可以看出搜寻标记指派可能出错的每一对未标记样本进行调整,是一个涉及巨大计算开销的大规模优化问题,所以半监督SVM研究的一个重点是如何设计出高效的优化求解策略,由此发展出很多方法,如基于图核函数梯度下降的LDS和基于标记均值估计的meanS3VM等。

图半监督学习

  给定一个数据集,我们可将其映射为一个图,数据集中每个样本对应于图中一个结点,若两个样本之间的相似度很高(或相关性很强),则对应的结点之间存在一条边,边的强度(strength)正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色,而未标记样本所对应的结点尚未染色。于是,半监督学习就对应于颜色在图上扩散或传播的过程。一个图可以用一个矩阵来描述,这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。
     图\(G=(V,E)\)基于\(D_{l} \cup D_{u}\)构建,其中点集\(V=\left\{\boldsymbol{x}_{1}, \ldots, \boldsymbol{x}_{l}, \boldsymbol{x}_{l+1}, \dots, \boldsymbol{x}_{l+u}\right\}\),边集\(E\)可表示为一个亲和矩阵(affinity matrix),常基于高斯函数定义为: \[ (\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. \]   假定从图\(G=(V,E)\)将学得一个实值函数\(f : V \rightarrow \mathbb{R}\),其对应的分类规则为:\(y_{i}=\operatorname{sign}\left(f\left(\boldsymbol{x}_{i}\right)\right), y_{i} \in\{-1,+1\}\)。直观上看,相似的样本应具有相似的标记,于是可定义关于\(f\)的能量函数(energy function): \[ \begin{aligned} E(f) &=\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}(\mathbf{W})_{i j}\left(f\left(\boldsymbol{x}_{i}\right)-f\left(\boldsymbol{x}_{j}\right)\right)^{2} \\ &=\frac{1}{2}\left(\sum_{i=1}^{m} d_{i} f^{2}\left(\boldsymbol{x}_{i}\right)+\sum_{j=1}^{m} d_{j} f^{2}\left(\boldsymbol{x}_{j}\right)-2 \sum_{i=1}^{m} \sum_{j=1}^{m}(\mathbf{W})_{i j} f\left(\boldsymbol{x}_{i}\right) f\left(\boldsymbol{x}_{j}\right)\right) \\ &=\sum_{i=1}^{m} d_{i} f^{2}\left(\boldsymbol{x}_{i}\right)-\sum_{i=1}^{m} \sum_{j=1}^{m}(\mathbf{W})_{i j} f\left(\boldsymbol{x}_{i}\right) f\left(\boldsymbol{x}_{j}\right) \\ &=\boldsymbol{f}^{T}(\mathbf{D}-\mathbf{W}) \boldsymbol{f} \end{aligned} \]   其中\(\boldsymbol{f}=\left(\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{f}_{u}^{\mathrm{T}}\right)^{\mathrm{T}}, \boldsymbol{f}_{l}=\left(f\left(\boldsymbol{x}_{1}\right) ; f\left(\boldsymbol{x}_{2}\right) ; \ldots ; f\left(\boldsymbol{x}_{l}\right)\right), \boldsymbol{f}_{u}=\left(f\left(\boldsymbol{x}_{l+1}\right);f\left(\boldsymbol{x}_{l+2}\right);\cdots;f\left(\boldsymbol{x}_{l+u}\right)\right).\)分别为函数\(f\)在有标记样本与未标记样本上的预测结果,\(\mathbf{D}=\operatorname{diag}\left(d_{1}, d_{2}, \dots, d_{l+u}\right)\)是一个对角矩阵,其对角元素\(d_{i}=\sum_{j=1}^{l+u}(\mathbf{W})_{i j}\)为矩阵\(\mathbf{W}\)的第\(i\)行元素之和。
  具有最小能量的函数\(f\)在有标记样木上满足\(f\left(\boldsymbol{x}_{i}\right)=y_{i}(i=1,2, \ldots, l)\),在未标记样本上满足\(\boldsymbol{\Delta f}=0\),其中\(\Delta=\mathbf{D}-\mathbf{W}\)为拉普拉斯矩阵(Laplacian matrix),以第\(l\)行与第\(l\)列为界,采用分块矩阵表示方式: \[ \mathbf{W}=\left[ \begin{array}{ll}{\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] \]   \(E(f)\)可重写为: \[ \begin{aligned} E(f)&=\left(\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{f}_{u}^{\mathrm{T}}\right)\left(\left[ \begin{array}{cc}{\mathbf{D}_{l l}} & {\mathbf{0}_{l u}} \\ {\mathbf{0}_{u l}} & {\mathbf{D}_{u u}}\end{array}\right] - \left[ \begin{array}{ll}{\mathbf{W}_{l l}} & {\mathbf{W}_{l u}} \\ {\mathbf{W}_{u l}} & {\mathbf{W}_{u u}}\end{array}\right]\right)\left[ \begin{array}{l}{\boldsymbol{f}_{l}} \\ {\boldsymbol{f}_{u}}\end{array}\right] \\ &=\boldsymbol{f}_{l}^{\mathrm{T}}\left(\mathbf{D}_{l l}-\mathbf{W}_{l l}\right) \boldsymbol{f}_{l}-2 \boldsymbol{f}_{u}^{\mathrm{T}} \mathbf{W}_{u l} \boldsymbol{f}_{l}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\mathbf{D}_{u u}-\mathbf{W}_{u u}\right) \boldsymbol{f}_{u} \end{aligned} \]   令\(\frac{\partial E(f)}{\partial f_{u}}=0\)得: \[ \boldsymbol{f}_{u}=\left(\mathbf{D}_{u u}-\mathbf{W}_{u u}\right)^{-1} \mathbf{W}_{u l} \boldsymbol{f}_{l} \]   令: \[ \begin{aligned} \mathbf{P} &=\mathbf{D}^{-1} \mathbf{W}=\left[ \begin{array}{cc}{\mathbf{D}_{l l}^{-1}} & {\mathbf{0}_{l u}} \\ {\mathbf{0}_{u l}} & {\mathbf{D}_{u u}^{-1}}\end{array}\right] \left[ \begin{array}{cc}{\mathbf{W}_{l l}} & {\mathbf{W}_{l u}} \\ {\mathbf{0}_{u l}} & {\mathbf{D}_{u u}^{-1}}\end{array}\right] \left[ \begin{array}{cc}{\mathbf{W}_{l l}} & {\mathbf{W}_{l u}} \\ {\mathbf{W}_{u l}} & {\mathbf{W}_{u u}}\end{array}\right] \\ &=\left[ \begin{array}{cc}{\mathbf{D}_{l l}^{-1} \mathbf{W}_{u l}} & {\mathbf{D}_{l l}^{-1} \mathbf{W}_{l u}} \\ {\mathbf{D}_{u u}^{-1} \mathbf{W}_{u l}} & {\mathbf{D}_{u u}^{-1} \mathbf{W}_{u u}}\end{array}\right] \end{aligned} \]   即\(\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}\)\(\boldsymbol{f}_{u}\)可重写为: \[ \begin{aligned} \boldsymbol{f}_{u} &=\left(\mathbf{D}_{u u}\left(\mathbf{I}-\mathbf{D}_{u u}^{-1} \mathbf{W}_{u u}\right)\right)^{-1} \mathbf{W}_{u l} \boldsymbol{f}_{l} \\ &=\left(\mathbf{I}-\mathbf{D}_{u u}^{-1} \mathbf{W}_{u u}\right)^{-1} \mathbf{D}_{u u}^{-1} \mathbf{W}_{u l} \boldsymbol{f}_{l} \\ &=\left(\mathbf{I}-\mathbf{P}_{u u}\right)^{-1} \mathbf{P}_{u l} \boldsymbol{f}_{l} \end{aligned} \]   于是,将\(D_l\)上的标记信息作为\(\boldsymbol{f}_{l}=\left(y_{1} ; y_{2} ; \ldots ; y_{l}\right)\)代入\(\boldsymbol{f}_{u}\),即可利用求得的\(\boldsymbol{f}_{u}\)对未标记样本进行预测。
  上面描述的是针对二分类问题的标记传播(label propagation)方法,下面来看一个适用于多分类问题的标记传播方法。
  假定\(y_{i} \in \mathcal{Y}\),图、点集、边集的定义都与之前一样。对角矩阵\(\mathbf{D}=\operatorname{diag}\left(d_{1}, d_{2}, \dots, d_{l+u}\right)\)的对角元素\(d_{i}=\sum_{j=1}^{l+u}(\mathbf{W})_{i j}\),定义一个\((l+u) \times|\mathcal{Y}|\)的非负标记矩阵\(\mathbf{F}=\left(\mathbf{F}_{1}^{\mathrm{T}}, \mathbf{F}_{2}^{\mathrm{T}}, \ldots, \mathbf{F}_{l+u}^{\mathrm{T}}\right)^{\mathrm{T}}\),其第\(i\)行元素\(\boldsymbol{x}_i\)为示例\(\mathbf{F}_{i}=\left((\mathbf{F})_{i 1},(\mathbf{F})_{i 2}, \ldots,(\mathbf{F})_{i|y|}\right)\)的标记向量,相应的分类规则为\(y_{i}=\arg \max _{1 \leqslant j \leqslant|\mathcal{Y}|}(\mathbf{F})_{i j}\)
  对于\(i=1,2, \ldots, m, j=1,2, \dots,|\mathcal{Y}|\),将\(\mathbf{F}\)初始化为: \[ \mathbf{F}(0)=(\mathbf{Y})_{i j}=\left\{\begin{array}{ll}{1,} & {\text { if }(1 \leqslant i \leqslant l) \wedge\left(y_{i}=j\right)} \\ {0,} & {\text { otherwise }}\end{array}\right. \]   显然,\(\mathbf{Y}\)的前\(l\)行就是\(l\)个有标记样木的标记向量。基于\(\mathbf{W}\)构造一个标记传播矩阵\(\mathbf{S}=\mathbf{D}^{-\frac{1}{2}} \mathbf{W} \mathbf{D}^{-\frac{1}{2}}\),其中\(\mathbf{D}^{-\frac{1}{2}} = \operatorname{diag}\left(\frac{1}{\sqrt{d_{1}}}, \frac{1}{\sqrt{d_{2}}}, \ldots, \frac{1}{\sqrt{d_{l+u}}}\right)\),于是有迭代计算式: \[ \mathbf{F}(t+1)=\alpha \mathbf{S} \mathbf{F}(t)+(1-\alpha) \mathbf{Y} \]   其中\(\alpha \in (0,1)\)为用户指定的参数,用于对标记传播项\(\mathbf{SF}(t)\)与初始化项\(\mathbf{Y}\)的重要性进行折中.基于上式迭代至收敛可得: \[ \mathbf{F}^{*}=\lim _{t \rightarrow \infty} \mathbf{F}(t)=(1-\alpha)(\mathbf{I}-\alpha \mathbf{S})^{-1} \mathbf{Y} \]   根据\(\mathbf{F}^{*}\)可获得\(D_u\)中样本的标记\(\left(\hat{y}_{l+1}, \hat{y}_{l+2}, \ldots, \hat{y}_{l+u}\right)\),算法伪代码如下所示:

  上图伪代码表示的算法对应于正则化框架: \[ \min _{\mathbf{F}} \frac{1}{2}\left(\sum_{i, j=1}^{l+u}(\mathbf{W})_{i j}\left\|\frac{1}{\sqrt{d_{i}}} \mathbf{F}_{i}-\frac{1}{\sqrt{d_{j}}} \mathbf{F}_{j}\right\|^{2}\right)+\mu \sum_{i=1}^{l}\left\|\mathbf{F}_{i}-\mathbf{Y}_{i}\right\|^{2} \]   其中\(\mu \gt 0\)为正则化参数。因为有标记样本通常很少而未标记样本很多,为缓解过拟合,可在上式中引入针对未标记样本的\(L_2\)范数项\(\mu\Sigma_{i=l+1}^{l+u}||\mathbf{F}_i||^2\)。在\(\mu=\frac{1-\alpha}{\alpha}\)时,上式的最优解恰为的迭代收敛解\(\mathbf{F}^{*}\)。上式右边第二项是迫使学得结果在有标记样本上的预测与真实标记尽可能相同,而第一项则迫使相近样本具有相似的标记,它与式\(E(f)\)都是基于半监督学习的基本假设,不同的是上式考虑离散的类别标记,而式\(E(f)\)则是考虑输出连续值。
  图半监督学习方法在概念上相当清晰,且易于通过对所涉矩阵运算的分析来探索算法性质,但此类算法的缺陷也相当明显,首先是在存储开销上,若样本数为\(0(m)\),则算法中所涉及的矩阵规模为\(O(m^2)\),这使得此类算法很难直接处理大规模数据。另一方面,由于构图过程仅能考虑训练样本集,难以判知新样本在图中的位置,因此,在接收到新样本时,或是将其加入原数据集对图进行重 构并重新进行标记传播,或是需引入额外的预测机制,例如将\(D_l\)和经标记传播后得到标记的\(D_u\)合并作为训练集,另外训练一个学习器例如支持向量机来对新样本进行预测。

基于分歧的方法(disagreement-based methods)

  与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同,基于分歧的方法使用多学习器,而学习器之间的分歧对未标记数据的利用至关重要。

协同训练(co-training)

  协同训练是此类方法的重要代表,它最初是针对多视图数据设计的,因此也被看作多视图学习(multi-view learning)的代表。
  在不少现实应用中,一个数据对象往往同时拥有多个属性集,每个属性集就构成了一个视图。例如对一部电影来说,它拥有多个属性集,图像画面信息所对应的属性集、声音信息所对应的属性集等。于是,一个电影片段可表示为样本\(\left(\left\langle\boldsymbol{x}^{1}, \boldsymbol{x}^{2}\right\rangle, y\right)\),其中\(\boldsymbol{x}^{i}\)是样本在视图\(i\)中的示例,即基于该视图属性描述而得的属性向量,不妨假定\(\boldsymbol{x}^{1}\)为图像视图中的属性向量,\(\boldsymbol{x}^{2}\)为声音视图中的属性向量,\(y\)是标记(电影的类型),这样的数据就是多视图数据。
  假设不同视图具有相容性(compatibility),即其所包含的关于输出空间\(\mathcal{Y}\)的信息是一致的,记\(\mathcal{Y}^1\)表示从图像画面信息判别的标记空间,\(\mathcal{Y}^2\)表示从声音信息判别的标记空间,则有\(\mathcal{Y}=\mathcal{Y}^{1}=\mathcal{Y}^{2}\),在此假设下,显式地考虑多视图有很多好处,不同视图信息的互补性会给学习器的构建带来很多便利。
  协同训练正是很好地利用了多视图的相容互补性。假设数据拥有两个充分(sufficient)且条件独立视图,充分是指每个视图都包含足以产生最优学习器的信息,条件独立则是指在给定类别标记条件下两个视图独立。在此情形下,可用一个简单的办法来利用未标记数据:首先在每个视图上基于有 标记样本分别训练出一个分类器,然后让每个分类器分别去挑选自己最有把握的未标记样本赋予伪标记,并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新。这个“互相学习、共同进步”的过程不断迭代进行,直到两个分类器都不再发生变化,或达到预先设定的迭代轮数为止。算法伪代码如下图所示:

  若在每轮学习中都考察分类器在所有未标记样本上的分类置信度,会有很大的计算开销,因此在算法中使用了未标记样本缓冲池。分类置信度的估计则因基学习算法\(\mathcal{L}\)而异,例如若使用朴素贝叶斯分类器,则可将后验概率转化为分类置信度;若使用支持向量机,则可将间隔大小转化为分类置信度。
  协同训练过程虽简单,但令人惊讶的是,理论证明显示出,若两个视图充分且条件独立,则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。然而,视图的条件独立性在现实任务中通常显很难满足,因此性能提升幅度不会那么大,但研究表明,即便在更弱的条件下,协同训练仍可有效地提升弱分类器的性能。
  协同训练算法本身是为多视图数据而设计的,但此后出现了一些能在单视图数据上使用的变体算法,它们或是使用不同的学习算法,或使用不同的数据采样,甚至使用不同的参数设置来产生不同的学习器,也能有效地利用未标记数据来提升性能。后续理论研究发现,此类算法事实上无需数据拥有多视图,仅需弱学习器之间具有显著的分歧(或差异),即可通过相互提供伪标记样本的方式来提升泛化性能。不同视图、不同算法、不同数据采样、不同参数设置等,都仅是产生差异的渠道,而非必备条件
  基于分歧的方法只需采用合适的基学习器,就能较少受到模型假设、损失函数非凸性和数据规模问题的影响,学习方法简单有效、理论基础相对坚实、适用范围较为广泛。为了使用此类方法,需能生成具有显著分歧、性能尚可的多个学习器,但当有标记样本很少,尤其是数据不具有多视图时,要做到这一点并不容易,需有巧妙的设计。

半监督聚类(semi-supervised clustering)

  半监督聚类利用监督信息可以获得更好的聚类效果。聚类任务中获得的监督信息大致有两种类型:

  • 第一种类型是必连(must-link)与勿连(cannot-link)约束,前者是指样本必属于同一个簇,后 者是指样本必不属于同一个簇。
  • 第二种类型的监督信息则是少量的有标记样本。

约束\(k\)均值(Constrained k-means)算法

  约束\(k\)均值(Constrained k-means)算法是利用第一类监督信息的代表。给定样本集\(D\)以及“必连”关系集合\(\mathcal{M}\)和勿连关系集合\(\mathcal{C}\)\(\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \in \mathcal{M}\)表示\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\)必属于同簇,\(\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \in \mathcal{C}\)表示\(\boldsymbol{x}_{i}\)\(\boldsymbol{x}_{j}\)必不属于同簇。该算法是\(k\)均值算法的扩展,它在聚类过程中要确保\(\mathcal{M}\)\(\mathcal{C}\)中的约束得以满足,否则将返回错误提示,算法伪代码如下图所示:

约束种子\(k\)均值(Constrained Seed k-means)算法

  第二种监督信息是少量有标记样本。假定少量的有标记样本为\(S=\bigcup_{j=1}^{k} S_{j} \subset D\),其中\(S_{j} \neq \varnothing\)为隶属于第\(j\)个聚类簇的样本。直接把监督信息作为种子,用它们初始化\(k\)均值算法的\(k\)个聚类中心,并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系。这就是约束种子\(k\)均值算法,算法伪代码如下图所示:

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 半监督学习(Semi-supervised Learning)
  3. 3. 生成式方法(Generative Methods)
  4. 4. 半监督SVM(Semi-Supervised Support Vector Machine,S3VM)
    1. 4.1. TSVM(Transductive Support Vector Machine)
  5. 5. 图半监督学习
  6. 6. 基于分歧的方法(disagreement-based methods)
    1. 6.1. 协同训练(co-training)
  7. 7. 半监督聚类(semi-supervised clustering)
    1. 7.1. 约束\(k\)均值(Constrained k-means)算法
    2. 7.2. 约束种子\(k\)均值(Constrained Seed k-means)算法
  8. 8. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...