周志华 机器学习 西瓜书 全书16章 ppt ch13半监督学习.pptVIP

图半监督学习 上面描述的是一个针对二分类问题的“单步式”标记传播(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]是利用第一类监督信息的