马尔可夫链理解PageRank算法
在《移动迷宫：探秘马尔可夫链》一文中，我们通过一道老鼠在迷宫中随机游走的问题介绍了马尔可夫链，从而更好地理解了矩阵和矩阵的乘法. 本文将带大家解决文末留下的后两个问题：
- 老鼠在进行足够多（无穷多）次移动后, 是不是一定会逃出迷宫？
- 若迷宫并不存在出口, 则老鼠在进行足够多（无穷多）次移动后, 落在各个格子里的概率如何？
为了能让大家更好地理解后面两个问题的实际背景, 本文将介绍谷歌(Google)公司的PageRank网页排名算法并以此为背景对后面两个问题给出一般性的解答.
问题回顾与分析
迷宫共有4个格子, 相邻格子有门相通, 4号格子就是迷宫出口. 1号格子有一只老鼠, 这只老鼠以每分钟一格的速度在迷宫里乱窜（它通过各扇门的机会均等）.
例 1 ( 移动迷宫 )
老鼠在进行足够多（无穷多）次移动后, 是不是一定会逃出迷宫？
若迷宫并不存在出口, 则老鼠在进行足够多（无穷多）次移动后, 落在各个格子里的概率如何？
对于第一个问题, 由于老鼠到达4号格子就不会继续发生转移, 而1、2、3、4号格子相互连通, 我们不难猜想得到经过足够多次转移后, 老鼠都会抵达4号格子.
之前我们已经得到该马尔可夫链问题的转移矩阵及次转移后的状态矩阵表达式,
对于第二个问题, 如果迷宫不存在出口, 那么落在4号格子的老鼠经过一次转移就等可能的进入3号格子或2号格子. 由4个格子高度对称性你可能会猜测小老鼠落在各个格子的概率相同. 其实该问题与前者的区别只是转移矩阵发生了变化,
两个问题我们要讨论的都是当足够大时, 是否收敛, 即是否存在.
所以我们要研究的是一个马尔可夫链在经过多次转移后是否会稳定于一个特定的状态向量, 如果这个状态向量还与初始状态向量无关的话就再美妙不过了.
PageRank算法
为了能够更好地理解这个问题的实际背景, 这里先介绍谷歌的PageRank网页排名算法.
当我们在谷歌中搜索“橘子”时, 其在服务器后台中会找到数以亿计包含关键字“橘子”的网页, 那么谷歌是如何依据重要性对网页进行排名的呢? 要知道早期的搜索引擎由于没有很好的办法来获知哪个网页更相关, 用户往往需要自己逐个检验搜索结果.
在1999年, 两个斯坦福大学的研究生Sergey Brin [1]和Lawrence Page [2], 也就是Google的两位创始人, 所研发的新一代搜索引擎在当时脱颖而出彻底改变了这一局面. 而其所借助的算法就被命名为PageRank, 这里Page既代表webpage网页又正好是发明人之一Lawrence Page的姓.
虽然目前Google在排名算法上已经采用了更多、更科学的组合方案, PageRank算法对搜索结果排名的影响已经越来越小, 但可以毫不夸张的说是PageRank算法让Google就此崛起.
PageRank算法的主要基于这样一条假设：如果一个网页被其他重要网页所链接, 那么就也被认为是重要的. 很多文章喜欢用“投票”的说法来解释这个算法, 我们这里从马尔可夫链的角度进行说明.
如果我们把用户停留在某个网页作为一个状态, 点击链接进入新的网页看作是一次转移, 假设用户等可能地点击网页中的链接, 那么我们就可以根据链接写出转移矩阵.
在匹配关键字的情况下, 如果某些页面更容易被用户访问到就理应更为重要. 也就是说我们可以把状态向量中停留在各个网页的概率看作是网页的重要程度, 概率越高越重要.
具体地, 假如我们有5个页面, 页面之间的链接如图所示,
则转移矩阵为
那问题自然就转化为对那个特定的状态向量的寻找上.
稳定态向量
首先给我们要寻找的那个向量一个数学定义：
定义 1 ( 稳定态向量 )
若是转移矩阵, 我们把满足 的向量 称为 的一个稳定态向量.
显然这个定义说明稳定态向量只与转移矩阵有关, 与初始状态 无关.
那么对于任意一个转移矩阵是否都存在稳定态向量 ? 唯一吗? 成立吗?
从PageRank实际需求出发, 我们需要这个稳定态向量 存在、唯一, 且满足 . 因为如果这样的话, 我们只需要随便指定一个初始状态向量做若干次矩阵乘法后, 所得的结果就会稳定在稳定态向量 附近.
然而事实并没有那么美好, 我们来检验以下几个转移矩阵的情况,
对于 , 有唯一的稳定态向量 [3],对任意 都有 .
对于, 有唯一的稳定态向量, 且状态向量的变化趋势随变化而变化.
若, 则在与间摆动, 而若, 则在与间摆动.
对于, 有无穷多个稳定态向量, 其中. 取不同的其最终可能稳定在不同的向量.
正数矩阵
下面我们给出一个结论, 即转移矩阵满足我们实际需求的一个充分条件:
命题 1 ( 充分条件 )
若转移矩阵各元素均为正数, 则
- 存在唯一稳定态向量,
- 对任意成立.
我们知道转移矩阵的每一列都是某一个状态向其他状态转移的概率, 现在要求中各元素都为正数, 即要求不能有.
回到PageRank算法的背景, 如果A网页没有到B网页的链接, 那么状态A转移到状态B的概率即为.
极端情况, 如果一个网页没有任何链接, 那么一旦转移到该网页就不会继续发生转移, 这显然不是我们所期望的情况.
再比如, 几个页面互相链接且都没有指向这些页面以外的链接, 也会导致一旦转移到其中一个页面就被局限在这些页面无法跳出了.
算法的修正
为了避免以上这些情况的发生, 保证网页间的随机游走能最终稳定在一个唯一的状态向量, 我们需要对转移矩阵进行修正, 让其不再有元素.
- 修正1：如果一个网页没有任何指向其他网页的链接, 则从这个网页转移到任何网页的概率相等.
以前面4个网页的情况为例, 对转移矩阵做如下修正,
- 修正2：让一个网页有的概率等可能地转移到任何一个网页, 有的概率等可能地转移到该页面所链接的网页.
即修正后的转移矩阵为,
其中是的方阵, 所有元素都为.
如此即能保证修正后的转移矩阵各项均为正数, 传说谷歌公司所采用参数的取值为. 具体仍然以前面5个网页的情况为例,
下面, 我们不妨就用这个矩阵来得到5个网页的排名, 即反复利用递推关系计算直至收敛(足够小) [4].
如果令, 利用计算机我们得到如下结果,
x1: (0.2, 0.2, 0.2, 0.2, 0.2)
x2: (0.120, 0.149, 0.460, 0.205, 0.064)
x3: (0.092, 0.246, 0.321, 0.288, 0.050)
x4: (0.115, 0.182, 0.403, 0.252, 0.045)
x5: (0.101, 0.221, 0.354, 0.272, 0.049)
x6: (0.109, 0.198, 0.384, 0.260, 0.047)
x7: (0.104, 0.211, 0.366, 0.268, 0.048)
x8: (0.107, 0.203, 0.377, 0.263, 0.047)
x9: (0.106, 0.208, 0.370, 0.266, 0.048)
x10: (0.107, 0.205, 0.374, 0.264, 0.048)
x11: (0.106, 0.207, 0.372, 0.265, 0.048)
x12: (0.106, 0.206, 0.373, 0.265, 0.048)
x13: (0.106, 0.206, 0.372, 0.265, 0.048)
通过观察结果, 我们发现如果精确到0.001, 经过11次迭代后, 状态向量即稳定在. 即页面排名为.
进一步思考
事实上，稳定态向量就是转移矩阵的特征值所对应的一个特征向量, 出现多个稳定态向量其实就是特征值所对应的特征向量落在一个多维线性空间里.
那么是不是所有转移矩阵都有特征值, 即稳定态向量是否都存在?
实际上由于转移矩阵各列之和为, 所以线性方程组的系数矩阵, 如果进行初等行变换, 把每一行的元素都加到最后一行, 即得到行向量为零向量, 即不满秩, 所以这个线性方程组有非零解, 即有特征值及对应的特征向量, 所以稳定态向量一定存在.
参考文献
[1] David C. Lay & Steven R. Lay & Judi J. McDonald. Linear Algebra and Its Applications. Pearson Higher Ed.
本文最早于2018年12月发布于橘子数学公众号.
脚注