定义、属性和 PageRank 示例。
引言
1998 年，劳伦斯-佩奇(Lawrence Page)、谢尔盖-布林(Sergey Brin)、拉吉夫-莫特瓦尼(Rajeev Motwani)和特里-维诺格拉德(Terry Winograd)发表了《The PageRank Citation Ranking: Bringing Order to the Web》： 这篇文章介绍了现在著名的 PageRank 算法，它是 Google 的起源。二十多年过去了，谷歌已经成为一个巨头，尽管算法已经有了很大的发展，但 PageRank 仍然是谷歌排名算法的 “象征”(尽管很少有人能真正说出它在算法中所占的比重)。
从理论角度来看，有趣的是，对 PageRank 算法的一种常见解释依赖于马尔科夫链这一简单而基本的数学概念。我们将在本文中看到，马尔可夫链是随机建模的强大工具，对任何数据科学家都很有用。尤其是，我们将回答一些基本问题，如：什么是马尔可夫链？
概要
-
第一节，我们将给出理解马尔科夫链所需的基本定义 -
第二节，我们将讨论有限状态空间马尔可夫链的特殊情况 -
第三节，我们将讨论马尔可夫链的一些基本性质，并用许多小例子来说明这些性质 -
第四节，我们将把马尔可夫链与 PageRank 算法联系起来，并通过一个玩具示例了解马尔可夫链如何用于图节点的排序。
什么是马尔可夫链？
随机变量和随机过程
在介绍马尔可夫链之前，让我们先快速回顾一下概率论中一些基本但重要的概念。 首先，在非数学术语中，随机变量 是一个变量，其值被定义为随机现象的结果。这个结果可以是一个数字(或 “类数字”，包括向量)，也可以不是。例如，我们可以将随机变量定义为掷骰子的结果(数字)以及掷硬币的输出结果(不是数字，除非你指定 0 为正面，1 为背面)。还要注意的是，随机变量的可能结果空间可以是离散的，也可以是连续的：例如，正态随机变量是连续的，而泊松随机变量是离散的。
因此，我们可以将随机过程定义为以集合 为索引的随机变量集合，这些随机变量通常代表时间的不同时刻(下文中我们将假设这一点)。最常见的两种情况是： 是自然数集(离散时间随机过程)或 是实数集(连续时间随机过程)。例如，每天掷一枚硬币定义了一个离散时间随机过程，而股票市场期权价格的连续变化则定义了一个连续时间随机过程。不同时间瞬间的随机变量可以相互独立(以掷硬币为例)，也可以以某种方式相互依赖(以股票价格为例)，而且它们的状态空间(每个时间瞬间可能出现的结果的空间)可以是连续的，也可以是离散的。
不同类型的随机过程(空间/时间上的离散/连续)。
马尔可夫性质和马尔可夫链
有一些众所周知的随机过程系列：高斯过程、泊松过程、自回归模型、移动平均模型、马尔可夫链等。这些特殊情况各自具有特定的性质，使我们能够更好地研究和理解它们。
“马尔可夫性质”使得随机过程的研究更为简便。对于一个随机过程，已知当下状态后，获取更多的过去信息并不会对未来的行为提供额外帮助。更正式地说，在任何时刻，给定当前状态，未来状态的条件分布仅依赖于当前状态，而不受过去状态的影响，这被称为无记忆性质。符合这一性质的随机过程称为马尔可夫过程。
马尔可夫特性表达了这样一个事实：在给定的时间步长内，在知道当前状态的情况下，我们不必通过收集过去的信息来获得关于未来的任何信息，只与当前相关。
根据前面的定义，我们现在可以定义 “同源离散时间马尔科夫链”(为简单起见，下文中将用 “马尔科夫链 ”表示)。马尔科夫链**是一个具有离散时间和离散状态空间的马尔科夫过程。因此，马尔科夫链是一个离散的状态序列，每个状态都来自一个离散的状态空间(有限或非有限)，并且遵循马尔科夫性质。
在数学上，我们可以用以下方式表示马尔科夫链:
在每一时刻，过程在离散集合 中取值，使得:
那么，马尔可夫特性意味着我们有:
请再次注意，最后一个公式表达了这样一个事实：对于给定的历史状态(我现在的位置和我之前的位置)，下一个状态(我下一步去哪里)的概率分布只取决于当前的状态，而不取决于过去的状态。
我们决定在这篇介绍性文章中只描述基本的同质离散时间马尔可夫链。然而，也存在非同质(时间相关)和/或时间连续马尔科夫链。下面我们将不讨论模型的这些变体。还要注意的是，上面给出的马尔可夫性质的定义是极其简化的：真正的数学定义涉及过滤的概念，这远远超出了这篇简短介绍的范围。
描述马尔可夫链的随机动态
我们在上一小节中介绍了与任何马尔可夫链相匹配的一般框架。现在让我们来看看我们需要什么来定义这样一个随机过程的具体 “实例”。
首先要注意的是，如果离散时间随机过程没有验证马尔可夫性质，那么，它的全部特征描述可能会很麻烦：给定时间的概率分布可能取决于过去和/或未来的一个或多个时间点。所有这些可能的时间依赖性使得对过程的任何适当描述都变得困难。
然而，得益于马尔可夫特性，马尔可夫链的动态定义非常容易。事实上，我们只需要指定两样东西：初始概率分布(即时间 n=0 时刻的概率分布)，记为:
和一个过渡概率核(给出了任何2个状态之间，在 时间成功进入另一个状态的概率)，记为： 过渡概率核：
有了前两个已知对象，过程的全部(概率)动态就得到了很好的定义。事实上，过程中任何实现的概率都可以通过循环方式计算出来。
例如，假设我们想知道进程的前三个状态为 的概率。因此，我们要计算的概率是:
在这里，我们使用总概率定律，即出现 的概率等于先出现 的概率乘以之前出现 的概率，再乘以之前依次出现 和 的概率乘以最后出现 s2 的概率。数学上可以写成:
这就需要马尔可夫假设带来的简化。事实上，对于长链，我们可以得到最后状态的条件概率。然而，在马尔可夫情况下，我们可以利用以下条件简化这一表达式:
这样:
由于它们完全表征了过程的概率动态，因此许多其他更复杂的事件只需根据初始概率分布 和过渡概率核 即可计算。
有限状态空间马尔可夫链
矩阵和图表示
在此，我们假设 中可能存在的状态数量为 ：
那么，初始概率分布可以用一个大小为 的行向量 来描述，过渡概率可以用一个大小为 乘 的矩阵 来描述，即:
这种符号的好处在于如果我们用原始向量 表示第 步的概率分布，其分量由以下公式给出:
那么此后的简单矩阵关系成立:
将代表某一时间步概率分布的行向量与过渡概率矩阵右乘，就能得到下一时间步的概率分布。
因此，从这里我们可以看出，将概率分布从某一步演化到下一步，就像将初始步骤的行概率向量与矩阵 右乘一样简单。
有限状态空间马尔可夫链的随机动态可以很容易地表示为有值定向图，图中的每个节点都是一个状态，对于所有状态对 ，如果 ，则存在一条从 到 的边。
示例：《走向数据科学》阅读器
让我们举一个简单的例子来说明这一切。考虑一个虚构的《走向数据科学》读者的日常行为。每天有三种可能的状态：读者这天没有访问 TDS(N)，读者访问了 TDS 但没有阅读完整的文章(V)，读者访问了 TDS 并至少阅读了一篇完整的文章(R)。因此，我们有以下状态空间:
假设在第一天，该读者有 50% 的概率只访问 TDS，有 50% 的概率访问 TDS 并阅读至少一篇文章。那么描述初始概率分布( )的向量为:
再假设观察到以下概率：
-
当读者一天没有访问 TDS 时，他第二天仍有 25%的概率不访问，50%的概率只访问，25%的概率访问并阅读 -
当读者访问 TDS 一天而没有阅读时，他第二天再次访问而不阅读的几率为 50%，访问并阅读的几率为 50% -
当读者访问并阅读一天后，他第二天不访问的几率为 33%，只访问的几率为 33%，再次访问并阅读的几率为 34%
那么，我们有如下过渡矩阵:
根据上一小节，我们知道如何为该读者计算第二天 的每种状态的概率:
最后，这个马尔可夫链的概率动态可以用图形表示如下:
模拟我们虚构的 TDS 阅读器行为的马尔可夫链图。
马尔可夫链特性
在本节中，我们将只给出马尔科夫链的一些基本性质或特征。我们的目的不是深入研究数学细节，而是概述使用马尔可夫链时需要研究的兴趣点。我们已经看到，在有限状态空间情况下，我们可以将马尔科夫链描绘成一个图，因此我们将使用图来说明下面的一些特性。但是，我们应该记住，这些性质并不一定局限于有限状态空间情况。
可重复性、周期性、短暂性和递归性
在本小节中，让我们从描述状态或整个马尔可夫链的一些经典方法开始。 首先，如果可以从任何其他状态(不一定在一个时间步内)到达任何状态，我们就说马尔科夫链是可还原的。如果状态空间是有限的，并且链可以用图表示，那么我们可以说不可还原马尔可夫链的图是强连接的(图论)。
不可还原性说明。左边的链不是不可还原的：我们无法从 3 或 4 到达 1 或 2。右边的链(添加了一条边)是不可还原的：每个状态都可以从任何其他状态到达。
如果离开一个状态时，返回该状态需要 k 个时间步的倍数（k 是所有可能返回路径长度的最大公约数），则该状态具有周期 k。如果 k = 1，则称该状态为非周期性状态；如果整个马尔可夫链的所有状态都是非周期性的，则称该链为非周期性链。对于不可还原马尔可夫链，我们还可以提到这样一个事实：如果一个状态是非周期性的，那么所有状态都是非周期性的。
周期属性图解。左边的链是 2 周期的：当离开任何状态时，总是需要 2 步的倍数才能回到该状态。右边的链是 3 周期的。
如果当我们离开这个状态时，有一个非零的概率是我们永远不会回到这个状态，那么这个状态就是短暂的。反之，如果我们知道在离开该状态后，我们会在未来以 1 的概率回到该状态(如果该状态不是短暂的)，那么该状态就是重复的。
递推/递变性质图解。左边的链条是这样的 1、2 和 3 是瞬时的(当我们离开这些点时，我们不能绝对肯定我们会回到这些点)和 3 周期的，而 4 和 5 是经常的(当我们离开这些点时，我们绝对肯定我们会在某个时候回到这些点)和 2 周期的。右边的链多了一条边，使得整条链成为循环和非周期性的。
对于循环状态，我们可以计算出平均循环时间，即离开该状态时的预期返回时间。请注意，即使返回概率等于 1，也并不意味着预期返回时间是有限的。因此，在递归状态中，我们可以区分正递归状态(有限的预期返回时间)和空递归状态(无限的预期返回时间)。
静态分布、极限行为和遍历性
在本小节中，我们将讨论马尔科夫链所描述的(随机)动态的某些特性。
如果状态空间 上的概率分布 符合以下条件，则称其为稳态分布:
正如我们:
-
为当前状态的为 的概率 -
为在下一步概率为 的概率 那么静态分布验证了， 当前状态为 的概率等于下一步状态为 的概率。 根据定义，静态概率分布不会随时间变化。因此，如果初始分布 是静态分布，那么它在未来的所有时间步中都将保持不变。如果状态空间是有限的，那么 可以用矩阵来表示， 可以用原始向量来表示，我们就可以得出:
它再次表达了一个事实，即静态概率分布不会随着时间的推移而变化(正如我们看到的那样，概率分布乘以 就可以计算出下一个时间步的概率分布)。请注意，当且仅当不可还原马尔可夫链的所有状态都是正循环时，该链才具有静态概率分布。
与静态概率分布相关的另一个有趣性质如下。如果链是正循环(因此存在静态分布)和非周期性的，那么无论初始概率是多少，当时间步长达到无穷大时，链的概率分布都会收敛：链被称为有一个极限分布，它就是静态分布。在一般情况下，可以写成:
让我们再次强调一个事实，即初始概率分布不存在任何假设：无论初始设定如何，链的概率分布都会收敛到静态分布(链的均衡分布)。
最后，极性是与马尔可夫链行为相关的另一个有趣性质。如果马尔可夫链是不可还原的，那么我们也可以说这个链是 “遍历的”，因为它验证了下面的遍历定理。假设我们有一个从状态空间 到实线的应用 f(.)(例如，它可以是处于每个状态的成本)。我们可以定义这个应用沿着给定轨迹的平均值(时间平均值)。对于第 n 个第一项，其表示为:
我们还可以计算应用 在集合 上的平均值，该值由静态分布(空间平均值)加权，表示为:
然后，遍历定理告诉我们，当轨迹变得无限长时，时间平均值等于空间平均值(按静态分布加权)。遍历性质可以写成:
换一种说法就是，在极限状态下，轨迹的早期行为变得可以忽略不计，在计算时间平均值时，只有长期的静态行为才真正重要。
回到我们的 TDS 阅读器示例
我们再来看看 TDS 阅读器的例子。在这个简单的例子中，链显然是不可还原的、非周期性的，而且所有状态都是正循环。
为了展示马尔可夫链可以计算出的有趣结果，我们想看看状态 (“访问并读取 ”状态)的平均递归时间。换句话说，我们想回答以下问题：当我们的 TDS 阅读器在某一天访问并阅读时，平均需要等待多少天才能再次访问并阅读？让我们试着直观地了解一下如何计算这个值。
首先，我们用:
因此，我们要在这里计算 。根据离开 后到达的第一步推理，我们得到:
然而，要计算 ，需要知道 和 )。这两个量可以用相同的方法表示:
因此，我们有 3 个方程和 3 个未知数，求解这个系统时，我们得到 ， ， 。因此，状态 的平均重现时间值为 。因此，我们看到，通过一些线性代数，我们成功地计算出了状态 的平均重现时间(以及从 到 的平均时间和从 到 的平均时间)。
最后，我们来看看这条马尔科夫链的静态分布。要确定静态分布，我们必须求解下面的线性代数方程:
因此，我们必须找到与特征值 1 相关的 的左特征向量。解决这个问题，我们可以得到如下静态分布:
我们的 “TDS 阅读器 ”示例的静态分布。
我们还可以注意到一个事实： ，稍加思考就会发现这是一个非常合乎逻辑的特性(但我们不会在这篇文章中提供更多细节)。
由于该链是不可还原和非周期性的，这意味着从长远来看，概率分布将收敛于静态分布(对于任何初始化)。换句话说，无论 TDS 阅读的初始状态如何，只要我们等待足够长的时间并随机选取一天，那么这一天读者不访问的概率 、读者访问但不阅读的概率 以及读者访问并阅读的概率 就会出现。为了更好地理解这一收敛特性，让我们看看下面的图表，它显示了从不同起点开始的概率分布的演变过程，以及(快速)收敛到静态分布的过程:
三种不同初始化概率分布(蓝色、橙色和绿色)向静态分布(红色)收敛的可视化效果。
经典案例：PageRank 算法
现在该回到 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。
收获
本文的主要启示如下：
-
随机过程是随机变量的集合，通常以时间为索引(索引通常代表离散时间或连续时间) -
对于随机过程，马尔可夫性质表明，给定现在，未来的概率与过去无关(此性质也称为 "无记忆性质) -
离散时间马尔可夫链是具有离散时间指数的随机过程，它验证了马尔可夫性质 -
马尔可夫链的马尔可夫特性使得对这些过程的研究变得更加容易，并可以推导出一些有趣的明确结果(平均递推时间、静态分布......)。 -
对 PageRank 的一种可能的解释(并非唯一的解释)是，想象一个网络冲浪者随机地从一个网页浏览到另一个网页，并将网页的静态分布作为排名的一个因素(大致上，在稳态中访问量最大的网页一定是被其他访问量非常大的网页链接的网页，然后一定是最相关的网页)。
最后，让我们再次强调马尔可夫链在处理随机动态问题时的强大建模功能。由于马尔可夫链的良好特性，它被广泛应用于各个领域，如排队论(优化电信网络的性能，在这种网络中，信息必须经常争夺有限的资源，当所有资源都已分配完毕时，信息就会被排队)、统计学(众所周知的“马尔可夫链蒙特卡罗”随机变量生成技术就是基于马尔可夫链)、生物学(生物种群进化建模)、计算机科学(隐马尔可夫模型 是信息论和语音识别的重要工具)等。
显然，马尔可夫链在建模和计算方面所提供的巨大可能性远远超出了本文所介绍的内容，因此，我们鼓励感兴趣的读者阅读更多有关这些工具的资料，它们在(数据)科学家的工具箱中完全占有一席之地。
感谢您的阅读！