谱图学习(Spectral graph learning)

海南琼州大学在谱图理论发表多篇SCI论文,特别是在多核图谱理论方面做出很多开创性工作,居于世界领先地位。此外,这页简介它还因如周志华教授最近出版的很受热捧的《机器学习》一书说“聚类也许是机器学习中‘新算法’出现最多、最快的领域”,“聚类技术本身在现实任务中非常重要,因此,本章勉强采用了‘列举式’的叙述方式,相较于其他各章给出了更多的算法描述”。这页介绍最近引起广泛关注的一类很有效的谱图聚类-它已成为机器学习的很受重视的一个领域。

谱图聚类是最近引起广泛关注的一类很有效的聚类方法。由于这类方法使用某一矩阵(图)数据的特征向量进行聚类,因而统称为谱聚类算法。

同受教于物理教授却都成为计算机专家的许东的早7届的师兄Buhmann1995年指出:谱聚类算法是一种基于两点间相似关系的方法,这使得该方法适用于非测度空间,算法仅涉及到数据点的数目,因而可以避免由特征向量的过高维数所造成的奇异性问题。谱聚类算法又是一个判别式方法,不用对数据的全局性构作假设,而是首先收集局部信息来表示两点属于同一类的可能性,然后根据某一聚类判据作全局决策,将所有数据点划分到不相关的集合中。谱聚类的思想来源于谱图划分,它将数据聚类问题看成是一个无向图的多路划分问题。数据点可以看成是一个无向图G(V, E)的顶点V,加权边的集合E={Wij}表示基于某一相似度量计算的两点间的相似度。用表示待聚类数据点间的相似度矩阵,将其看做是该图的邻接矩阵,它包含了聚类所需要的所有信息。然后定义一个图划分判据,最优化这一判据使得同一类内的点具有较高的相似性,而不同类之间的点具有较低的相似性。

由于图划分问题的组合本质,求图划分判据的最优解是一个NP难问题。一个有效的求解方法是考虑问题的连续放松形式,这样可以将原问题转换为求解矩阵的特征值和特征向量问题,从而将这类方法称为聚类方法,有时可以认为谱方法是对图划分判据的逼近。

最早提出的谱图划分判据是简单的最小切(Min-cut)判据。它将连接图划分成两个子图(A, B),使得子图间的连接权值之和,即所谓的切最小:Min-cutA, B)。由于最小切判据仅考虑了外部连接而没有考虑每个聚类内部的连接,也就是没有对各个类进行规模限制,从而容易产生歪斜划分,不适于聚类问题。为了解决这一问题,后来提出的判据都是通过引入不同的平衡条件来获得性能更优的聚类判据:

率切(Ratio-cut)判据:Rcut(A, B)=cut(A, B)/|A| + cut(A, B)/|B|

其中, |A|, |B|表示各类内的结点数目。率切判据通过引入类规模平衡项来最小化类间相似性。

规范切(Normalized-cut)判据:Ncut(A, B)= cut(A, B)/vol(A) + cut(A, B)/vol(B)

其中vol(A)表示A到图中所有顶点权值之和。规范切判据引入容量的概念来规范化类间相关,从而考虑了相对于类内连接强度的类间连接。

最小最大切(Min-Max-cut)判据:MMcut(A, B)= cut(A, B)/ cut(A, A) + cut(A, B)/ cut(B, B)

同时最小化类间连接强度,最大化类间连接强度。

从这三种判据可推广到多路情形的多路划分判据:

多路率切:MRcut(C1, C2, Ck)=åkcut(Ck, G-Ck)/| Ck | ;

多路规范切:MNcut(C1, C2, Ck)= åkcut(Ck, G-Ck)/dk ;

多路最小最大切:MMMcut(C1, C2, Ck)= åkcut(Ck, G-Ck)/ cut(Ck, Ck) … … …

这需要一定基础如这里倒数第3段的归纳逻辑与人工智能”会议及书籍一段所说:我读研究生那时的国内及国外《机器学习》书籍我都有,并所说到的《机器学习》一书第一作者Michalski等的下面3大领域分别和机器学习交互的3本书-当然最好要结合近来人工智能的一些受关注的相关领域攻读才能找到更好的主题方向:即第1本是Michalski的《机器学习与数据挖掘》(关于“数据挖掘”,韩家炜教授的一直跟进更新的那套书是很受欢迎的)。第2本是傅京孙院士1971年主编的《Pattern Recognition and Machine Learning模式识别与机器学习》(关于“模式识别”其开拓者傅京孙院士主编的《模式识别应用》由程民德石青云戴汝为院士边肇祺教授翻译;最近Christopher M. Bishop独著的《Pattern recognition and machine learning模式识别与机器学习;看到边肇祺教授的《模式识别》也已改为这名-我有1988年版其后2000年版前十章一样-后面加神经网络统计学习基础支持向量机代替后几章,最近版好象以深度学习基础替换)。第3本是Simon Haykin独著的《神经网络与机器学习》(前一版1994年出的叫《神经网络》就已有768;关于神经网络在这里有一些介绍),它们也是这些领域较基本的,如此我也有它们。

