AI内参_51_049_PageRank算法的核心思想是什么

你好，我是洪亮杰。

今天我和你分享的主题是page rank算法的核心思想是什么？上周，我们介绍了信息搜索系统的历史进程，剖析了搜索系统的多轮打分系统，还深入探讨了倒排索引。

聊了聊它的核心技术。

这周我和你分享的是在互联网搜索引擎兴起之后的一个研发需要。

那就是如何理解网页和网页之间的关系，特别是怎么从这些关系中提取网页中除文字以外的其他特性。

这部分的一些核心算法曾是提高搜索引擎质量的重要推进力量。

另外我们这周要分享的算法也适用于其他信息网络，条件是这些信息网络要能够把信息用节点与节点的关系来表达。

今天我们一起来看一看，用图来表达网页与网页之间的关系，并且计算网页重要性的经典算法。

Page rank,我先简要的介绍一下page rank的历史。

时至今日，希尔盖布林和拉里佩奇作为谷歌这一雄厚科技帝国的创始人已经耳熟能影响，但一九九五年他们们两人还都在斯坦福大大计算机系系读读的博士生。

那个年代，互联网方兴未艾。

雅虎作为信息时代的第一代巨人诞生了，希尔盖和拉里都希望能够创立属于自己的搜索引擎。

一九九八年夏天，两个人都暂时离开斯坦福大学的博士生项目，转而全职项入到谷歌的研发工作中。

他们把整个项目的一个总结发表在了一九九八年的万维网国际会议上。

这是page rank算法的第一次完整表述。

Page rank一经提出，就在学术界引起了很大反响。

类变形以及对papage rank的各种解释和分析层出不穷。

在这之后很长的一段时间里，page rank几乎成了网页链接分析的代名词。

我在这里先介绍一下page rank的最基本形式，这也是希尔盖和拉里最早发表page rank式的思路。

首先我们来看一下每一个网页的周边结构，每一个网页都有一个输出链接的集合。

这里输出链接指的是从当前网页出发所指向的其他页面。

比如从页面a有一个链接到页面，b那么b就是a的输出链接。

根据这个定义可以同样定义输入链接指的就是指向当前页面的其他页面。

比如页面c指向页面a那么c就是a的输入链接。

有了输入链接和输出链接的概念后，下面我们来定义一个页面的配置rank.我们假定每一个页面都有一个值，叫做配ge rank来衡量这个页面的重要程度。

这个值是这么定义的。

当前页面i的配置rank值是i的所有输入链接配置rank值的加权和。

那么权重是多少呢？对于i的某一个配置rank, j假设其有n个输出链接，那么这个权重就是n分之一。

也就是说，j把自己的配置rank的n分之一分给i.从这个意义上来看，i的配置rank就是其所有输入链接，把它们自身的配置rank按照它们各自输出链接的比例分配给i谁的输出链接多，谁分配的就少一些。

反之，其的输出链接少，谁分配的就多一些，这是一个非常形象直观的定义。

然而有了这个定义还是远远不够的。

因为在这个定义下，页面i和页面j以及其他任何页面的配置，rank值是事先不知道的，反正是等式，两两边都有未知数，这看上去是个无解的问题。

希尔盖和拉里在他们的论文中采用了一种迭代算法，这个算法很直观。

那就是既然不知道这些配置rank的值，那我们就给它们一组初始值。

这个初始值可以是这样的情形。

所有页面有相同的配置，rank值。

然后根据我们上面所说的这个定义更新所有页面的配置rank值就这么一遍一遍的更新下法，直到所有页面的配置，rank不再发生很大变化。

或者说最后收敛到一个固定值为止。

他们在文章中展示了实际计算的情况，往往是在比较少的迭代次数后，配置rank值就能够收敛。

以上就是整个配置rank算法的基本思想和一种迭代算法，完全按照我们上面介绍的这个最原始的配置。

Rank算法。

希尔盖和拉里很快就遇到了麻烦。

第一个麻烦就是有一些页面并没有输出链接，比如某些PDF文件或者一些图片文件。

由于没有输出链接，这些页面只能聚集从上游输入链接散发来的配置rank值，而不能把自己的配置rank值分发出去。

这样的结果就是这些页面成为一些悬空节点。

悬空节点存在最大的问题，就是会使得配置rank的计算变得不收敛。

这些节点成了配置rank值的黑洞，导致悬空节点的配置rank值越来越大，直至吸干其他所有输入链接的值。

要解决这个问题，就要为悬空节点引流，能够把这些点的值分发出去。

引出去。

希尔德和拉里找到的一个方法是，对于每一个悬空节点都认为这个节点能够随机到达整个网络上的其他任意一个节点，也就是相当于人工的从这个节点连接到所有页面的一个节点，让当前悬空节点的配置，rank能够均匀的分散出去到其他所有的节点，这就解决了悬空节点的问题。

然而，原始的配置rank还存在其他问题，要想保证配置rank的收敛性，并且能够收敛到唯一节，我们还需要第二个改进。

第二个改进就是即便一个页面有自然的输出链接，我们也需要一个机制，能够从这个页面跳转到其他任何一个页面。

这也就是模拟假设，一个用户已经浏览到了某个页面。

一方面用户可以顺着这个页面提供的输出链接继续浏览下去。

另一方面，这个用户可以随机跳转到其他任何一个页面。

有了这个机制以后，对于所有的节点来说，配置rank的分配也就自然的产生了变化。

在之前的定义中，每个页面仅仅把自己的配置rank值输送给自己原生的所有输出链接中。

而现在这是一部分的分享，另外一部分还包括把自己的配置rank值分享到所有的页面。

当然，后者的总量应该比前者要少于是这里可以引入一个参数来控制，有多大的比例，我们是顺着输出链接走而多大的比例。

跳转其他页面。

通常情况下，这个参数的取值范围大约是百分之六十到百分之八十五。

有了这两个改进之后，整个网络上的每个页面实际上已经可以到达其他任何页面。

也就是说，整个页面网络成了一个完全连通的图配置，rank算法就有了唯一的收敛的解配置。

Rank k提出后不久，就学着开始针对配置rank模型和算法的性质进行分析。

大家很快发现，还有一些其他的方法可以对配置rank进行解释，也一种比较流流网也是有一一规解释。

配置rank的方法是把我们刚才说的这个分配等式写成矩阵的形式。

那么整个算法就变成了一个标准的求解一个随机矩阵的左特征向量的过程。

这个随机矩阵就是我们刚才讲到的，经过了两次修改后的跳转规律的矩阵形式。

而刚才所说的迭代方法正好就是求解特征向量的乘幂法。

在一定条件下的随机矩阵，经过乘幂法，就一定能够得到一个唯一解。

另外一种解释是，把刚才我们说的这个矩阵形式进行一次代数变形，也就是把等式两边的各项都移动到等式的一边，而另一边自然就是零。

那么整个式子就变成一个线性系统的阅解过程。

也就是说，从代数的角度来解释整个配置rank的求解过程。

今天我为你讲了现代搜索技术中的一个重要分支链接，分析中最重要的算法配置rank的核心资料，一起来回顾一下要点。

第一，我们讲了配置rank的一些简明历史和算法，对原始的定义和思路。

第二，我们讲了配置rank的两种改进。

第三，我们简要的介绍了针对配置rank的两种解释方法。

文末给你推荐了两篇参考文献，可以作为进一步深入了解配置rank的阅读资料。

最后给你留一个思考题，除了乘幂法，你觉得还有什么方法可以用来求解配置rank值呢？欢迎我给我留言，和我一起讨论。