pagerank算法，pagerank算法深入讲解？

1998年，Lawrence Page、Sergey Brin、Rajeev Motwani和Terry Winograd共同发表了一篇名为《PageRank引用排行:给网络带来秩序》的文章。他们在这篇文章中从谷歌的成立之初介绍了现在著名的PageRank算法。二十多年后，谷歌已经成为一个巨人，即使算法已经发展很多，PageRank仍然是谷歌排名算法的”象征”。

什么是马尔可夫链？

随机变量和随机过程

首先，在非数学术语中，随机变量 X是一个变量，其值被定义为随机现象的结果。该结果可以是一个数字（或”类数”，包括向量）或不是。例如，我们可以将随机变量定义为掷骰子的结果(数字)以及投掷硬币的输出(不是数字，除非您指定，例如，0为正面，1为反面)。还要注意，随机变量的可能结果的空间可以是离散，也可以是连续的：例如，例如，正态随机变量是连续的，而非随机变量是离散的。

然后我们可以定义一个随机过程（也称为随机过程）作为由集合T索引的随机变量的集合，其通常表示不同的时间瞬间。两种最常见的情况是：T是自然数集（离散时间随机过程）或T是实数集（连续时间随机过程）。例如，每天翻转硬币定义了离散时间随机过程，而股票市场期权价格连续变化定义一个连续的时间随机过程。不同时刻的随机变量可以相互独立（硬币翻转示例）或以某种方式依存（股票价格示例），也可以具有连续或离散的状态空间（每个时刻可能结果的空间）。

不同类型的随机过程

马尔可夫属性和马尔可夫链

存在一些众所周知的随机过程族：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。每个特定的属性使我们能够更好地学习和理解它们。

研究随机过程的一个特性是”马尔可夫属性”。以非正式的方式，马尔科夫特性表示，对于一个随机过程，如果我们知道在给定时间所取得的值，我们将不会通过收集更多知识获得有关该过程未来行为的额外信息。用稍微更数学的术语来说，给定当前状态和过去状态的流程，未来状态的条件分布只依赖于当前状态，而完全不依赖于过去状态(无记忆属性)。具有马尔可夫属性的随机过程称为马尔可夫过程。

基于先前的定义，我们现在可以定义”离散时间马尔可夫链”。马尔科夫链是马尔可夫过程与离散时间和离散状态空间。因此，马尔可夫链是一个离散的状态序列，每个状态都从一个离散的状态空间（有限或无有限）中提取的，并且遵循马尔可夫属性。

在数学上，我们可以表示马尔可夫链

在每个时刻，过程在离散集E中取其值，使得

然后，马尔可夫属性意味着我们拥有

再次注意，最后这个公式表达了这样一个事实:对于给定的历史状态(我现在的位置和以前的位置)，下一个状态(我接下来要去的位置)的概率分布只取决于当前状态，而不取决于过去的状态。

马尔可夫链的随机动态

首先注意，不验证马尔可夫性质的离散时间随机过程的完全表征可能是痛苦的：给定时间的概率分布可能取决于一个或 过去和/或未来时间的多重性。所有这些可能的时间，使任何适当的描述过程都存在潜在的困难。

但是，根据马尔可夫属性，马尔可夫链的动态非常容易定义。实际上，我们只需要指定两件事：初始概率分布（即时刻n = 0的概率分布）表示：

和一个转移概率核（给出一个状态，在时间n + 1，在时间n，对于任何状态对，在另一个状态下成功）的概率：

通过已知的前两个对象，可以很好地定义过程的完整（概率）动态。实际上，可以以循环方式计算任何实现过程的概率。例如，假设我们想要知道过程的前3个状态的概率是（s0，s1，s2）。所以，我们想要计算概率

在这里，我们使用总概率定律，它可以写为：

然后出现马尔可夫假设给出的简化。实际上，对于长链，我们将获得最后状态的重度条件概率。但是，在Markov案例中，我们可以使用它来简化此表达式

这样我们就有了

由于它们完全表征了过程的概率动态，因此可以仅基于初始概率分布q0和转移概率核p来计算许多其他更复杂的事件。最后一个基本关系是时间n + 1处的概率分布的表达，其相对于时间n的概率分布表示：

有限状态空间马尔可夫链

矩阵和图形表示

我们假设在E中我们有可能的N个有限数：

然后，初始概率分布可以由大小为N 的行向量q0描述，并且转移概率可以由大小为N×N的矩阵p来描述，使得

这种表示法的优点是，如果我们注意到在步骤n中用原始向量qn表示概率分布，使得它的分量由下式给出：

然后，简单矩阵关系保持不变

当右侧乘以表示给定时间步长的概率分布的行向量乘以转移概率矩阵时，我们获得下一时间步的概率分布。

