基于图和熵正则化的半监督分类算法

论文摘要

半监督学习（Semi-supervised Leaning,SSL）试图利用大量的无标记样本学习数据的内在几何结构,在此基础上利用少量的有标记样本完成降维、分类和回归等任务。由于SSL在减少人工标注代价、提高机器学习性能方面的突出优势,以及在网页检索、文本分类、基于生物特征的身份识别和医疗诊断等领域应用的广泛性,从上世纪90年代开始,它就在机器学习界引起了关注。目前,SSL已成为机器学习研究中最受关注的问题之一。本文在分析了SSL的发展现状和目前仍存在的问题的基础上,对基于图和熵正则化的半监督分类学习中的若干重要问题进行了研究,具体研究内容和成果如下:1、数据图的构造。数据图的构造是设计基于图的SSL算法的第一步。大多数传统数据图构造方法是参数依赖的,且对参数较敏感;另一方面,最近提出的基于稀疏表达的最小化L1模构造模型不能保证非负解,因此不能直接用作图上边的权重。针对这些不足,提出了两个基于非负稀疏表达的最小化L1模构造模型:L1IMP和L1IMPv。两个新模型在现有最小化L1模构造模型的基础上增加了非负约束,从而使得模型的稀疏解不仅可以反映成对样本间的紧密程度,而且可以直接用作图上边的权重。此外,新的图构造方法可以在确定图的邻接结构的同时完成边的权重计算。结合标记传播算法,在UCI和人脸数据集上的实验结果表明,L1IMP和L1IMPv在大多数情况下的分类效果优于传统方法。2、基于不相似性的图SSL算法。负相似性在协同过滤等问题中经常出现。针对目前提出的大部分图SSL算法都不能处理不相似性或负相似性的不足,提出了一个基于负相似性的图SSL模型SMLP。SMLP的优化目标是如下两个量的比值:类标记和正相似性的不一致性以及类标记和负相似性的一致性;同时,SMLP允许有标记样本的标记予以重新标记,运用一种全局优化方法求解SMLP,可以在O ( n3logε-1 )时间内获得一个ε-最优解。在UCI数据集和协同过滤问题上验证了SMLP算法的有效性。3、适于处理标记有噪声数据的图SSL算法。算法的基本思路是运用软标记方法来处理标记有噪声数据。首先,利用各种标记软化方法将样本的类标记转化为软标记,相比硬标记,软标记可以更好地容纳监督者对模式类别的不确定性。在此基础上,嵌入现有的基于图的SSL算法LGC,以达到预期目的。在有类重叠的UCI和物体识别数据集上的实验表明,与基于硬标记的LGC算法相比,基于软标记的LGC算法可以更好地用于标记有噪声数据的半监督分类学习。4、基于熵正则化的SSL算法。提出了一个基于条件Havrda-Charvat’s Structuralα-熵正则化的直推式半监督分类模型MinEnt。MinEnt的基本思想是:一个好的聚类标准是对无标记样本的一个好的刻画。在MinEnt模型中,用条件Havrda-Charvat’s Structuralα-熵聚类标准刻画无标记样本及其所属类别之间的关系,同时对有标记样本采用其对数似然函数。设计了基于拟牛顿法的求解算法。所提出的算法是判别式的,降低了对模型的依赖程度;同时,它可以预测样本空间中任何一个样本的标记,是一种直推式方法。在UCI数据集上的仿真实验验证了该算法的有效性。

论文目录

• 摘要
• Abstract
• 图目录
• 表目录
• 第一章 绪论
• 1.1 选题背景和研究意义
• 1.2 半监督学习的概念及基本假设
• 1.2.1 半监督学习的概念
• 1.2.2 半监督学习的基本假设
• 1.3 半监督学习的研究进展及发展方向
• 1.3.1 半监督学习的研究进展
• 1.3.2 半监督学习的发展方向
• 1.4 本文的主要研究内容
• 1.5 本文的组织
• 第二章 半监督学习典型算法
• 2.1 基于生成式模型的半监督学习算法
• 2.2 基于协同训练的半监督分类算法
• 2.3 基于低密度分离的半监督分类算法
• 2.3.1 转导支持向量机TSVM
• 2.3.2 熵最小化方法
• 2.4 基于图模型的半监督学习算法
• 2.4.1 图算法的正则化框架
• 2.4.2 最小分割Mincut
• 2.4.3 高斯随机场和调和函数GRF
• 2.4.4 谱图分割SGP
• 2.4.5 局部和全局一致性LGC
• 2.4.6 流形正则化MR
• 2.4.7 基于线性邻域的标记传播LNP
• 2.5 算法比较与分析
• 2.5.1 测试数据集和算法的参数设置
• 2.5.2 测试结果与分析
• 2.6 本章小结
• 第三章 基于非负稀疏表达的数据图构造
• 3.1 标记传播算法
• 3.2 传统的数据图构造方法
• 3.3 基于稀疏表达的数据图构造方法
• 3.4 基于非负稀疏表达的数据图构造模型
• 3.4.1 第一个改进模型
• 3.4.2 第二个改进模型
• 3.4.3 改进的基于非负稀疏表达的数据图构造算法
• 3.5 实验及分析
• 3.5.1 A Toy Problem
• 3.5.2 实际数据集
• 3.5.2.1 分类准确率的比较
• 3.5.2.2 参数对算法的影响
• 3.6 本章小结
• 第四章 基于不相似性的图半监督分类算法及其在协同过滤问题中的应用
• 4.1 基于不相似性的图半监督分类算法介绍
• 4.2 基于软约束和不相似性的图半监督二分类模型
• 4.3 基于软约束和不相似性的图半监督多分类模型
• 4.4 全局优化算法
• 4.5 实验及分析
• 4.5.1 第一组实验
• 4.5.2 第二组实验
• 4.5.2.1 协同过滤问题简介
• 4.5.2.2 实验结果及分析
• 4.6 本章小结
• 第五章 基于图的半监督算法LGC 在标记有噪声数据中的应用
• 5.1 标记有噪声下的学习
• 5.2 软标记
• 5.2.1 K 邻近软标记（K-nearest neighbor，KNN）
• 5.2.2 Keller 软标记
• 5.2.3 基于近邻原型分类器的软标记（Generalized nearest prototype classifier，GNPC）
• 5.2.4 基于模糊C 均值聚类的软标记
• 5.3 基于软标记的LGC 算法
• 5.3.1 LGC 算法简介
• 5.3.2 带软标记的LGC 算法
• 5.4 实验及分析
• 5.4.1 试验设计
• 5.4.2 实验结果及分析
• 5.5 本章小结
• 第六章 基于最小熵正则化的半监督分类算法
• 6.1 Havrda-Charvat’s Structural α-熵聚类标准
• 6.1.1 最小熵聚类标准
• 6.1.2 Havrda-Charvat’s Structural α-熵聚类标准
• 6.2 基于最小Havrda-Charvat’s Structural α-熵正则化的半监督分类模型
• 6.2.1 最大似然准则
• 6.2.2 半监督分类模型
• 6.3 模型求解
• 6.3.1 二分类问题
• 6.3.2 多分类问题
• 6.3.3 拟牛顿法求解模型
• 6.4 实验及分析
• 6.5 本章小结
• 结论与展望
• 参考文献
• 攻读博士学位期间取得的研究成果
• 致谢