陈加略,第十三章：半监督学习,背景（半监督学习）,隔壁老王,品瓜师,吃,背景（半监督学习）,品瓜师,吃,模型,有标记样本,无标记样本,直推学习,（纯）半监督学习,待测数据,背景（主动学习）,品瓜师,吃,背景（主动学习）,品瓜师,吃,主动学习,待测数据,模型,有标记样本,无标记样本,标注者,未标记样本的效用,未标记样本的假设,要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设，其中有两种常见的假设。 聚类假设（clustering assumption）： 假设数据存在簇结构，同一簇的样本属于同一类别。 流形假设（manifold assumption）： 假设数据分布在一个流形结构上，邻近的样本具有相似的输出值。,流形假设可看做聚类假设的推广,大纲,未标记样本 生成式方法 半监督SVM 图半监督学习 基于分歧的方法 半监督聚类,生成式方法,假设样本由这个假设意味着混合成分 高斯混合模型生成, 且每个类别对应一个高斯混合成分： 其中,生成式方法,由最大化后验概率可知：,生成式方法,假设样本独立同分布，且由同一个高斯混合模型生成，则对数似然函数是：,生成式方法,高斯混合的参数估计可以采用EM算法求解，迭代更新式如下： E步：根据当前模型参数计算未标记样本属于各高斯混合成分的概率。,生成式方法,M步：基于 更新模型参数,生成式方法,将上述过程中的高斯混合模型换成混合专家模型，朴素贝叶斯模型等即可推导出其他的生成式半监督学习算法。 此类方法简单、易于实现, 在有标记数据极少的情形下往往比其他方法性能更好。 然而, 此类方法有一个关键: 模型假设必须准确, 即假设的生成式模型必须与真实数据分布吻合; 否则利用未标记数据反而会显著降低泛化性能。,大纲,未标记样本 生成式方法 半监督SVM 图半监督学习 基于分歧的方法 半监督聚类,半监督SVM,半监督SVM,半监督支持向量机中最著名的是TSVM(Transductive Support Vector Machine),半监督SVM,TSVM采用局部搜索来迭代地寻找近似解.,无标记样本,有标记样本,SVM0,伪标记,SVM1,训练,训练,训练,标注,半监督SVM,SVM1,无标记样本,搜索,指派可能出错的样本,交换样本标记,有标记样本,训练,训练,SVM2,半监督SVM,未标记样本的伪标记不准确,半监督SVM,未标记样本进行标记指派及调整的过程中, 有可能出现类别不平衡问题,即某类的样本远多于另一类。 为了减轻类别不平衡性所造成的不利影响, 可对算法稍加改进: 将优化目标中的 项拆分为 与 两项,并在初始化时令：,半监督SVM,显然, 搜寻标记指派可能出错的每一对未标记样本进行调整, 仍是一个涉及巨大计算开销的大规模优化问题。 因此, 半监督SVM研究的一个重点是如何设计出高效的优化求解策略。 例如基于图核(graph kernel)函数梯度下降的Laplacian SVMChapelle and Zien, 2005、基于标记均值估计的meanS3VMLi et al., 2009等.,大纲,未标记样本 生成式方法 半监督SVM 图半监督学习 基于分歧的方法 半监督聚类,图半监督学习,给定一个数据集, 我们可将其映射为一个图, 数据集中每个样本对应于图中一个结点, 若两个样本之间的相似度很高(或相关性很强), 则对应的结点之间存在一条边, 边的“强度”(strength)正比于样本之间的相似度(或相关性)。 我们可将有标记样本所对应的结点想象为染过色, 而未标记样本所对应的结点则尚未染色. 于是, 半监督学习就对应于“颜色”在图上扩散或传播的过程。 由于一个图对应了一个矩阵, 这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。,图半监督学习,我们先基于 构建一个图 ，其中结点集 边集E可表示为一个亲和矩阵(affinity matrix),常基于高斯函数定义为:,图半监督学习,假定从图 将学得一个实值函数 。 直观上讲相似的样本应具有相似的标记,即得到最优结果于是可定义关于f的“能量函数”(energy function)Zhu et al., 2003:,图半监督学习,采用分块矩阵表示方式: 由 可得:,图半监督学习,图半监督学习,上面描述的是一个针对二分类问题的“单步式”标记传播(label propagation)方法, 下面我们来看一个适用于多分类问题的“迭代式”标记传播方法Zhou et al., 2004. 仍基于 构建一个图 其中结点集 定义一个 的非负标记矩阵 ，其第i行元素 为示例 的标记向量, 相应的分类规则为: 将F初始化为：,图半监督学习,基于W构造一个标记传播矩阵 ，其中 , 于是有迭代计算式: 基于迭代至收敛可得:,图半监督学习,事实上, 算法对应于正则化框架Zhou et al., 2004: 当 时, 最优解恰为迭代算法的收敛解 。,图半监督学习,图半监督学习,图半监督学习方法在概念上相当清晰, 且易于通过对所涉矩阵运算的分析来探索算法性质。 但此类算法的缺陷也相当明显. 首先是在存储开销高。 另一方面, 由于构图过程仅能考虑训练样本集, 难以判知新样本在图中的位置, 因此, 在接收到新样本时, 或是将其加入原数据集对图进行重构并重新进行标记传播, 或是需引入额外的预测机制。,大纲,未标记样本 生成式方法 半监督SVM 图半监督学习 基于分歧的方法 半监督聚类,基于分歧的方法,基于分歧的方法(disagreement-based methods)使用多学习器, 而学disagreement亦称diversity 习器之间的“分歧”(disagreement)对未标记数据的利用至关重要。 协同训练(co-training)Blum and Mitchell, 1998是基于分歧的方法的重要代表, 它最初是针对“多视图”(multi-view)数据设计的, 因此也被看作“多视图学习”(multi-view learning)的代表.,基于分歧的方法,网页分类任务中的双视图,图片视图,文字视图,基于分歧的方法,协同训练正是很好地利用了多视图的“相容互补性”. 假设数据拥有两个“充分”(sufficient)且“条件独立”视图。,视图1,视图2,模型1,模型2,最确信样本,最确信样本,基于分歧的方法,基于分歧的方法,协同训练过程虽简单, 但令人惊讶的是, 理论证明显示出, 若两个视图充分且条件独立, 则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高Blum and Mitchell, 1998. 不过, 视图的条件独立性在现实任务中通常很难满足,不会是条件独立的因此性能提升幅度不会那么大, 但研究表明, 即使在更弱的条件下,协同训练仍可有效地提升弱分类器的性能周志华, 2013.,基于分歧的方法,协同训练算法本身是为多视图数据而设计的,性集合的常见数据但此后出现了一些能在单视图数据上使用的变体算法。 它们或是使用不同的学习算法Goldman and Zhou,2000、或使用不同的数据采样Zhou and Li, 2005b、甚至使用不同的参数设置Zhou and Li, 2005a来产生不同的学习器, 也能有效地利用未标记数据来提升性能。 后续理论研究发现, 此类算法事实上无需数据拥有多视图, 仅需弱学习器之间具有显著的分歧(或差异), 即可通过相互提供伪标记样本的方式来提高泛化性能周志华, 2013。,基于分歧的方法,基于分歧的方法只需采用合适的基学习器, 就较少受到模型假设、损失函数非凸性和数据规模问题的影响, 学习方法简单有效、理论基础相对坚实、适用范围较为广泛。 为了使用此类方法, 需能生成具有显著分歧、性能尚可的多个学习器, 但当有标记样本很少、尤其是数据不具有多视图时, 要做到这一点并不容易。,大纲,未标记样本 生成式方法 半监督SVM 图半监督学习 基于分歧的方法 半监督聚类,半监督聚类,聚类是一种典型的无监督学习任务, 然而在现实聚类任务中我们往往能获得一些额外的监督信息, 于是可通过“半监督聚类”(semi-supervised clustering)来利用监督信息以获得更好的聚类效果. 聚类任务中获得的监督信息大致有两种类型： 第一种类型是“ 必连”(must-link)与“勿连”(cannot-link)约束，前者是指样本必属于同一个簇, 后者则是指样本必不属于同一个簇； 第二种类型的监督信息则是少量的有标记样本.,半监督聚类,约束k均值(Constrained k-means)算法Wagstaff et al., 2001是利用第一类监督信息的代表。 该算法是k均值算法的扩展,它在聚类过程中要确保“必连”关系集合与“勿连”关系集合中的约束得以满足, 否则将返回错误提示。,半监督聚类,不冲突，选择最近的簇,冲突，尝试次近的簇,半监督聚类,半监督聚类,第二种监督信息是少量有标记样本。即假设少量有标记样本属于k个聚类簇。 这样的监督信息利用起来很容易: 直接将它们作为“种子”, 用它们初始化k均值算法的k个聚类中心, 并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系. 这样就得到了约束种子k均值(Constrained Seed k-means)算法Basu et al., 2002。,半监督聚类,半监督聚类,阅读材料,半监督学习的研究一般认为始于Shahshahani and Landgrebe, 1994, 该领域在上世纪末、本世纪初蓬勃发展. 国际机器学习大会(ICML) 从2008年开始评选“十年最佳论文”, 在短短6年中, 半监督学习四大范型(paradim)中基于分歧的方法、半监督SVM、图半监督学习的代表性工作先后于2008年Blumand Mitchell, 1998、2009年Joachims, 1999、2013年Zhu et al., 2003获奖. 半监督学习在利用未标记样本后并非必然提升泛化性能, 在有些情形下甚至会导致性能下降. 对生成式方法, 其成因被认为是模型假设不准确Cozmanand Cohen, 2002, 因此需依赖充分可靠的领域知识来设计模型. 对半监督SVM, 其成因被认为是训练数据中存在多个“低密度划分”, 而学习算法有可能做出不利的选择; S4VM Li and Zhou, 2015 通过优化最坏情形性能来综“安全”指利用未标记数 合利用多个低密度划分, 提升了此类技术的安全性.据之后, 确保泛化性能至少不差于仅利用有标记数据更一般的“安全”(safe)半监督学习仍是一个未决问题.,阅读材料,本章主要介绍了半监督分类和聚类, 但半监督学习已普遍用于各类机器学习任务, 例如在半监督回归Zhou and Li, 2005a、降维Zhang et al., 2007等方面都有相关研究. 更多关于半监督学习的内容可参见Chapelle et al., 2006b,Zhu, 2006, 周志华, 2013, Zhou and Li, 2010则是关于基于分歧的方法的专门介绍. Settles, 2009是一个关于主动学习的介绍.,