关于谱图学习及相关领域的重要性,其最近出现就已很热的知识图谱就如中国计算机学会专委会常委公安部徐云峰处长的“智能时代:用知识图谱来学习和理解世界”说“知识图谱是目前最常用的机器学习方法”“机器学习的实质是从大量数据中学到知识(即深度学习),从与环境的不断交互中学到知识(即强化学习),实现对知识进行构建和自动扩展,很大程度上解决了知识表示与自动获取问题。其中的节点代表实体或者概念,的边代表实体/概念之间的各种语义关系,比如说两个实体之间的相似关系。语义网络可以看成是一种用于存储知识的数据结构,即基于的数据结构,其中图可以是向图,也可以是向图”。再如在科技日报中国青年报新华网等可见标题为“知识图谱:预见未来的神器”的第一段说“眼下最‘红’的人工智能和大数据,让身边的一切都变得“聪明”起来,Siri会跟你聊天,汽车能实现无人驾驶,机器人也可以问诊看病。而真正让机器能与人类沟通对话的‘幕后英雄’是知识图谱,”,上面两个领域之名最后一词都是Graph--也即一类广义图论

最近徐云峰又发表广受关注的一文:“应用超算以及人工智能技术实现网络安全智能化”(见这文附他和王靖亚教授等合写的2013年的网络安全,其实徐云峰主撰很多书,如2007年的网络伦理2010年的物理安全2014年的弱点挖掘2014年的访问控制等等)。

除了上面2个涉及图论的领域外,也可参考这页的相关领域以及新近出版的一些涉及图论书籍所属的领域:1、李建中等的(不确定)图数据挖掘;2、朱文武的图表征学习等;3Hamilton的图表示学习等;4、异质图表示学习;5、图机器学习;6、图深度学习;7、图神经网络;8、图深度神经网络等等等(仅涉及图论与机器学习、人工智能交互的领域就已如此甚众,而图论还在其他很多领域更…,那这页说的“图论正吞噬世界,其趋势已无法逆转”,而“图论彻底颠切还如在图数据库看来这并非都是“危言耸听!?!)

也以及参考清华大学张长水教授2007主持的图上的机器学习算法及其应用的研究”等,也可参考一些较综述性的谱图理论博士学位论文:如全国优秀博士学位论文提名论文--基于谱图理论的人脸表情识别算法研究”,大连理工侯海燕教授的“基于知识图谱的科学计量学进展研究”,“基于谱图理论的强化学习研究”,“基于图的半监督学习及其应用研究”,“Web信息网络社区挖掘的关键技术研究”,“图上的传播学习研究及应用”,“谱图理论支持下的高分辨率遥感影像多尺度分割研究”,“图谱理论在齿轮箱故障诊断中的应用研究”,等等。

