马尔可夫 与 隐马尔可夫

马尔可夫链

无记忆性 #机器学习 #大数定律

马尔可夫证明，在满足一定相依结构条件时，即使数据不独立，也大概存在大数定律。例如马尔可夫链在不可约、非周期、正常返等条件下有遍历定理，可以看作大数定律的推广。这说明“大数定律必须基于独立同分布”是一种常见但不完整的理解。
某一个状态只由前一个状态决定，这就是一个一阶马尔可夫模型。状态间的转移仅依靠于前 n 天的状态，即状态间的转移仅依靠于前 n 个状态的过程。这个过程就称为 n 阶马尔科夫模型。
马尔科夫链的核心三要素

• 状态空间 S
  
• 初始分布 π
  
• 转移概率矩阵 P
  马尔可夫链的核心要素：状态空间、初始分布、转移概率矩阵；其核心性质是马尔可夫性，也称无后效性。
  

事例理解分析

【【数之道 18】"马尔可夫链"是什么？了解它只需5分钟！】 https://www.bilibili.com/video/BV19b4y127oZ/
一个包罗状态 A 和状态 B 的马尔可夫模型，其中状态 A 保持在自身的概率为 40%，由状态 A 转移到状态 B 的概率为 60%；状态 B 保持在自身的概率为 50%，由状态 B 转移到状态 A 的概率为 50%。
转移矩阵为：
\(A^T = \begin{array}{c c c} & \text{A} & \text{B} \\ \text{A} & 0.4 & 0.5 \\ \text{B} & 0.6 & 0.5 \end{array}\)
初始状态分布：

\[\begin{vmatrix}  1\\ 0\end{vmatrix}\]
初始状态分布为各分量非负且和为 1。
在已知第一天吃A的情况下，第二天选择的概率为：

\[\begin{vmatrix} 0.4 & 0.5 \\ 0.6 & 0.5\end{vmatrix} * \begin{vmatrix}  1\\ 0\end{vmatrix} =  \begin{vmatrix}  0.4\\ 0.6\end{vmatrix}\]
由马尔科夫链定义可知，时刻 \(X_{t+1}\)  的状态只与 \(X_t\)  有关
继续推演得到第n天的概率分布：

\[\begin{vmatrix} 0.4 & 0.5 \\ 0.6 & 0.5\end{vmatrix} ^ n * \begin{vmatrix}  1\\ 0\end{vmatrix} =  \begin{vmatrix}  0.454545\\ 0.545454\end{vmatrix}\]
可以发现其 收敛 了

可以看出马尔科夫链在解决状态依靠的应用中有着极大的作用。使用马尔科夫链可以很好的简化模型，并且运算出概率。

隐马尔可夫链

隐马尔可夫模型（Hidden Markov Model, HMM）的核心思想是：系统内部存在一个不可直接观测的隐藏状态序列，该序列按马尔可夫链演化；每个时刻的隐藏状态会以一定概率“发射”出一个可观测的观测值。我们只能看到观测序列，并希望推测隐藏状态或学习模型参数。简单来说，就是状态序列不会直接表现出来，而是状态序列会有一定的概率表现为某种观测值，需要通过观测值来判断状态序列的状态。
【最简单的例子动画理解隐马尔可夫模型！】 https://www.bilibili.com/video/BV1ko4y1P7Zv/
核心假设

• 齐次马尔可夫假设：当前隐藏状态只依靠前一时刻的隐藏状态。
  
• 观测独立性假设：当前观测只依靠当前隐藏状态，与其他状态和观测无关。
  

事件理解

一个隐马尔可夫模型的案例，其中隐状态为雨天、阴天和晴天，可观测状态为沮丧和开心。雨天转移到雨天、阴天和晴天的概率分别为0.5、0.3和0.2；阴天转移到雨天、阴天和晴天的概率分别为0.4、0.2和0.4；晴天转移到阴天和晴天的概率分别为0.3和0.7。雨天产生沮丧和开心的概率分别为0.9和0.1；阴天产生沮丧和开心的概率分别为0.6和0.4；晴天产生沮丧和开心的概率分别为0.2和0.8。在这个例子中，天气的状态即为隐藏状态序列，而心情则是可观测值。
转移矩阵 与 发射矩阵：

