【其实很简单】拉普拉斯算法和拉普拉斯矩阵
epi.clyce 2019-5-29原创 机器学习数学
关键词
拉普拉斯算子拉普拉斯矩阵机器学习算法

内容同步发布于知乎专栏人工智障领养中心,欢迎支持呀


在机器学习、多维信号处理等领域,凡涉及到图论的地方,相信小伙伴们总能遇到和拉普拉斯矩阵和其特征值有关的大怪兽。哪怕过了这一关,回想起来也常常一脸懵逼,拉普拉斯矩阵为啥被定义成  1559122569266.svg  ?这玩意为什么冠以拉普拉斯之名?为什么和图论有关的算法如此喜欢用拉普拉斯矩阵和它的特征值?

最近读论文的时候,刚好趁机温习了一下相应的内容,寻本朔源一番,记录下来,希望大家阅读之后,也能够有个更加通透的理解。

要讲拉普拉斯矩阵,就要从拉普拉斯算子讲起,要讲拉普拉斯算子,就要从散度讲起~

于是我们从散度开始,发车啦~~~


通量与散度

首先我们来看一道初中物理题:

小明乘帆船出行,刮来一阵妖风,假设帆的面积为  1559122569263.svg  , 和妖风的夹角为  1559122569801.svg  ,妖风在每单位面积上的垂直风压为  1559122569808.svg  ,求妖风对帆的推动力
1559122569803.jpg

那么聪明伶俐(?)的我们一定知道,这道题的答案应该是  1559122569811.svg  。

如果我们用  1559122570521.svg  表示风的向量(且  1559122570587.svg  ),用  1559122570766.svg  表示帆的法向量,结合高中数学知识我们知道上述公式也可以写成 1559122570792.svg

。。。

如果我们现在再把题目弄复杂一点,假设船帆不是一个平面,而是一个空间中的曲面  1559122570837.svg  ,在  1559122570841.svg  所在的每一点(面积微元  1559122571459.svg )处,其法向量为  1559122571531.svg  ,且空间中存在的风为  1559122571834.svg  ,根据大学数学知识我们可以得到: 1559122571844.svg

于是我们就得到了通量  1559122571850.svg  的定义,  1559122571852.svg

。。。

那么如果我们有一个封闭曲面呢,比如:

1559122572534.jpg

在向量场下的封闭曲面


此时我们指定曲面每一点处的法向量为该点朝外的向量:

1559122572537.jpg


红色箭头为法向量,注意在上面的例子中风与帆的比喻并不完全恰当,在计算通量的时候一般我们认为向量场会穿过曲面,而非被挡住

于是我们有

1559122572847.svg

对于上图,根据向量乘法的基本原理,聪明的我们很容易知道,对于射入曲面的那一部分(左半边),其通量为,而对于射出曲面的那一部分(右半边),其通量为正。

更进一步的思考我们可以得出,相互抵消后,这一曲面上的总通量为  1559122572871.svg

。。。

接下来我们看下一张图:

1559122572915.jpg

显然,在这一向量场中,红色曲面上的总通量为负,而绿色曲面上的总通量为正。 那么我们不断缩小这两个曲面,直至其无限接近一个点  1559122572913.svg  ,并将其总通量除以曲面所围成的体积  1559122573607.svg  ,得到:

1559122574099.svg  ,

我们便得到了点  1559122574097.svg  处的散度。

。。。

根据上面的分析,我们不难看出,在红圈所在圆心处的散度为负,而绿圈圆心处的散度为正。

结合上述定义,我们知道,散度衡量了一个点处的向量场是被发射还是被吸收,或者说,对于散度为正的点,散度越大,意味着相应的向量场越强烈地在此发散,而对于散度为负的点,意味着相应的向量场在此汇聚

嗯,就这么简单~ XD

拉普拉斯算子

接下来就是我们可爱的拉普拉斯算子啦~~

根据定义,函数  1559122574100.svg  的拉普拉斯算子  1559122574423.svg  又可以写成  1559122574684.svg  ,其被定义为函数  1559122575007.svg  梯度散度

那么这又是什么意思呢?

我们知道,在直角坐标系下,一个函数  1559122575006.svg  在  1559122575241.svg  处的梯度是一个向量  1559122575339.svg  ,

于是函数  1559122575721.svg  的梯度函数  1559122576022.svg

就构成了一个在三维空间下的向量场。