因此，我们在这里看到，将给定步骤的概率分布演变为下一步骤就像将初始步骤的行概率向量乘以矩阵p一样简单。这也意味着我们拥有：

我们举一个简单的例子来说明这一切。考虑一个上网读者的日常行为。对于每一天，有3种可能的状态：读者今天不访问某网站，读者访问该网站但没有阅读完整帖子（V），和读者访问并阅读至少一篇完整帖子（R）。所以，我们有以下状态空间

假设在第一天，该读者有50％的机会访问，有50％的机会访问并阅读至少一篇文章。然后描述初始概率分布（n = 0）的向量：

想象一下，还观察到以下概率：

• 当读者第一天天不访问该网站时，第二天他有25％的机率仍然没有访问，50％的概率只访问，25％访问和阅读；
• 当读者第一天访问该网站却在没有阅读的情况下时，他有50％的概率在第二天不阅读的情况下再次访问，50％的人访问且阅读；
• 当读者第一天访问并阅读时，他有33％的概率在第二天不访问，33％的概率只访问，34％的概率访问并再次阅读。

所以，我们有以下转换矩阵

根据前面的小节，我们知道如何为这个读者计算第二天每个州的概率（n = 1）

最后，该马尔可夫链的概率动态可以图形表示如下：

马尔可夫链属性

可还原性，周期性，短暂性和复发性

让我们从这个小节开始，用一些经典的方法来描述一个状态或者一个完整的马尔可夫链。

首先，我们说马尔可夫链是不可简化的，如果有可从任何其他状态到达任何一状态。如果状态空间是有限的，并且链可以用图表示，那么我们可以说不可简化的马尔可夫链的图是强连通的（图论）。

左边的链不是不可简化的：从3或4，我们不能达到1或2。右边的链（增加了一条边）是不可简化的：每个状态都可以从任何其他状态到达。

一个状态的周期是k，如果在离开状态时，返回到该状态需要多个k个时间步长(k是所有可能返回路径长度的最大公约数)。如果k = 1，那么状态就是非周期的。

左边的链是2周期的：当离开任何状态时，总是需要两个步骤的倍数才能回到它。右边的链子是3周期的。

一个状态是短暂的，如果当我们离开这个状态时，我们永远不会返回它的非零概率状态是暂时的。相反，如果我们知道我们将在离开之后以概率1返回该状态，则状态是经常性的。

左方的链条是这样的：1、2和3是短暂的(当离开这些点时，我们不能绝对肯定我们会回到它们的位置)。 而4和5是重复的(当我们离开这些点时，我们绝对肯定我们会在某个时候回到它们)。右边的链子还有一个边使整个链循环。

对于循环状态，我们可以计算平均重现时间，即离开状态时的预期返回时间。请注意，即使返回的概率等于1，也不意味着预期的返回时间是有限的。因此，在周期性状态中，我们可以区分正复发状态（有限预期返回时间）和零复发状态（无限期望返回时间）。

静态分布，限制行为和遍历性

一个概率分布在状态空间Eπ是一个平稳分布验证

如果验证，则状态空间E上的概率分布π被称为静止分布

像我们一样

然后静态分布验证：

根据定义，静止概率分布是这样的，它不会随时间演变。因此，如果初始分布q是静态分布，那么对于所有未来的时间步长它将保持不变。如果状态空间是有限的，则p可以用矩阵表示，π可以用原始向量表示，然后我们得到：

再一次，它表达了一个事实，即静止的概率分布不会随着时间的推移而发展。请注意，当且仅当所有状态都是正向重复时，不可简化的马尔可夫链具有静态概率分布。

与静止概率分布相关的另一个有趣的属性如下。如果链是循环正和非周期时，无论初始概率是多少，当时间步长变为无穷大时，链的概率分布会被限制：该链被认为具有限制分布，而不是静态分布。在一般情况下，它可以写

让我们再次强调这样一个事实，即在初始概率分布上没有假设：无论初始设置如何，链的概率分布都会被限制到平稳分布。

最后，遍历性是另一个与马尔可夫链行为相关的有趣属性。如果马尔可夫链是不可约的，那么我们也说这个链是”遍历的”，因为它验证了下面的遍历定理。假设我们有一个从状态空间E到实线的应用程序f（.）（例如，它可以是每个状态的成本）。我们可以定义沿给定轨迹（时间平均值）采用此应用程序的平均值。对于第n个第一项，它表示为:

我们还可以计算应用f的平均值，该集合E由表示为的静态分布（空间均值）加权

然后遍历定理告诉我们，当轨迹变得无限长时的时间平均值等于空间平均值（由静态分布加权）。可以写出遍历属性

换句话说，在极限情况下，轨迹的早期行为变得可以忽略不计，只有长期静止行为在计算时间均值时才真正重要。

再次看访问网站阅读的示例

在这个简单的例子中，链明显不可约，非周期性，所有状态都是反复出现的。