\[A = \left[ \begin{array}{c c c} 0.5 & 0.3 & 0.2 \\ 0.4 & 0.2 & 0.4 \\ 0.0 & 0.3 & 0.7 \end{array} \right] B = \left[ \begin{array}{c c} 0.9 & 0.1 \\ 0.6 & 0.4 \\ 0.2 & 0.8 \end{array} \right]\]

• A 的行：雨天、阴天、晴天；列：雨天、阴天、晴天。
  
• B 的行：雨天、阴天、晴天；列：沮丧、开心。
  
• 晴天到雨天概率为 0。
  

根本标题

评估标题

常用算法：前向算法、后向算法。

下面为了演示前向算法，换成一个更简单的二状态 HMM 例子。

假设隐状态是天气：\(q_{t} \in \{\mathrm{晴}, \mathrm{雨} \}\)  可观测值是心情：\(o_{t}\in \{ \mathrm{开心}, \mathrm{沮丧} \}\)
假设天气影响心情：晴天更容易开心，雨天更容易沮丧。
初始天气概率：\(\pi = [ P (\mathrm{晴}) = 0.6, P (\mathrm{雨}) = 0.4 ]\)
天气转移矩阵 A，行表示当前天气，列表示下一天天气：
\(A = \begin{array}{c c c} & \text{晴} & \text{雨} \\ \text{晴} & 0.7 & 0.3 \\ \text{雨} & 0.4 & 0.6 \end{array}\)
发射矩阵 B，表示给定天气下出现某种心情的概率：
\(B = \begin{array}{c c c} & \text{开 心} & \text{沮 丧} \\ \hline \text{晴} & 0.8 & 0.2 \\ \text{雨} & 0.3 & 0.7 \end{array}\)
现在有一个观测到的心情序列：

\[O = \left(o_{1}, o_{2}, o_{3}\right) = (\mathrm{开 心}, \mathrm{沮 丧}, \mathrm{开 心})\]
在给定 HMM 参数下，这个心情序列出现的概率是多少？前向算法可以求它。后向算法则从未来倒推，常用于平滑和 Baum-Welch 训练。
前向算法

前向算法的目标是盘算：\(P (O \mid \lambda)\) ，也就是在给定 HMM 参数的情况下，整个观测序列出现的概率。
其中，\(O = \left(o_{1}, o_{2}, \dots , o_{T}\right)\) 表示观测序列；\(\lambda = (A, B, \pi)\) 表示模型参数。
\(\pi_{i} = P \left(q_{1} = s_{i}\right)\) 表示初始时刻处于状态 \(s_i\)​ 的概率。这里 i 是状态编号。
\(a_{ij} = P \left(q_{t+1} = s_{j} \mid q_{t} = s_{i}\right)\) 表示现在的 序列为 \(s_{i}\)，而下一个时刻的序列为 \(s_{j}\) 的概率。
\(b_{i} \left(o_{t}\right) = P \left(o_{t} \mid q_{t} = s_{i}\right)\) 表示现在 序列为 \(s_{i}\)，当前对应的观测值为 \(o_{t}\) 的概率。
\(\alpha_{t-1} (i) = P \left(o_{1}, o_{2}, \dots , o_{t-1}, q_{t-1} = s_{i} \mid \lambda\right)\) 表示从第 1 个观测一直看到第 \(t−1\) 个观测，并且在 \(t−1\) 时刻隐状态恰恰是 \(s_i\) 的联合概率。
前向变量：

\[\alpha_{t} (i) = P \left(o_{1}, o_{2}, \dots , o_{t}, q_{t} = s_{i} \mid \lambda\right)\]
代表从第一个观测一直看到第 \(t\) 个观测，并且当前隐状态正好是 \(s_i\) 的联合概率。
其中，\(\sum_{i=1}^{N} \alpha_{t-1} (i) a_{ij}\) 的前半部分 \(\alpha_{t-1} (i)\) 表示 “已经走到上一时刻状态 \(s_i\) 的累计概率”，而后半部分 \(a_{ij}\) 表示“从上一时刻状态 \(s_i\) 转移到当前状态 \(s_j\) 的概率”。再对所有大概的上一状态 \(s_i\) 求和的 \(\sum_{i=1}^{N} \alpha_{t-1} (i) a_{ij}\) 也就是在思量完前 \(t-1\) 个观测后，当前时刻 t 到达状态 \(s_j\) 的总概率。
乘被骗前状态 \(s_j\) 产生当前观测 \(o_t\) 的概率 \(b_{j}(o_{t})\) 得到：