附:关于谱图学习,刚见到2016年机器学习国际会议网站-它一共有4个大会邀请演讲,而下面在网上所搜见的“耶鲁大学教授讲授图像识别算法”和“耶鲁大学博士演讲:拉普拉斯矩阵图像的算法和应用”,它俩其实演讲的题目都是“Laplacian Matrices of Graphs: Algorithms and Applications图的拉普拉斯矩阵学习:算法和应用”,即这就是2016年机器学习国际会议4个大会邀请演讲之一,演讲者是信息科学诺贝尔奖奈望林纳奖得主Daniel Spielman(其实,2016年机器学习国际会议4个大会邀请演讲中还有一个演讲题目是“Mining Large Graphs: Patterns, Anomalies, and Fraud Detection并看这Mining Large Graphs”全文见它讲的也同样是完全就是图论)。这会议是“机器学习”最重要的会议,而广泛共识是机器学习是人工智能的核心,那这年人工智能的一半核心就是图论(还如Daniel Spielman的博士Kelner的博士Madry建立值得信赖的人工智能--Madry的博士论文是“From Graphs to Matrices, and Back: New Techniques for Graph Algorithms从图论到矩阵,再回到:图论算法的新技术-正是图论的;还可见图论神经网络也许是人工智能的未来

这页就主要简述图谱论(上面是这领域的其中的图的拉普拉斯谱论),它也算是图论的一个领域,而下面见信息科学的全部诺贝尔奖得主全都做图论,其与信息科学和计算机的关系也可见这里。关于谱图论的作用在被认为是将统治世界的当今最疯狂全球最火热的人工智能的核心学科看到第1个是谱图学习领域,谱图论的作用也如加拿大几年就投入百亿元的海底观测网的节点大多就铺设超过千米的深海底--而应用谱图论的电力和通信系统可靠性是海网的核心工程,海网也已是国务院制定的今后20中国第一科技基础设施,而我国只有南中国海的深度常达5千米-我国的渤海黄海东海的平均深度分别仅是十几、几十和近百米。也因海网不仅需要谱图论更主要研究电路与系统的可靠性如此中国唯一深海之滨的海南琼州大学也和1998年当选IEEE电路与系统学会主席、欧洲科学院院士并写的3本书全都是图论Thulasiraman教授合作多篇SCI论文(Thulasiraman的世界领导性如最近出版他任主编--Elsevier的杂志主编、德国Andreas Brandstädt(《离散应用数学》杂志的纪念他的文集有主编Endre Boros院士等大师写的文章)Tako Nishizeki大师仅任编辑的1214的图论、组合优化与算法巨著《Handbook of Graph Theory, Combinatorial Optimization, and Algorithms》,又如1992编写第二版的包含几乎所有科学领域的《Encyclopedia of Physical Science and Technology物理科学与技术百科全书》的“Circuit Theory电路理论”就是他独立撰写。就因和多个世界大师合作如此我们海南琼大的工作受到相关专家关注:如余桂东校长的博士学位论文一共有113篇参考文献但只有引用1中文论文(即只引用我们海南省三亚市琼州学院陈德钦院长的中文论文和2本书是美籍大师李文卿及中科大人都尊称为“乔公”的--这中文的1篇论文2本书是参考文献第111112113)也即余桂东校长的博士学位论文是做和海南琼大陈德钦书记的相关的‘哈密顿图的拉普拉斯谱’的(并她一个年轻小女孩刚当校长就在省中心的合肥市为一个很不起眼的小学校拿到用地面积约425、总投资约19亿元的新校区)。当然象“电路与系统”的书我也看如海南琼大师爷Robert Lee Moore的博士Kline的博士Papoulis的《电路与系统:现代方法》中文版和英文版我都有(这里还见他的2本书还成为中国第一本海洋研究生用书最先参考的2)。其实我的导师柳柏濂教授的中国“第一本”研究生用书《组合矩阵论》首版578页的第一章从第1页到这章最后段都讲谱图论基础-这也是为其后各章打下基础-如最后章的最后几节就以谱图论结束全书!这是国内第一本最全面讲图谱论的书--所以得感谢我的导师20多年来我也评审许多谱图论的论文,如这方面的著名的SCI杂志AAECC的主编Marc Giusti教授就邀请我评审编号为1437的下面论文这是因前个世纪90年代初我成为邻域并复圈结构图世界第一领军专家起就一直担任过这领域投去SCI杂志的很多论文审稿人。虽有Brouwer\Haemers\Cvetkovic等的书,但多次排名世界第一的加州理工学院等权威大师的国外第一本《组合矩阵论》著作在1991年才正式出版,而我的这导师1986年在美国起就着手写上面《组合矩阵论》专著并如1990年就已有3千页油刻印版给当时的我们来研读并其后成为中国1教育部批准的全国数学“研究生教学用书”)。用“图的谱”或“图的拉普拉斯谱”在论文网上搜索--可知最早的博士论文是我导师柳柏濂教授指导的和中国第一个国际主席李学良指导的博士论文如“图的谱性质的研究”等,当然这里和我导师合作的李乔和邵嘉裕也是贡献很大的开拓者,其后是来信评价推荐海南琼大得到中国科技界全面肯定的课题的工作为海南最高奖的上海市学位办主任束金龙教授指导的博士论文是中国最多的如刘瑞芳的图的拉普拉斯谱半径、于广龙的组合矩阵论中图谱、林辉球的图的邻接谱和距离谱、翟明清的图的结构参数与特征值、吴雅容的图的特征值和陈影影的图的距离谱和距离拉普拉斯谱等都是束金龙教授独立指导的-似是至今指导谱图论博士最多的 

谱图论的重要作用也可参考信息科学桂冠--内万林纳奖第八内万林纳(Nevanlinna)奖获得者美国国家科学院院士上面开头在ICML做报告的耶鲁大学Daniel Spielman教授的2004年写并其后多次修改《谱图理论及其应用》及参考Fan Chung院士的《复图和网络》等。注:第一个获得最高奖的化学大师都旗帜鲜明地摇旗呐喊:21世纪是信息科学起火车头作用带动所有科学的世纪,而这信息科学奖4才颁发给1,足见堪比诺贝尔奖之珍贵。这Daniel Spielman图论博士Jonathan A. Kelner2011年刚毕业的上面已说的图论博士Aleksander Madry刚在去年国际数学家大会45分钟邀请报告-毕业才几年啊(这Aleksander Madry另一导师的做Disjoint Paths(最长的是哈密顿路)博士Jon Kleinberg在比上面Daniel Spielman更早的第七届获得称为数学界诺贝尔奖的这Nevanlinna-并他和这里第1段说同是美国三院院士的合写《算法设计》)。此外,Spielman还获得50万美元天才奖--他的上面提过的图论博士Kelner也做得很不错-其哈佛本科毕业时是1600人中2个获得未来最杰出科学家奖的,这领域也可参考金院士撰写的谱图论》以及新近发展的图神经网络学习