全文共7050字，预计学习时长14分钟
1998年，Lawrence Page、Sergey Brin、Rajeev Mowatani和Terry Winorad出版了“PageRank引文排名：为网页带来秩序（The PageRank Citation Ranking: Bringing Order to the Web）”，该文介绍了谷歌起初使用的而如今非常著名的PageRank算法。
20多年后，谷歌已经成为互联网巨头，即使算法已经发展了很多，PageRank仍然是谷歌排名算法的“象征”（即使很少有人能真正说出它在算法中所占的重量）。
从理论角度来看，有趣的是，PageRank算法的一个常见解释依赖于简单但基本的马尔可夫链数学概念。我们将在本文中看到，马尔可夫链是随机建模的强大工具，对任何数据科学家都金昌seo技术培训:有用。更特别的是，我们将回答一些基本的问题，例如：什么是马尔可夫链，它们有什么好的性质，以及可以用它们做什么？
在第一部分中，我们将给出理解马尔可夫链是什么所需的基本定义。在第二部分中，我们将讨论有限状态空间马尔可夫链的特殊情况。在第三部分中，我们将讨论马尔可夫链的一些基本性质，并用许多小例子来说明这些性质。在第四部分中，我们将联系PageRank算法，在一个小实例中看到如何使用马尔可夫链对图的节点进行排序。
注意：这篇文章需要概率论和线性代数的基础知识。特别是将使用以下概念：条件概率、特征向量和全概率定律。
1.什么是马尔可夫链？
随机变量和随机过程
在介绍马尔可夫链之前，让我们先简单回顾一些基本但重要的概率论概念。
首先，在非数学术语中，随机变量X是一个变量，其值被定义为随机现象的结果。这个结果可以是一个数字（或“类似数字”，包括向量），也可以不是。例如，我们可以将一个随机变量定义为掷骰子（数字）的结果以及掷硬币的输出（不是数字，除非你将0指定给头，将1指定给尾）。还要注意，随机变量的可能结果空间可以是离散的或连续的：例如，正态随机变量是连续的，而泊松随机变量是离散的。
然后我们可以将随机过程定义为一组随机变量，这些随机变量由一个集合T索引，该集合通常表示不同的时间瞬间（我们将在下面假设）。
最常见的两种情况是：T是自然数集（离散时间随机过程）或T是实数集（连续时间随机过程）。例如，每天抛硬币定义了一个离散的时间随机过程，而股票市场期权的价格不断变化则定义了一个连续的时间随机过程。不同时刻的随机变量可以相互独立（抛硬币的例子）或以某种方式依赖（股票价格的例子），也可以有连续或离散的状态空间（每个时刻可能产生结果的空间）。
不同类型的随机过程（空间/时间的离散/连续）
马尔可夫性质与马尔可夫链
有一些众所周知的随机过程家族：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。这些特定的案例，每一个都有具体的特性，使我们能够更好地研究和理解它们。
“马尔可夫性质”是使研究随机过程更加容易的一个性质。马尔可夫性质非常非正式地表示，对于一个随机过程，如果我们知道在给定时间过程所取的值，我们就不会通过收集更多关于过去的知识来获得关于过程未来行为的任何额外信息。用更为数学的术语表述，在任何给定的时间内，给定当前和过去状态的过程的未来状态的条件分布仅取决于当前状态，而完全不取决于过去状态（无记忆属性）。具有马尔可夫性质的随机过程称为马尔可夫过程。
马尔可夫性质表示这样一个事实，即在给定的时间步和已知当前状态的情况下，通过收集有关过去的信息，我们不会得到任何关于未来的额外信息。基于前面的定义，我们现在可以定义“同构离散时间马尔可夫链”（为了简单起见，下面将称为“马尔可夫链”）。马尔可夫链是一个具有离散时间和离散状态空间的马尔可夫过程。因此，马尔可夫链是一个离散的状态序列，每个状态序列都是从一个离散的状态空间（有限或无限）中提取出来的，并且遵循马尔可夫性质。
在数学上，我们可以用下列式子表示马尔可夫链：
其中，在每一时刻，过程的值都是取自离散集E中的，如下所示：
那么，马尔可夫性质意味着有如下结论：
最后一个公式表达了这样一个事实：对于给定的历史（我现在在哪里，我以前在哪里），下一个状态（我将去向何方）的概率分布仅取决于当前状态，而不取决于过去的状态。
我们决定在这篇介绍性文章中只描述基本的同构离散时间马尔可夫链。然而，也存在异构（时间依赖）和/或时间连续的马尔可夫链。下面我们将不讨论模型的这些变体。还要注意，上面给出的马尔可夫性质的定义是非常简单的：真正的数学定义涉及过滤的概念，这远远超出了这个适度介绍的范围。
马尔可夫链的随机动态特征
我们在前面的小节中引入了一个与任何马尔可夫链匹配的一般框架。现在让我们看看定义这样一个随机过程的特定“实例”需要什么。
首先要注意的是，没有验证马尔可夫性质的离散时间随机过程的完整描述可能是痛苦的：给定时间的概率分布可能依赖于过去和/或未来的一个或多个时间瞬间。所有这些可能的时间依赖性使得对过程的任何适当描述都可能变得困难。
然而，由于马尔可夫性质的存在，马尔可夫链的动态是很容易定义的。实际上，我们只需要指定两件事：初始概率分布（即时间瞬间的概率分布n=0）表示为：
以及一个过渡概率核（它给出了一个状态，在n+1时，对于任意一对状态，在n时，成功于另一个状态的概率）表示为：
在已知前两个对象的情况下，过程的完全（概率）动态被很好地定义。事实上，任何实现过程的概率都可以反复计算。
例如，假设我们想知道过程前3个状态的概率为（s0、s1、s2）。所以，我们要计算概率：
这里，我们使用全概率定律，说明（s0，s1，s2）的概率等于第一个s0的概率乘以有s0条件下的s1的概率，乘以有s0和s1的条件下有s2的概率。从数学上讲，它可以写为：
然后出现了由马尔可夫假设给出的简化。事实上，对于长链，我们将获得上一个状态的严格条件概率。然而，在马尔可夫的情况下，我们可以用它来简化这个表达式：
这样我们就有了：
由于它们充分描述了过程的概率动态，因此许多其他更复杂的事件只能基于初始概率分布q0和过渡概率核p来计算。最后一个值得给出的基本关系是时间n+1处概率分布的表达式，相对地表示为时间n的概率分布：
2. 有限状态空间马尔可夫链
矩阵与图表示
我们假设在E中有一个有限的N个可能状态：
然后，初始概率分布可以用N大小的行向量q0来描述，过渡概率可以用N*N大小的矩阵p来描述，从而
这种表示法的优点是，如果我们注意到用一个原始向量qn表示步骤n的概率分布，那么它的分量由
然后简单的矩阵关系成立
将表示给定时间步的概率分布的行向量与过渡概率矩阵右相乘，得到下一时间步的概率分布。
所以，我们在这里看到，将概率分布从一个给定的步骤发展到下一个步骤，就像把初始步骤的行概率向量与矩阵p右相乘一样简单，这也意味着有：
有限状态空间马尔可夫链的随机动态可以很容易地表示为一个有价值的定向图，这样图中的每个节点都是一个状态，并且对于所有状态对（ei，ej），如果p（ei，ej）>0，则存在一条从ei到ej的边。边的值就是这个概率p（ei，ej）。
示例：Towards Data Science读者
举一个简单的例子来说明这一切。假设一个Towards Data Science读者的日常行为。每一天有三种可能的状态：读者今天不访问TDS（N），读者访问TDS但不阅读全文（V），读者访问TDS并阅读至少一篇全文（R）。所以，我们有以下状态空间：
假设在第一天，读者只有50%的可能访问TDS，50%的可能访问TDS并至少阅读一篇文章。描述初始概率分布（n=0）的向量是
同时，假设观察到以下概率：
如果读者一天不访问TDS，他有25%的可能第二天仍然不访问，50%的可能只访问，25%的机会访问和阅读。
当读者在一天内不阅读的情况下访问TDS时，他有50%的可能在第二天不阅读的情况下再次访问，50%的可能在第二天不阅读的情况下访问和阅读。
当读者在一天中访问并阅读时，他有33%的可能第二天不访问（希望这篇文章不会有这种效果！），33%的可能只访问，34%的可能再次访问和阅读。
然后，我们有下面的过渡矩阵
根据前面的小节，我们知道如何为这个读者计算第二天每个状态的概率（n=1）
最后，该马尔可夫链的动态概率可以用图形表示如下：
我们虚拟TDS读者行为模型的马尔可夫链的图形表示。
3. 马尔可夫链性质
在本节中，我们只给出一些基本的马尔可夫链性质或特征。这个想法并不是深入到数学细节中去，而是更深入地给出在使用马尔可夫链时需要研究的兴趣点的概述。正如我们已经看到的，在有限状态空间的情况下，我们可以把马尔可夫链描绘成一个图，注意我们将使用图形表示来说明下面的一些属性。然而，我们应该记住，这些属性不一定局限于有限状态空间的情况。
可还原性、周期性、短暂性和复发性
从这一小节开始，用一些经典的方法来描述一个状态或整个马尔可夫链。
首先，如果一个马尔可夫链可以从任何其他状态到达任何状态（不一定是在一个时间步内），那么它是不可约的。如果状态空间是有限的，并且链可以用图表示，那么我们可以说不可约马尔可夫链的图是强连通的（图论）。
不可约性的说明。左边的链是可约的：从3到4我们不能到达1或2。右边的链（添加了一条边）是不可约的：每个状态都可以从任何其他状态到达。
一个状态有周期k，如果在离开这个状态时，任何返回到该状态需要k时间步数的倍数（k是所有可能返回路径长度中最大的公因数）。如果k=1，那么状态被称为非周期的，如果所有的状态都是非周期的，那么整个马尔可夫链就是非周期的。对于不可约马尔可夫链，我们还可以提到一个事实，如果一个状态是非周期的，那么所有状态都是非周期的。
周期性的说明。左边的链是2周期的：当离开任何状态时，它总是需要2个步骤的倍数才能回到它。右边的链子是三周期的。
当我们离开这个状态时，如果有一个非零的概率，我们将永远不会回到它，那么状态就是瞬时的。相反，一个状态是反复出现的，如果我们知道我们将来会回到那个状态，在离开后概率为1（如果它不是暂时的）。
重现/瞬变特性的图解。左边的链是这样的：1，2和3是暂时的（当离开这些点时，我们不能绝对确定我们会回到它们）和3周期的，而4和5是经常性的（当离开这些点时，我们绝对确定我们会在某个时间回到它们）和2周期的。右边的链还有一个边，使得整条链子循环和不定期。
对于循环状态，我们可以计算平均循环时间，即离开状态时的预期返回时间。注意，即使返回概率等于1，也并不意味着预期返回时间是有限的。因此，在循环状态中，我们可以区分正循环状态（有限预期返回时间）和空循环状态（无限预期返回时间）。
稳定分布、极限行为和遍历性
在本小节中，我们讨论了用马尔可夫链描述的（随机）动态的某些方面的特性。
状态空间E上的概率分布，如果它能证明，就称为稳定分布。
因为有
然后稳定分布验证如下
根据定义，一个稳定的概率分布是这样的，它不会随时间而演化。因此，如果初始分布q是一个稳定分布，那么它将在以后所有的时间步骤中保持不变。如果状态空间是有限的，p可以用矩阵表示，可以用原始向量表示，然后我们得到：
它再一次表达了一个事实，即一个稳定的概率分布不会随着时间而发展（正如我们看到的那样，将概率分布乘以p，可以计算下一个时间步的概率分布）。注意，当且仅当不可约马尔可夫链的所有状态都是正循环时，它才具有稳定的概率分布。
与稳定概率分布有关的另一个有趣的性质是，如果链是循环正的（因此存在一个稳定分布），并且是非周期的，那么，无论初始概率是什么，当时间步数变为无穷大时，链的概率分布都会收敛：链被称为有一个极限分布，它只不过是稳定分布。一般情况下，可以写为：
让我们再次强调一个事实，即初始概率分布没有假设：链的概率分布收敛到稳定分布（链的平衡分布），而不管初始设置如何。
最后，遍历性是与马尔可夫链行为相关的另一个有趣的性质。如果一个马尔可夫链是不可约的，那么我们也说这个链是“遍历的”，因为它证明了下面的遍历定理。假设我们有一个应用程序f（.）从状态空间e转到实线（例如，每个状态下的成本）。我们可以定义这个应用程序沿给定轨迹（时间平均值）的平均值。对于第n个第一个术语，其表示为：
我们也可以用稳定分布（空间平均值）表示的集E上应用f的平均值：
然后遍历定理告诉我们，轨道无限长时的时间平均值等于空间平均值（由稳定分布加权）。遍历属性可以写为：
以另一种方式陈述，它说，在极限情况下，轨道的早期行为变得可以忽略不计，在计算时间平均值时，只有长期的稳定行为才真正重要。
回到TDS读者示例
再次考虑一下TDS读者示例。在这个简单的例子中，链显然是不可约的，非周期的，并且所有的状态都是循环正的。
为了展示可以用马尔可夫链计算的有趣的结果，我们想看看状态R（状态“访问和读取”）的平均重现时间。换言之，我们想回答以下问题：当我们的TDS读者在一天中访问和阅读时，在他访问和阅读之前，我们平均需要等待多少天？让我们试着得到一个如何计算这个值的思路。
首先，我们表示：
所以我们要在这里计算m（R，R）。离开R后第一步的推理，我们得到：
然而，这个表达式需要知道m（N，R）和m（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的平均递推时间（以及从N到R的平均时间和从V到R的平均时间）。
为了总结这个例子，让我们看看这个马尔可夫链的稳定分布是什么。为了确定稳定分布，我们必须解出下面的线性代数方程
因此，我们必须找到与特征值1相关的p的左特征向量。解决这个问题，我们得到如下的稳定分布
“TDS读者”示例的稳定分布
我们也可以注意到（r）=1/m（R，R），这是一个相当合理的身份。
由于链是不可约和非周期的，这意味着从长远来看，概率分布将收敛到稳定分布（对于任何初始化）。另一种说法是，不管我们的TDS读者的初始状态是什么，如果我们等待足够长的时间，随机选择一天，那么我们有一个概率（N），读者今天不访问，一个概率（V），读者访问但不阅读，以及一个概率（R），读者访问和阅读。为了更好地理解收敛性，让我们看一下下图，它显示了从不同起点开始的概率分布的演化和（快速）收敛到稳定分布的过程。
3种不同初始概率分布（蓝色、橙色和绿色）向稳定分布（红色）收敛的可视化。
4. 经典例子：PageRank算法
现在是时候回到PageRank了！在进一步讨论之前，我们为PageRank给出的解释并不是唯一可能的解释，而且原始论文的作者在设计方法时不一定考虑马尔可夫链。但是，下面的解释有很大的优势seo优化策略，可以很好地理解。
随机上网者
PageRank试图解决的问题是：如何使用给定集之间的现有链接对给定集的页进行排名（我们可以假设此集已被过滤，例如在某些查询上）？
为了解决这个问题并能够对页面进行排名，PageRank大致如下。
我们认为，一个随机的网络冲浪者是在其中一个网页的初始时间。然后，这个冲浪者开始随机导航，通过点击每一页，在一个链接上，导致另一个页面的考虑集（假设链接到该集以外的页面是不允许的）。对于给定的页面，所有允许的链接都有相同的被点击机会。
这里我们有一个马尔可夫链的设置：页面是不同的可能状态，从一个页面到另一个页面的链接定义了过渡概率（权重使得在每个页面上所有链接的页面都有相同的机会被选择），并且无内存属性由浏览者的行为清楚地验证。如果我们还假设定义的链是正循环和非周期的（一些小技巧被用来确保我们满足这个设置），那么在很长一段时间之后，“当前页”的概率分布收敛到稳定分布。所以，不管起始页是什么，在很长金昌seo技术培训:时间之后，如果我们选择一个随机的时间步，每个页面都有可能（几乎固定）成为当前页面。
PageRank背后的假设是，在稳定分布中最可能的页面也必须是最重要的（我们经常访问这些页面，因为它们接收来自在这个过程中访问过很多页面的链接）。稳定概率分布为每个状态定义PageRank的值。
一个小实例
为了让这一切更清楚，让我们考虑一个小例子。假设我们有一个很小的网站，有7个页面，标签从1到7，页面之间有链接，如下图所示：
为了清晰起见，在先前的表示中没有显示每个过渡的概率。但是，由于“导航”应该是纯随机的（我们也讨论了“随机行走”），因此可以使用以下简单规则轻松恢复值：对于具有K个外联的节点（具有K个链接到其他页面的页面），每个外联的概率等于1/K。因此，概率过渡矩阵是：
其中为了提高可读性0.0值已被“.”替换。在进一步计金昌seo技术培训:算之前，我们可以注意到这个马尔可夫链是不可约的，也是非周期的，因此，经过长期的运行，系统收敛到一个稳定分布。正如我们已经看到的，我们可以通过解决下面的左特征向量问题来计算这个稳定分布。
这样我们就可以得到每一页的PageRank（稳定分布的值）的下列值：
根据包含7页的小示例计算的PageRank值。
这个小网站的PageRank排名是1>7>4>2>5=6>3。
本文的主要结论
随机过程是随机变量的集合，通常随时间变化（指数通常表示离散或连续时间）。
对于随机过程，马尔可夫属性表示，考虑到目前，未来的概率与过去无关（该属性也称为“无记忆属性”）。
离散时间马尔可夫链是具有离散时间指数且验证马尔可夫性质的随机过程。
马尔可夫链的马尔可夫性质使得对这些过程的研究更加容易理解，并能得出一些有趣的显式结果（平均重现时间、稳定分布……）
对PageRank（不是唯一的）的一种可能的解释是，想象一个网页冲浪者随机地从一个页面导航到另一个页面，并将页面上的诱导稳定分布作为排名的一个因素（大致上，稳定状态下访问最多的页面必须是由其他访问最多的页面链接的页面，然后必须是最相关的）。
马尔可夫链对于处理随机动态时的问题建模是非常强大的。由于其良好的性能，它们被用于各种领域，如排队理论（优化电信网络的性能，其中消息必须经常竞争有限的资源，并在所有资源都已分配时排队），统计（众所周知的“马尔可夫链蒙特卡罗”随机变量生成技术是基于马尔可夫链的）、生物学（生物种群进化模型）、计算机科学（隐马尔可夫模型是信息论和语音识别的重要工具）等。
上一篇：SEO站内优化技术，你会实践操作吗？ 下一篇：没有了
推荐阅读
相关阅读