\[\alpha_{t} (j) = \left[ \sum_{i=1}^{N} \alpha_{t-1} (i) a_{ij} \right] b_{j} \left(o_{t}\right)\]
也就是说： 前向概率 = 过去累计概率 x 状态转移 x 当前观测概率，更准确地说，是先对所有大概的上一状态求和，再乘当前发射概率。
到了末了时刻 T，当前状态大概是任意一个状态，所以需要把所有状态的前向概率加起来：

\[P (O \mid \lambda) = \sum_{i=1}^{N} \alpha_{T} (i)\]
后向算法

后向算法同样可以求：\(P (O \mid \lambda)\) 但它的思路与前向算法相反。
后向变量：

\[\beta_{t} (i) = P \left(o_{t+1}, o_{t+2}, \dots , o_{T} \mid q_{t} = s_{i}, \lambda\right)\]
代表在当前时刻 t 已知隐状态为 \(s_i\) 的条件下，从下一时刻 \(t+1\) 开始直到末了时刻 T 的所有后续观测出现的概率。
在末了时刻 T，后面已经没有任何观测，因此规定：\(\beta_{T} (i) = 1\) ，这表示已经到序列末尾，后续“空观测序列”出现的概率记为 1。
其中，\(a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\)的第一部分 \(a_{ij}\) 表示“从当前时刻状态 \(s_i\) 转移到下一时刻状态 \(s_j\) 的概率”；第二部分 \(b_j(o_{t+1})\) 表示“下一时刻状态 \(s_j\) 产生下一观测 \(o_{t+1}\) 的概率”；第三部分 \(\beta_{t+1}(j)\) 表示“已经到达下一时刻状态 \(s_j\) 后，从 \(t+2\) 时刻开始直到末了时刻 T 的所有剩余观测出现的概率”。
因此，\(a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\) 表示：“当前处于状态 \(s_i\)，下一时刻转移到状态 \(s_j\)，状态 \(s_j\) 产生观测 \(o_{t+1}\)，并且之后剩余观测继续出现”的概率。
由于下一时刻大概转移到任意一个状态 \(s_j\)，所以需要对所有大概的下一状态 \(s_j\) 求和：

\[\beta_t(i) = \sum_{j=1}^{N} a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)\]
也就是说：后向概率 = 状态转移 × 下一观测概率 × 未来剩余观测概率。
更准确地说，是先思量当前状态 \(s_i\) 转移到每一个大概的下一状态 \(s_j\)，分别乘上该状态产生下一观测的概率以及之后剩余观测出现的概率，末了再对所有大概的下一状态 \(s_j\) 求和。
后向算法是从末了时刻向前递推的。
到了末了时刻 T，后面已经不存在新的观测，因此规定： \(\beta_T(i)=1\) 这里的 1 表示：在已经到达末了时刻之后，不再需要产生任何后续观测，因此剩余空序列出现的概率记为 1。
然后按照

\[\beta_t(i) = \sum_{j=1}^{N} a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)\]
从 \(T-1\) 时刻开始不断向前递推，最终得到 \(\beta_1(i)\)。得到第一时刻的后向概率后，可以结合初始状态概率和第一个观测的发射概率盘算整个观测序列的概率： $$P(O\mid\lambda) = \sum_{i=1}^{N} \pi_i b_i(o_1) \beta_1(i)$$
其中， \(\pi_i\) 表示“初始时刻处于状态 \(s_i\) 的概率”， \(b_i(o_1)\) 表示“状态 \(s_i\) 产生第一个观测 \(o_1\) 的概率”， \(\beta_1(i)\) 表示“在第一时刻处于状态 \(s_i\) 的条件下，从第二个观测到末了一个观测全部出现的概率”。因此，对所有大概的初始状态 \(s_i\)​ 求和”后，就可以得到完整观测序列 O 出现的概率：\(P(O\mid\lambda) = \sum_{i=1}^{N} \pi_i b_i(o_1)\beta_1(i)\)
解码标题

常用算法：Viterbi 算法。
一、Viterbi 变量

Viterbi 变量定义为：

\[\delta_t(j)=\max_{q_1,q_2,\dots,q_{t-1}}P(o_1,o_2,\dots,o_t,q_1,q_2,\dots,q_{t-1},q_t=s_j\mid \lambda)\]
它表示：到时刻 \(t\) 为止，当前隐状态是 \(s_j\) 的所有路径中，概率最大的那条路径的概率。

