8.2 隐马尔可夫模型 (Hidden Markov Models)

使用马尔可夫模型，我们看到了如何通过随机变量链来合并随时间的变化。例如，如果我们想用上面的标准马尔可夫模型知道第 10 天的天气，我们可以从初始分布 $P(W_0)$ 开始，并使用带有我们转移模型的迷你前向算法来计算 $P(W_{10})$。然而，在时间 $t = 0$ 和时间 $t = 10$ 之间，我们可能会收集新的气象证据，这些证据可能会影响我们对任何给定时间步天气概率分布的信念。简单来说，如果天气预报预测第 10 天有 80% 的几率下雨，但第 9 天晚上天空晴朗，那么 80% 的概率可能会急剧下降。这正是隐马尔可夫模型 (Hidden Markov Model) 帮助我们的地方——它允许我们在每个时间步观察一些证据，这可能会影响每个状态的信念分布。我们的天气模型的隐马尔可夫模型可以使用如下所示的贝叶斯网络结构来描述：

Weather HMM

与普通马尔可夫模型不同，我们现在有两种不同类型的节点。为了区分，我们将每个 $W_i$ 称为状态变量 (state variable)，将每个天气预报 $F_i$ 称为证据变量 (evidence variable)。由于 $W_i$ 编码了我们对第 $i$ 天天气概率分布的信念，因此第 $i$ 天的天气预报条件依赖于这种信念应该是一个自然的结果。该模型暗示了与标准马尔可夫模型相似的条件独立关系，并为证据变量增加了一组关系：

\[F_1 \perp W_0 \mid W_1\] \[\forall i = 2, \dots, n; \quad W_i \perp \{W_0, \dots, W_{i-2}, F_1, \dots, F_{i-1}\} \mid W_{i-1}\] \[\forall i = 2, \dots, n; \quad F_i \perp \{W_0, \dots, W_{i-1}, F_1, \dots, F_{i-1}\} \mid W_i\]

就像马尔可夫模型一样，隐马尔可夫模型假设转移模型 $P(W_{i+1} \mid W_i)$ 是平稳的。隐马尔可夫模型做出了额外的简化假设，即传感器模型 (sensor model) $P(F_i \mid W_i)$ 也是平稳的。因此，任何隐马尔可夫模型都可以仅用三个概率表来紧凑地表示：初始分布、转移模型和传感器模型。

作为关于符号的最后一点，我们将定义在观察到截至目前的所有证据 $F_1, \dots, F_i$ 的情况下，时间 $i$ 的信念分布 (belief distribution)：

\[B(W_i) = P(W_i \mid f_1, \dots, f_i)\]

同样，我们将定义 $B'(W_i)$ 为在观察到证据 $f_1, \dots, f_{i-1}$ 的情况下，时间 $i$ 的信念分布：