于是乎,我们对这一向量场  1559122576023.svg  求散度  1559122576357.svg  ,即得到了  1559122576358.svg  的拉普拉斯算子  1559122576363.svg  。

为什么要这样做呢?

让我们想像一座山,根据梯度的定义,在山峰周围,所有的梯度向量向此汇聚,所以每个山峰处的拉普拉斯算子为负;而在山谷周围,所有梯度从此发散,所以每个山谷处的拉普拉斯算子为正。所以说,对于一个函数,拉普拉斯算子实际上衡量了在空间中的每一点处,该函数梯度是倾向于增加还是减少

歪个楼,描述物理系统最优美的公式之一拉普拉斯方程,  1559122576836.svg  ,大家可以想一想,这一公式表达了物理系统怎么样的特征呢?

图论下的函数

我们知道,互相连接的节点可以构成一张,其中包含所有点构成的集合  1559122577150.svg  , 和所有边构成的集合  1559122577471.svg  。

对于实数域上的函数  1559122577469.svg  ,我们可以理解为一种对于  1559122577474.svg  的映射,将每个可能的  1559122577913.svg  映射到一个对应的  1559122578103.svg  上(  1559122578366.svg  )。

相应地,我们也可以定义一个图函数  1559122578740.svg  ,使得图上的每一个节点  1559122578737.svg  ,都被映射到一个实数  1559122578742.svg  上。

比如说,假设我们有一个这样的社交网络图谱:

1559122578873.jpg

假设说每一条边的权值对应两个人之间信息的流通程度。现在我们想要分析这个社交网络上的信息传播,我们不仅需要知道信息流通的程度,我们还要知道每个人发动态的活跃程度,于是我们现在给这个图一个函数  1559122579081.svg  ,使得:

1559122579436.svg

这里的负数似乎可以理解为,  1559122579796.svg  和  1559122579801.svg  是谣言终结者,可以阻止信息的传播~

那么我们得到这样一张图:

1559122579822.jpg


图函数的梯度

我们定义了图论的函数,那么应该如何给图论下的函数定义梯度呢?

我们记得,梯度的意义在于,衡量函数在每一个点处,在每个正交方向上的变化,如  1559122579818.svg  的梯度在  1559122580113.svg  方向的分量  1559122580417.svg

在图论中,我们认为一个节点沿着每一条边通向它的相邻节点,而每两条边之间互相并没有什么关系,也就是说我们认为这个节点的每一条边互相都是正交的

并且对于两个节点,我们定义其距离  1559122580724.svg  为其边权值的倒数(比如上面社交网络的例子,我们可以认为,两个人的信息流通程度越低,两个人的友谊就“越远”)

那么对于一个节点  1559122580792.svg  ,我们认为其梯度在一条通向  1559122580835.svg  的边  1559122580833.svg  上的分量

1559122581065.svg

(其中  1559122581389.svg  为  1559122581721.svg  到  1559122581961.svg  的距离),

为了计算梯度,我们给出一个这样的矩阵:

每一行代表一个点,每一列代表一条边,使得对于每个点每条边,如果该条边从该点发射出去,且权值为  1559122581965.svg  ,则将矩阵中对应的这一元素置为  1559122582006.svg  ,如果该条边指向该点,则将对应的元素置为  1559122582263.svg  

具体到上面社交网络的例子,我们有相应的矩阵  1559122582509.svg  :

1559122582818.jpg

我们又有关于图函数  1559122583107.svg  的列向量  1559122583109.svg  :

1559122583110.png

我们试着计算  1559122583343.svg  :

1559122583534.svg

经过观察我们可以知道,最后计算结果的向量,即是整个图  1559122583685.svg  在  1559122583901.svg  函数上的梯度  1559122584209.svg  ,其中每一行,为该梯度在一条边上的分量。

所以对于图  1559122584210.svg  ,我们有  1559122584520.svg  ,使得  1559122584540.svg

拉普拉斯算子与拉普拉斯矩阵

我们记得在函数中,拉普拉斯算子的定义为函数梯度的散度,即每一点上其梯度的增加/减少,那么对于图函数,其每一“点”即为每个“节点”,其梯度的散度该怎么定义呢?

我们几乎可以立刻可以想到,图函数每一点上梯度的散度,即是从该节点射出的梯度,减去射入该节点的梯度,那么我们几乎又可以立即想到(?),根据这样的定义去计算散度,只要把原来的梯度再左乘一个这样的矩阵就可以啦:

每一行代表一个点,每一列代表一条边,使得对于每个点每条边,如果该条边从该点发射出去,则将矩阵中对应的这一元素置为  1559122584852.svg  ,如果该条边指向该点,则将对应的元素置为  1559122584903.svg  

命名这一矩阵为  1559122585736.svg


也就是说,我们把  1559122585738.svg  的每个元素,正的变成1,负的变成-1,就得到了  1559122585740.svg

1559122585739.svg

那么,

1559122586513.svg

于是我们得到了图论函数的拉普拉斯算子  1559122586521.svg  ,即我们常说的拉普拉斯矩阵

注意在我们上面的范例中,将任意一条边的方向反转,等价于在  1559122586755.svg  的一列上乘以  1559122586757.svg  ,这种情况下最终  1559122586758.svg  不会改变,也就是说拉普拉斯矩阵的值与图中每一条边的方向无关,所以拉普拉斯矩阵一般用来表述无向图

计算  1559122586805.svg  的值,我们得到矩阵:

1559122587561.svg

注意到这一对称矩阵,对角线即是每个点的,而其余的元素,则是负的邻接矩阵,于是乎我们得到了拉普拉斯矩阵的经典算式:

1559122587576.svg

(至于外面的各种资料为什么往往只使用  1559122587932.svg  而非  1559122587939.svg  ,个人认为是因为前者只涉及减法,计算远远快于后者,所以程序中一般使用前者。但是为了理解拉普拉斯矩阵的意义,对后者的了解在我看来是必须的

拉普拉斯矩阵的重要性质

拉普拉斯矩阵之所以如此常用,是因为其一大重要性质: 拉普拉斯矩阵的  1559122587938.svg  个特征值  1559122587941.svg  都是非负值,且有  1559122588557.svg

同时,我们引入关于矩阵  1559122588772.svg  和  1559122589040.svg  的瑞利熵的概念:  1559122589857.svg

其中  1559122589043.svg    1559122589041.svg  共轭矩阵,对于  1559122589586.svg  为实数矩阵的情况下  1559122589791.svg

而通过拉格朗日乘子法可以得出,瑞利熵的一个非常重要的特点就是: 瑞丽熵的最大值,等于  1559122590075.svg  的最大特征值,瑞利熵的最小值,等于  1559122590073.svg  的最小特征值

再看看图算法中对于拉普拉斯矩阵  1559122590076.svg  的运算中常常出现的f  1559122590752.svg  ,结合上文所述的拉普拉斯矩阵的重要性质,那么拉普拉斯矩阵在各种图算法中的应用,想必大家也能够理解啦~

[修改于 2 年前 - 2019-05-29 20:16:31]

来自:计算机科学 / 机器学习数理化 / 数学
radio
1年11个月前
1楼

失踪人口回归系列

回复
评论
2
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
虎哥
1年11个月前 修改于 1年11个月前
2楼

@虎哥

回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
月光曲
1年11个月前
3楼

比数学书容易看懂

回复
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

%7B%22isDisplay%22%3Atrue%7D

仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
等待中...
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
处理中..
处理失败
插入表情
我的表情
共享表情
Emoji
上传
注意事项
最大尺寸100px,超过会被压缩。为保证效果,建议上传前自行处理。
建议上传自己DIY的表情,严禁上传侵权内容。
点击重试等待上传{{s.progress}}%处理中...已上传
空空如也~
草稿箱
加载中...
此处只插入正文,如果要使用草稿中的其余内容,请点击继续创作。
{{fromNow(d.toc)}}
{{getDraftInfo(d)}}
标题:{{d.t}}
内容:{{d.c}}
继续创作
删除插入插入
{{forum.displayName}}
{{forum.countThreads}}
篇文章,
{{forum.countPosts}}
条回复
{{forum.description || "暂无简介"}}
ID: {{user.uid}}
学术分隐藏
{{submitted?"":"投诉或举报"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png
插入公式
分享回复:{{shareId}}
加载中...
评论控制
加载中...
文号:{{pid}}
加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
加入关注取消关注
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
建议修改
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}
下载资料
{{fileName}}
大小:{{size}}
下载当前附件将花费 {{costMessage}}
{{description}}
你当前剩余 {{holdMessage}}
{{fileName}}
大小:{{size}}
当前附件免费。
你已购买过此附件,下载当前附件不需要花费积分。
加载中...
{{errorInfo}}
附件已丢失
当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}