转自MIT牛人林达华的 “图˙谱˙马尔可夫过程˙聚类结构 ”————经典、透彻

本文主要是介绍转自MIT牛人林达华的 “图˙谱˙马尔可夫过程˙聚类结构 ”————经典、透彻,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目中所说到的四个词语,都是MachineLearning以及相关领域中热门的研究课题。表面看属于不同的topic,实际上则是看待同一个问题的不同角度。不少文章论述了它们之间的一些联系,让大家看到了这个世界的奇妙。

从图说起

这里面,最简单的一个概念就是”(Graph),它用于表示事物之间的相互联系。每个图有一批节点(Node),每个节点表示一个对象,通过一些边(Edge)把这些点连在一起,表示它们之间的关系。就这么一个简单的概念,它对学术发展的意义可以说是无可估量的。几乎所有领域研究的东西,都是存在相互联系的,通过图,这些联系都具有了一个统一,灵活,而又强大的数学抽象。因此,很多领域的学者都对图有着深入探讨,而且某个领域关于图的研究成果,可以被其它领域借鉴。

矩阵表示:让代数进入图的世界

在数学上,一种被普遍使用的表达就是邻接矩阵(AdjacencyMatrix)。一个有N个节点的图,可以用一个Nx N的矩阵G表示,G(i,j)用一个值表示第i个节点和第j个节点的联系,通常来说这个值越大它们关系越密切,这个值为0表示它们不存在直接联系。这个表达,很直接,但是非常重要,因为它把数学上两个非常根本的概念联系在一起:”(Graph)矩阵”(Matrix)。矩阵是代数学中最重要的概念,给了图一个矩阵表达,就建立了用代数方法研究图的途径。数学家们几十年前开始就看到了这一点,并且开创了数学上一个重要的分支——代数图论(AlgebraicGraph Theory)

代数图论通过图的矩阵表达来研究图。熟悉线性代数的朋友知道,代数中一个很重要的概念叫做”(Spectrum)。一个矩阵的很多特性和它的谱结构——就是它的特征值和特征向量是密切相关的。因此,当我们获得一个图的矩阵表达之后,就可以通过研究这个矩阵的谱结构来研究图的特性。通常,我们会分析一个图的邻接矩阵(AdjacencyMatrix)或者拉普拉斯矩阵(LaplaceMatrix)的谱——这里多说一句,这两种矩阵的谱结构刚好是对称的。

谱:分而治之的代数

谱,这个词汇似乎在不少地方出现过,比如我们可能更多听说的频谱,光谱,等等。究竟什么叫呢?它的概念其实并不神秘,简单地说,谱这个概念来自分而治之的策略。一个复杂的东西不好直接研究,就把它分解成简单的分量。如果我们把一个东西看成是一些分量叠加而成,那么这些分量以及它们各自所占的比例,就叫这个东西的谱。所谓频谱,就是把一个信号分解成多个频率单一的分量。

矩阵的谱,就是它的特征值和特征向量,普通的线性代数课本会告诉你定义:如果Av = c v,那么c就是A的特征值,v就叫特征向量。这仅仅是数学家发明的一种数学游戏么?——也许有些人刚学这个的时候,并一定能深入理解这么个公式代表什么。其实,这里的谱,还是代表了一种分量结构,它为使用分而治之策略来研究矩阵的作用打开了一个重要途径。这里我们可以把矩阵理解为一个操作(operator),它的作用就是把一个向量变成另外一个向量:y= A x。对于某些向量,矩阵对它的作用很简单,Av = cv,相当于就把这个向量v拉长了c倍。我们把这种和矩阵A能如此密切配合的向量v1,v2, ... 叫做特征向量,这个倍数c1,c2, ...叫特征值。那么来了一个新的向量x的时候,我们就可以把x分解为这些向量的组合,x= a1 v1 + a2 v2 + ...,那么Ax的作用就可以分解了:Ax = A (a1 v1 + a2 v2 + ...) = a1 c1 v1 + a2 c2 v2... 所以,矩阵的谱就是用于分解一个矩阵的作用的。

这里再稍微延伸一点。一个向量可以看成一个关于整数的函数,就是输入i,它返回v(i )。它可以延伸为一个连续函数(一个长度无限不可数的向量,呵呵),相应的矩阵A 变成一个二元连续函数(面积无限大的矩阵)。这时候矩阵乘法中的求和变成了积分。同样的,A的作用可以理解为把一个连续函数映射为另外一个连续函数,这时候A不叫矩阵,通常被称为算子。对于算子,上面的谱分析方法同样适用(从有限到无限,在数学上还需要处理一下,不多说了)——这个就是泛函分析中的一个重要部分——谱论(SpectralTheory)。

马尔可夫过程——从时间的角度理解图

