马尔可夫链通俗解释（马尔可夫链是个什么鬼）

马尔可夫链通俗解释（马尔可夫链是个什么鬼）随机变量和随机过程什么是马尔可夫链？大纲在第一部分中，我们将给出理解马尔可夫链所需的基本定义。在第二节中，我们将讨论有限状态空间马尔可夫链的特殊情况。然后，在第三部分中，我们将讨论马尔可夫链的一些基本属性，并将用许多小例子来说明这些属性。最后，在第四部分中，我们将使用PageRank算法建立链接，并在玩具示例上查看Markov链如何用于对图表的节点进行排名。注意，本文要求概率和线性代数的基础知识。特别是，将使用以下概念：条件概率、特征向量和总概率定律。

点击上方关注，All in AI中国

这篇文章是与Baptiste Rocca共同撰写的。

介绍

1998年，Lawrence Page，Sergey Brin，Rajeev Motwani和Terry Winograd发表了《PageRank引用排行：让网络变得有序》这篇文章，他们介绍了现在著名的PageRank算法。二十多年后的今天，谷歌已经成为一个巨人，即使算法已经发展很大，PageRank仍然是谷歌排名算法的一个“象征”（即使很少有人能真正说出它在算法中占据的权重）。

从理论的角度来看，值得注意的是，PageRank算法的一种常见解释依赖于马尔可夫链简单但基本的数学概念。我们将在本文中看到马尔可夫链是随机建模的强大工具，它对任何数据科学家都有用。更具体地说，我们将回答一些基本问题，例如：什么是马尔可夫链，他们有什么好的属性以及可以用它们做些什么？

大纲

在第一部分中，我们将给出理解马尔可夫链所需的基本定义。在第二节中，我们将讨论有限状态空间马尔可夫链的特殊情况。然后，在第三部分中，我们将讨论马尔可夫链的一些基本属性，并将用许多小例子来说明这些属性。最后，在第四部分中，我们将使用PageRank算法建立链接，并在玩具示例上查看Markov链如何用于对图表的节点进行排名。

注意，本文要求概率和线性代数的基础知识。特别是，将使用以下概念：条件概率、特征向量和总概率定律。

什么是马尔可夫链？

随机变量和随机过程

在介绍马尔可夫链之前，让我们先快速回顾一下概率论的一些基本但重要的概念。

首先，在非数学术语中，随机变量X是一个变量，其值被定义为随机现象的结果。该结果可以是数字（或“数字类似”，包括向量）或不是。例如，我们可以定义一个随机变量作为滚动骰子（数字）的结果以及翻转硬币的输出（不是数字，除非您指定例如0到头部和1到尾部）。还要注意，随机变量的可能结果的空间可以是离散的或连续的：例如，正常随机变量是连续的，而泊松随机变量是离散的。

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

不同类型的随机过程（离散/连续的空间/时间）

马尔可夫性质和马尔可夫链

存在一些众所周知的随机过程族：高斯过程、泊松过程、自回归模型、移动平均模型、马尔可夫链等。这些特殊情况各自具有特定属性，使我们能够更好地研究和理解它们。

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

马尔可夫性质表达了一个事实，即给定时间步长且知道当前状态，我们将不会通过收集有关过去的信息获得有关未来的任何信息。

基于先前的定义，我们现在可以定义“同质离散时间马尔可夫链”（为了简单起见，将在下文中将其表示为“马尔可夫链”）。马尔可夫链是具有离散时间和离散状态空间的马尔可夫过程。因此，马尔可夫链是一个离散的状态序列，每个状态都来自一个离散的状态空间（有限或无有限），并且遵循马尔可夫性质。

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

在任意时刻、过程在离散集E中的值，

那么，马尔可夫性质意味着我们拥有

再次注意，这最后一个公式表达了这样一个事实：对于给定的历史（我现在和我之前的位置），下一个状态（我下一步）的概率分布仅取决于当前状态而不是过去的状态。

注意，我们决定在这篇介绍性文章中仅描述基本的同质离散时间马尔可夫链。然而，也存在不均匀的（时间依赖的）和/或时间连续的马尔可夫链。我们不会在下面讨论该模型的这些变体。另请注意，上面给出的马尔可夫性质的定义极为简化：真正的数学定义涉及过滤的概念，这远远超出了本文简单介绍的范围。

表征马尔可夫链的随机动态

我们在前一小节中介绍了一个由任意马尔可夫链匹配的通用框架。现在让我们看看需要什么来定义这种随机过程的特定“实例”。

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

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

和一个转移概率核（它给出了任意一对状态在n 1时刻的状态在n时刻成功的概率）

通过已知的前两个对象，可以很好地定义过程的完整（概率）动态。实际上，这个过程的任何实现的概率都可以以一种循环的方式计算出来。

例如，假设我们想要知道过程的前3个状态的概率是（s0，s1，s2）。我们要计算概率

在这里，我们使用总概率定律，表明具有（s0，s1，s2）的概率，等于具有第一个s0的概率，乘以在已知s0的情况下s1的概率，乘以在已知s0和s1的情况下s2的概率。

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

这样我们就有了

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

有限状态空间马尔可夫链