为了显示可以用马尔可夫链计算的有趣结果，我们想要查看状态R的平均重现时间（状态”访问和读取”）。换句话说，我们想回答以下问题：当我们的读者某一天访问并读取，我们需要了解在他访问并再次阅读之前平均等待多少天？

首先，我们表示

所以我们想在这里计算m（R，R）。离开R后到达第一步的推理，我们得到了

然而，该表达式需要知道m（N，R）和（V，R）来计算m（R，R）。这两个量可以用相同的方式表示

因此，我们有3个具有3个未知数的方程，当我们求解该系统时，我们得到m（N，R）= 2.67，m（V，R）= 2.00和m（R，R）= 2.54。状态R的平均复发时间的值则为2.54。因此，我们看到，通过一些线性代数，我们设法计算状态R的平均重现时间。

总结这个例子，让我们看看这个马尔可夫链的平稳分布是什么。为了确定平稳分布，我们必须求解下面的线性代数方程

因此，我们必须找到与特征值1相关的p的左特征向量。解决这个问题，我们得到以下平稳分布

我们还可以注意到π（R）= 1 / m（R，R）的事实，这在考虑它时有一个非常合乎逻辑的标识。

由于链是不可约的和非周期性的，这意味着，从长远来看，概率分布将收敛到静止分布。换句话说，无论初始状态如何，如果我们等待足够长的时间并随机选择一天，那么我们有一个概率π（N），读者今天不会访问，概率为π （五）读者访问但未阅读，读者访问和读取的概率π（R）。为了更好地掌握这种收敛性，让我们看一下下图，它显示了从不同起点开始的概率分布演变和被限制到静止分布。

可视化3个不同初始化概率分布（蓝色，橙色和绿色）向静止分布（红色）的收敛。

一个经典的例子：PageRank算法

我们将用马尔可夫链对PageRank进行解释，原始论文的作者在设计方法时并不一定考虑马尔可夫链。以下解释可以很好理解。

随机网络冲浪者

PageRank要解决的问题如下：我们如何通过使用它们之间的现有链接对给定集合的页面进行排序

为了解决这个问题并能够对页面进行排名，PageRank大致如下进行。我们们认为，随机网页是在其中一个网页上的初始时间。然后，这个冲浪者开始随机地导航，通过点击每个页面上的一个链接，该链接指向所考虑的集合的另一个页面。对于给定页面，所有允许的链接都有相同的机会被点击。

我们这里有一个马尔可夫链的设置：页面是不同的可能状态，转换概率是由页面到页面的链接定义的,并且加权使得在每个页面上所有链接的页面都有相同的机会被选择,并且这些属性可以通过用户的行为清楚地得到验证。如果我们还假设定义的链是循环正和非周期性的，那么在很长一段时间后，“当前页面”概率分布会收敛到静止分布。因此，无论起始页面如何，经过很长一段时间后，如果我们选择随机时间步长，每个页面都有一个概率作为当前页面。

PageRank背后的假设是，静态分布中最可能的页面也必须是最重要的。然后，静态概率分布为每个状态定义PageRank的值。

一个小例子

假设我们有一个小网站，其中有7个页面标记为1到7，并且页面之间有链接，如下图所示。

为清楚起见，在先前的表示中没有显示每个转换的概率。但是，由于”导航”应该是纯随机的，可以使用以下简单规则很容易地恢复值：对于一个具有K的节点(一个具有K链接到其他页面的页面)，每个节点的概率等于1/K。 性质转移矩阵:

其中0.0值已被’.’取代 为了便于阅读。在进一步计算之前，我们可以注意到这个马尔可夫链是不可约的以及非周期性的，因此，在长期运行之后，系统收敛到静止分布。正如我们已经看到的，我们可以通过求解下面的左特征向量问题来计算这个静态分布

这样做我们获得了每页的PageRank值（静态分布的值）

在我们的玩具示例中计算的PageRank值包含7页。

这个小网站的PageRank排名是1> 7> 4> 2> 5 = 6> 3。

总结

最后，让我们再次强调马尔可夫链在处理随机动力学时对问题建模的强大作用。由于它们的良好特性，它们被用于各种领域，例如排队理论，优化电信网络的性能，其中消息必须经常竞争有限的资源并且在所有资源已经被分配时排队）；统计信息，众所周知的”马尔可夫链蒙特卡罗”随机变量生成技术基于马尔可夫链；生物学，生物种群进化的建模；计算机科学，隐马尔可夫模型是信息论和语音识别等领域的重要工具。

好了，这篇文章的内容营销圈就和大家分享到这里，如果大家对网络推广引流和网络创业项目感兴趣，可以添加微信：Sum8338 备注：营销圈引流学习，我拉你进直播课程学习群，每周135晚上都是有实战的推广引流技术和网络创业项目课程分享，当然是免费学！