（计算机软件与理论专业论文）一种基于李群的半监督学习算法及应用研究.pdf

一种基于李群的半监督学习算法及应用研究中文摘要 一种基于李群的半监督学习算法及应用研究奉 中文摘要 半监督学习是近年来倍受人们关注的新的机器学习方法，本文将李群理论引入到 半监督学习领域中，给出了基于李群的半监督学习算法。主要包括以下几方面内容： 1 分析了半监督学习的研究现状； 2 给出了基于李群代数结构和几何结构的半监督学习模型； 3 给出了线性李群的半监督学习算法( s s l a g l ( n ) ) ，并将其应用于一类甾体 药物的活性预测； 4 给出了参数李群的半监督学习算法( s s l a p l g ) ，并将其应用于u c i 医学数 据集的降维和分类； 5 针对药物毒性预测，给出了基于s s l a p l g 的药物毒性预测模拟系统，并在 t o x 数据集上得到验证。 通过本文的研究，一方面，丰富了半监督学习的研究内容；另一方面，将基于 李群的半监督学习算法应用于医学数据集的降维以及药物的活性分析和毒性的预测 分类当中，为提出的新方法找到了应用背景。 关键词：半监督学习，李群，李群机器学习，药物活性预测 + 本文的研究得到国家自然科学基金项目支持( 6 0 7 7 5 0 4 5 ) i 作者：徐寒香 指导老师：李凡长 a s e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m b a s e do nl i e g r o u pa n da p p l i c a t i o n a b s t r a c t s e m i - s u p e r v i s e dl e a r n i n gh a sb e e nt a k e nm u c ha t t e n t i o ni nr e c e n ty e a r s a san e w m a c h i n el e a r n j n gm e t h o d i nt h i sp a p e r ，w ei n t r o d u c el i eg r o u pt os e m i 。s u p e r v l s e d l e 锄i n ga 1 1 dp u tf o r w a r ds e m i s u p e r v i s e dl e a r n i n gb a s e d o i ll i eg r o u p t h em a i nr e s e a r c h r e s u l t sa r ec o n c l u d e da sf o l l o w s ： 1 i n t r o d u c t i o no fs e m i s u p e r v i s e dl e a r n i n g ； 2 t h em o d e l so fs e m i s u p e r v i s e dl e a r n i n gb a s e d o nl i eg r o u pa r eg i v e n ，i n c l u d i n g t h ea l g e b r am o d e la n dt h eg e o m e t r i cm o d e l ； 3 t h ea l g o r i t h mo fs e m i s u p e r v i s e dl e a r n i n gb a s e d o ng l ( n ) ( s s l a - g l ( n ) ) a n di t s u s ei nt h ep r e d i c t i o no fa c t i v i t yo fs t e r o i dd r u g s ； 4 t h ea l g o r i t h r no fs e m i s u p e r v i s e dl e a r n i n g b a s e do np a r a m e t e rl i eg r o u p ( s s l g p l g ) a n di t su s ei nt h ed i m e n s i o n a l i t yr e d u c t i o na n d c l a s s i f i c a t i o no fu c i m e d i c a ld a t a s e t ； 5 f o rd r u gt o x i c i t yp r e t i c t i o n ，w eg i v eas i m u l a t i o ns y s t e mb a s e do ns s l a p l g t o p r e d i c td r u gt o x i c i t ya n d v a l i d a t ei tw i t ht o xd a t a s e t t h r o u g | lt h ew o r ko ft h i sp a p e r ，o no n eh a n d ，t h ec o n t e n to fs e m i - s u p e r v i s e dl e a r n i n g i se 血c 1 1 e d ，o nt h eo 也e rh a n d ，w eu s es e m i - s u p e r v i s e dl e a r n i n gb a s e do nl i eg r o u p t o m e d i c a ld a t ai no r d e rt or e a l i z ed i m e n s i o n a l i t yr e d u c t i o na n dc l a s s i f i c a t i o n ，a sw e l l a st h e p r e d i c t i o no fm e d i c a la c t i v i t ya n dt o x i c i t y , t h i sc a r le x t e n dt h en o v e la p p l i e so f t h ea b o v e p r o p o s e dn e w m e t h o d s k e vw o r d s ：s e m i s u p e r v i s e dl e a m i n g ，l i eg r o u p ，l i eg r o u p m a c h i n el e a r n i n g ， d r u ga c t i v i t yp r e d i c t i o n w r i t t e n b y ：x uh a n x i a n g s u p e r v i s e db y ：l if a n z h a n g s u p p o r t e db yn a t i o n a ln a t u r a l s c i e n c ef o u n d a t i o n o fer - c h i n a ( 6 0 7 7 5 0 4 5 ) 1 1 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：名妫一e t 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：夕摩翥日 导师签 日期：丝： 一种基于李群的半监督学习算法及应用研究第一章引言 第一章引言 半监督学习和李群机器学习是近年来倍受人们关注的新的机器学习方法。本章分 析了半监督学习的研究现状和李群机器学习的研究进展。关于半监督学习方面，介绍 了当前流行的五个算法：s e l f - t r a i n i n g ( 自训练) 算法，带有生成混合模型的e m 算法， c o t r a i n i n g ( 协同训练) 算法，t s v m ( 直推式支持向量机) 算法，基于图的算法。 1 1 半监督学习研究现状 利用大量的未标记示例来建立更好的分类器，减少人力物力消耗，改善机器学习 性能的半监督学习在理论和实践上已引起广大研究者的兴趣，是当前机器学习研究中 最受关注的问题之一【1 捌。 目前半监督学习的方法主要包括：带有生成混合模型的e m 算法、s e l f - t r a i n i n g ( 自训练) 算法、c o t r a i n i n g ( 协同训练) 算法、直推式支持向量机t s v m ( 即将决 策边界避开数据稠密区域) 和基于图的方法等等【2 】。对这些算法实际中是这样选择的： 如果数据能够形成很好的聚类，就可以选择带有生成混合模型的e m 算法；如果特征 能够分解为两个子集，则选择c o t r a i n i n g 算法是合适的；如果有相似特征的两个点在 同一类中，则可利用基于图的算法；如果已经利用了s v m ，则在半监督情况下利用 t s v m 是一个自然扩展；如果已经存在一个复杂的监督分类器，则可利用s e l f - t r a i n i n g 算法1 3 j 。下面就相关算法进行介绍。 1 1 1 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 1 所示。s e l f - t r a i n i n g 假定自己的高置信度的预测是正确的，在 s e l f - t r a i n i n 中会首先利用少量的有标记数据训练出一个分类器，然后将这个分类器用 于对未标记数据进行分类，通常挑选置信度最高的未标记样本，连同它们的预测标记 加入训练集。分类器重新训练，迭代这个过程。 第一章引言 一种基于李群的半监督学习算法及应用研究 表1 1 s e l f - t r a i n i n g 算法流程 输入：特征集合v ；训练已标记样本集合三；未标记样本集u ； s e l f - t r a i n i n g 的循环次数丁，样本置信度阈值弓 f o r t = l ，2 ，t 1 利用标注样本集三在特征集合矿上训练分类器c ； 2 利用分类器c 对所有未标记样本甜u 进行预测，计算其预测置信度瓦，判断 l 是否大于，如果小于乃，舍弃这次预测； 3 将较高置信度的样本加入到训练已标记样本集三中。 e n df o r 输出：分类结果及最终分类器c 。 注意到分类器是利用自身的预测来学习，因此这个过程被称为s e l f - t e a c h i n g 或者 b o o t s t r a p p i n g 。为了避免一个分类器强化自己的错误，一些算法试图利用置信度低于 一个阈值就不去学习未标记点的方法来避免这种情况的产生。通常，生成混合模型和 e m 算法能被看作一个特殊情况下的软s e l f - t r a i n i n g 。s e l f - t r a i n i n g 已经被用于现实生 活中的自然语言处理任务，y a r o w s k y ( 1 9 9 5 ) 利用s e l f - t r a i n i n g 对词义消歧，例如， 判定在给定的上下文中单词“p l a n t 是“生物体”还是“工厂”1 9 】。 因此s e l f - t r a i n i n g 的优点在于其简单性，它是一个封装算法，能利用现有的分类 器，但是早期的错误会被强化，导致算法性能不高。 1 1 2 生成式模型算法 生成式模型是半监督学习的一个常用技术。它假设模型满足概率条件 p ( x ，y ) = p ( y ) p ( x l 力，此处p ( xi 少) 是一个可识别的混合分布，例如高斯混合模型。 此类算法是将生成式模型作为分类器，将大量的未标记数据属于每个类别的概率视为 一组缺失参数，然后采用最大似然估计( m l e ) 、最大后验估计( m a p ) 或贝叶斯算 法等来进行标记估计和模型参数估计，使得混合分量能够确定；在理想情况下仅利用 一个分量的有标记示例就能完全确定混合分布。此类算法可以看成是在少量有标记数 据周围进行聚类，是早期直接采用聚类假设的做法。 对于半监督分类而言，生成式模型通过估计数据点的联合概率分布，可以描述出 2 一种基于李群的半监督学习算法及应用研究 第一章引言 数据点属于哪一个确定的类别标记，而非类别决定边界。常见的生成模型有：高斯分 布( g a u s s i a nd i s t r i b u t i o n ) 、高斯混合分布( g a u s s i a nm i x t u r em o d e l ) ，和e m 算法合 作，常用于图像分类；多项式分布( m u l t i n o m i a ld i s t r i b u t i o n ) 、朴素贝叶斯( n m v e b a y e s ) ，与e m 算法并用，常用于文本分类；隐马尔科夫模型( h i d d e nm a r k o vm o d e l s ) ， 用b a u m w e l c h 算法，常用于语音识别。生成式模型算法常关注以下几个问题【2 】： ( 一) 可识别性 混合模型理想上应该是可识别的。一般令 岛，表示由参数秒索引的分布族，秒是 可识别的，如果 b 岛p e 。p e ： 等于混合分量的置换。如果模型族是可识别的，理论上无限u 能从分量索引的置换中 学习到口。 ( 二) 模型正确率 如果混合模型假设是正确的，未标记数据能够保证增加正确率，然而如果模型是 错误的，未标记模型就有可能降低正确率。c o z m a n 等人( 2 0 0 3 ) 观察到这一结果【10 1 。 因此构造和实际对应的混合模型就很重要。例如n i g a m ( 2 0 0 1 ) 指出在文本范畴 内一个标题可能包含几个子标题，如果对这多个子标题合起来作模型就比单个的要 好，也可采用降低未标记样本权重的方法【1 1 1 。 ( 三) e m 局部最大化 即使混合模型假设是正确的，实际中混合分量是由e m 算法确定的，但是e m 算 法易导致局部最大值。n i g a m ( 2 0 0 1 ) 指出如果局部最大值偏离全局最大值，未标记 样本就会破坏学习，相关修正措施是经过主动学习精确选择一个开始剧1 1 】。 ( 四) 聚类和标记 代替利用一个概率生成混合模型，一些方法是利用多个聚类算法来聚集整个数据 集，然后利用已标记样本标记每个群组，d a r a 等人( 2 0 0 2 ) 探讨过这个问题【1 2 】。尽 管性能良好特别是聚类算法和真实数据分布匹配时，但是这些方法很难分析算法的本 质。 因此，生成式模型的优势在于有着清晰的深入研究的概率框架，当模型正确时， 算法性能会非常好；但是模型的正确性很难证明，如何确定和实际匹配的模型仍是一 第一章引言一种基于李群的半监督学习算法及应用研究 个o p e n 问题，如果模型不够匹配，未标记数据反而会降低算法性能。 1 1 3c o t r a i n i n g 算法和多视图学习 ( 一) c o - t r m n i n g 最初的c o t r a i n i n g 算法是a b l u m 和t m i t c h e l l 在1 9 9 8 提出的【2 3 1 。他们假设数据 集有两个充分冗余( s u f f i c i e n ta n dr e d u n d a n t ) 视图( v i e w ) ，即满足下列假设：( 1 ) 特征能够分成两个集合；( 2 ) 每一个子特征集足够训练成一个好的分类器；( 3 ) 两个 集合对给定的类是条件独立的。利用已标记数据在相互独立的两个子集上，初始训练 出两个不同的分类器。这两个分类器分别对未标记数据进行分类，每次互相标记一部 分自认为置信度高的数据给对方，然后重新训练使模型得以更新，进一步迭代到没有 更多合适的未标记数据加入，此类算法隐含地利用了聚类假设或流形假设。 c o t r a i n i n g 算法描述如表1 2 ： 表1 2 标准c o 一仃a i n i n g 算法 输入：给定两个充分冗余的特征集k 和k ；已标记训练集l ；未标记训练集u w h i l e 未标注集合【，非空时d o 分类器c 1 更新分类器c 2 ： 1 在训练集三的特征集k 上训练分类器c l ； 2 。 对未标注样本集u 中的样本进行分类，并计算其置信度； 3 将置信度最高的甩个样本从未标注样本集u 中取出加入到训练样本集三。 分类器c 2 更新分类器c l ： 1 在训练集三的特征集k 上训练分类器g ； 2 对未标注样本集u 中的样本进行分类，并计算其置信度； 3 将置信度最高的，1 个样本从未标注样本集d 中取出加入到训练样本集三。 e n dw h i l e 输出：分类器c l 、c 和最终的分类结果 在c o t r a i n i n g 中，未标记数据帮助降低形式空间大小。换句话说，两个分类器( 或 假设) 对大量未标记数据和已标记数据必须一致。必须假定两个子特征是充分的才能 利用u 上每一个学习器的标记，子特征必须是条件独立的以至于分类器的高置信数据 4 一种基于李群的半监督学习算法及应用研究 第一章引言 点相对其它分类器是独立同分布样本【l 引。 n i g a m 为比较c o t r a i n i n g 和带有e m 的生成混合模型进行了广泛的实验，结果表 明如果条件独立假设确实满足，则c o t r a i n i n g 的性能较好。此外，代替标注- - d , 部分 高置信点，尽可能标记整个u ，称这种范例为c o e m 。最后，如果没有本质特征分 解，则随机地将特征集分解为两个子集来建立人工分解，表明带有人工特征分解的 c o t r a i n i n g 仍然有用，尽管不如以前【1 l 】。j o n e s s ( 2 0 0 5 ) 将c o t r a i n i n g ，c o e m 和其 它相关算法用于文本信息抽取。b a l c a n 和b l u m ( 2 0 0 6 ) 说明在分类器只有一个己标 记点的特殊情况下，c o t r a i n i n g 的效率也相当好。z h o u 等人( 2 0 0 7 ) 给出了一个利 用典型相关分析的c o t r a i n i n g 算法，也仅只需要一个已标记剧2 1 。 c o t r a i n i n g 对特征分解需要很强的假设，许多研究者就来考虑是否能降低这些条 件。g o l d m a n 和z h o u ( 2 0 0 0 ) 利用从同一个属性集上训练出的两个不同的分类器， 并利用一个学习器的高置信数据点，在协同训练过程中，每个分类器通过统计技术来 估计标记置信度，并且把标记置信度最高的示例进行标记后提交给另一个分类器作为 有标记训练例，以便对方进行更新，该过程反复进行，直到达到某个停止条件 4 1 。此 后，z h o u g ( 2 0 0 4 ) 又对该算法进行了扩展，提出了一个民主的单视图多学习器 c o t r a i n i n g 算法，使其能够使用多个从己标记数据上训练得到的不同种类的分类器， 再预测未标记样本，如果大部分学习器都确定未标记点的分类，则该类别就作为标记， 将该样本点和其标记再重新加入训练集，所有的学习器在更新后的训练集上重新训 练，最终的标记由所有学习器根据权重投票产生【1 5 】。类似地z h o u 和l i ( 2 0 0 5 ) 提出 了利用三个学习器的t r i t r a i n i n g 算法，如果其中两个均同意未标记点的类别，则该 类别可被用到第三个学习器的学习，这个方法避免了对任何学习器去大量测定标记置 信度，节省了时间，得到广泛利用，例如它可用于没有不同视图或分类器的数据集【1 6 。 ( 二) 多视图学习 更一般的，能利用学习器间的协定来定义学习范例。c o t r a i n i n g 的特殊假设在多 视图学习模型中一般不再需要。反之，多种假设( 带有不同的归纳偏置，例如，决策 树，s v m 等等) 从相同的已标记数据集中被训练，且需要对任何给定的未标记样例 作近似的预计。d e s a ( 1 9 9 3 ) 开始研究了多视图学习，s i n d h w a n i ( 2 0 0 5 ) 和b r e f e l d 等人( 2 0 0 6 ) 分别将其用于半监督回归，此外f a r q u h a r ( 2 0 0 6 ) 也建立了对多个学习 器间协定的理论分析【2 l 。 5 第一章引言 一种基于李群的半监督学习算法及应用研究 1 1 4t s v m 算法 半监督的s v m s ( s 3 v m s ) 和t r a n s d u c t i v es v m s ( t s v m s ) 是等价的，它假设不同类 别的未标记数据能被一个大的m a r g i n 分开，因此算法主要通过最大化“未标记数据 m a r g i n 来实现，s 3 v m s 是带有未标记数据的标准支持向量机的扩展【l ”。在标准s v m 中仅仅能利用已标记数据，目的是在重构核希尔伯特空间中寻找最大m a r g i n 的线性 边界。在s 3 v m s 中，未标记数据也能利用，目的是寻找未标记数据的标记，通过加 入约束项使得未标记数据落在m a r g i n 之外，以致线性边界在已标记和未标记数据上 都有最大m a r g i n ，决策边界在未标记数据上有最小的泛化误差【l 8 。 图1 1t s v m 如在图1 1 中，未标记数据有助于决定边界的稀疏区域。如仅有已标记数据，则 最大m a r g i n 边界为点线表示，如果还有未标记点( 白点) ，则实线表示最大边界。 半监督的s v m s 算法流程如表1 3 ： 表1 3 半监督的s v m s 的算法流程 桶八：核k ；杈值 ，五；已标记样本榘三2 而乃) ；禾标记样本集u5 毛 步骤：t s v m 能够看作是在未标记样本上增加一个额外正则化项。令厂 ) = 厅 ) + b 此处办( x ) h 鬈。解最优化问题为： 呼n 善i ( 1 一以( 誓) ) + + 删l + 五毫( 1 一i 厂( 誓) i ) + s t -z1-z”()：寻圭舅1， ；。“l 鲁“ 输出：由f ( x 、的符号对测试样例x 分类。 6 一种基于李群的半监督学习算法及应用研究第一章引言 其中( z + ) = m a x ( z ，0 ) ，最后一项由未标记点x 指派标i e f ( x ) 产生，未标记点上的边 距因此标记为lf ( x ) i 。损失函数( 1 一i ( 薯) 1 ) + 有一个如图1 2 的非凸的帽形( h a t ) ， 与标准s v m 的目标是凸函数不同，这是解该优化问题困难的根本原因。 图1 2t s v m 损失函数( 1 一lf ( x i ) 4 - 目前已有s v m7 i g h ，v s v m ，连续s 3 v m ，确定性退火法，凹凸程序处理( c c c p ) ， 分支定界法( b r a n c ha n db o u n d ) 等方法来解决这个问题。 c h a p e l l e 和z i e n ( 2 0 0 5 ) 提出了利用一个高斯函数来估计帽形损失，并在原始空 间进行梯度搜索。s i n d h w a n i 等人( 2 0 0 6 ) 利用确定性退火的办法，从一个“简单 的问题开始，并逐渐变形到t s v m 目标。类似的思想，c h a p e l l e 等人( 2 0 0 6 ) 使用一 个连续的方法，也经最小化一个简单的凸目标函数开始，并逐渐变形到t s v m 目标( 利 用高斯代替帽形损失) ，使用先前的迭代去初始化下一步迭代。c o l l o b e r t 等人( 2 0 0 6 ) 直接优化硬s v m ，使用近似优化过程称为凹凸程序( c c c p ) ，关键是要看到，帽形 损失是凸函数和凹函数之和，用线性上限取代凹函数，可以让凸函数最小化去产生损 失函数的上限，这样反复进行，直至达到局部最小。利用c c c p 能明显加快t s v m 训 练。s i n d h w a n i 和k e e r t h i ( 2 0 0 6 ) 针对线性s 3 v m s 提出了一个快速算法，适合大规模 的文本应用【l 】。利用分支定界搜索技术，c h a p e l l e 等人( 2 0 0 6 ) 针对较小数据集找到 一个全局最优方法，结论表明有较高的正确率。尽管分支定界对大型数据集可能不会 有用，结果仍指出了带有更好估计方法的t s v m 的潜力【2 】。 因此，半监督的s v m s 的优势在于有着清晰的数学框架，s v m 算法能用的地方， 半监督的s v m s 算法均可使用。但是在算法过程中，最优化很困难，容易陷入局部最 7 5 2 5 l 5 o 2 1 o 第一章引言一种基于李群的半监督学习算法及应用研究 优，算法的模型假设条件比生成式模型要低，但是效果也可能变差。 1 1 5 基于图的算法 图是在已标记和未标记点上给定的，它假设通过边权重连接的示例趋向相同的标 记，因此基于图正则化框架的半监督学习算法直接或间接地利用了流形假设。具体步 骤为：先根据训练例及某种相似度度量建立一个图，其中节点表示数据集中的标记和 未标记样例，边( 可能加权) 反映样例间的相似度，然后，定义所需优化的目标函数 并使用决策函数在图上的光滑性作为正则化项来求取最优模型参数。这些方法通常都 假定图上标记是光滑的，图方法本质上是一个参数的、判别的、转导的方法。 ( 一) 图的正则化 许多基于图的方法可以被视为估计图上的函数厂。厂需同时满足两个条件：1 ) 应该接近给定的已标记节点的标签y ，；2 ) 整个图是光滑的。这可以表示在一个正规 化的框架下的第一项是损失函数，第二项是一个正则化项。 几个基于图的方法基本上是类似的，不同点在于具体选择的损失函数和正则化 项。b l u m 和c h a w l a ( 2 0 0 5 ) 把半监督学习问题看作是求图上的最小切的过程，对图 进行分割，得到的不同区域对应于不同的类n t l 9 】。s z u m m e r 和j a a k k o l a ( 2 0 0 1 ) 利 用图上随机游走理论，建立半监督学习的随机场模型，这和扩散核有点相似【2 0 】。z h u x 等( 2 0 0 3 ) 指出高斯随机场和调和函数方法是一种对离散m a r k o v 随机场连续的张驰 方法，目标函数是一个带有无限权值的二次损失函数，和基于图上组合l a p l a c i a n 的 正则化项2 1 l 。z h o u d 等( 2 0 0 3 ) 指出局部和全局一致性方法的目标函数也是二次损 失函数加上正则化项，其中正则化项为标准化l a p l a c i a n l 2 2 1 。b e l k i n 等( 2 0 0 4 ) 说明 流形正则化假设输入空间距离较近的两点应该具有相同的标记，在t i k h o n o v 正则化 算法的基础上，利用边缘分布的几何特性，引入表示样本固有几何结构的正则化项。 然而在并入新的正则化项后，需要对两个正则化参数进行选择，这不仅增加了求解的 难度，而且理论基础也需要进一步的完善f 2 3 1 。此外，也有研究者从拉普拉斯谱的图核、 谱图变换、局部学习正则化等方面来进行探讨【2 】。 ( 二) 图构造 显然在基于图的半监督学习中，图是算法的核心部分。在实际应用中，图是数据 8 一种摹于李群的半监督学习算法及应用研究第一章引言 表示的直接形式，所以图的构建一定程度上影响着算法的性能。z h u x ( 2 0 0 5 ) 认为， 构建一个良好的图( 能够充分反映数据的几何结构) 比选择一种方法更为重要，并对图 的构建进行了讨论，但是图的构建方法并没有得到广泛的研究。c a r r e i r a p e r p i n a n 和 z e m e l ( 2 0 0 5 ) 在最小生成树( m s t ) 的基础上，利用树的集成方法，建立了鲁棒性较 强的图。目前研究图构造主要有以下不同的方法。1 ) 利用领域知识；2 ) 近邻图；3 ) 局部拟合1 2 j 。 因此基于图的方法的优势在于：有着清晰的数学框架：如果构造的图和问题很拟 合的话，算法的性能就很强；并且可以扩展到有向图。但是，如果图不匹配，算法的 性能就很差，并且算法对图的结构和边的权重都很敏感。 综上所述，目前关于半监督学习方面尽管取得了如此多的成绩，但从各种算法可 以看出，针对“数据= 标注数据+ 未标注数据 这个模式形成的各种半监督学习还缺 乏一般的系统理论。鉴于这样的实际情况，本文从对称性的角度来进行研究。 1 2 问题提出 对称性是自然界最普遍、最重要的特性。近代科学表明，自然界的所有重要的规 律均与某种对称性有关，甚至所有自然界的相互作用，都具有某种特殊的对称性 所谓“规范对称性 【驯。 无论什么样的对称现象，都与两种不同的情况相比较分不开的。在数学上，将两 种情况间通过确定的规则对应起来的关系，称为从一种情况到另一种情况的变换。在 物理学中，对称性的概念也可以概括为：如果某一现象或系统在某一变换( 如进行平 移、转动、空间反射、时间反演、伸缩和置换等对称变换) 下不改变，就说该现象或 系统具有该变换所对应的对称性【25 i 。大致地讲，对称性变换是保持系统不变的状态变 换，主要要求在对称性变换后：系统的统计诠释不变，并且系统的规律不变1 2 引。既然 每一种对称性都和某种特定的变换相联系，那么对称性的千差万别也就集中反映在与 之相联系的各种变换上。由数学理论研究可知，系统地研究各种变换之间普遍联系规 律的数学分支是群论，所以群是研究对称性问题的基础。在半监督学习中，学习系统 为“数据= 标注数据+ 未标注数据 这样的模式，标记的确定与不确定可通过某种对 应规则进行联系，即未标注数据经过某种变换后能得到它的标记值，从而转为标记数 9 第一章引言一种基于李群的半监督学习算法及应用研究 据，这种变换不会影响学习系统本质的诠释信息及内在规律，因此半监督学习系统中 数据本身有无标记自然形成对称变换关系。此外，应用处理对象的集合连同定义在其 上的运算都成一个群，因此从数据分析的角度来讲，数据自然蕴含着群结构。而在所 有的群中，物理学家应用得最广泛的群是李群。所有对称性变换在复合作用下均构成 李群，各种子空间、线性变换、非奇异矩阵都基于通常意义的矩阵乘法也构成李群。 在李群中的映射、变换、度量、划分等都对机器学习中的方法研究有重要意义。 关于这方面的工作，李凡长教授及其李群机器学习研究小组从2 0 0 4 年开始研究， 首次提出了“李群机器学习( l i eg r o u pm a c h i n el e a r n i n g ，简记l m l ) 的概念并建 立了李群机器学习模型及相关学习算法，其目的就是基于月d 上的一个给定的被观测 数据集合，用李群中的可微性把被观测数据集合的非线性结构进行线性化，使其约简 成易于理解、表示和处理的线性数据，然后通过局域李代数和李群之间的一一对应关 系映射到观测空间中去。从目前取得的成果看，其基础理论主要来源于两个方面：一 方面是李群机器学习继承了流形学习的优点，另一方面是李群机器学习充分利用了李 群的代数结构和几何结构的数学本质。 李群机器学习从产生至今，已在文本分类、人群分类、晶体辅助分类系统、人脸 识别和药物分子对接等机器学习的应用领域取得了一些成功的应用，并引起了广大研 究者们的兴趣。现就相关成果综述如下：文献 2 7 3 3 首先提出了李群机器学习概念及 其公理系统，内容包括：1 ) 一致性假设公理；2 ) 划分独立性假设公理；3 ) 对偶性 假设公理；4 ) 泛化假设公理；文献 3 4 1 给出了李群机器学习的左作用模型，右作用 模型，代数模型，几何模型，以及d y n k i n 图几何算法，基于s o ( 3 ) 群分类器算法，并 将其成功应用于文本分类和晶体辅助系统分类；文献 3 5 】给出了李群机器学习中偏序 集及格的定义，提出了李群机器学习子空间轨道生成格的概念及轨道生成的广度优 先、深度优先和轨道生成启发式学习算法，并将其应用于葡萄酒化学成分数据集的分 类；文献 3 6 】给出了李群机器学习中的辛群分类器研究，并将其应用于人脸识别：文 献 3 7 提出了李群机器学习中量子群分类器的设计，给出了基于量子群生成元的分子 匹配算法和基于量子群同构的药效团检索算法，并将其应用于d n a 序列的分类和药 物设计的分子对接中；文献【3 8 】给出了基于纤维丛的机器学习算法，并将其应用于非 线性降维；文献【3 9 】提出了基于李群的半监督学习算法，并将其用于药物活性预测； 文献【4 0 给出了种同调的边缘学习算法，并将其应用于晶体结构的预测和分类；文 1 0 一种基于李群的半监督学习算法及应用研究 第一章引言 献 4 1 1 给出了基于李群的覆盖算法，并将其应用于药物分子对接设计中。 基于此，本文将李群引入到半监督学习方法中，提出“一种基于李群的半监督学 习算法及应用研究 的硕士论文课题。 1 3 研究目标及内容安排 鉴于目前半监督学习和李群机器学习的研究现状，本文将李群理论引入到半监督 学习当中，利用李群良好的代数结构和几何结构来表示和分析数据，给出了一种基于 李群的半监督学习算法。 本文的研究内容分为七章： 第一章主要介绍半监督学习研究现状，分析相关算法。 第二章介绍李群相关理论以及线性李群、参数李群的基础知识。 第三章给出了基于李群代数结构和几何结构的半监督学习模型。 第四章给出了基于线性李群的半监督学习算法及应用。 第五章给出了基于参数李群的半监督学习算法及应用。 第六章针对药物毒性预测实例，给出了基于李群半监督学习的药物毒性预测模拟 系统。 第七章是论文总结和展望。 第二章相关理论基础 一种基于李群的半监督学习算法及应用研究 第二章相关理论基础 李群是与拓扑群和微分几何有着密切联系的一个数学分支。本章主要介绍了李群 理论的基本知识，以及两类特殊的李群线性李群和参数李群的相关背景知识。 2 1 李群 2 1 1 李群概念 李群( l i eg r o u p ) 是挪威数学家李( m a r i u ss h o p h u sl i e ) 在1 8 4 7 年创建的一门数学 理论。李群是一类重要的微分流形，同时，它也是一个群，并且群运算是光滑的。也 就是说，李群是代数和几何的自然结合体，具有丰富的内在理论【2 6 】。 首先，给出李群的具体定义： 定义2 1 李群设g 是一个非空集合，满足： 1 g 是一个群； 2 g 也是一个微分流形； 3 群的运算是可微的，即：由gx g 到g 的映射矽：( g l ，9 2 ) hg i 9 2 是可微的映射，其 中蜀，是g 中任意元素。 则称g 是一个李群( l i eg r o u p ) 。设g 是任意李群，取其单位元e 周围的某一局部坐标 系，根据条件3 有： ( g i 9 2 ) = 矽( g t ，g ；，g ：，g ；) ，= 1 ， ( 2 1 ) 矽是其自变量群，彭( i t = 1 ，2 ，厂) 的解析函数，函数称为李群g 的合成函数，可 简记为( 蜀9 2 ) = 矽声( g 。，9 2 ) 。同时，在李群g 内，g ) 澍g lh 酊1 也是解析的。 从李群的定义可知，李群是群结构与流形结构( 拓扑结构、微分结构) 的有机复合 体，两种结构的有机复合使得李群具有了代数群和流形所不具有的性质，下节所述的 局部生成性是这种复合性质的突出体现，即：一个李群，局部在一定意义上可以决定 整体性质，因此可以用群运算的可微性把群的结构线性化【4 2 喇】。 定义2 2 设g 是一个李群，则对任一g g 称g 到g 的映射： 1 2 一种基于李群的半监督学习算法及应用研究第二章相关理论基础 r g ：x x g ，坛g ( 2 2 ) t ：x g x ，v x g ( 2 3 ) 分别称为g 的左平移和右平移，它们显然都是g 到自身的解析同胚映射，在李群理 论中起着十分重要的作用【2 6 】。 显然下面四个性质成立。 1 ( t ) = t 一- ，( ) = “ 2 t ，r g 以及映射x x 一均是g 的自同胚映射； 3 口幽= t 色- 也是g 的白同胚映射，且坛g ，a c l g ( x ) = g x g ； 4 对任何自然数，z ，映射( 一，x 2 ，) 一_ 毛 是g 兰g 琶：兰g 到g 的连续映射。 定义2 3 李群作用设m 是一个流形，g 是一个李群，g 在m 上的作用人是一 个光滑映射，人：g m 专m 满足： a ( e ，x ) = x ，v x m ，e 为g 的单位元 ( 2 4 ) a ( 9 1 9 2 ，x ) = 人( 蜀，a ( 9 2 ，x ) ) ，v g l ，9 2 g ，v x m ( 2 5 ) 特别，如果觇，x 2 m ，3 9 g ，使得从a ( g ，五) = x 2 那么g 称为可迁的李群作用。 定义2 3 表明人，为m 上的恒等变换人。= 人。o 人，即存在着李群和这样定义 5 1 5 25 l5 2 的变换群之间的同态，于是得到李群作用的一个等价定义， 人：g _ d 矽( m ( 2 6 ) g 专a g 其中d i f f ( m ) 表示m 上的微分同胚群。 李群在微分方程中的作用是非常重要的，李群作用使得李群对应于微分流形上的 变换群，具体来说，v g g ，可以定义m 上的一个变换， 人g ( x ) = a ( g ，x ) ，v x m ( 2 7 ) 2 1 2 李代数 以d 1 ( g ) 表示解析向量场集合，d j ( g ) 表示解析一次微分形式集合。 第二章相关理论基础 一种基于李群的半监督学习算法及应用研究 定义2 4 输入数据g 构成李群，向量场x d 1 ( g ) 称为左不变向量场，如果 v g g 有 心( x ) = z ( 2 8 ) 设x ，y d 1 ( g ) 都是左不变向量场，定义换位运算 ，y 】_ xo y - y o x ( 2 9 ) 则 x ，】，】也是左不变的( 。表示映射的合成) 4 5 】。 定理2 1 1 输入数据g 构成李群，李群g 的所有左不变向量场的集合对所有定义的换位运算 来说构成李代数，称为李群g 的李代数目。 2 李群g 的李代数与g 在p 处的切空间z g 在映射 x 专x ic = x e ，x 日 下是同构的线性空间，因而d i mg = d i mg ，因此可在疋g 中定义换位运算为： 【托，匕】= i x ，y l 。，呱，匕l g ( 其中，x ，y 是左不变向量场，在e 处的值分别为 t ，艺，l g 为与同构的李代数) 。可理解为左不变向量场同构的李代数，也可 以理解为单位元素e 的切空间疋g 同构的李代数。 定义2 5 李代数作用设g 是一个李代数，m 是一微分流形，在m 上的作用是 一光滑映射元：g x m m ，满足： 1 五( 0 ，p ) = p ，跏m 2 v y 日，利用这个光滑映射，可以构造m 上的一个向量场 ( 允似p ) = 知( 缈，p ) ，跏m 其中元表示日和m 上所有向量场构成的集合z ( m ) 之间的对应，要求 元 ，y 】= - - a ，元y 】 满足上面两个条件的名称为李代数作用。 李群作用和李代数作用有密切的关系，主要用到下面两个结论： 定理2 2 如果人：g m 专m 是一个李群作用，那么 o r ：g m 专m ( 2 1 0 ) 1 4 一种基于李群的半监督学习算法及应用研究第二章相关理论基础 a ( v ，p ) = a ( e x p ( v ) ，p ) ( 2 1 1 ) 为一李代数作用。 定理2 3 给定一个李代数作用名：g x m _ m ，那么在一个李群g 上，它的李代数 日，以及一个李群作用人：g x m 专m ，满足： 五( y ，p ) = a ( e x p ( v ) ，p ) ( 2 1 2 ) 其中y 属于单位元的一个邻域。 2 1 3 李群的生成元 李群的生成元，即无穷小变换，表征李群的无穷小特征，也就是说表征单位元 附近的群的性质，从无穷小群着手可以研究李群的局域性质。在邻域中的每一点都 代表一个群元素。设邻域，中有v g ( a ) ，g ( p ) g ，且g ( t z ) g ( f 1 ) 属于邻域，。现研究， 中群结构。 ( 一) 无穷小群生成元 设v g ( a ) ，g ( p ) i ，且i 口| 1 。对g ( a ) 、g ( p ) 作泰勒展开，保留线性项， g ( 口) = g ( o ) + k + 一5 1 ( 2 1 3 ) g ( ) = g ( o ) + 以以+ a = l 冥中设有： 以- ( 掣0 ， 亿 称为李群g 的无穷小生成元，亦为n x 挖矩阵。一般r 维李群有，个无穷小群生成元【2 4 1 。 由于确定群元的参数化条件不同，x