Markov 链
Markov 链是刻画随机变量序列的概率分布的模型.
定义
设 $\{X_t\mid t=1,2,\cdots\}$ 是随机序列, 若 $X_t$ 都在 $S$ 中取值, 则称 $S$ 是 $\{X_t\}$ 的状态空间, $S$中的元素称为 状态.
如果对任何正整数 $t\geq 2$ 和 $S$ 中的状态 $s_i,s_j,s_{i_1},s_{i_2},\cdots,s_{i_{t-1}}$, 随机序列 $\{X_t\}$ 满足
$$ P(X_{t+1}=s_j\mid X_t=s_i,X_{t-1}=s_{i_{t-1}},\cdots,X_1=s_{i_1}) \\ = P(X_{t+1}=s_j\mid X_t=s_i) = P(X_2=s_j\mid X_1=s_i) $$则称$\{X_t\}$为时齐的 Markov 链.
我们称
$$a_{ij} = P(X_2 = s_j | X_1 = s_i), s_i, s_j \in S$$为 Markov 链 $\{X_t\}$ 的 转移概率. 称矩阵 $A = [a_{ij}]$ 为 Markov 链 $\{X_t\}$ 的 一步转移概率矩阵, 简称为 转移矩阵.
Markov 链的初始状态 $X_1$ 的分布称为 初始分布, 记为 $\pi = (\pi_1,\pi_2,\cdots,\pi_N)$, 其中 $\pi_i = P(X_1 = s_i)$.
设 $|S| = N$, 则转移矩阵为 $N \times N$ 矩阵, 且 $\sum_{j=1}^N a_{ij} = 1$.
Markov 链的性质直观上可以理解为, 在时刻 $t$ 的状态只与时刻 $t-1$ 的状态有关, 与之前的状态无关. 也就是说, Markov 链具有 无记忆性.
隐 Markov 模型
实际中, 我们往往无法直接观察到 Markov 链的状态, 而只能观察到与状态相关的观测值.
隐 Markov 模型 (HMM) 刻画了首先由一个马尔可夫链随机生成不可观测的状态随机序列 $\{X_t\}$, 再由每个状态 $X_t$ 生成一个观测 $O_t$ 而生成观测随机序列 $\{O_t\}$ 的过程.
设 观测概率 矩阵 $B = [b_{ij}]$, 其中 $b_{ij} = P(O_t = o_j | X_t = s_i)$.
算法HMM
输入: 隐 Markov 模型 $M = (A, B, \pi)$, 其中 $A$ 是转移概率矩阵, $B$ 是观测概率矩阵, $\pi$ 是初始分布.
输出: 长度为 $T$ 的观测序列.
- 令 $t=1$, 随机选择初始状态 $X_1$ 使得 $P(X_1 = s_i) = \pi_i$.
- 根据状态 $X_t$ 和观测概率矩阵 $B$, 随机生成观测 $O_t$ 使得 $P(O_t = o_j | X_t = s_i) = b_{ij}$.
- 根据状态 $X_t$ 和转移概率矩阵 $A$, 随机选择下一个状态 $X_{t+1}$ 使得 $P(X_{t+1} = s_j | X_t = s_i) = a_{ij}$.
- 令 $t = t + 1$, 如果 $t \leq T$, 则返回第 2 步, 否则停止.
- 返回观测序列 $\mathbf{O} = (O_1, O_2, \cdots, O_T)$.
概率计算方法
Markov 的第一个核心问题是概率计算问题: 给定 Markov 模型 $\lambda = (A,B,\pi)$, 计算 $p(\mathbf{O} | \lambda)$, 其中 $O=(O_1,O_2, \cdots, O_T)$, 即计算给定模型时得到观测序列的概率.
前向算法
我们定义前向概率:
$$\alpha_t(i) = p(O_1, O_2, \cdots, O_t, X_t = s_i | \lambda)$$显见 $\alpha_T(i) = p(\mathbf{O}, X_T = s_i | \lambda)$, 因此 $p(\mathbf{O} | \lambda) = \sum_{i=1}^N \alpha_T(i)$. 对于首项:
$$ \begin{aligned} \alpha_1(i) &= p(O_1, X_1 = s_i | \lambda) \\ &= p(X_1 = s_i | \lambda) p(O_1 | X_1 = s_i, \lambda) \\ &= \pi_i b_i(O_1) \end{aligned} $$推导递推式:
$$ \begin{aligned} \alpha_{t+1}(i) &= p(O_1, O_2, \cdots, O_t, O_{t+1}, X_{t+1} = s_i | \lambda) \\ &= \sum_{j=1}^N p(O_1, O_2, \cdots, O_t, X_t = s_j, X_{t+1} = s_i | \lambda) \\ &= \sum_{j=1}^N \alpha_t(j) p(O_{t+1}|X_{t+1}=s_i, \lambda) p(X_{t+1}=s_i|X_t=s_j, \lambda) \\ &= \sum_{j=1}^N \alpha_t(j)b_i(O_{t+1}) a_{ji} = \left(\sum_{j=1}^N a_{ji}\alpha_t(j)\right)b_i(O_{t+1}) \\ \end{aligned} $$前向算法
$$\alpha_1(i) = \pi_i b_i(O_1)$$$$\alpha_{t+1}(i) = \left(\sum_{j=1}^N a_{ji}\alpha_t(j)\right)b_i(O_{t+1})$$$$p(\mathbf{O} | \lambda) = \sum_{i=1}^N \alpha_T(i)$$后向算法
我们定义后向概率:
$$\beta_t(i) = p(O_{t+1}, O_{t+2}, \cdots, O_T | X_t = s_i, \lambda)$$约定 $\beta_T(i) = 1$. 仿照前向算法的思路推导即可.
后向算法
$$\beta_T(i) = 1$$$$\beta_t(i) = \sum_{j=1}^N a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)$$$$p(\mathbf{O} | \lambda) = \sum_{i=1}^N \pi_i b_i(O_1) \beta_1(i)$$Viterbi 算法
Markov 的第二个核心问题是解码问题: 给定 Markov 模型 $\lambda = (A,B,\pi)$ 和观测序列 $O$, 计算最可能的状态序列 $X = \{X_1, X_2, \cdots, X_T\}$. 即找:
$$X^* = \argmax_X p(X | \mathbf{O}, \lambda)$$也可以定义为:
$$X^* = \argmax_X p(X, O| \lambda)$$Viterbi 算法是求解该问题的动态规划算法. 考虑时刻 $T$ 状态为 $s_i$ 的所有单个路径 $(X_1,X_2,\cdots X_{T-1},X_T = s_i)$ 的概率最大值为
$$ \delta_{T}(i) = \max_{X_{1},X_{2},\cdots,X_{T-1}} P(X_{1},X_{2},\cdots,X_{T-1},O_{1},O_{2},\cdots,O_{T},X_{T}=s_{i}|\lambda) $$对于最优路径 $X^*$, 即有:
$$ P(X^*|\mathbf{O},\lambda) = \max_{1 \le i \le N} \delta_{T}(i), X_T^* = \argmax_{1 \le i \le N} \delta_{T}(i) $$特别地, $\delta_1(i)=\pi_i b_i(O_1)$. 既然要动态规划, 递推公式如下:
$$ \delta_t(i) = \max_{1 \le j \le N} \left( \delta_{t-1}(j) a_{ji} \right) b_i(O_t) $$动态规划还要记住路径, 用 $\Psi_t(s_i)$ 记录时刻 $t$ 状态为 $s_i$ 的概率最大的路径的前一个状态, 即:
$$ \Psi_t(s_i) = \argmax_{1 \le j \le N} \left( \delta_{t-1}(j) a_{ji} \right) $$算法Viterbi
输入: $\lambda = (A,B,\pi)$, 观测序列 $\mathbf{O} = (O_1,O_2,\cdots,O_T)$
输出: 最优状态序列 $X^* = (X_1^*, X_2^*, \cdots, X_T^*)$
- 初始化 $\delta_1(i) = \pi_i b_i(O_1)$, $\Psi_1(s_i) = 0$.
- 对于 $t=2,3,\cdots,T$: $$ \begin{aligned} \delta_t(i) &= \max_{1 \le j \le N} \left( \delta_{t-1}(j) a_{ji} \right) b_i(O_t) \\ \Psi_t(s_i) &= \argmax_{1 \le j \le N} \left( \delta_{t-1}(j) a_{ji} \right) \end{aligned} $$
- 选择最优路径: $$ \begin{aligned} P^* &= \max_{1 \le i \le N} \delta_T(i) \\ X_T^* &= \argmax_{1 \le i \le N} \delta_T(i) \end{aligned} $$
- 从时间 $T$ 追溯历史: $$X_{t-1}^* = \Psi_t(X_t^*)$$
- 返回最优路径 $X^* = (X_1^*, X_2^*, \cdots, X_T^*)$.
Baum-Welch 算法
Markov 的第三个核心问题是学习问题: 给定观测序列 $O$ 和隐 Markov 模型 $\lambda = (A,B,\pi)$, 计算最优的模型参数使得似然 $p(O|\lambda)$ 最大.
如果 Markov 链是可观测的, 则可以直接用极大似然估计来估计参数. 如果隐藏, 可以用 EM 算法来估计参数. 我们依然沿用 EM 算法的思路:
$$ Q(\theta|\theta^{(t)}) = \sum_{Z} LL(\theta|D,Z) p(Z|D,\theta^{(t)}) $$用 $\bar{\lambda}$ 表示当前的参数, 则在 M 步中的 $Q$ 函数为:
$$ \begin{aligned} Q(\lambda|\bar{\lambda}) &= \sum_{X} p(X|\mathbf{O},\bar{\lambda}) \log p(\mathbf{O},X|\lambda) \\ &= \frac{1}{p(O|\bar{\lambda})} \sum_{X} p(\mathbf{O},X|\bar{\lambda})\log p(\mathbf{O},X|\lambda) \end{aligned} $$忽略前面的常数项, Baum-Welch 直接定义 $Q$ 函数为:
$$ Q(\lambda|\bar{\lambda}) = \sum_{X} p(X|\mathbf{O},\bar{\lambda})\log p(\mathbf{O},X|\lambda) $$如果我们记相应的隐状态序列为 $X = (X_1=s_{i_1}, X_2=s_{i_2}, \cdots, X_T=s_{i_T})$, 则有:
$$ P(\mathbf{O},X|\lambda) = \pi_{i_1} b_{i_1}(O_1) \prod_{t=1}^{T-1} a_{i_t i_{t+1}} b_{i_{t+1}}(O_{t+1}) $$代入有
$$ \begin{aligned} Q(\lambda,\bar{\lambda}) & =\sum_{X}p(\mathbf{O},X|\bar{\lambda})\log\left[\pi_{i_{1}}b_{i_{1}}(O_{1})\prod_{t=1}^{T-1}a_{i_{t}i_{t+1}}b_{i_{t+1}}(O_{t+1})\right] \\ &=\sum_{X}p(\mathbf{O},X|\bar{\lambda})\log\pi_{i_{1}}+\sum_{X}p(\mathbf{O},X|\bar{\lambda})\left[\sum_{t=1}^{T-1}\log a_{i_{t}i_{t+1}}\right] +\sum_X p(\mathbf{O},X|\bar{\lambda})\left[\sum_{t=1}^T\log b_{i_t}(O_t)\right]. \end{aligned} $$三个部分分别设为 $Q_1, Q_2, Q_3$.
计算 Q1
$$ \begin{aligned} Q_1 &= \sum_{i=1}^N \sum_{X_1=s_i, X_2, \cdots, X_T} p(\mathbf{O},X|\bar{\lambda}) \log \pi_i \\ &= \sum_{i=1}^N p(\mathbf{O},X_1=s_i|\bar{\lambda}) \log \pi_i \\ \end{aligned} $$$\pi_i$ 要满足 $\sum_{i=1}^N \pi_i = 1$, 因此可以用 Lagrange 乘子法来求解. 得到:
$$ \pi_i = \frac{p(\mathbf{O},X_1=s_i|\bar{\lambda})}{p(O|\bar{\lambda})} = p(X_1=s_i|\mathbf{O},\bar{\lambda}) $$计算 Q2
类似 $Q_1$ 的处理手法:
$$ Q_2 = \sum_{i,j=1}^{N} \sum_{t=1}^{T-1} p(\mathbf{O}, X_t=s_i, X_{t+1}=s_j|\bar{\lambda}) \log a_{ij} $$附加条件 $\sum_{j=1}^N a_{ij} = 1$, Lagrange 乘子法求解, 得到:
$$ a_{ij} = \frac{\sum_{t=1}^{T-1}P(X_t=s_i,X_{t+1}=s_j|\mathbf{O},\bar{\lambda})}{\sum_{t=1}^{T-1}P(X_t=s_i|\mathbf{O},\bar{\lambda})} $$这里分子分母也同时除了 $p(O|\bar{\lambda})$.
计算 Q3
仍然类似处理:
$$ Q_{3}=\sum_{j=1}^{N}\sum_{t=1}^{T}P(\mathbf{O},X_{t}=s_{j}|\bar{\lambda})\log b_{j}(O_{t}) $$附加条件 $\sum_{k=1}^M b_j(k) = 1$. 注意 $b_{j}(O_{t})$ 和 $b_{j}(t)$ 并不见得相同, 我们需要简单改写一下:
$$ \log b_j(O_t) = \sum_{k=1}^M I(O_t=\nu_k) \log b_j(k) $$此时再用 Lagrange 乘子法求解, 得到:
$$ b_{j}(k) = \frac{\sum_{t=1}^{T}P(X_{t}=s_{j}|\mathbf{O},\bar{\lambda})I(O_{t}=\nu_{k})}{\sum_{t=1}^{T}P(X_{t}=s_{j}|\mathbf{O},\bar{\lambda})} $$这里分子分母也同时除了 $p(O|\bar{\lambda})$.
于是核心转化为了计算:
$$ \begin{aligned} \gamma_t(i|\lambda) &= p(X_t=s_i|\mathbf{O},\bar{\lambda})\\ \xi(i,j|\lambda)&=p(X_t=s_i,X_{t+1}=s_j|\mathbf{O},\bar{\lambda}) \end{aligned} $$利用 Bayes 公式, 结合前向后向算法可得结果.
算法Baum-Welch
输入: 观测序列 $\mathbf{O} = (O_1,O_2,\cdots,O_T)$.
输出: 隐 Markov 模型 $\lambda = (A,B,\pi)$.
- 初始化 $\lambda = (A,B,\pi)$.
- 按概率计算方法计算前向概率 $\alpha_t(i)$ 和后向概率 $\beta_t(i)$.
- 计算以下参数: $$ \begin{aligned} \gamma_t(i|\lambda) &= \frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N \alpha_t(j)\beta_t(j)} \\ \xi(i,j|\lambda) &= \frac{\alpha_t(i)a_{ij}b_j(O_{t+1})\beta_{t+1}(j)}{\sum_{j=1}^N \sum_{k=1}^N \alpha_t(k)a_{kj}b_j(O_{t+1})\beta_{t+1}(k)} \\ \pi_i &= \gamma_1(i|\lambda) \\ a_{ij} &= \frac{\sum_{t=1}^{T-1} \xi(i,j|\lambda)}{\sum_{t=1}^{T-1} \gamma_t(i|\lambda)} \\ b_{j}(k) &= \frac{\sum_{t=1}^{T} \gamma_t(j|\lambda)I(O_t=\nu_k)}{\sum_{t=1}^{T} \gamma_t(j|\lambda)} \end{aligned} $$
- 得到新的参数 $\lambda = (A,B,\pi)$.
- 重复步骤 2-4 直到收敛.
- 返回隐 Markov 模型 $\lambda = (A,B,\pi)$.