隐马尔可夫模型
介绍 Link to heading
状态序列 (上面那行x) 隐藏的马尔科夫链随机生成的状态序列，称为状态序列
观测序列 (下面那行y) 每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列
马尔科夫模型是关于时序的概率模型
隐状态可以转换但是观测状态之间不能互相转换，所以要由隐状态->观测状态和观测状态1->观测状态2
假设Q是所有可能的状态序列，V是所有可能的观测序列
$$ Q = {q_1,q_2,...,q_N} $$$$ V = {v_1,v_2,...,v_M} $$假设有$N$个隐藏状态，$M$个观测状态
[!info] 好比每天的天气有晴天、阴天、雨天三种状态，而每天的天气又会影响人们的心情，人们的心情有开心、平静、两种状态，这样就有$N=3$个隐藏状态，$M=2$个观测状态
假设$I$是长度为$T$的状态序列，$O$是对应的观测序列。
假设$A$是状态转移概率矩阵，$B$是观测概率矩阵，$\pi$是初始状态概率向量。
[!info] $A$是一个$N \times N$的矩阵，代表从一个状态转移到另一个状态的概率，$B$是一个$N \times M$的矩阵，代表从一个状态转移到一个观测的概率，$\pi$是一个$1 \times N$的向量，代表初始状态的概率
$$ A = [a_{ij}]_{N \times N} i,j=1,2,...,N $$
其中$a_{ij}$表示在时刻$t$处于状态$i$的条件下在时刻$t+1$转移到状态$j$的概率
$$ a_{ij} = P(i_{t+1}=q_j|i_t=q_i) $$$$ B = [b_j(k)]_{N \times M} j=1,2,...,N;k=1,2,...,M $$
其中$b_j(k)$表示在时刻$t$处于状态$j$的条件下生成观测$k$的概率
$$ b_j(k) = P(o_t=v_k|i_t=q_j) $$$$ \pi = [\pi_i]_{1 \times N} i=1,2,...,N $$
其中$\pi_i$表示时刻$t=1$处于状态$i$的概率
$$ \pi_i = P(i_1=q_i) $$隐马尔科夫模型由初始状态概率向量、状态转移概率矩阵A和观测概率矩阵B决定。$\pi$和A决定状态序列，B决定观测序列。因此，隐马尔科夫模型可以由三元符号表示，即：$\lambda = (\pi,A,B)$。称为隐马尔科夫模型的三要素。
两个基本假设 Link to heading
- 齐次马尔科夫性假设：假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关。即
- 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他时刻的状态及观测无关。即
三个基本问题 Link to heading
- 概率计算问题：给定模型$\lambda=(A,B,\pi)$和观测序列$O={o_1,o_2,...,o_T}$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda)$
- 学习问题：已知观测序列$O={o_1,o_2,...,o_T}$，估计模型$\lambda=(A,B,\pi)$参数，使得在该模型下观测序列概率$P(O|\lambda)$最大
- 预测问题：已知模型$\lambda=(A,B,\pi)$和观测序列$O={o_1,o_2,...,o_T}$，求给定观测序列条件概率$P(I|O,\lambda)$最大的状态序列$I={i_1,i_2,...,i_T}$
[!info] 问题一： 给定模型参数，人们心情的状态序列的概率
问题二： 给定人们心情的状态序列，估计模型参数
问题三： 给定模型参数和人们心情的状态序列，预测天气的序列
概率计算问题 Link to heading
在模型$\lambda=(A,B,\pi)$下，给定观测序列$O={o_1,o_2,...,o_T}$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda)$
暴力求解 Link to heading
对于状态序列$I=(i_1,i_2,...,i_T)$的概率是:
$$ P(I|\lambda) = \pi_{i_1}a_{i_1i_2}...a_{i_{T-1}i_T} $$对上面这种序列，产生的观测序列$O=(o_1,o_2,...,o_T)$的概率是:
$$ P(O|I,\lambda) = b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T) $$I和O的联合概率是:
$$ P(O,I|\lambda) = P(O|I,\lambda)P(I|\lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) $$对所有可能的状态序列求和:
$$ P(O|\lambda) = \sum_{I}P(O,I|\lambda) = \sum_{i_1,...,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) $$这样的时间复杂度是$O(TN^T)$
前向算法 Link to heading
引入前向概率$\alpha_t(i)$，表示时刻$t$处于状态$i$且观测到$o_1,o_2,...,o_t$的概率
$$ \alpha_t(i) = P(o_1,o_2,...,o_t,i_t=q_i|\lambda) $$这里用到了动态规划的思想
对于时刻$t=1$，有
$$ \alpha_1(i) = \pi_ib_i(o_1)
i=1,2,…,N $$
对于时刻$t=2,3,...,T$，有
$$ \alpha_{t+1}(i) = [\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1})
i=1,2,…,N $$
$a_{ji}$表示在时刻$t$处于状态$j$的条件下在时刻$t+1$转移到状态$i$的概率
$b_i(o_{t+1})$表示在时刻$t+1$处于状态$i$的条件下生成观测$o_{t+1}$的概率
这里的意思是，对于时刻$t+1$，状态$i$的概率是由时刻$t$的所有状态$j$转移到状态$i$的概率乘以状态$i$生成观测$o_{t+1}$的概率
最终的观测序列概率是
$$ P(O|\lambda) = \sum_{i=1}^N\alpha_T(i) $$这样的时间复杂度是$O(TN^2)$
[!info] 对于每个$\alpha_t(j)$，都要对$N$个状态$i$求和，因此每个$\alpha_t(j)$的时间复杂度是$O(N)$
对于每个时间步，都需要计算$N$个$\alpha_t(j)$
一共有$T-1$个时间步，所以总的时间复杂度是$O(TN^2)$
学习问题 Link to heading
Baun-Welch算法 Link to heading
[!info] Baun-Welch算法是EM算法在隐马尔科夫模型中的应用 建议在看此部分之前先了解EM算法
已知观测序列$O={o_1,o_2,...,o_T}$，估计模型$\lambda=(A,B,\pi)$参数，使得在该模型下观测序列概率$P(O|\lambda)$最大
$$ P(O|\lambda) = \sum_{I}P(O,I|\lambda) \\ = \sum_{I}P(O|I,\lambda)P(I|\lambda) \\ = \sum_{i_1,...,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) $$确定完全数据的对数似然函数
$$ \begin{aligned} L(\lambda) & = \log P(O|\lambda) \\ & = \log \sum_{I}P(O,I|\lambda) \\ & = \log \sum_{I}P(O|I,\lambda)P(I|\lambda) \\ & = \log \sum_{i_1,...,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) \end{aligned} $$首先初始化参数，然后迭代以下两步直到收敛
E步：Q函数
$$ \begin{aligned} Q(\lambda,\lambda^{'}) & = E_{I|O,\lambda^{'}}[\log P(O,I|\lambda)] \\ & = \sum_{I}P(I|O,\lambda^{'})\log P(O,I|\lambda) \\ & = \sum_{I}P(I|O,\lambda^{'})\log P(O|I,\lambda)P(I|\lambda) \\ & = \sum_{I}P(I|O,\lambda^{'})\log[\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T)] \\ & = \sum_{I}\log[\pi_{i_1}P(O,I)|\lambda^{'}] + \sum_{I}(\sum_{t=1}^{T-1}\log a_{i_{t-1},i_{t}})P(I|O,\lambda^{'}) + \sum_{I}(\sum_{t=1}^{T-1}\log b_{i_t}(o_t))P(I|O,\lambda^{'}) \end{aligned} $$其中，$\lambda^{'}$是模型参数的估计值（常量），$\lambda$是要极大化的参数
M步：极大化Q函数
$$ \lambda^{'} = \arg \max_{\lambda}Q(\lambda,\lambda^{'}) $$使用拉格朗日乘子法，约束条件是 $\sum_{i=1}^Nb_{jk}=$，对$\lambda$求导，得到$\lambda$的更新公式
$$ \begin{aligned} \pi_i & = \frac{P(i_1=q_i|O,\lambda^{’})}{\sum_{j=1}^N P(i_1=q_j|O,\lambda^{’})} \ & = \frac{\gamma_1(i)}{\sum_{j=1}^N \gamma_1(j)} \end{aligned}
$$
$$ \begin{aligned} a_{ij} & = \frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\sum_{j=1}^N \xi_t(i,j)} \\ & = \frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)} \end{aligned} $$$$ \begin{aligned} b_j(k) & = \frac{\sum_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum_{t=1}^{T}\gamma_t(j)} \end{aligned} $$其中，$\gamma_t(i)$表示时刻$t$处于状态$i$的概率，$\xi_t(i,j)$表示时刻$t$处于状态$i$且时刻$t+1$转移到状态$j$的概率
预测问题 Link to heading
维特比算法 Link to heading
已知模型$\lambda=(A,B,\pi)$和观测序列$O={o_1,o_2,...,o_T}$，求给定观测序列条件概率$P(I|O,\lambda)$最大的状态序列$I={i_1,i_2,...,i_T}$
这里用到了动态规划的思想，引入前向概率$\alpha_t(i)$，表示时刻$t$处于状态$i$且观测到$o_1,o_2,...,o_t$的概率，如果已知$\alpha_t(i)$，则可以递归地计算$\alpha_{t+1}(i)$
最终的思想就是 构建路径，回溯查找
构建 Link to heading
首先定义两个变量，$\delta_t(i)$和$\psi_t(i)$，分别表示时刻$t$处于状态$i$的所有单个路径中概率最大值和在时刻$t$状态为$i$的所有单个路径中概率最大的 前一个状态（第t-1个节点）
也就是分别记录当前状态的最大概率和最大概率对应的前一个状态，前者是为了计算后面的最大概率，后者是为了回溯查找路径
初始化 Link to heading
$$ \delta_1(i) = \pi_ib_i(o_1) $$$$ \psi_1(i) = 0 $$递推 Link to heading
由变量$\delta$的递推公式
$$ \delta_{t+1}(i) = \max_{1 \leq j \leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}) $$由变量$\psi$的递推公式
$$ \psi_{t+1}(i) = \arg \max_{1 \leq j \leq N}[\delta_t(j)a_{ji}] $$终止 Link to heading
$$ P^* = \max_{1 \leq i \leq N}\delta_T(i) $$其中，$P^*$是最大概率，$\delta_T(i)$是时刻$T$处于状态$i$的所有单个路径中概率最大值
也就是最优路径的概率
$$ i_T^* = \arg \max_{1 \leq i \leq N}\delta_T(i) $$其中，$i_T^*$是时刻$T$处于状态$i$的所有单个路径中概率最大的状态
也就是最优路径的最后一个状态
回溯 Link to heading
$$ i_t^* = \psi_{t+1}(i_{t+1}^*) $$其中，$i_t^*$是时刻$t$处于状态$i$的所有单个路径中概率最大的状态
根据$\psi$和最优状态$i_T^*$，可以回溯得到最优路径
这样的时间复杂度是$O(TN^2)$