（计算机应用技术专业论文）李群机器学习的覆盖算法及其应用研究.pdf

李群机器学习的覆盖算法及其应用研究 中文摘要 中文摘要 李群机器学习( l m l ) 既继承了流形学习的优点，又充分利用了李群的代数结构 和几何结构的数学本质，自提出以来就引起了许多研究者的关注。本文是在李群机器 学习的理论框架上，以李群机器学习的代数模型、几何模型、公理系统为基础作迸一 步研究，给出了李群机器学习覆盖算法，并将李群机器学习引入到药物分子设计领域， 应用在药物构效关系模型和分子对接模型中，通过实例应用为提出的新算法找到了应 用背景。 。 由此可以看出，本文的特色主要体现在以下几个方面： 1 给出了李群机器学习中群的线性表示、覆盖群等相关理论； 2 给出了李群机器学习覆盖算法，包括单连通覆盖算法、通用覆盖群求解算法 和多连通覆盖算法； 3 给出了覆盖算法在计算机辅助药物分子设计的应用，包括构效关系模型、药 物分子对接。 关键词：李群机器学习；覆盖群；单连通覆盖算法；多连通覆盖算法。 本文的研究得到国家自然科学基金项目( 6 0 7 7 5 0 4 5 ) 的支持。 i 作者：管文文 指导老师：李凡长( 教授) r e s e a r c ho fc o v e r i n ga l g o r i t h mi nl i eg r o u pm a c h i n el e a r n i n g a b s t r a c t l i eg r o u pm a c h i n el e a r n i n g ( l m l ) i n h e r i tt h ea d v a n t a g e so fm a n i f o l dl e a r n i n g m e t h o da n dm a k ef u l lu s eo ft h el i eg r o u p ss t r u c t u r eo fa l g e b r a i ca n dg e o m e t r yi n m a t h e m a t i c s s i n c ei tp r o p o s e d ，l i eg r o u pm a c h i n el e a r n i n gm e t h o dh a sb e e nc a u s e dt h e s p e c i c a lc o n c e m i n gb ym a n yr e s e a r c h e r s t h i sp a p e ri sb a s e do nt h et h e o r yo fl i eg r o u p m a c h i n el e a r n i n g ( l m l ) ，i tc o m b i n e sa l g e b r am o d e la n dt h eg e o m e t r ym o d e li nl i eg r o u p m a c h i n el e a r n i n ga n df r o mt h er e s e a r c hw ec o n c l u d et h ec o v e ra r i t h m e t i co fl i eg r o u p m a c h i n el e a r n i n g w ea l s oi n d u c tt h el i eg r o u pm a c h i n el e a r n i n gt ot h ed r u gm o l e c u l e d e s i g n ，i n c l u d i n gt h ea p p l i c a t i o no fd r u ge f f e c t i v em o d e la n dm o l e c u l ec o n n e c tm o d e l t h r o u g ht h e s ee x a n a p l e s ，w eg e tt h ea p p l i c a t i o nb a c k g r o u n do fo u rn e wa l g o r i t h m s a b o v e a l l ，t h em a i nc h a r a c t e r i s t i c so ft h i sp a p e ra r ea sf o l l o w s ： 1 t h et h e o r yo fl i n e a rr e p r e s e n t a t i o n so fg r o u p ，c o v e t i n gg r o u pi nl m la r eg i v e n 2 t h ec o v e r i n ga l g o r i t h mo fl m li sg i v e n ，i n c l u d i n gs i m p l yc o n n e c t e dc o v e t i n g a l g o r i t h m ，t h es o l m i o no fu n i v e r s a lc o v e r i n gg r o u p ，m u l t i p l yc o n n e c t e dc o v e r i n g a l g o r i t h m 3 t h ea p p l i c a t i o no fc o m p u t e ra i d e dd r u gm o l e c u l a rd e s i g nb a s e do nc o v e r i n g a l g o r i t h m s a r e g i v e n ，i n c l u d i n g t h em o d e lo f q u a n t i t a t i v es t r u c t u r e a c t i v i t y r e l a t i o n s h i p sa n dd r u gm o l e c u l a rd o c k i n gm e t h o d s k e y w o r d s ：l i eg r o u pm a c h i n el e a r n i n g ；c o v e r i n gg r o u p ；s i m p l yc o n n e c t e dc o v e r a l g o r i t h m ；m u l t i p l yc o n n e c t e dc o v e r i n ga l g o r i t h m w r i t t e nb y ：w e n w e ng u a n s u p e r v i s e db y ：f a n z h a n gl i s u p p o r t e db yn a t i o n a ln a t u r es c i e n c ef o u n d a t i o no fe r c h i n a ( 6 0 7 7 5 0 4 5 ) 1 1 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创，l 生声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：磕童垒 日 期：垒2 ：垒三 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 ，髫， 研究生签名： 丝墨圣 日 期： 竺罩：垦：圭 导师签 李群机器学习的覆盖算法及其应用研究 第一章引言 第一章引言 1 1 李群机器学习的研究现状 李群机器学习( l i eg r o u pm a c h i n el e a m i n g ，简记为l m l ) 的目的就是基于尺d 上 的一个给定的被观测数据集合，用群的可微性把被观测数据群的非线性结构进行线性 化，使其约简成易于理解、表示和处理的线性数据，然后通过局域李代数和李群之间 的一一对应关系映射到观测空间中去恢复数据的真实性【l 】。 李凡长教授领导的李群机器学习研究小组从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 ) 的概念，并建立 了李群机器学习模型及相关学习算法，从目前取得的成果看，其基础理论主要来源于 两个方面：一方面是李群机器学习继承了流形学习的优点，另一方面是李群机器学习 充分利用了李群的代数结构和几何结构的数学本质。 李群机器学习从产生至今，已在文本分类、人群分类、晶体辅助分类系统、葡萄 酒化学成分分析、分子对接、药效团模型方法等机器学习的应用领域成功地进行了一 些应用，现就相关成果综述如下： 1 1 1 李群机器学习的公理系统 h u a nx u 和f a n z h a n gl i 2 】首先提出了李群机器学习中的公理系统，内容包括： 1 ) 一致性假设公理； 2 ) 划分独立性假设公理； 3 ) 对偶性假设公理； 4 ) 泛化假设公理。 根据李群机器学习的定义，一致性假设公理主要研究g ( 观测空间) 和m ( 样本 空间) 。划分独立性假设公理就是研究将样本集m 放到 维空间，寻找等价关系，使 得问题决定的不同对象划分在不相交的区域内或将胛维非线性问题映射成线性问题， 形成可解的线性结构；对偶假设公理主要研究观测空间g 和样本空间m 之间的对偶 关系；泛化假设公理则主要研究从样本集合m 中建立观测集g 的模型，泛化能力就 第一章引言李群机器学习的覆盖算法及其应用研究 是对模型g 为真程度的指标。 从机器学习的发展历史看，早期机器学习的研究主要集中在划分假设的研究上， 而近期机器学习的研究则主要考虑划分假设和泛化能力，对一致性假设的考虑不多。 李群机器学习则包含了上述4 种假设，其学习范式能考虑这几个方面的假设就是因为 有李群理论的支持，这正充分体现了数学工具在机器学习领域中的重要作用，同时也 是李群机器学习方法和其他机器学习方法的主要区别之一。 1 1 2 李群机器学习模型 近年来，几何结构学习引起了研究者的强烈兴趣，微分几何和线性代数在获取这 种结构中起了一定的作用。李群是一个把代数结构和几何结构融为一体的数学工具， 根据李群的数学本质，任何一个李群( 非线性结构) 都可以找到一个李代数( 线性结 构) 和它对应，这样就可以将机器学习面对的高维数据、非线性数据等通过李群和李 代数之间的关系来进行数据约简。2 0 0 5 年，f a n z h a n gl i 和h u a nx u 3 。5 1 基于李群、单 参数子群、李代数等这些李群理论中的基本概念和相关定理，将李群引入到机器学习 中去，提出了李群机器学习的概念及李群机器学习模型。在介绍李群机器学习之前， 首先了解一下李群： 设g 是一个非空集合，满足： 1 ) g 是一个群； 2 )g 也是一个微分流形； 3 ) 群的运算是可微的，即：由g x g 到g 的映射0 。，g ：) hg 。g ；1 是可微 的映射。 则称g 是一个李群( l i eg r o u p ) 。 从李群的定义，可以看出：李群既是一个群，也是一个微分流形。从一般定义上 讲，流形就是点、线、面以及各种高维连续空间概念的推广，而我们的所有观察数据 都是可以和点、线、面等结构建立起对应关系的。也就是说，李群可以用来表示现实 世界中的高维数据。 根据李群的定义，作者给出了李群机器学习( l m l ) 的定义： 令g 表示输入空间，m 表示输出域，且有g r d ，m 尺d ，d d ，借用 2 李群机器学习的覆盖算法及其应用研究 第一章引言 李群的定义将g 对m 的左作用用如f 映射矽表不： c , o ：g m 争m ， g ，x 专缈q ，x ) ， 其中，缈( g 。，妒( g ：，x ) ) = 缈悖，g ：，x ) ，缈0 ，x ) = x 。 于是对任意g g ，m 上存在微分同胚变换： 9 9 ：mj m ， x 专妒( g ，x ) ， 且映射集合移。，g g 满足：唿。哝：= 哝1 9 2 ，纯= i d m 。 由此，可得李群机器学习框图：如图1 1 。 图1 1 李群机器学习左作用模型 类似可定义群g 对m 的右作用： ：m gj m ， x ，g 寸妙g ，g ) ， 其中，少 g ，g 。) ，g ：) = ( x ，g ，g ：) ，妙b ，p ) = x 。 李群机器学 - j 右作用框图见图1 2 。 m 第一章引言李群机器学习的覆盖算法及其应用研究 m 图1 2 李群机器学习右作用模型 易看出g 对m 右作用对应的微分同胚变换： 少，：m m ， x 专0 ，g ) 。 由于李群是一个具有群结构的解析流形，而且群运算是解析的。利用这种李群机 器学习范式我们可以分析数据的维数、紧致性、连通性、幂零性、子群、陪集、商群、 量子群等。这些基本结构，为设计李群机器学习的算法、分类器奠定了基础。 ( 一) 李群机器学习的代数模型 根据李群机器学习的概念，将李代数、单参数子群、左不变向量场和左不变流形 这四种不同的数学结构定义成自然的一一对应关系，即李代数丝 左不变向量场) 丝 左不变流动) 丝 单参数子群) 。在李群机器学习系统中，对于输入数据集g ，e h 上述 对应关系可得李群机器学习代数模型，如图1 3 所示。 i 单参数子警? 尺一g ) i l 微分 g ， ( 1 ) 、 卜于 l 左不变流动尺g 与g ) 图1 3 李群机器学习代数模型 基于这些数学结构的关系，文中还研究提出了李群机器学习的李代数根系计算模 型，分解模型及分类模型等。 ( 二) 李群机器学习的几何模型 4 李群机器学习的覆盖算法及其应用研究 第一章引言 利用李群的一些几何性质，如平移性、测地线性质等，可以得到李群机器学习的 几何模型。它们将有利于李群机器学习系统中的表示和度量。 i观测集 左平移线性变换d r 。样本点a 的切空间t o ( g ) i 图1 4 李群机器学习几何模型 在此基础上，文献 6 提出了李群机器学习的等距映射算法及李群机器学习的测 地线距离的学习算法。 由此可见，李群机器学习方法是一种代数模型和几何模型融为一体的学习方法， 这也是他和其他学习方法相区别的要点之一：如流形学习只是一种学习几何结构的方 法，而统计机器学习只是一种学习代数结构的方法。 1 1 3 李群机器的线性分类器设计及应用 随着信息时代的到来，机器学习算法遇到的数据种类越来越多，如航天数据、生 物数据和晶体数据等。根据李群机器学习的意义：gxm 专m 。这些特定的观测 数据g 可以构造成相应的典型群来进行处理，而这些典型群都能嵌入在高阶u ( ，z ) 群 中作为子群来进行学习【7 1 。 在具体构造线性分类器的过程中，必须首先描述符合一定条件的事务全部，称为 观测集合，其中的每一个事务称为这个集合的一个元素，其次对给定集合定义一个线 性组合，且集合中任意一组元素的任意线性组合仍是这个集合的元素，则构成线性空 间。 一般来说，线性分类器的构造可分如下步骤： 第一步：将样本集映射到g 这个非空集合上； 第二步：根据g 构造相应的李群结构； 第一章引言李群机器学习的覆盖算法及其应用研究 第三步：将所得的李群作用于所建立的李群机器学习模型中； 第四步：形成相应的分类器； 第五步：实例测试； 第六步：应用。 文献【8 以典型群s o ( n ) 为基础，将问题限定在三维矢量空间上，构造了李群机 器学习的s o ( 3 ) 分类器。在该分类器中，对每一个群元计算其矩阵行列式的值，一组 矩阵行列式为+ 1 ，而另一组矩阵行列式为1 ，从而达到分类的目的。 在传统的文本分类算法中，常常需要度量两个文档之间的相似度，常用的度量 标准有欧几里德距离、向量的夹角余弦等。f a n z h a n gl i 和h u a nx u l 6 i 提出了一种新的 文本分类方法，简称l g c ( l i eg r o u pc l a s s i f i c a t i o n ) 。在该算法中，将文档构成的向量 空间看成是嵌入在一个微分流形当中的，每个文档对应着流形上的点，然后用测地线 距离而非欧氏距离来度量两个文档之间地相似度。将该算法与采用欧氏距离为度量标 准的髓最近邻算法( k 1 州) 分别对文档进行分类，并对查全率和查准率进行比较。 因为李群机器学习分类方法是将样本空间看成是一个微分流形，因此文档向量空间被 看成是弯曲的，这比欧氏空间描述文档集合更能体现出异构、复杂的特性，而测地距 离是欧氏距离的一般化，将它作为度量标准更具一般性和普遍性。实验结果表明l g c 算法提高了文本分类的性能。 众所周知，晶体是固体中非常重要的组成部分，理想晶体中的原子排列具有周 期性，所有晶体结果都用晶格来描述，晶格是一种数学上的抽象，它由数学上的集合 点在空间有规律的做周期性的无限重复分布构成。在物理学中，对于晶体主要是研究 它的宏观物理性质和对称性之间的关系。若把晶体宏观对称中的理想晶形所有对称操 作看成元素，把操作的乘法看成运算，那么这些元素和这一运算如满足群的定义：满 足封闭性、存在单位元、存在逆元、满足结合律，又由相交定理，上述的对称操作都 相交于原点，在任何一个操作矩阵作用下，原点应保持不变，即这些操作组成的群为 三维正交群0 ( 3 ) 的有限子群，它与李群中的正交群有着密切的联系。因此，文献 7 ， 1 0 针对晶体物理学家倍受关注的晶体分类问题，提出了基于李群机器学习的晶体分 类器，根据晶体的基本结构，构造晶体的对称变换群、晶格点群，对晶体可能的1 1 种固有点群，3 2 种点群，7 种晶系，1 4 种布拉菲( b r a v a i s ) 格点，7 3 种简单空间群 6 李群机器学习的覆盖算法及其应用研究 第一章引言 和2 3 0 种空间群，并将机器学习方法引入到晶体分类中，初步实现了基于李群机器学 习的晶体的计算机辅助分类系统，为李群机器学习找到了应用领域。 1 1 4 李群机器学习中偏序集及格 在机器学习中，由于所学习的各类问题之间的特殊性和一般性，恰当地描述和合 理地选择假设空间有着非常重要的意义，李群中关于偏序，学习子空间轨道生成格等 的概念恰恰适用于这个问题，因而陈凤在李群机器学习中给出了李群机器学习空间、 学习子空间、轨道、目标轨道，并引入了偏序集及格的概念【9 】，文中将学习子空间表 示成偏序集的形式。偏序集的最大元素是学习子空间中最一般的点，即具有零描述的 点，这样的点对学习样例不加任何限制，因而可以描述任何事物。偏序集中的极小元 素是学习子空间中最具体的点，即与学习样例对应( 可以将样例本身看成一个具体的 概念) 。于是，考虑到将学习样例集尸规范成偏序，并且根据需要映射到对应的学习 子空间中，从而能与合理的操作算子集合f ( fcg 。) 相对应。 举例来说，在人脸识别中，可以利用眼睛，鼻子，嘴巴等局部特征识别人脸，从 不同的角度来研究这些特征，若从上到下来观测，用它们之间的位置关系高于来 描述偏序，得到：眼睛鼻子嘴巴，反之，从下往上观测，则有嘴巴鼻子眼 睛。当然这些局部特征一般为矩形，从独立个体的观测角度，它们相互之间是离散的， 没有交集，但从邻域的观点来看，其又是连续的，相交的，它们的交集便组成了人脸 这一整体。 在现实世界中，为了能更好的描述所处理的问题，可以将样例数据集尸通过一定 的变换映射到一个新的学习子空间中去。但是各个元素之间的相互关系不会发生改 变，对应于原学习子空间的元素，一方面可将尸看作是由p 生成的新的样例集合， 即对样例集尸所作的轨道划分不会改变其本质特征，从而保证轨道划分的正确性；另 一方面，对于两个同构的样例集p 和尸，可以使用相同的轨道划分方法，从而避免 重复学习。 在李群机器学习中，当将样例集从原高维空间映射到低维空间中时，样例之间局 部的偏序关系不变，要使样例经过映射后仍保持原有的性质和内在的结构关系，文献 1 1 进而提出了李群机器学习中局部有限偏序集上的m o b i u s 函数，利用m 6 b i u s 函数 第一章引言李群机器学习的覆盖算法及其应用研究 来作为学习算法中判断学习过程中各个状态之间关系的参数，若两个状态之间是等价 的则该函数值为1 ，否则为0 。 然而，在李群机器学习中，需要学习的目标函数的复杂度取决于它的表示方式， 学习任务的难度也随之变化。因此，很有必要选择与特定的学习问题匹配的表示，作 者进而提出了李群机器学习中的g a u s s 系数和g a u s s 多项式，将输入空间的样例数据 简单映射到另一个空间，寻找包含了原始属性中必要信息的最小特征集，这对李群机 器学习的计算和泛化性能都有益。 若将学习子空间( 具体的学习问题) 描述成含有若干结点的有向图或树，有向图 中由初始状态到达目标状态的某条通路( 树中始于根结点到达叶子结点的分支) 正是 一种格结构。路径上的结点关系不能任意调换，体现在具体问题中，可理解为待学习 ( 分类) 的样例，在该结点用此操作算子为最佳，即有利于得到最优轨道。为了有效 的生成目标轨道，作者提出了李群机器学习中的格的概念。 同样以人脸识别为例来说明，上述我们将眼睛，鼻子，嘴巴这些局部的特征按照 不同的观测角度描述成两种偏序结构，用矩形区域来表示这些局部特征，它们不可调 换的先后关系就形成了一个格结构，一旦确定了图形的关键点，要从一个局部特征找 到另外的特征需要考虑两者之间的位置关系，如嘴和鼻子的邻域是连通的，可以通过 计算它们的交、并关系，由己知位置的一方来确定另外一方的位置。 1 1 5 李群机器学习中子空间轨道生成格算法 根据独立划分假设公理及一致性假设公理，观测空间集合中的每一个元素都可以 用一组独立实参数来描写，结合李群机器学习的几何模型特点，在李群机器学习空间 的基础上，文献 9 11 提出了李群机器学习子空间轨道生成格的概念及轨道生成的广 度优先、深度优先和轨道生成启发式学习算法。 对于轨道生成，文中从给定的权值( 已知第一层权值) 出发，利用每个已有的权 值作简单的计算，从而创建新的权值即第二层轨道中的所有权值列表，一个普通 的权值对应于长度为2 的样例中的元素列表，重复执行该过程，通过利用下一个低层 的权值和简单计算可以获得任一层次的权值列表。因而，在给定的第一层权值有序的 情况下，整个轨道，或者说整个学习子空间的图就可以通过这种方法生成。但是在此 要考虑两个问题，首先是计算轨道时所需要的存储空间，其次是使用该方法生成下一 李群机器学习的覆盖算法及其应用研究第一章引言 层列表所需要的重复计算的次数。由于对为每个新创建的轨道元素而重复创建的列表 进行简单查找的速度慢，效率低，因此，提出了一种用于决定是否将一个轨道元素添 加到下一个更高层次的权值列表中的方法，轨道的更高层次仅需要局部数据，即新权 值和创建此权值的所用的一个简单计算。这样就解决了重复计算问题并且为生成轨道 提供了一个新的方法，与其一次生成一个层次，找出该层的所有权值，我们可以将轨 道考虑成一棵树且按“深度优先”来进行计算，尽可能到达较深层次轨道中的权值， 并且在回溯到未计算的“分支”之前根据一定的规范来存储某个权值。后面的方法( 轨 道生成深度优先) 用一个堆栈很容易处理，这个堆栈具有成员数的先验范围，也就是 样例集中样例数目，这样就有利于减少存储空间。由于在计算机中很难一次性存储一 个非常大的轨道，这个新的方法一由于其较小的空间需求，可被用于生成轨道结点。 在李群子空间轨道生成格的理论基础上，陈凤进一步提出了轨道生成的广度优 先、深度优先和轨道生成启发式学习算法，并用实例比较了广度优先和深度优先学习 算法的分类正确率和时间消耗，可见两个算法各有利弊，并将启发式学习算法g o 的 分类结果与n b a y e s ，c 4 5 及k - n n 算法的结果比较，从分类正确率来看，g o 算法 的可行性和有效性较高。 1 1 6 李群机器学习中量子群分类器研究 量子群作为经典李群、李代数的基本对称概念的推广，与非交换几何、量子对称 性等密切相关，针对机器学习系统中面对的非交换性和非对称性问题，基于量子群的 基本理论，何书萍提出了李群机器学习中量子群分类器的基本构造方法及相关算法 【1 2 】。同时结合机器学习中的非交换问题，进一步研究提出了量子超平面上的线性变换 学习算法。 要构造量子群分类器，只要利用量子群的j a c o b i 条件分析观测数据的量子群和量 子代数的性质，并将量子群看成量子超平面的线性系统，通过非交换空间上的降维、 线性化等形式对观测数据进行处理，将观测数据的非线性结构约简成线性结构，然后 根据量子群上线性变换学习算法对其进行分类。 量子群上的对称线性变换学习算法q g r o u p l i n e a r 功，描述如下： 9 第一章引言李群机器学习的覆盖算法及其应用研究 1 对x 和y 进行降维处理后，得到告与r ，且他们必须满足关系孝7 7 = - q 。叩孝， f 2 - - - 0 ，r 2 , - - 0 ； 2 对x ，y 和吉，r 分别同时作对称线性变换z ，使得变换后的x ，y 和芎，7 仍 满足关系砂= q y x ，q c 和孝矽= 一q - a 7 7 孝，孝2 = 0 ，r 2 = 0 ； 3 检验对称线性变换z 是否满足k ，7 ，万) 间的关系，若为否，则调整系数q ， 直到找到合格的变换z ，则z 即为所求的对称线性变换。 4 返回线性变换z 。 将量子群的对称线性变换学习算法所得的线性变换作用于所建立的量子群结构 中，便可得到我们所需的经典量子群，再利用量子群分类器的分类算法进行分类，并 训练出合适的分类器。应用此学习算法对d n a 序列进行分类分析，并将分类结果与 s v m 的算法进行比较和分析，取得了明显的效果。 同时给出了基于量子群生成元的分子匹配算法和基于量子群同构的药效团匹配 算法，并应用量子群的学习算法实现了计算机辅助药物分子设计中的分子对接和三维 分子检索，并初步实现了三维分子检索系统，为李群机器学习中的量子群学习方法找 到了广泛的应用背景。 1 1 7 李群机器学习中辛群分类器研究 付会欣在李群机器学习模型以及相关算法的基础上，将辛群引入到李群机器学习 分类器的研究中来【1 3 1 。因为辛群具有2 挖维结构，而根据辛群的张量表示，辛群在学 习过程中，可以利用2 刀维结构的特点，将n 维用作训练样例，其余，z 维用作测试样 例，从而将辛群和学习过程的分类器对应起来。在分类器设计过程中，针对高维数据， 首先利用辛群框架内的降维方法对数据进行降维，降维之后对于待分类的样本，构成 新的辛矩阵，再对这个辛矩阵进行化简求得对应的训练特征，以此作为学习过程训练 样例。最后对待检测样本按同样方式进行处理，利用辛群分类算法得到样例特征，如 果两类特征匹配，则将结果输出。 辛群分类器的设计方法可以分为样本的辛矩阵表示和辛空间下矩阵的化简方法 两步，将样本表示成辛群的张量形式然后给出样本的辛矩阵表示，接下来的重点是对 该辛矩阵进行化简，化简矩阵的辛算法可以描述如下： 李群机器学习的覆盖算法及其应用研究第一章引言 1 将原始序列去均值并归一化为单位方差； 2 根据最小嵌入维数d ，构建轨道矩阵x 和实对称矩阵彳。计算其上三角阵； 3 增加嵌入维数至d ：，构建新的矩阵，并将d ，维的辛几何线性映射为d ，个归一 化的辛主分量，最后获得k 个不同嵌入维数辛几何的平均值； 4 对原始序列的替代数据重复步骤2 、3 ； 5 根据检验统计量来辨认序列的确定性。 其中的替代数据采用迭代幅度调整的付立叶变换方法，将上述辛算法用于辛矩阵 构造过程，化简辛矩阵成为上三角阵，就可以将原始序列变换上三角矩阵。 根据上述步骤可以得出辛群分类器的设计过程。文章同时给出了人脸识别过程中 的辛群分类器设计和数据集分类过程中的辛群分类器设计，并结合设计步骤，给出了 相应的分类器算法，同时给出了实例验证。通过对比其他的分类算法可以看出，辛群 分类器算法在分类性能上具有一定的优越性。 1 1 8 基于流形学习的纤维丛学习算法研究 张炯【1 4 l 将纤维丛理论引入流形学习中，建立了纤维丛学习模型，给出了流形学习 下的纤维丛表示和基本概念，以及切丛模型和主纤维丛模型；给出了基于切丛局部主 方向的向量场降维算法和基于切丛联络的主曲线构建算法。 文中基于切空间的主曲线构建算法主要思想如下： s t e p1 使用k 个球形邻域 纵h ，61 ) ，q k ( 坨，62 ) ，玖( k ，60 覆盖样本数据； s t e p2 对每一个邻域q k ( 九f ，6 山f = 1 ，2 ，k 内数据点x i l ，x 1 2 ，x 加计算e 缸) ， c o v k , ( x ) 及其特征向量毛七产( 毛f 1 ，毛z 2 ，毛f ) ； s t e p3 令毛k t = m i n 毛r ( k _ 1 ) t ，毛咖 ，m = 1 ，2 ，其中毛( k - 1 ) f 为q ( 缸爪h8 ，) 内数据点协 方差矩阵的主特征向量，并且g ( k ，8 ，) 包含于g ( h6 ，) ，计算甄( 九f ，6f ) ，i = 1 ，2 ，k 内数据点轴在毛蔚上的投影，及局部重构向量x i k ； s t e p4 连接x 腩，应用样条函数或局部光滑化方法近似光滑的主曲线； s t e p5 计算全局重构误差g m s e t ，如果g m s e k - g m s e k 1 小于某个阈值，则停止 迭代。否则令k = k + l ，转s t e p l 。 该算法将数据集分割成球形邻域的开覆盖，在邻域上构造切空间来拟合主曲线， 第一章引言李群机器学习的覆盖算法及其应用研究 并且通过不断细分数据集在极限意义下构建主曲线。 文章通过对纤维丛学习模型进行了深入研究，利用纤维丛这一工具进一步分析处 理流形及其切丛结构，并将纤维丛学习算法在模式识别中进行了有效的应用。 1 2 问题提出及意义 假设y = f ( x ) 是问题世界的模型，z = n ( x ) 是观测环境噪音，样本集是在噪音环境下， 经过有限次观察，从问题世界获得的一组观测数据，记为s ( z ， x k ，y k ) ) 。它是问题世界 所有可能观测数据的一个子集。关于李群机器学习的一致性假设公理，我们通过对样 本集的分析，可以部分地还原问题世界。数学中已经证明，当李群g 的群空间是多 连通时，则一定存在另一个群空间是单连通的简单李群，它与原李群g 之间有多一 对应的同态关系，称之为李群g 的覆盖群。覆盖群和李群之间存在着局域同构的关 系，可以同构地表示原李群的性质，这恰好对应着学习问题，通过对样本集的学习， 可以部分地还原问题世界，从而解决真实问题。 可以利用李群特殊的代数几何结构，对样本数据进行有效表示。样本构成的特征 空间是嵌入在一个微分流形中，构成一个李群。通过对李群性质的分析，得知李群的 性质与其群空间的连通度有密切关系，当李群的群空间是多连通的时候，则该群的真 实表示是多值表示。而在学习过程中，直接对多值表示问题进行分析时，往往是困难 的，所以我们把李群问题转化其覆盖群上进行求解，利用李群和覆盖群之间的同构关 系，可以有效地解决这一难题。覆盖的思想主要是把同类问题进行覆盖，从而把不同 类问题分割开来，这样做的好处是很明显的，通过对同类样本进行学习，能够得到更 好的学习能力。在对多类问题进行拟合的时候，可以利用李群特殊的代数几何结构， 最大程度地保持问题空间的不变性。本文在李群机器学习的相关理论基础上，根据观 测数据集和样本数据之间形成的内在机制，给出了李群机器学习的覆盖算法。 本文同时将李群机器学习引入到药物设计领域中来，随着计算机技术及计算化 学、分子生物学和药物化学的发展，药物设计进入了理性阶段，理性药物设计是在分 子甚至电子水平上考虑分子结构，它需要有先进的技术支撑，计算机的辅助是理性药 物设计的重要手段。基于分子水平的计算机辅助药物设计( c a d d ) 综合并借助了多 学科的先进技术、方法和成果，为理性药物设计提供了强有力的基本工具和手段。自 从1 9 6 0 年定量构效关系方法提出以来，经过4 0 多年的探索和努力，尤其是到1 9 9 0 1 2 李群机器学习的覆盖算法及其应用研究第一章引言 年以后，随着多种新方法的出现，c a d d 已经发展为一门完善和新兴的研究领域。它 的应用缩短了药物研究与开发的进程，大大提高了药物开发的效率，也为人们研制新 药提供了崭新的思路和成功的希望u 6 j 。 计算机辅助药物分子设计方法都是基于各种分子模拟技术及各种数值统计方法， 其中包括分子力学方法、量子力学方法、蒙特卡罗及分子动力学方法、数值和非数值 优化技术等。这些方法各有特点及局限性，需要取长补短，有时需要结合使用。 但是随着生物信息大规模地迅猛发展，给计算机辅助药物设计提出了新课题和挑 战，需要新的思想的加入，常规的计算机算法虽然仍可以应用于药物设计中，但越来 越不适用于大样本高向量的药物数据分析。西蒙曾给出的学习的定义：学习是系统的 变化，这种变化可使系统做相同工作时更有效。机器学习的目的是期望能从数据中自 动地获得相应的理论，通过采用如推理，模型拟合及从样本中学习，适用于缺乏一般 性的理论“噪声”模式，及大规模海量数据集。因此，机器学习形成了与常规方法互 补的可行的方法。机器学习使得利用计算机从海量的药物分子信息中提取有用知识， 发现知识成为可能。机器学习方法在大样本，多向量的数据分析工作中发挥着日益重 要的作用，而目前大量的分子数据库处理需要计算机能自动识别、标注，以避免即耗 时又花费巨大的人工处理方法。早期的科学方法( 观测和假设) 面对高数据的体积， 快速的数据获取率和客观分析的要求，已经不能仅依赖于人的感知来处理了。因而， 药物分子设计与机器学习相结合也就成了必然。 近年来，随着机器学习技术的发展，已有许多机器学习方法用于药物分子设计中， 如支持向量机( s v m ) 、人工神经网络( a n n ) 、k 近邻、遗传算法等方法。b u r b i d g e 首次将s v m 用于药物设计之后【l ，国内外部分学者开始系统地使用s v m 进行药物 设计研究，例如，n o r i n d e r 等人将单因素优化和变量选择策略与s v m 相结合，成功 建立了4 类目标化合物的构效关系模型，文献 1 8 】中利用支持向量机回归( s v r ) 方法 研究了3 9 个麻醉药毒性的定量构效关系，建立了一个定量构效关系模型。s o n g 等人 将s v m 应用于药物筛选，亦取得了较优的效果【1 9 l 。文献 2 0 中利用b p 神经网络结 合s i r n a 序列的序列组成特征、热力学特征和二级结构特征等影响其活性的各种因 素，来预测s i r n a 的活性。文献【2 1 利用遗传算法，结合多元线性回归和交叉验证方 法，对一系列s c h i f f 碱类核糖核苷酸还原酶抑制剂作了二维定量构效关系的研究，计 算得到了一组效果较好的定量构效关系模型，模型不仅具有良好的回归能力，而且还 第一章引言 李群机器学习的覆盖算法及其应用研究 具有良好的预测能力。w a n g 等人【2 2 】将蒙特卡罗模拟和遗传算法相结合的构象分析方 法进行分子构象的优化。这些学习算法的应用，大大提高了药物分子设计的效果。 根据药物分子结构的自身规律特性，我们自然考虑用群论的观点来考虑分子结构 对称性问题。许多物理化学家已经利用群论来分析分子对称性问题，对称的概念是和 变换密切联系在一起的，所谓结构的对称性就是指它对某种变换保持不变的性质，利 用群的性质可以更加直观有效地解决此类问题【2 3 1 。群论是关于对称的数学。群论能根 据分子结构的对称性质来对分子进行分类，并能对许多分子的性质进行预测。而李群 是在物理化学领域应用最为广泛的群，它有着良好的代数几何性质，是具有群结构的 解析流形，而且群运算是解析的。利用李群机器学习范式我们可以分析数据的维数、 紧致性、连通性、子群、覆盖群等等，这些基本结构可以在药物分子设计中过程中得 到广泛的应用。 综上所述，概括李群机器学习的基本成果，本文做进一步研究，提出“李群机器 学习的覆盖算法及其应用研究”的硕士论文课题。 1 3 研究目标及内容安排 鉴于目前李群机器学习方法还处于初步阶段，还有许多工作需要进一步深入研 究。本文在李群机器学习的一致性假设公理的基础上，根据观测数据集和样本数据之 间形成的内在机制，遵循李群具有的整体性质、局部性质及生成元、简单李群、混合 李群、覆盖群等数学结论具有的数学内涵进行了深入的研究，给出了李群机器学习覆 盖算法，包括单连通覆盖算法和多连通覆盖算法。根据分子结构的特性，并给出在药 物分子设计问题中的应用。既丰富了李群机器学习理论，同时也为数据分析提供了一 种新的机器学习方法。 本文的研究内容分为六章： 第一章主要介绍了李群机器学习的研究背景和研究现状。 第二章介绍李群机器学习中的群表示理论、李群的基本性质和李群的覆盖群的相 关理论。 第三章介绍了李群机器学习的单连通覆盖算法，包括覆盖群判断算法、通用覆盖 群算法、单连通覆盖算法。 第四章给出了李群机器学习的多连通覆盖算法。 1 4 李群机器学习的覆盖算法及其应用研究 第一章引言 第五章给出李群机器学习覆盖算法在分子对接中的应用，对分子对接模型中柔性 对接的相关问题进行了研究。 第六章给出了结论及展望。 第二章李群机器学习覆盖算法的相关理论李群机器学习的覆盖算法及其应用研究 第二章李群机器学习覆盖算法的相关理论 本章主要介绍了李群机器学习覆盖算法的相关理论，包括群的线性表示理论、李 群的基本性质和李群的覆盖群理论，这些知识是研究李群机器学习覆盖算法的理论基 础。 2 1 群的线性表示 群的线性表示理论是群论能在物理和其他领域得到广泛应用的基础。从群论观点 看，两个同构的群，群的性质相同。由于矩阵群比较容易研究，如能找到一个矩阵群 和给定群同构，那么研究清楚此矩阵群的性质，也就完全掌握了给定群的性质。如果 矩阵群只是与给定群同态，那么矩阵群只反映给定群的部分性质，但对研究给定群的 性质也有作用。与给定群同构或同态的矩阵群称为给定群的线性表示。 定义2 1 1 若行列式不为零的m m 矩阵集合构成的群d ( g ) 与给定g 同构或同 态，则d ( g ) 称为g 的一个m 维线性表示，简称表示( r e p r e s e n t a t i o n ) 。在d ( g ) 中，与 g 中元素r 对应的矩阵d ( r ) ，称为元素r 在表示d ( g ) 中的表示矩阵，d ( r ) 的矩阵 迹z ( r ) = t r d ( r ) 称为元素r 在表示d ( g ) 中的特征标( c h a r a c t e r ) 。 规定表示矩阵的行列式不为零，是为了排除表示矩阵与零矩阵直和的平庸情况。 在此规定下，恒元的表示矩阵是单位矩阵，d ( e ) = 1 ，互逆元素的表示矩阵互为逆矩阵， d ( r - 1 ) = d ( 尺) 。若d ( g ) 与群g 同构，则d ( g ) 称为群g 的真实表示，若同态，则称 非真实表示。让群中所有元素都对应1 ，d ( r ) = l ，得到的表示称为恒等表示，也称平 庸表示。 任何群都有恒等表示。矩阵群本身是自己的一个表示，称为自身表示。表示矩阵 都是幺正矩阵的表示称为幺正表示。表示矩阵都是实正交矩阵的表示称为实正交表 示。 在具体寻找群的所有线性表示之前，先要把此问题做适当的简化。 定义2 1 2 如果群g 所有元素r 的两个表示d ( g ) 和d ( g ) 中的表示矩阵存在同一 相似变换关系5 ( r ) = x d ( r ) x ，则这样的两个表示称为等价( e q u i v a l e n t ) 表示，记作 d ( g ) = d ( g ) 。 1 6 李群机器学习的覆盖算法及其应用研究第二章李群机器学习覆盖算法的相关理论 两个等价表示维数相等，相似变换矩阵x 也是同维非奇矩阵，与群元素无关等 价于同一表示的两表示互相等价。等价表示没有实质上的区别，寻找群g 所有表示 的问题简化为寻找群g 所有不等价的表示问题。 如何来判断两表示是否等价? 任意元素在两个等价表示中的特征标相等： z ( r ) = t r d ( r ) = t r d ( r ) = z ( r ) 。 对于有限群，每个元素在两表示中的特征标对应相等，是两表示等价的必要条件。 由于特征标是类的函数，为了检验两表示的等价性，只需要在每个类中选的一个元素， 检验它们在两表示中的特征标是否相等。 定义2 1 3 如果群g 表示d ( g ) 的每一个表示矩阵d ( r ) 都能通过一个相似变换x 化成同一形式的阶梯矩阵 脚蹦= r 固雠，) 。 则此表示称为可约表示，否则称为不可约表示( i r r e d u c i b l e ) 。可以看到上式中两个 子矩阵d 1 ( 尺) 和d 2 ( r ) 的集合分别构成群g 的线性表示。元素在可约表示中的特征 标等于在子表示中的特征标之和 z ( g ) = z 1 ( r ) + z 1 ( r ) 表示d ( g ) 的性质完全由两个子表示的性质表达出来。反过来说，把若干个不可 约表示直和起来，就构成一个已完全约好的可约表示。这样的可约表示没有给出任何 新的性质：它的表示空间是若干个不可约表示的表示空间的直和，空间中的矢量可唯 一地分解为分属各子空间的矢量之和，分别按各不可约表示变换。因此，寻找群所有 不等价表示的问题进一步简化为寻找群的所有不等价不可约表示的问题。 所以我们可以说群