8.1 马尔可夫模型 (Markov Models)
在之前的笔记中，我们讨论了贝叶斯网络，以及它们是如何用于紧凑地表示随机变量之间关系的绝妙结构。我们现在将介绍一种本质上相关的结构，称为马尔可夫模型 (Markov model)，出于本课程的目的，可以将其视为类似于链状、无限长度的贝叶斯网络。我们在本节中使用的运行示例是天气模式的日常波动。我们的天气模型将是时间依赖的 (time-dependent)（就像一般的马尔可夫模型一样），这意味着我们将为每一天的天气有一个单独的随机变量。如果我们定义 \(W_i\) 为代表第 \(i\) 天天气的随机变量，我们的天气示例的马尔可夫模型将如下所示：
我们应该存储关于马尔可夫模型中涉及的随机变量的什么信息？为了跟踪我们正在考虑的量（在这种情况下是天气）如何随时间变化，我们需要知道它在时间 \(t = 0\) 的初始分布 (initial distribution) 和某种转移模型 (transition model)，该模型表征了在时间步之间从一个状态移动到另一个状态的概率。马尔可夫模型的初始分布由 \(P(W_0)\) 给出的概率表枚举，从状态 \(i\) 转移到 \(i + 1\) 的转移模型由 \(P(W_{i+1} | W_i)\) 给出。注意，这个转移模型意味着 \(W_{i+1}\) 的值仅条件依赖于 \(W_i\) 的值。换句话说，时间 \(t = i + 1\) 的天气满足马尔可夫性质 (Markov property) 或无记忆性质 (memoryless property)，并且独立于除 \(t = i\) 之外的所有其他时间步的天气。
使用我们的天气马尔可夫模型，如果我们想使用链式法则重建 \(W_0\)、\(W_1\) 和 \(W_2\) 之间的联合分布，我们会想要：
\(P(W_0, W_1, W_2) = P(W_0)P(W_1 | W_0)P(W_2 | W_1, W_0)\)
然而，根据我们的假设，即马尔可夫性质成立且 \(W_0 \perp W_2 | W_1\)，联合分布简化为：
\(P(W_0, W_1, W_2) = P(W_0)P(W_1 | W_0)P(W_2 | W_1)\)
我们拥有从马尔可夫模型计算此所需的一切。更一般地说，马尔可夫模型在每个时间步做出以下独立性假设：\(W_{i+1} \perp \{W_0, \dots, W_{i-1}\} | W_i\)。这允许我们通过链式法则如下重建前 \(n + 1\) 个变量的联合分布：
\(P(W_0, W_1, \dots, W_n) = P(W_0)P(W_1|W_0)P(W_2|W_1)\dots P(W_n|W_{n-1}) = P(W_0)\prod_{i=0}^{n-1}P(W_{i+1}|W_{i})\)
马尔可夫模型中通常做出的最后一个假设是转移模型是平稳的 (stationary)。换句话说，对于所有的 \(i\) 值（所有时间步），\(P(W_{i+1} | W_i)\) 是相同的。这允许我们仅用两个表来表示马尔可夫模型：一个用于 \(P(W_0)\)，一个用于 \(P(W_{i+1} | W_i)\)。
8.1.1 迷你前向算法 (The Mini-Forward Algorithm)
我们现在知道如何计算马尔可夫模型跨时间步的联合分布。然而，这并没有明确帮助我们回答关于某个给定日期 \(t\) 的天气分布的问题。自然地，我们可以计算联合分布，然后对所有其他变量进行边缘化 (marginalize)（求和消元），但这通常效率极低，因为如果我们有 \(j\) 个变量，每个变量可以取 \(d\) 个值，则联合分布的大小为 \(O(d^j)\)。相反，我们将介绍一种更有效的技术，称为迷你前向算法 (mini-forward algorithm)。
它的工作原理如下。根据边缘化的性质，我们知道
\[P(W_{i+1}) = \sum_{w_i}P(w_i, W_{i+1})\]根据链式法则，我们可以将其重新表达如下：
\(\boxed{P(W_{i+1}) = \sum_{w_i}P(W_{i+1}|w_i)P(w_i)}\)
这个方程应该有一些直观的意义——为了计算时间步 \(i + 1\) 的天气分布，我们查看由 \(P(W_i)\) 给出的时间步 \(i\) 的概率分布，并使用我们的转移模型 \(P(W_{i+1} | W_i)\) 将此模型“推进”一个时间步。有了这个方程，我们可以通过从我们的初始分布 \(P(W_0)\) 开始并使用它来计算 \(P(W_1)\)，然后依次使用 \(P(W_1)\) 来计算 \(P(W_2)\)，依此类推，从而迭代地计算我们选择的任何时间步的天气分布。让我们通过一个例子来演示，使用以下初始分布和转移模型：
| \(W_0\) | \(P(W_0)\) |
|---|---|
| sun | 0.8 |
| rain | 0.2 |
| \(W_{i+1}\) | \(W_i\) | \(P(W_{i+1} | W_i)\) |
|---|---|---|
| sun | sun | 0.6 |
| rain | sun | 0.4 |
| sun | rain | 0.1 |
| rain | rain | 0.9 |
使用迷你前向算法，我们可以如下计算 \(P(W_1)\)：
\(P(W_1 = sun) = \sum_{w_0}P(W_1 = sun | w_0)P(w_0)\) \(= P(W_1 = sun | W_0 = sun)P(W_0 = sun) + P(W_1 = sun | W_0 = rain)P(W_0 = rain)\) \(= 0.6 \cdot 0.8 + 0.1 \cdot 0.2 = \boxed{0.5}\)
\(P(W_1 = rain) = \sum_{w_0}P(W_1 = rain | w_0)P(w_0)\) \(= P(W_1 = rain | W_0 = sun)P(W_0 = sun) + P(W_1 = rain | W_0 = rain)P(W_0 = rain)\) \(= 0.4 \cdot 0.8 + 0.9 \cdot 0.2 = \boxed{0.5}\)
因此我们 \(P(W_1)\) 的分布是：
| \(W_1\) | \(P(W_1)\) |
|---|---|
| sun | 0.5 |
| rain | 0.5 |
值得注意的是，晴天的概率从时间 \(t = 0\) 的 80% 下降到时间 \(t = 1\) 的仅 50%。这是我们转移模型的直接结果，该模型倾向于过渡到雨天而不是晴天。这引出了一个自然的后续问题：在给定的时间步处于某种状态的概率是否会收敛？我们将在下一节中解决这个问题的答案。
8.1.2 平稳分布 (Stationary Distribution)
为了解决上述问题，我们必须计算天气的平稳分布 (stationary distribution)。顾名思义，平稳分布是指随着时间的推移保持不变的分布，即
\[P(W_{t+1}) = P(W_t)\]我们可以通过将上述等价性与迷你前向算法使用的相同方程相结合，来计算处于给定状态的这些收敛概率：
\[P(W_{t+1}) = P(W_t) = \sum_{w_t}P(W_{t+1} | w_t)P(w_t)\]对于我们的天气示例，这给了我们以下两个方程：
\(P(W_t = sun) = P(W_{t+1} = sun | W_t = sun)P(W_t = sun) + P(W_{t+1} = sun | W_t = rain)P(W_t = rain)\) \(= 0.6 \cdot P(W_t = sun) + 0.1 \cdot P(W_t = rain)\)
\(P(W_t = rain) = P(W_{t+1} = rain | W_t = sun)P(W_t = sun) + P(W_{t+1} = rain | W_t = rain)P(W_t = rain)\) \(= 0.4 \cdot P(W_t = sun) + 0.9 \cdot P(W_t = rain)\)
现在我们有两个未知数的两个方程。为了求解，请注意这些概率之和必须等于 1，即
\[P(W_t = sun) + P(W_t = rain) = 1\]因此，如果我们令 \(x = P(W_t = sun)\) 和 \(y = P(W_t = rain)\)，我们可以写出以下方程组：
- \[x + y = 1\]
- \[0.6x + 0.1y = x\]
- \[0.4x + 0.9y = y\]
使用第一个方程，我们可以将 \(y = 1 - x\) 代入其他两个方程，这给了我们一个未知数的单个方程：
\[0.6x + 0.1(1 - x) = x\]求解该方程得出 \(x = 1/5\)，将此值代入第一个方程得出 \(y = 4/5\)。因此，我们的平稳分布是：
| \(W\) | \(P(W)\) |
|---|---|
| sun | 0.2 |
| rain | 0.8 |
从这个结果，我们可以得出结论，随着我们进行迷你前向算法并让时间趋于无穷大，下雨的概率收敛到 80%。这是我们转移模型的另一个直接结果，该模型倾向于过渡到雨天而不是晴天。