• \(a_{ij} = P \left(q_{t+1} = s_{j} \mid q_{t} = s_{i}\right)\) 表示现在的 序列为 \(s_{i}\)，而下一个时刻的序列为 \(s_{j}\) 的概率。
  
• \(\pi_{i} = P \left(q_{1} = s_{i}\right)\) 表示在已知序列长度为 i 的序列 \(s_{i}\) 的概率为 \({\pi}_i\) 。
  
• \(b_{i} \left(o_{t}\right) = P \left(o_{t} \mid q_{t} = s_{i}\right)\) 表示现在 序列为 \(s_{i}\)，当前对应的观测值为 \(o_{t}\) 的概率。
  路径记录变量定义为：
  

\[\psi_t(j)=\arg\max_{1\leq i\leq N}\left[\delta_{t-1}(i)a_{ij}\right]\]
它记录：到达当前状态 \(s_j\) 的最优路径，是从哪一个上一状态转移过来的。
二、思路流程导向

初始化：

\[\delta_1(i)=\pi_i b_i(o_1)\]
由于在第一个时刻还没有发生任何状态转移，也不存在“上一时刻的最优路径”，所以 Viterbi 算法直接用“第一时刻处于状态 \(s_i\)，并且观察到 \(o_1\)”的联合概率

\[\psi_1(i)=0\]
在第一个时刻 t=1，状态 \(s_i\) 没有“上一时刻状态”，因此它不存在前驱状态。
递推：

\[\delta_t(j)=\max_{1\leq i\leq N}\left[\delta_{t-1}(i)a_{ij}\right]b_j(o_t)\]
其中，前边一部分 \(\delta_{t-1}(i)a_{ij}\) 表示先沿着“到达上一时刻状态 \(s_i\) 的最优路径”走到 \(t-1\) 时刻，再从 \(s_i\) 转移到当前状态 \(s_j\) 后，这条扩展路径的概率。而添加上 \(max\) 后表示所有可以或许到达当前状态 \(s_j\) 的候选路径中，选出概率最大的一条。末了末了再乘 \(b_j(o_t)\) 也就是当前状态 sjs_j 产生当前观测 \(o_t\) 的概率。
终止：

\[P^*=\max_{1\leq i\leq N}\delta_T(i)\]

到了末了时刻 T，比力“以每一个隐状态 \(s_i\) 作为最终状态时，对应的最优路径概率”，然后从中选出最大的那个概率。

\[q_T^*=\arg\max_{1\leq i\leq N}\delta_T(i)\]

在末了时刻 T，从所有大概的隐状态 \(s_i\) 中，找出那个使 Viterbi 概率 \(\delta_T(i)\) 最大的状态，并把它作为最优隐状态序列的末了一个状态。

回溯：

\[q_t^*=\psi_{t+1}(q_{t+1}^*),\quad t=T-1,T-2,\dots,1\]
其中，\(q_{t+1}^*\) 表示已经确定的“第 \(t+1\) 时刻最优状态”；\(\psi_{t+1}(q_{t+1}^*)\) 当第 \(t+1\) 时刻处于最优状态 \(q_{t+1}^*\) 时，使得这条最优路径成立的“上一时刻状态”是谁。因此，整个公式就是 已知下一时刻最优状态 \(q_{t+1}^*\)，通过之前生存的前驱记录 \(\psi\)，找到它对应的上一时刻最优状态 \(q_t^*\) 。
因此可以概括为：

\[\text{前向算法：对所有路径求和，求 }P(O\mid\lambda)\]

\[\text{Viterbi 算法：在所有路径中取最大值，求最大概隐状态路径 }Q^*\]
Viterbi 算法的整体逻辑是：

\[\text{前向盘算最优概率}+\text{记录最优前驱}+\text{反向回溯最优路径}\]
学习标题

1. 有监督学习

在有监督学习中，不仅知道观测序列：

\[O=(o_1,o_2,\dots,o_T)\]
还知道对应的真实隐状态序列：