\[B'(W_i) = P(W_i \mid f_1, \dots, f_{i-1})\]

定义 $e_i$ 为在时间步 $i$ 观察到的证据，你有时候可能会看到从时间步 $1 \leq i \leq t$ 的聚合证据重新表达为以下形式：

\[e_{1:t} = e_1, \dots, e_t\]

在这种符号下，$P(W_i \mid f_1, \dots, f_{i-1})$ 可以写成 $P(W_i \mid f_{1:(i-1)})$。这种符号将在接下来的部分中变得相关，我们将讨论将新证据迭代地合并到我们的天气模型中的时间流逝更新。

8.2.1 前向算法 (The Forward Algorithm)

使用上述条件概率假设和条件概率表的边缘化性质，我们可以推导出 $B(W_i)$ 和 $B'(W_{i+1})$ 之间的关系，该关系与迷你前向算法的更新规则形式相同。我们首先使用边缘化：

\[B'(W_{i+1}) = P(W_{i+1} \mid f_1, \dots, f_i) = \sum_{w_i}P(W_{i+1}, w_i \mid f_1, \dots, f_i)\]

然后可以用链式法则将其重新表达如下：

\[B'(W_{i+1}) = P(W_{i+1} \mid f_1, \dots, f_i) = \sum_{w_i}P(W_{i+1} \mid w_i, f_1, \dots, f_i)P(w_i \mid f_1, \dots, f_i)\]

注意到 $P(w_i \mid f_1, \dots, f_i)$ 仅仅是 $B(w_i)$ 并且 $W_{i+1} \perp \{f_1, \dots f_i\} \mid W_i$，这简化为我们 $B(W_i)$ 和 $B'(W_{i+1})$ 之间的最终关系：

\[\boxed{B'(W_{i+1}) = \sum_{w_i}P(W_{i+1} \mid w_i)B(w_i)}\]

现在让我们考虑如何推导出 $B'(W_{i+1})$ 和 $B(W_{i+1})$ 之间的关系。通过应用条件概率的定义（带有额外的条件），我们可以看到

\[B(W_{i+1}) = P(W_{i+1} | f_1, ..., f_{i+1}) = \frac{P(W_{i+1}, f_{i+1} | f_1, ..., f_i)}{P(f_{i+1} | f_1, ..., f_i)}\]

在处理条件概率时，一个常用的技巧是推迟归一化，直到我们需要归一化的概率，我们现在将使用这个技巧。更具体地说，由于 $B(W_{i+1})$ 的上述展开式中的分母对于由 $B(W_{i+1})$ 表示的概率表中的每一项都是通用的，我们可以省略实际除以 $$P(f_{i+1}

f_1, …, f_i)$。相反，我们可以简单地注意到$B(W_{i+1})$与$P(W_{i+1}, f_{i+1}

f_1, …, f_i)$$ 成正比：

\[B(W_{i+1}) \propto P(W_{i+1}, f_{i+1} | f_1, ..., f_i)\]

比例常数等于 $$P(f_{i+1}

f_1, …, f_i)$。每当我们决定要恢复信念分布$B(W_{i+1})$$ 时，我们可以将每个计算出的值除以这个比例常数。现在，使用链式法则我们可以观察到以下内容：

\[B(W_{i+1}) \propto P(W_{i+1}, f_{i+1} | f_1, ..., f_i) = P(f_{i+1} | W_{i+1}, f_1, ..., f_i)P(W_{i+1} | f_1, ..., f_i)\]

根据前面所述的与隐马尔可夫模型相关的条件独立假设，$$P(f_{i+1}

W_{i+1}, f_1, …, f_i)$等价于简单的$P(f_{i+1}

W_{i+1})$，并且根据定义$P(W_{i+1}

f_1, …, f_i) = B’(W_{i+1})$。这允许我们以最终形式表达$B’(W_{i+1})$和$B(W_{i+1})$$ 之间的关系：

\[\boxed{B(W_{i+1}) \propto P(f_{i+1} | W_{i+1})B'(W_{i+1})}\]

结合我们刚刚推导出的两个关系，产生了一种称为前向算法 (forward algorithm) 的迭代算法，它是前面迷你前向算法的隐马尔可夫模型模拟：

\[\boxed{B(W_{i+1}) \propto P(f_{i+1} | W_{i+1})\sum_{w_i}P(W_{i+1} | w_i)B(w_i)}\]

前向算法可以被认为由两个独特的步骤组成：时间流逝更新 (time elapse update)，对应于从 $B(W_i)$ 确定 $B'(W_{i+1})$，以及观测更新 (observation update)，对应于从 $B'(W_{i+1})$ 确定 $B(W_{i+1})$。因此，为了将我们的信念分布推进一个时间步（即从 $B(W_i)$ 计算 $B(W_{i+1})$），我们必须首先通过时间流逝更新将我们模型的状态推进一个时间步，然后通过观测更新合并来自该时间步的新证据。考虑以下初始分布、转移模型和传感器模型：

$W_0$	$B(W_0)$
sun	0.8
rain	0.2

$W_{i+1}$	$W_i$	$P(W_{i+1} \mid W_i)$
sun	sun	0.6
rain	sun	0.4
sun	rain	0.1
rain	rain	0.9

$F_i$	$W_i$	$P(F_i \mid W_i)$
good	sun	0.8
bad	sun	0.2
good	rain	0.3
bad	rain	0.7

为了计算 $B(W_1)$，我们首先执行时间更新以获得 $B'(W_1)$：

\[B'(W_1 = sun) = \sum_{w_0}P(W_1 = sun | w_0)B(w_0) = P(W_1 = sun | W_0 = sun)B(W_0 = sun) + P(W_1 = sun | W_0 = rain)B(W_0 = rain)\] \[B'(W_1 = sun) = 0.6 \cdot 0.8 + 0.1 \cdot 0.2 = \boxed{0.5}\] \[B'(W_1 = rain) = \sum_{w_0}P(W_1 = rain | w_0)B(w_0) = P(W_1 = rain | W_0 = sun)B(W_0 = sun) + P(W_1 = rain | W_0 = rain)B(W_0 = rain)\] \[B'(W_1 = rain) = 0.4 \cdot 0.8 + 0.9 \cdot 0.2 = \boxed{0.5}\]

因此：

$W_1$	$B'(W_1)$
sun	0.5
rain	0.5

接下来，我们将假设第 1 天的天气预报是好的（即 $F_1 = good$），并执行观测更新以获得 $B(W_1)$：

\[B(W_1 = sun) \propto P(F_1 = good | W_1 = sun)B'(W_1 = sun) = 0.8 \cdot 0.5 = \boxed{0.4}\] \[B(W_1 = rain) \propto P(F_1 = good | W_1 = rain)B'(W_1 = rain) = 0.3 \cdot 0.5 = \boxed{0.15}\]

最后一步是归一化 $B(W_1)$，注意 $B(W_1)$ 表中的条目总和为 $0.4 + 0.15 = 0.55$：

\[B(W_1 = sun) = 0.4 / 0.55 = \frac{8}{11}\] \[B(W_1 = rain) = 0.15 / 0.55 = \frac{3}{11}\]

因此我们 $B(W_1)$ 的最终表如下：

$W_1$	$B(W_1)$
sun	$\frac{8}{11}$
rain	$\frac{3}{11}$

注意观察天气预报的结果。因为天气预报员预测天气好，我们对晴天的信念从时间更新后的 $\frac{1}{2}$ 增加到观测更新后的 $\frac{8}{11}$。

作为结束语，上面讨论的归一化技巧实际上可以在使用隐马尔可夫模型时显着简化计算。如果我们从某个初始分布开始，并且有兴趣计算时间 $t$ 的信念分布，我们可以使用前向算法迭代计算 $B(W_1), ..., B(W_t)$，并且只在最后通过将 $B(W_t)$ 表中的每个条目除以其条目之和来归一化一次。

\(W_1\)	\(B(W_1)\)
sun	\(\frac{8}{11}\)
rain	\(\frac{3}{11}\)