（计算机应用技术专业论文）结构半监督学习算法及其应用研究.pdf

苏州大学学位论文使用授权声明 删i ilxlliiiiirll|lii ii i i y 1 7 3 2 0 2 1 。 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文囤 论文作者签 导师签 日期： 结构半监督学习算法及其应用研究中文摘要 结构半监督学习算法及其应用研究 中文摘要 在如今科技飞速发展的时代，无论是科学研究还是社会生活领域，都收集和积累 了大量的数据。对这些数据进行有效地分析和利用，不仅是计算机科学发展的目标， 同时也能在很大程度上推动医学、地质学、气象学等传统学科和信息生物学、组合化 学等新兴交叉学科的发展。在实际应用中，人工对数据进行标记常常是比较费时和昂 贵的，并且在很多领域中，标记数据的获得都需要有经验的专业人员。 半监督学习在具有较少标记样本的条件下，通过融合几乎无代价的未标记样本能 够获得令人满意的学习效果和泛化能力。半监督学习在视频跟踪、网页分类、医学图 像分析、智能交通、生物信息学等领域都有着广泛的应用。 本文对相似性度量、协同训练和基于群论的机器学习等方面进行深入讨论，并应 用到图像分类和检索领域，主要完成了以下工作： ( 1 ) 分析了半监督学习的研究现状，对各种算法之间的联系和区别进行了比较。 ( 2 ) 提出了一种嵌入知识的相似性度量算法，使图的构造能够融入样本的空间结 构信息，并能够通过已标记样本对空间中相邻的样本施加影响。使基于图的 半监督学习算法在维数高、样本量少的情况下也能够取得较好的分类效果。 ( 3 ) 对协同训练进行了理论分析，实现了基于图的协同训练算法，并结合相关反 馈方法应用到了图像检索的实例当中。 ( 4 ) 针对“人类感知主观性”等问题，给出了一种基于图像不变特征和扩大检索 结果相异性的半监督检索方法。 关键字：半监督学习算法，图像检索，相似性度量，图像不变特征 作者：宿洪禄 指导老师：李凡长( 教授) 本文的研究得到国家自然科学基金项目支持( 6 0 7 7 5 0 4 5 ) i a b s t r a c ts t r u c t u r es e m i - s u p e r v i s e dl e a r n i n ga n di t sa p p l i c a t i o n s t r u c t u r es e m i s u p e r v i s e dl e a r n i n ga n di t sa p p l i c a t i o n a bs t r a c t i nt o d a y se r ao fs c i e n c ea n dt e c h n o l o g y , w h e t h e rs c i e n t i f i co rs o c i a ll i f ei sc o l l e c t e d a n da c c u m u l a t e dm a s s i v ed a t a a n a l y z i n gt h e s em a s s i v ed a t ai st h eg o a lo fc o m p u t e r s c i e n c e a n dt h et e c h n i q u ec a na l s op r o m o t em u c ho ft h em e d i c i n e ，g e o l o g y , m e t e o r o l o g y , 目录 第一章绪论l 1 1 半监督学习研究进展1 1 1 1 半监督学习的基本问题2 1 1 2 生成式模型4 1 1 3 s e l f - t r a i n i n g 算法5 1 1 4 c o t r a i n i n g 算法6 1 1 5 直推支持向量机9 1 1 6 基于图的方法1 0 1 1 7 半监督学习算法的选择1 3 1 2 研究内容安排1 4 第二章结构半监督学习算法1 6 2 1 一种嵌入先验知识的相似性度量学习算法1 6 2 1 1 相似性度量的一般方法1 6 2 1 2 图像间的相似性度量方法1 8 2 1 3 一种嵌入先验知识的相似性度量算法1 9 2 2 基于图的协同训练算法2 2 2 2 1 协同训练中分类器的选择2 2 2 2 2 基于图的协同训练算法有效性分析2 3 2 3 本章小结2 4 第三章相似性度量学习算法在图像检索中的应用2 5 3 1 图像检索基础2 5 3 1 1 图像的特征表示2 7 3 1 2 用户反馈信息3 4 3 1 3 检索效果评价方法3 6 3 2 嵌入知识相似性度量学习算法实验分析3 9 3 2 1 基于图的半监督学习模型3 9 3 2 2 基于知识空间的噪声消减4 0 3 2 3 实验结果分析4 2 3 3 本章小结4 5 第四章协同结构学习算法在图像检索中的应用4 6 4 1 测试数据集的利用4 6 4 2 图像特征量化4 7 4 3 系统设计与实现4 8 4 4 本章小结4 9 第五章基于相异性和不变特征的半监督图像检索5 0 5 1 半监督学习框架5 0 5 2 图像检索系统的语义。5 1 5 3 图像的不变特征5 2 5 4 扩大检索结果相异度的方法5 3 5 5 系统设计与实验分析5 5 5 6 本章小节5 7 第六章总结与展望5 8 6 1 总结5 8 6 2 将来的工作5 8 参考文献6 0 附勇乏6 6 科研情况6 6 论文发表情况6 6 中英文名词对照6 6 致 射6 8 结构半监督学习算法及其应用研究第一章绪论 第一章绪论 随着信息技术的飞速发展，数据的收集、存储能力得到了极大的提高，无论是科 学研究还是生产生活的各个领域中都积累了大量的数据，比如医学领域需要维护和处 理大量的c t 、x 光、超声波等影像数据；气象学、地质勘探、生物信息学等领域也需 要处理采集到的大量数据。然而，面对海量的数据，人们却很难对数据进行分析从中 发现有用的信息。对这些数据进行有效地分析以发掘数据中蕴含的有用信息，成为几 乎所有领域的共同需求。 在大部分领域中，样本的标签的获得相当的费时费力，未标记样本的获得却相对 廉价和容易的多，例如，在文本分类、图像分类、语音分类的任务中，我们可以轻松 地从互联网上得到海量的未标记数据。如果仅使用少量“昂贵的标记数据而不利用 大量“廉价”的未标记数据，则是对数据资源的极大浪费。因此，在已标记数据比较 少时，如何利用大量的未标记数据来改善学习器的性能已经成为当前机器学习研究中 最受关注的问题之一。 半监督学习主要讨论如何将大量的未标记样本和少量的已标记样本结合起来，以 提高学习器的泛化能力。在实际应用当中半监督学习算法所需的条件容易满足，并且 能够节省投入，因此有着广泛的应用。绝大部分半监督学习算法基于以下假设：( 1 ) 互相邻近的点，趋向于拥有相同的标记；( 2 ) 经过高密度区域的一条路径连接的点趋 向于拥有相同的标记，也称为聚类假设。第一个假设为局部性质，第二个假设为全局 性质。一般地，传统的监督学习算法仅依赖于局部性质，例如k 小n 算法。需要注意 的是，处于同一簇的点最可能属于同一类，但并不意味着每一簇都构成单一紧致的类， 只能说明同一簇中找不到明显不同的两个类。 1 1 半监督学习研究进展 近年来，半监督学习吸引了很多学者的关注，针对不同形式的问题，提出了一些 经典的算法，如基于局部和全局一致性的方法【5 】，基于产生式模型的方法【3 l ，基于图 第一章绪论结构半监督学习算法及其应用研究 的方法【l 】【6 1 ，低密度划分的方法【13 1 ，基于多视图方法【4 1 等。 广义的半监督学习通常包含：加入标记信息或限制条件的半监督聚类【5 2 1 ，半监督 降维【5 2 1 ，半监督回归【3 】，半监督特征提取，半监督度量学习【2 】，半监督分类【5 2 】，以及 对已有非监督算法进行改进，以便能够融入已标记信息的方法。狭义的半监督学习主 要研究己知有限标记信息的基础上，融合大量未标记样本提供的分布特性的算法。国 内有很多研究小组在国际的半监督学习领域有着重要的影响【5 4 】，软件学报也在0 8 年 专门推出半监督学习专刊。鉴于半监督算法范围的广泛性，本文在涉及多个领域的同 时重点讨论狭义半监督学习的分类问题。 1 1 1 半监督学习的基本问题 给定已标记样本 ( ，咒) ，x jer n , 】，) ，类别集三= 1 c ) ，其中薯是样本点( 观 测点) ，r ”为样本观测空间，只为对应样本点的标记，】，为标记集合。前，个样本点 ( f ，) 为已标记样本，对应的标记为虼= 挑厶i ，) ，如果只有样本点而没有对应 的值，即样本为 x tx i r ” ，则称为未标记样本。通常，未标记样本的数量远远大于 标记样本的数量( ，u ) 。在传统的有监督学习中，学习器通过对大量已标记训练样 例建立模型，用来对未见实例进行预测，即监督学习的训练样例全部是有标记示例； 而无监督学习是针对未标记数据本身所具有的规律性进行学习的过程。 大量的未标记数据是否能够辅助少量标记样本的学习，未标记数据是否具有理论 上的价值，这个半监督学习中的基础理论，得到许多学者的深入研究。从表面来看， 未标记样本不能提供直接的类别信息，而看似没有任何实际价值，但在某些情况下它 却可以提供其它有用的信息。关于这个问题，d j m i l l e r 和h s u y a r 5 6 1 从数据分布估 计的角度进行了直观的分析。假设所有数据服从n 个高斯的混合分布，即 卫 f ( x 1 0 ) = 厂( x i 皖) ( 1 1 ) n = l 其中二。= 1 为混合系数。这样，标记就表示为一个由选定的混合成分碱和特征向 量薯以p ( qt ，m ，) 为概率的随机变量。根据最大后验概率假设，可得最优分类为： 办( x ) - a r g m a x , p ( c i 2k m i2 ，i ) 尸( 2jx ) ( 1 2 ) kl 2 结构半监督学习算法及其应用研究第一章绪论 其中 p ( m ：# 兰至二 (13)iix f ) = 2 可上- 二j 一 ( 1 3 ) ，c t n f ( _ i 铭) 要使k 取得最大值，则要求尸( q = k i = 歹，) 和p ( = ，i x ) 这两项尽可能的大， 尸( q = k i 嵋= ，) 和类标记有关，而尸( = i x ) 和类标记是无关的。因此，可以通 过使用大量未标记样本来提高p ( = j i x ) 的估计精度。这表明未标记样本有助于提 高学习器的泛化能力，从而也表明未标记样本在半监督学习中具有改善性能的价值。 图1 - 1 说明了在两类分别为高斯分布的情况下，未标记样本的使用可以帮助进行参数 估计，同时也需要在某些假设的基础上建立未标记样本和目标间的联系。 ( a ) 标记样本( b ) 标记样本和未标记样本 ( c ) 从标记样本学习得到的模型 ( d ) 已标记和未标记样本相结合得到的模型 图1 - 1 未标记样本作用 c o z m a n 和c o h e n l 2 3 】【2 4 1 等人做了进一步研究，他们认为当模型假设不正确时是否 能够提高学习器的性能，与相对于标记样本集的模型复杂度有关。如果模型复杂度相 第一章绪论 结构半监督学习算法及其应用研究 对于标记样本集大小为高的话，则加入未标记样本就可以提高学习器的性能。同时， 也提出了三种未标记样本导致学习器性能下降的情况：1 、当样本的特征维数较小时， 加入未标记样本反而会降低学习器的性能：2 、当有标记样本数量较多时，贝叶斯学 习器的性能随着未标记样本的加入而降低；3 、当在少量的已标记样本中加入的未标 记样本数量非常少时，学习器的性能会降低；如果加入的未标记样本足够多，反而又 可以提高学习器的性能。 1 1 2 生成式模型 生成式模型【5 6 】( g e n e r a t i v em o d e l s ) 被绝大部分机器学习学者公认为最早的半监 督学习方法( 模型如图1 2 ) ，是一种直接采用聚类假设的算法。假设模型满足联合概 率p ( x ，y ) = p ( y ) p ( xy ) ，其中p ( xy ) 是一个可区分的混合分布( 如果p ( x ) 分解为 ，p ( y ) p ( x i 夕) 是唯一的，则称模型是可区分的) ，例如高斯混合模型。数据点是由 混合分布中不同参数的分布产生的。利用大量未标记数据区分出混合模型中的不同分 布，用e m 算法进行不同分布源的标签和参数估计。即： p ( yix ，口，万) p ( xy ，p ) p ( yi 万)( 1 4 ) 并通过下式自然地融入未标记样本的信息： p ( x f 秒，万) = 。p ( z i y ，口) ，( y i 万) ( 1 5 ) 不过，需要注意的是，不是加入了未标记数据就一定会获得很好的结果，如果生 成式模型存在模型和数据的偏差，那么随着数据的增多，结果反而会变差，再者o u t l i e r 的存在也可能会使生成式模型性能下降。理论上每个分布中最少只需要一个标记数 据。s h a h s h a h a n i 和l a n d g r e b e 把生成式模型扩展为每类代表几个成分【3 1 1 。 图1 2 生成式的半监督学习模型 这些可用于随机生成的观察值建模，特别适用于给定某些隐藏参数情况。在机器 4 结构半监督学习算法及其应用研究第一章绪论 学习中，或用于直接对数据建模，或作为生成条件概率密度函数的中间步骤。通过使 用贝叶斯规则可以从生成模型中得到条件分布。如果观察到的数据是完全由生成模型 所生成的，那么就可以f i t t i n g 生成模型的参数，从而尽可能的增加数据相似度。但数 据很难由生成模型完全得到，所以比较恰当的方式就是直接对条件密度函数建模。 与生成式模型相对应的，如果对后验概率建模，则属于判别式模型。基本思想是 在有限样本条件下建立判别函数，并不考虑样本的产生模型，而是直接研究预测模型。 判别式模型寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。它的分 类边界更灵活，能清晰的分辨出多类或某一类与其他类之间的差异特征。由生成模型 可以得到判别模型，但由判别模型得不到生成模型。判别式模型的例子：s v m 。 1 1 3 s e l f t r a i n i n g 算法 s e l f - t r a i n i n g 学习方法是基于规则的，它直接对已有监督学习算法进行修改，融 入未标记信息来实现半监督学习的一种算法。是将监督算法半监督化的一个通用框 架，同时也是半监督学习研究在广度方面的扩展。学习器对未标记数据的预测用来帮 助下次训练，可以看作是学习器的自我学习和训练的过程，因此被称为s e l f - t r a i n i n g 算法。s e l f - t r a i n i n g 是一种增量式算法，首先利用少量的已标记数据训练出一个分类 器，然后将这个分类器用于对未标记数据进行分类，并从中选择置信度最高的未标记 样本( 通常利用条件熵进行判断，并假设分类置信度高的样本的分类是正确的) ，将 它们加入到训练集中，重新训练分类器，循环往复，直到所有样本都被标记完成为止 ( 具体流程见图1 3 ) 。这种训练方法的一个缺陷是很容易导致分类器的误差累积，从 而影响分类器性能。 s e l f - t r a i n i n g 是一种w r a p p e r 算法，它包装后的算法的效率取决于所采用的监督 学习算法，很难从整体上进行分析。如果采用0 1 损失，未标记数据不产生任何作用； 如果采用边界最大化方法，决策边界会偏离未标记数据，一般很难再进行深入地分析。 文献【3 2 j 深入讨论了在s e l f - t r a i n i n g 中采用线性回归，l i g i s t i c 回归等方法的收敛性。 s e l f - t r a i n i n g 可以看作是信息检索中的一种相关反馈，在相关反馈中，先在一个集合 上做初始的查询，然后通过不断地增加最匹配的项来修正初始查询。s e l f - t r a i n i n g 算 法与这个过程非常的相似，它通过将标记置信度最高的未标记样本加入到已标记样本 第一章绪论结构半监督学习算法及其应用研 中来不断修正初始分类器。 图1 - 3s e l f - t r a i n i n g 算法流程 通常，生成混合模型和e m 算法能被看作一个特殊情况下的软s e l f - t r a i n i n g ，另 外s 3 v m 和t s v m 也是对监督算法的修改和推广。 1 1 4 c o t r a i n i n g 算法 现实案例中，某些数据的特征存在着天然子集划分。例如，网页数据中文本部分 和超链接部分。如果多个特征子集之间满足兼容、条件独立和充分性条件，那么就可 以利用这些特征子集的天然划分实现基于多视图的半监督学习算法，从而达到减少标 注量、缩小目标函数搜索空间和提高分类准确率的目的。 a b l u m 和t m i t c h e l l 提出c o t r a i n i n g 算法 4 1 ，并假设数据集具有两个充分冗余 视图：第一，每一个属性集都足以训练一个强学习器；第二，在给定标签情况下，每 一个属性集都条件独立于另一个属性集。首先利用已标记数据在两个相互独立的子集 上，训练两个不同的分类器。这两个分类器分别对未标记数据进行标记，然后每次互 相标记一部分自认为置信度高的数据给对方，重新训练并更新模型，迭代直到没有合 适的未标记数据加入为止。基于多视图的算法隐含地利用了聚类假设或流形假设。 如下描述c o t r a i n i n g 模型：假设有样本空间x = x l 五，其中x 和五为x 上 的两个视图，并假设每个视图都足以训练出一个分类器。设d 为x 上的概率分布，c 1 6 结构半监督学习算法及其应用研究 第一章绪论 和c 2 分别为墨和置上的概念类，c l c 2 为x 上的概念类。假设所有分布d 下的非 零概率样本，与某一目标函数石g 一致，与另一个目标函数石c 2 也是一致的，也 就是，如果f = ( 石，厶) c lxc 2 为x 上的目标函数，则对于任一个样本x = ( 五，x ：) 有 石( 五) f 2 ( x 2 ) ，称d 对样本x 指派零概率。 接下来，我们定义一种“相容性”概念：若d 对满足石( 五) 五( 毪) 的样本 x = ( ，恐) 指派零概率，则称目标函数f = ( z ，五) c lx c 2 与d 是相容的。 基于“相容性概念，我们会发现，即使c l 和g 是复杂度很高的大概念类，与 分布d 相容的目标概念集仍然可能会比较小。因此，我们能够利用未标记样本来查询 哪些目标概念是相容的，从而有助于减少学习算法所需的标记样本数量。 我们借助将分布视为加权二部图来描述c o t r a i n i n g 算法，二部图可以表示为 g d ( 置，五) 。图中左边的每个顶点对就视图置中的一个特征向量，右边的每一顶点 对应视图x ，中的一个特征向量，当且仅当在d 分布下样本x = ( 五，x 2 ) 以非零概率存在 时，左右顶点间存在一条边，该边的权重为该样本存在的概率。为方便起见，我们去 掉所有出度和入度为零的顶点，这些顶点对应于那些概率为零的样本点。图1 4 表示 二部图g d 和g ，每一条边表示样本x = ( 五，屯) 在分布d 下非零概率存在，实线边表 示样本是有限样本集合s 中已经观察到的样本。 图1 4 二部图和g 在基于二部图的描述方式下，概念空间c 与d “相容”就对应于图中没有交叉线 的划分，每一个划分称为一个连通成分。也可以根据图中相交线的权重来定义一个划 第一章绪论结构半监督学习算法及其应用研究 分的不相容度p = 1 一昂【( 而，x 2 ) ：f ( x 1 ) 六( ) 】，( 0 p 1 ) 。 给定一个未标记样本集s ，我们可以很容易画出一个二部图g ，图中对于每个 样本x = ( x 1 ，x 2 ) s ，都存在一条边( 一，x 2 ) 。这样属于同一连通分量的样本就必然属于 同一个类。因此，我们发现未标记样本可以帮助利用未标记样本，使用比较少的已标 记样本来提高学习器的学习能力并且减少标记大量样本所带来的工作量。 以上分析的基础上，可以证明：在充分冗余视图假设成立时，在有分类噪音时， 如果c 2 是p a c 可学习的，有视图五上的一个初始的弱有效的学习器向( _ ) ，利用协 同训练算法，只需要未标记样本可以学得( gc ) 。这意味着，只要有足够的未标记样 本，能过协同训练算法。我们可以将一个在少量标记样本上学习到的弱学习器提高到 任意精度。 输入：给定两个充分冗余的特征集k 和； 已标记数据集三；未标记数据集u 中很 结构半监督学习算法及其应用研究第一章绪论 难满足c o t r a i n i n g 算法的两个假设。z h o u 和“提出了利用三个学习器和低约束条 件的t r i t r a i n i n g 算法【3 3 1 ，它不要求数据集具有充分冗余视图，也不要求在训练过程 中必需使用不同类型的分类器。这种方法不仅可以简便处理标记置信度估计问题以及 对未见实例的分类问题，还能够利用集成学习来提高泛化能力，避免了对任何学习器 去测定大量标记置信度，节省了时间，并得到广泛利用。k a m a ln i g a m 和r a y i dg h a n i t 2 6 】 对协同训练算法在不具有充分冗余视图的问题上进行了实验，其结果表明，当属性集 充分大时，可以随机地把属性集划分成两个视图，在此基础上进行协同训练也可以取 得较好的效果。 在基于内容的图像检索( c b i r ) 领域，z h o u 等人【1 9 】【2 0 】将协同训练引入图像检 索中，提出了协同训练的主动半监督相关反馈算法，通过协同训练和主动学习相结合， 可以有效地利用图像库中的未标记图像来提高检索性能。 1 1 5 直推支持向量机 聚类假设将边缘概率e ( x ) 和类条件概率p ( yx ) 联系起来，在p ( x ) 较大的高密度 区域内p ( y ix ) 的变化较小。一些半监督学习算法直接借助聚类假设，通过边缘概率 p ( x ) 对类条件概率p ( y i x ) 施加约束，以此融入未标记数据的信息，从而达到半监督 学习的目的。 t r a n s d u c t i v es v m ( t s v m ) 是s v m 的扩展。在传统推导式机器学习中，先利用已 标记数据来得到一个分类函数( 利用己知数据进行学习的过程) ，然后用分类函数对 感兴趣的样本点来分类，而t s v m 是一种直接从已知样本出发对特定的未知样本进 行识别和分类的技术。直推式的学习最早是由v a p n i k 于1 9 9 8 年提出的。v a p n i k 认为， 经典的归纳学习假设期望学习得到一个在整个样本分布上具有低错误率的决策函数， 这实际上把问题复杂化了，因为在很多情况下，人们并不关心决策函数在整个样本分 布上性能如何，而只是期望在给定的要预测的示例上达到最好的性能【5 4 1 。t s v m 假 设不同类别的未标记数据能够被一个大间隔分开，它不仅实现了将分类界面推到数据 的低密度区域，而且将监督情况下的大间隔思想推广到了半监督学习情况，以保证在 完成半监督分类时，分类器仍然具有良好的推广性能。然而，由于未标记样本的标签 未知，简单的推广在半监督情况下遇到了困难，样本间隔很难确切描述。通常施加一 9 第一章绪论结构半监督学习算法及其应用研究 个弱约束，使得未标记数据落在间隔之外，即未标记样本一定要属于某一类，决策边 界在未标记数据上有最小的泛化误差。直观上，未标记数据能指导线性边界避开数据 稠密区域。在此，优化目标可以表达为： m i n 去0 w 旷+ c 董+ c 毒 ( 1 6 ) 1 - i = l，= 月+ l 使得下面条件满足： y i ( w x i + b ) 1 一毒( 1 i 力) w 薯+ 6 i 1 一磊 ( 以+ 1 f 刀+ 聊) 毒 0( 1 i 以+ 朋) t s v m 建立了一种直接从已知样本出发对未知样本进行识别和分类的方法和原 则。由于是从特殊到特殊的推理，所以难以直接进行客观验证。另外，t s v m 也存在 其它方面的不足，比如时间复杂度较高，需要预先设置正负比例等等。 图1 - 6 在t s v m 中，u 有助于决定边界在稀疏地区。如仅有已标记数据，则最大m a r g i n 边界为点线表示；如果有未标记点( 白点) ，则实线表示最大m a r g i n 边界。 1 1 6 基于图的方法 图中的节点代表已标记和未标记数据，边的权重表示被连接的两个节点的相似程 度，创建图的方法有全连通图、稀疏图、k n n 图、6 n n 图等。其中参数k 控制边的 数量，直接影响到权重的计算量，也对最终的分类效果产生一定的影响，但目前对于 l o 结构半监督学习算法及其应用研究第章绪论 k 的选取往往还只是经验性的方法。 首先，根据训练样本建立图g = ，其中顶点v v 用来表示样本点，边 e e y y 表示样本间的关系( 如图1 - 7 所示) 。w 为图g 的权值矩阵，彬，r ，是 基于欧氏距离计算的权重，t c a , f i , , v , 的度z 定义为z = ，样本间的权值函数为 - e x p ( - 蝉) ( 1 7 ) 然后，定义所需优化的目标函数并通过决策函数在图上的光滑性作为正则化项来 求取最优模型参数。这些方法通常都假定图上标记是光滑的。许多基于图的方法可以 被视为估计图上的函数厂。厂需同时满足两个条件：1 、应该接近给定的已标记节点 的标签此；2 、应该对整个图是光滑的。这可以表示为一个正规化的框架，第一项是损 失函数，第二项是一个正则化项。基于图的方法本质上是非参数的( n o n p a r a m e t r i c ) 、 判别式的( d i s c r i m i n a t i v e ) 和直推的( t r a n s d u c t i v e ) 。 她5 0 s x , 掣 图1 7 连接样本点的图 图模型中大部分节点都是未标记数据，节点所属的类可以通过连接边向它的邻居 节点传播( 如图1 7 ) ，就像已标记节点将类别信息推向未标记节点。比如，对于图 1 - 8 ( a ) q b 两个手写体数字，虽然他们属于同一类别，但距离却相差得很远。在基于欧 氏距离构建的k n n 图上，相邻图像间的欧氏距离比较小，如果存在大量的数字2 的 图像，那么在图上将存在连接两个手写体数字的一条路径，假设路径为图1 - 8 ( b ) 中所 示。那么图中相邻的两个顶点具有足够高的相似度，所以在标签传播的过程中会使得 图1 - 8 ( a ) 中两个手写体数字具有相同的标记。 第一章绪论 结构半监督学习算法及其应用研究 d 么 ( a ) d aa & 2 么 ( b ) 图1 8 未标记样本组成的路径 总的来说，基于图结构的半监督学习主要的思想就是利用已标记数据和未标记数 据构建一个图g ，然后用如下方法对未标记数据分类：用拉普拉斯矩阵作为正则化子、 用最小割图作为低密度划分、调合函数的方法( 实质就是对拉普拉斯矩阵的谱分解) 、 再者就是把图上的r a n d o mw a l k 作为判定方法( 从图中任意一个结点出发，把已标记 样本作为吸收壁的随机扩散方法，这也是标记传播的基本思想) 。 ( 一) m i n c u t s 在二分类的情况下，可以把半监督学习看作是一个图的最d , g - 0 问题【4 9 】。在已标记 和未标记样本上建立一个加权图，在图中寻找最小割，并根据划分对样本点进行标记 ( 如图1 - 9 所示) 。通过线性规划解决划分问题，见下式： v z e ( ) = w ( i ，驯朋) 一厂( 列，f ：v 专 o ，1 ) ( 1 8 ) ，j 图1 - 9 m i n c u t 算法 二j 二+ 啪 相应的框架由两部分构成：损失函数和正则化算子，其中损失函数为 z l e l 0 0f t 一只1 2 ，正则化算子为1 1 , w ，i z z i = 1 1 , w ，k 一乃1 2 。m i n c u t s 只给出一个 没有置信度的“硬 分类，因此无法得到封闭式的唯一解。 结构半监督学习算法及其应用研究 第章绪论 ( - - ) c o n s i s t e n c y 算法 z h o ue ta 1 提出一种基于局部和全局一致假设的方法【5 】【6 们。数据点用全连通图来 进行表示，数据标签从已标记数据向未标记数据进行传播，具体传播过程如下式： 即) ，蚤，4 - 4 , s 厄砌+ ( 1 刊川) ( 1 9 ) 算法收敛于： f = ( 1 一口) ( 1 一口s ) 。1 y( 1 1 0 ) c o n s i s t e n c y 方法的任务可以看作是优化一个关于图中节点的函数，使它在相邻 节点上光滑变化，而在不同流形上有较大的变化。目标函数为： 胛，= 三酬去e 一再1 小2 静蚓1 2 n 其中c 维向量z = e l l 鬈：，k 表示标记节点f 的类别，c 维向量c 表示算法对节点 本质上讲，文献 3 9 】 4 8 提出的方法与 3 】中的s p e c t r a l 方法等都是c o n s i s t e n c y 方 z h ue ta 1 提出基于调和函数的方法，并在文献【1 】 3 8 】中讨论与随机游走、最小割 图、谱图聚类的联系。其框架与m i n c u t s 的不同之处在于，z h u 的方法中预测标注值 松弛到实数域，而不是 o ，1 ，从而保证能够得到一个封闭式的唯一解( 见下式) 。 町) 2 否w ( f ，州邝h ) 2 ( 1 1 2 ) f ：v 专 0 ，1 】 把以上几种方法相比较，m i n c u t s 和调和方法能够保持已标记数据的标记，而 c o n s i s t e n c y 方法为标记数据施力n t - - 个惩罚项，则可能使标记改变。 1 1 7 半监督学习算法的选择 根据没有免费的午餐定理【4 2 1 ，并不存在天然最优的分类器。对于半监督学习 算法的选择，只能根据应用的实际情况选择最优的算法。对于每一种半监督学习算法， 第一章绪论 结构半监督学习算法及其应用研究 都需要建立在一定假设的基础上才能工作。如果一个算法能够成功解决某一个问题， 只能说明该算法所依赖的模型假设与该问题的实际情况是相互匹配的。也就是说我们 不能脱离具体问题来讨论半监督学习算法的优劣，只能具体问题具体地分析1 1 引。 对于半监督学习算法的选择，可以按以下经验性的思路进行：如果问题存在天然 划分的特征子集，可以尝试使用基于多视图的方法；如果特征相似的数据倾向于属于 相同的类别，则可以尝试使用基于图的半监督方法；如果已经存在了可以使用的比较 用研究第一章绪论 分类和检索的基础理论，并在人工数据集和c o r e l 图像库上对嵌 行实验分析。 图的算法作为基本分类器的协同结构进行理论分析的基础上，结 在半监督图像检索中的应用实例。 第五章把基于群论的机器学习理论中的不变特征应用到图像检索中，给出了一种 基于图像不变特征和扩大检索结果相异性的半监督检索方法。通过实验中查全率与查 准率的相关变化来进行分析。 第六章为论文的总结与展望。 第二章结构半监督学习算法结构半监督学习算法及其应用研究 第二章结构半监督学习算法 本章内容分为两部分，首先提出一种在图构造过程中能够融入先验知识的相似性 度量算法，使得在图中能够施加标记信息的影响并反映流形结构的信息；然后讨论一 种基于图的半监督算法在协同结构下的应用问题。 2 1 一种嵌入先验知识的相似性度量学习算法 在半监督学习中，利用相似性度量方法计算两样本间的相似性，根据相似性进行 标签的传播。另外在图像检索系统中，对于图像特征表示方法特定的情况下，图像检 索的效果在某种程度上取决于所选用的度量方法【2 1 。 2 1 1 相似性度量的一般方法 相似性度量方法就是利用距离函数来计算对象的特征序列之间的距离，用这种距 离来表示对象问的相似性程度。 假设存在n 个p 维样本点： x j = ( 薯1 ，薯2 ，) 。， f = 1 ，2 ，n 用各点之间的距离来衡量各样本问的相似性程度。令d ( 薯，z ，) 为样本薯，x j 之间的 距离，一般要求它满足下列条件【4 1 】： ( 1 ) d ( t ，x ，) o ，且j ( 一，) = o 当且仅当t = x j ( 2 ) d ( t ，x j ) = d ( x ，x i ) ( 3 ) d ( 薯，x ，) d ( x j ，x k ) + d ( x k ，x ，) 下面简单介绍几种距离度量的方法。 ( 一) m i n k o w s k i 距离 如果特征的各个分量之间是正交无关的，并且各维的重要程度相同的话，可以采 用m i n k o w s k i 距离： 1 6 第二章结构半监督学习算法 没，可以采用马氏距离： ( 2 1 ) 维度比较少的某个属性被淹 d ( 薯，_ ) = ( 薯，x j ) s ( 薯，0 ) - ( 2 2 ) 其中s 为样本的协方差矩阵。一般情况下，马氏距离在图像分类和检索中具有较高的 正确率和查准率，但公式中的协方差矩阵也增加了计算量。 ( 三) 角度相似性函数 文2 晌 q 3 x ，x 它表示特征薯和x j 之间夹角的余弦，即薯的单位向量与x ，的单位向量之问的点 积【4 1 1 。特例：当特征的取值仅为 o ，1 ) 两个值时，夹角余弦度量具有特别的含义，即 当特征的第f 个分量为l 时，认为该特征具有第f 个属性；当特征的第f 个分量为0 时， 认为该特征无此属性。这时，x , t x ，的值就等于薯和0 这两个向量共同具有的属性数 目。忙t0 为中具有的特征数目和_ 中具有的特征数目的几何平均。因此，在特 征取值为0 和1 的二值情况下，s ( 薯，x ，) 等于和x j 中具有的共同特征数目的相似性 测度。 对于归一化后的向量余弦和欧氏距离会给出相同的排序，推导过程为： ( 1 元一歹i ) 2 = 坚；( 誓一只) 2 = 2 ( 1 一翌。，以) 这表明余弦法和利用向量欧氏距离法得出的结果是一致的。 ( 四) 方差加权距离 对标准化后的数据计算欧氏距离时，即为方差加权距离： 肌，、一( 靠一) 2 - 烈如2 瞎耸il 矧 3 i j ( 2 4 ) 第二章结构半监督学习算法 结构半监督学习算法及其应用研究 2 1 2 图像间的相似性度量方法 在本文实验部分要涉及到图像间的相似性度量方法，所以在相似性度量这个部分 也一并列出。在图像检索中用于衡量两幅图像间的相似性程度，常用的两种方法有分 块颜色直方图相似度量和颜色相邻矩阵相似度量。 ( 一) 分块颜色直方图相似度量 两个区块6 l 和6 2 间的颜色直方图的距离，常采用如果距离公式： d ( 6 l ，b 2 ) = m i n ( b 1 6 2 。，) ( 2 5 ) 上式称为直方图相交距离3 7 1 ，其中，l 为直方图的柄数，即量化的颜色数。m i n ( 毛6 2 ，) 表示块6 1 和6 2 中颜色值为f 的点数的极小值。两个块间相似性度量为： m i n ( b l p6 2 。f ) s i r e ( b , ，6 2 ) = 且丁一 ( 2 6 ) 6 1 ， f f i l 比较时，两幅图像对应位置的块进行比较。 ( 二) 颜色相邻矩阵相似度量 把两幅图像颜色相邻矩阵的相关系数，作为两幅图像间的相似度口1 1 。此时，图像 么和b 间的相似度量定义如下： 其中， $ i m ( a ，b ) = k ( 吼。一心) ( ，一儿) i = lj = l ( 2 7 ) 儿5 古善善吼， t s = 吉， 2 万缶缶。 ( 三) 纹理相似度计算 图像彳和b 的纹理特征矩阵分别为死、疋，定义彳和b 间的纹理相似度为： 1 8 结构半监督学习算法及其应用研究第二章结构半监督学习算法 s i r e ( a , b ) = 1 - 丢两1 b - - 而 1 a + 。, m 芝酬x a , - a ) ( 2 8 ) 其中心和为无和疋的均值，以，磊分别为l 和瓦的标准差。 2 1 3 一种嵌入先验知识的相似性度量算法 在基于图的半监督学习中，图的建立是算法非常重要的组成部分。在实际应用中， 图是数据表示的直接形式，所以图的构建一定程度上影响着算法的性能。构建一个能 够充分反映数据的几何结构的图比选择一种方法更为重要，但是图的构建方法却没有 得到广泛的研究【l 】。 关于图的构造方法主要有：全连通图、k n n 图、6 n n 图等。文献【1 2 】提出一种 相似于局部线性嵌入方法( 1 0 c a l l yl i n e a re m b e d d i n g ) 的图构造方法，每一个数据点都 由其相邻数据点进行线性重构，即： i i l i n q = i i x , 一一州_ ，坳_ 1 1 2 旺z x j n ( x , ) = 1 ，。 ( 2 9 ) 其中( 薯) 为薯相邻的数据点集合。 通常假设数据点散布在低维流形上或流形附近，根据这个假设，图应该能够较好 的表示潜在的低维流形，它应该尽可能避免连接到流形外的近路( s h o r t c u t ) ，避免错误 断开流形区域的间隔( c a p ) ，且能反映数据点的密度信息。c a r r e i r a p e r p i n a n 和z e m e l 在最小生成树( m s t ) 的基础上，利用树的集成方法，建立了鲁棒性较强的图【5 5 1 。目前 研究图构造主要有一下一些不同的方法：利用领域知识；近邻图；局部拟合。 绝大多数模式识和机器学习的算法不可避免地要涉及到距离的度量，相对于人工 选择一种度量方法，从数据中学到的度量会更加有效。半监督框架下度量学习中的监 督信息通常通过标记或相似对与不相似对的形式给出。最先采用对约束进行半监督聚 类的方法，是在k m e a n s 聚类算法中考虑相似对和不相似对。本章提出的方法是基于 流形结构的度量学习。 2 1 3 1 嵌入先验知识的概念 现实当中的数据通常呈现为复杂的流形结构。从待分类的未标记数据中能得到 1 9 第二章结构半监督学 - j 算法 结构半监督学习算法及其应用研究 的，主要是整个数据集所构成的空间结构信息；从已标记数据中能得到的，主要是类 别信息。对于相似性度量方法的选择，欧氏距离只能作为一种局部度量来使用，而不 能够反映数据集在空间当中分布的整体特性，不适合作为相似性的度量方法。由于处 于同一高密度区域的数据点应该具有高相似性，所以当数据点共同位于空间中的一个 子流形上的时候，更应该沿着流形结构进行相似关系的比较，这就需要融合密度和流 形结构的信息。例如，图2 1 ( a ) 所示