回到这个题目,那么图的谱是干什么的呢?按照上面的理解,似乎是拿来分解一个图的。这里谱的作用还是分治,但是,不是直观的理解为把图的大卸八块,而是把要把在图上运行的过程分解成简单的过程的叠加。如果一个图上每个节点都有一个值,那么在图上运行的过程就是对这些值进行更新的过程。一个简单,大家经常使用的过程,就是马尔可夫过程(MarkovProcess)

学过随机过程的朋友都了解马尔可夫过程。概念很简单——“将来只由现在决定,和过去无关。考虑一个图,图上每个点有一个值,会被不断更新。每个点通过一些边连接到其它一些点上,对于每个点,这些边的值都是正的,和为1。在图上每次更新一个点的值,就是对和它相连接的点的值加权平均。如果图是联通并且非周期(数学上叫各态历经性,ergodicity),那么这个过程最后会收敛到一个唯一稳定的状态(平衡状态)

图上的马尔可夫更新过程,对于很多学科有着非常重要的意义。这种数学抽象,可以用在什么地方呢?(1)Google对搜索结果的评估(PageRank)原理上依赖于这个核心过程,(2)统计中一种广泛运用的采样过程MCMC,其核心就是上述的转移过程,(3)物理上广泛存在的扩散过程(比如热扩散,流体扩散)和上面的过程有很重要的类比,(4)网络中的信息的某些归纳与交换过程和上述过程相同(比如RandomGossiping),还有很多。非常多的实际过程通过某种程度的简化和近似,都可以归结为上述过程。因此,对上面这个核心过程的研究,对于很多现象的理解有重要的意义。各个领域的科学家从本领域的角度出发研究这个过程,得出了很多实质上一致的结论,并且很多都落在了图的谱结构的这个关键点上。

图和谱在此联姻

根据上面的定义,我们看到邻接矩阵A其实就是这个马尔可夫过程的转移概率矩阵。我们把各个节点的值放在一起可以得到一个向量v,那么我们就可以获得对这个过程的代数表示,v(t+1)= A v(t)。稳定的时候,v= A v。我们可以看到稳定状态就是A的一个特征向量,特征值就是1。这里谱的概念进来了。我们把A的特征向量都列出来v1,v2, ...,它们有Avi = ci vivi其实就是一种很特殊,但是很简单的状态,对它每进行一轮更新,所有节点的值就变成原来的ci倍。如果0< ci < 1,那么,相当于所有节点的值呈现指数衰减,直到大家都趋近于0

一般情况下,我们开始于一个任意一个状态u,它的更新过程就没那么简单了。我们用谱的方法来分析,把u分解成u= v1 + c2 v2 + c3 v3 + ... (在数学上可以严格证明,对于上述的转移概率矩阵,最大的特征值就是1,这里对应于平衡状态v1,其它的特征状态v2,v3, ..., 对应于特征值1> c2 > c3 > ... > -1)。那么,我们可以看到,当更新进行了t步之后,状态变成u(t)= v1 + c2^t v2 + c3^t v3 + ...,我们看到,除了代表平衡状态的分量保持不变外,其它分量随着t增长而指数衰减,最后,其它整个趋近于平衡状态。

从上面的分析看到,这个过程的收敛速度,其实是和衰减得最慢的那个非平衡分量是密切相关的,它的衰减速度取决于第二大特征值c2c2的大小越接近于1,收敛越慢,越接近于0,收敛越快。这里,我们看到了谱的意义。第一,它帮助把一个图上运行的马尔可夫过程分解为多个简单的字过程的叠加,这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二,它指出平衡状态是对应于最大特征值1的分量,而收敛速度主要取决于第二大特征值。

我们这里知道了第二大特征值c2对于描述这个过程是个至关重要的量,究竟是越大越好,还是越小越好呢?这要看具体解决的问题。如果你要设计一个采样过程或者更新过程,那么就要追求一个小的c2,它一方面提高过程的效率,另外一方面,使得图的结构改变的时候,能及时收敛,从而保证过程的稳定。而对于网络而言,小的c2有利于信息的迅速扩散和传播。

聚类结构——从空间的角度理解图

c2的大小往往取决于图上的聚类结构。如果图上的点分成几组,各自聚成一团,缺乏组与组之间的联系,那么这种结构是很不利于扩散的。在某些情况下,甚至需要O(exp(N))的时间才能收敛。这也符合我们的直观想象,好比两个大水缸,它们中间的只有一根很细的水管相连,那么就需要好长时间才能达到平衡。有兴趣的朋友可以就这个水缸问题推导一下,这个水缸系统的第二大特征值和水管流量与水缸的容积的比例直接相关,随比例增大而下降。

对于这个现象进行推广,数学上有一个重要的模型叫导率模型(Conductance)。具体的公式不说了,大体思想是,节点集之间的导通量和节点集大小的平均比例和第二大特征值之间存在一个单调的上下界关系。导率描述的是图上的节点连接的空间结合,这个模型把第二特征值c2和图的空间聚集结构联系在一起了。