矩阵和图形表示

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

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

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

然后，简单的矩阵关系成立

（此处不会详细说明，但可以很容易地找到）。

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

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

有限状态空间马尔可夫链的随机动态可以很容易地表示为一个有价值的有向图，这样图中的每个节点都是一个状态，对于所有状态对（ei，ej），存在从ei到ei的边缘。 ej如果p（ei，ej）> 0。然后，边缘的值是相同的概率p（ei，ej）。

示例：面向数据科学的读者

我们举一个简单的例子来说明这一切。考虑虚构的数据科学读者的日常行为。对于每一天，有3种可能的状态：读者今天不访问TDS（N），读者访问TDS但没有阅读完整帖子（V）并且读者访问TDS并阅读至少一篇完整帖子（R）。所以，我们得到以下情况

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

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

• 如果读者不是每天访问TDS，那么第二天他仍然有25%的机会不访问TDS 50%的机会只访问TDS 25%的机会访问和阅读TDS
• 当读者一天不阅读就访问TDS时，他有50%的机会在第二天不阅读的情况下再次访问TDS 50%的机会是访问和阅读
• 当读者每天访问和阅读时，他有33%的机会在第二天不访问(希望这篇文章不会有这种效果!)，33%的机会只访问和34%的机会再次访问和阅读

然后，我们有以下迁移矩阵

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

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

马尔可夫链的图形表示模拟我们虚构的TDS阅读器行为

马尔可夫链属性

在本节中，我们仅提供一些基本的马尔可夫链属性或特征。我们的想法不是要深入研究数学细节，而是更多地概述使用马尔可夫链时需要研究的兴趣点。正如我们已经看到的那样，在有限状态空间的情况下，我们可以将马尔可夫链描绘成图形，注意我们将使用图形表示来说明下面的一些属性。但是，应该记住，这些属性不一定限于有限状态空间的情况。

不可约性，重现性，周期性和遍历性

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

首先，我们说马尔可夫链是不可约的，如果它可以从其他状态到达任何一种状态（不一定是在一个时间步骤）。如果状态空间是有限的，如果状态空间是有限的，链可以用图表来表示，那么我们可以说不可约马尔可夫链的图是强连通的（图论）。

不可约性的例证。左边的链不是不可简化的：从3或4我们不能达到1或2右边的链（已经添加了一条边）是不可约的：可以从任何其他状态到达每个状态。

一个状态的周期是k，如果在离开它时，任何返回到该状态都需要多个k个时间步长（k是所有可能的返回路径长度的最大公约数）。如果k = 1，那么该状态被认为是非周期性的，并且如果其所有状态都是非周期性的话，则整个马尔可夫链是非周期性的。对于不可约的马尔可夫链，我们还可以提到这样的事实：如果一个状态是非周期性的，则所有状态都是非周期性的。

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

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

遍历/周期性的例证。左边的链是这样的：1、2和3是瞬态的（当离开这些点时，我们不能完全确定会回到它们）和3-periodic，而4和5具备重复性（当离开这些时我们肯定会在某个时间回到他们身上）还有2-periodic。右侧的链条还有一条边缘，使整条链具有周期性和非周期性。

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

固定分布、限制行为和遍历性

在本小节中，我们讨论了表征马尔可夫链描述的（随机）动态的某些方面的特征。

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

像我们一样

然后平稳分布验证

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

再一次，它表达了一个事实，即平稳的概率分布不会随着时间的推移而发展（正如我们所看到的那样，权利乘以概率分布乘以p可以计算下一时间步长的概率分布）。请注意，当且仅当所有状态都是正向重复时，不可约马尔可夫链具有平稳概率分布。

与平稳概率分布相关的另一个有趣的属性如下。如果链是复发性正（所以存在一个平稳分布）和非周期的话，不管最初的概率是什么，链条的概率分布，当时间步长趋于无穷收敛：据说这条链的限制分布只不过是平稳分布。在一般情况下，它可以写成

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

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

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

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

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

回到我们的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个不同初始化概率分布（蓝色，橙色和绿色）向平稳分布（红色）的收敛。

一个经典的例子：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。

小贴士

本文的主要内容如下：

• 随机过程是随机变量的集合，通常随时间变化索引（索引通常表示离散时间或连续时间）
• 对于随机过程，Markov属性表示，鉴于目前，未来的概率与过去无关（该属性也称为“无记忆属性”）
• 离散时间马尔可夫链是具有离散时间指数的随机过程，并且验证马尔可夫性质
• 马尔可夫链的马尔可夫性质使得对这些过程的研究更容易处理，并且可以得出一些有趣的显式结果（平均递归时间、平稳分布......）
• 对PageRank（不是唯一的）的一种可能的解释在于想象一个上网的人，它随机地从一个页面导航到另一个页面，并将诱导的平稳分布作为排名因素（粗略地说，稳定状态下访问量最大的页面）必须是由其他访问过的页面链接的那个，然后必须是最相关的页面）

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

显然，马尔可夫链在建模和计算方面提供的巨大可能性远远落后于这种适度的介绍，因此，我们鼓励有兴趣的读者阅读更多有关这些工具的信息。

谢谢阅读！

编译出品