\[Q=(q_1,q_2,\dots,q_T)\]
也就是说，每一个时刻既知道心情，也知道真实天气。
因此可以直接统计初始状态、状态转移和发射观测的次数，从而估计 HMM 参数：\(\lambda=(A,B,\pi)\)
初始状态概率定义为：\(\pi_i=P(q_1=s_i)\)  有监督学习中，可以直接统计所有训练序列第一个状态为 \(s_i\) 的数量。
状态转移概率定义为：\(a_{ij}=P(q_{t+1}=s_j\mid q_t=s_i)\) 由于真实天气序列已知，可以直接统计相邻天气对：\((q_t,q_{t+1})\)  其中行表示当前天气，列表示下一天天气。
发射概率定义为：\(b_i(o_k)=P(o_t=o_k\mid q_t=s_i)\)  也就是：当天气为 \(s_i\) 时，产生心情 \(o_k\) 的概率。
由于每个时刻的真实天气和心情都已知，可以直接统计。因此：\(\lambda=(A,B,\pi)\)
有监督学习的整体过程
有监督学习的输入是：\((O,Q)\) 其中观测序列 O 和真实隐状态序列 Q 都是已知的。
整体过程可以概括为：

\[(O,Q)\rightarrow\text{统计初始状态次数、状态转移次数、状态—观测对应次数}\rightarrow\text{盘算概率}\rightarrow\lambda=(A,B,\pi)\]
初始状态概率：

\[\pi_i=\frac{M_i}{M}\]
其中 \(M_i\) 是以状态 \(s_i\) 开始的序列数量，\(M\) 是训练序列总数。
状态转移概率：

\[a_{ij}=\frac{N_{ij}}{\sum_{j=1}^{N}N_{ij}}\]
其中 \(N_{ij}\) 是从状态 \(s_i\) 转移到状态 \(s_j\) 的真实次数。
发射概率：

\[b_i(o_k)=\frac{M_i(o_k)}{\sum_k M_i(o_k)}\]
其中 \(M_i(o_k)\) 是状态 \(s_i\) 产生观测 \(o_k\) 的真实次数。
2. 无监督学习：Baum-Welch 算法

Baum-Welch 算法的目标就是：只知道观测序列 \(O\)，不知道天气序列 \(Q\)，通过迭代估计出更合理的 \((\pi,A,B)\)。
核心变量:
状态占用概率：\(\gamma_t(i)=P(q_t=s_i\mid O,\lambda)\)  表示在完整观测序列 O 已知的条件下，第 t 时刻隐状态为 \(s_i\) 的概率。
状态转移概率：\(\xi_t(i,j)=P(q_t=s_i,\ q_{t+1}=s_j\mid O,\lambda)\) 表示在完整观测序列 O 已知的条件下，第 t 时刻发生 \(s_i\rightarrow s_j\) 这一转移的概率。
它们由前向概率和后向概率盘算得到：

\[\gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O\mid\lambda)}\]
这本质是一个后验概率：用“观测序列发生且第 t 时刻状态为 \(s_i\)​”的联合概率，除以整条观测序列发生的概率。

\[\xi_t(i,j)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{P(O\mid\lambda)}\]
这些 \(\xi_t(i,j)\) 可以理解为：在当前模型下，每个相邻时刻发生某种天气转移的软计数。
更新初始状态概率

\[\pi_i^{\text{new}}=\gamma_1(i)\]
更新状态转移概率

\[a_{ij}^{\text{new}}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}\]
更新发射概率

\[b_i^{\text{new}}(o_k)=\frac{\sum_{t_t=o_k}\gamma_t(i)}{\sum_{t=1}^{T}\gamma_t(i)}\]
Baum-Welch 算法不断重复：

\[\lambda^{(k)}\rightarrow\alpha,\beta\rightarrow\gamma,\xi\rightarrow\lambda^{(k+1)}\]
即：\(\text{用当前模型估计隐状态概率}\rightarrow\text{用估计结果重新盘算模型参数}\)
详细步调是：

• 用当前参数 \(\lambda^{(k)}\) 盘算前向概率 \(\alpha_t(i)\) 和后向概率 \(\beta_t(i)\)；
  
• 盘算状态占用概率 \(\gamma_t(i)\) 和状态转移概率 \(\xi_t(i,j)\)；
  
• 用 \(\gamma_t(i)\) 更新初始概率 \(\pi\)；
  
• 用 \(\xi_t(i,j)\) 和 \(\gamma_t(i)\) 更新转移矩阵 A；
  
• 用 \(\gamma_t(i)\) 更新发射矩阵 B；
  
• 得到新参数 \(\lambda^{(k+1)}\)；
  
• 重复上述过程，直到 \(P(O\mid\lambda)\) 或参数根本不再变化。
  

免责声明：如果侵犯了您的权益，请联系站长及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金.