图上的聚类结构越明显,c2越大;反过来说,c2越大,聚类的结构越明显,(c2= 1)时,整个图就断裂成非连通的两块或者多块了。从这个意义上说,c2越大,越容易对这个图上的点进行聚类。机器学习中一个重要课题叫做聚类,近十年来,基于代数图论发展出来的一种新的聚类方法,就是利用了第二大特征值对应的谱结构,这种聚类方法叫做谱聚类(SpectralClustering)。它在ComputerVision里面对应于一种著名的图像分割方法,叫做NormalizedCut。很多工作在使用这种方法。其实这种方法的成功,取决于c2的大小,也就是说取决于我们如何构造出一个利于聚类的图,另外c2的值本身也可以作为衡量聚类质量,或者可聚类性的标志。遗憾的是,在paper里面,使用此方法者众,深入探讨此方法的内在特点者少。

归纳起来

·图是表达事物关系和传递扩散过程的重要数学抽象

·图的矩阵表达提供了使用代数方法研究图的途径

·谱,作为一种重要的代数方法,其意义在于对复杂对象和过程进行分解

·图上的马尔可夫更新过程是很多实际过程的一个重要抽象

·图的谱结构的重要意义在于通过它对马尔可夫更新过程进行分解分析

·图的第一特征值对应于马尔可夫过程的平衡状态,第二特征值刻画了这个过程的收敛速度(采样的效率,扩散和传播速度,网络的稳定程度)。

·图的第二特征分量与节点的聚类结构密切相关。可以通过谱结构来分析图的聚类结构。

马尔可夫过程代表了一种时间结构,聚类结构代表了一种空间结构,把它们联系在一起了,在数学刻画了这种时与空的深刻关系。

MarkovChain在数学上确实可以视为LinearDynamic System的一个特例LinearDynamic System的很多观点其实是可以用于分析Markovprocess的。

Linear System
是一个非常博大的领域,从这个角度去看待Markovprocess是一个很好的角度。LinearSystem关注特征方程的根,并且有很多工作描述了特征根和动态特性的关系。而Markov的第一,第二特征值问题其实是这个大问题的一个重要特例。

Linearcontrol system的设计思想用于设计MarkovChain Monte Carlo,对采样过程施加反馈式的动态控制,应该是在实用中有重要价值的思路。下次见到AlanWillsky的时候,我可以和他交流一下这个问题的看法。

从另外一个角度说,Markov过程本身有一些重要的特点,使得它值得作为一个专门的topic,独立于LinearSystem进行研究。转移概率矩阵(或者转移算子)的谱半径(Spectralradius)1,并且是自伴的(Self-adjoint),这决定了它的全部特征根都是实数,而且都在[-1,1]之间。相比于很多其它领域的线性系统,这是非常特殊的。

对于Vision还有一些AI领域来说,它的Markov过程还有着一些难点:multi-mode& highly peaked. 形象的说,就是巨大的星球之间用一跟细丝来往,而且随着系统的规模加大,第二特征值1gap以几何级数衰减,也就是收敛时间指数增长。这在传统线性动态系统中是不多见的。

 

转自:http://blog.sina.com.cn/s/blog_58195f6b0101ee72.html

这篇关于转自MIT牛人林达华的 “图˙谱˙马尔可夫过程˙聚类结构 ”————经典、透彻的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/984845

相关文章

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个

自定义类型:结构体(续)

目录 一. 结构体的内存对齐 1.1 为什么存在内存对齐? 1.2 修改默认对齐数 二. 结构体传参 三. 结构体实现位段 一. 结构体的内存对齐 在前面的文章里我们已经讲过一部分的内存对齐的知识,并举出了两个例子,我们再举出两个例子继续说明: struct S3{double a;int b;char c;};int mian(){printf("%zd\n",s

Solr 使用Facet分组过程中与分词的矛盾解决办法

对于一般查询而言  ,  分词和存储都是必要的  .  比如  CPU  类型  ”Intel  酷睿  2  双核  P7570”,  拆分成  ”Intel”,”  酷睿  ”,”P7570”  这样一些关键字并分别索引  ,  可能提供更好的搜索体验  .  但是如果将  CPU  作为 Facet  字段  ,  最好不进行分词  .  这样就造成了矛盾  ,  解决方法

OpenCV结构分析与形状描述符(11)椭圆拟合函数fitEllipse()的使用

操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆,该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意,由于数据点靠近包含的 Mat 元素的边界,返回的椭圆/旋转矩形数据

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering) Power Iteration Clustering (PIC) 是一种基于图的聚类算法,用于在大规模数据集上进行高效的社区检测。PIC 算法的核心思想是通过迭代图的幂运算来发现数据中的潜在簇。该算法适用于处理大规模图数据,特别是在社交网络分析、推荐系统和生物信息学等领域具有广泛应用。Spa