隐马尔科夫链

3.1 隐马尔科夫链的概念

定义 如果随机过程 $\{(X_n,S_n),n>0\}$$\Bqty{(X_n, S_n), n > 0}$ 满足以下条件, 则称为 隐马尔科夫链,

1. 状态序列 $\{X_n,n>0\}$$\Bqty{X_n, n > 0}$ 是马尔科夫链并且不可观测, 状态空间为 $\mathcal{S}$$\cal S$.

2. 信号序列 $\{S_n,n>0\}$$\Bqty{S_n, n > 0}$ (非马尔科夫链) 是可观测的, 信号空间为 $\mathcal{S}$$\scr S$.

3. 进入状态 $j$$j$ 时以概率 $p(s\mid j)$$p(s \mid j)$ 发出信号 $s$$s$, 其中 $\mathrm{\forall }j\in \mathcal{S}:{\displaystyle \sum _{s\in \mathcal{S}}p(s\mid j)=1}$$\forall j \in \cal S \colon \dsum_{s \in \scr S} p(s \mid j) = 1$.

4. 给定状态 $j$$j$ 时, $p(s\mid j)$$p(s \mid j)$ 独立于先前的状态与信号.

问题 0 已知信号序列, 计算状态的概率.

3.2 问题 1：计算产生信号序列的概率

问题 1 计算产生信号序列的概率.

思路 1.1 遍历算法

备注 计算量大, 约 $2n{N}^n$$2n N^n$ 次.

思路 1.2 向前递推

备注 计算量较小, 约 $nN$$nN$ 次.

思路 1.3 向后递推（略）

于是有 ${\displaystyle P\{{\mathit{S}}^n={\mathit{s}}_n\}=\sum _i{p}_{i}p(s_1\mid i)B_1(i)}$$\d P\Bqty{ \bm S^n = \bm s_n } = \sum_i p_i p(s_1 \mid i) B_1(i)$.

思路 1.4 前后递推; Forward-Backward 算法（略）

3.3 问题 2：由信号序列预测状态序列

问题 2 已知信号序列, 预测前 $n$$n$ 个状态.

思路 2.1 预测单个状态, 使得到该状态的概率最大.（略）

于是 $\hat{j}=\underset{j}{\mathrm{argmax}}{F}_k(j)B_k(j)$$\hat j = \argmax j F_k(j) B_k(j)$.

备注 这样可以使预测对的状态数的期望最大, 但是得到的未必是最可能状态序列.

思路 2.2 预测状态序列, 使得到整个轨迹的概率最大.

思路 2.2.1 遍历算法

于是 $(i_1,\cdots ,i_n)=\underset{i_1,\cdots ,i_n}{\mathrm{argmax}}P\{{\mathit{X}}_n=(i_1,\cdots ,i_n)\mid {\mathit{S}}^n={\mathit{s}}_n\}$$(i_1, \cdots, i_n) = \argmax{i_1, \cdots, i_n} P\Bqty{\bm X_n = (i_1, \cdots, i_n) \mid \bm S^n = \bm s_n}$.

备注 这样可以得到最可能状态序列, 但是计算量大.

思路 2.2.2 Viterbi 算法

欲求最可能的状态序列, 先对每个 $j$$j$ 确定 $V_1(j)$$V_1(j)$, 再依次确定 $V_n(j)$$V_n(j)$.

之后令 $i_n=\underset{i}{\mathrm{argmax}}{V}_n(i)$$i_n = \argmax i V_n(i)$, 再依次令 $i_k=\underset{i}{\mathrm{argmax}}{P}_{i,i_{k+1}}{V}_k(i)$$i_k = \argmax i P_{i,i_{k+1}} V_{k}(i)$.