目录
马尔可夫模型
概念导入
某时间段内，交通信号灯颜色变化：红-黄-绿-红
在某个星期天气的变化状态序列：晴朗 - 多云 - 雨天
像交通信号灯一样，某一个状态只由前一个状态决定，这就是一个一阶马尔可夫模型。而像天气这样，天气状态间的转移仅依赖于前 n 天天气的状态，即状态间的转移仅依赖于前 n 个状态的过程，这个过程就称为n 阶马尔科夫模型。
马尔可夫模型定义
存在一类重要的随机过程，这些过程中，如果一个系统有 $N$ 个状态 $S_1, S_2, \ldots, S_N$，随着时间的推移，该系统从某一状态转移到另一状态。如果用 $g(t)$ 表示系统在时间 $t$ 的状态变量，那么在时刻 $t$ 的状态为 $S_j \ (1 \leq j \leq N)$ 的概率取决于前 $t-1$ 个时刻 $(1, 2, \ldots, t-1)$ 的状态，该概率为：
假设一：离散的一阶马尔可夫链：如果在特定情况下，系统在时间 $t$ 的状态只与其在时间 $t-1$ 的状态相关，则该系统构成一个离散的一阶马尔可夫链：
假设二：状态与时间的独立性：如果只考虑独立于时间 $t$ 的随机过程，状态与时间无关，那么
即，$t$ 时刻状态的概率取决于前 $t-1$ 个时刻 $(1, 2, \ldots, t-1)$ 的状态，且状态的转换与时间无关。则该随机过程就是马尔可夫模型。
隐马尔可夫模型
概念导入
对于盲人无法获得天气的情况，但他们可以触摸树叶通过树叶的干燥程度来判断天气的状态。于是天气就是一个隐状态，树叶是一个可观察的状态。
HMM中，我们不知道模型具体的状态序列，只知道状态转移的概率，即状态转换过程是不可观察的。因此，该模型是一个双重随机过程，包括模型的状态转换和特定状态下可观察时间的随机。
HMM组成
假设有 $N$ 个袋子，每个袋子中有 $M$ 种不同颜色的球。选择一个袋子，取出一个球，然后得到球的颜色。这个过程可以用隐藏马尔可夫模型（HMM）来描述，具体参数如下：
- 状态数为 $N$（即袋子的数量）。
- 每个状态可能的符号数为 $M$（即不同颜色球的数目）。
- 状态转移概率矩阵 $A = [a_{ij}]$，其中 $a_{ij}$ 表示从一只袋子（状态 $S_i$）转向另一只袋子（状态 $S_j$）取球的概率。
- 观察概率矩阵 $B = [b_j(k)]$，其中 $b_j(k)$ 表示从第 $j$ 个袋子中取出第 $k$ 种颜色的球的概率。
- 初始状态的概率分布 $\pi = [\pi_i]$，其中 $\pi_i$ 表示模型在开始时处于状态 $S_i$ 的概率。
模型的三要素为 $\lambda = [\pi, A, B]$ ：
初始状态概率 $\pi$: 模型在初始时刻各状态出现的概率，通常记为 $\pi = (\pi_1, \pi_2, \ldots, \pi_N)$，其中 $\pi_i$ 表示模型的初始状态为 $S_i$ 的概率。
状态转移概率 $A$: 模型在各个状态间转换的概率，通常记为矩阵 $A = [a_{ij}]$，其中 $a_{ij}$ 表示在任意时刻 $t$，若状态为 $S_i$，则在下一时刻状态为 $S_j$ 的概率。
输出观测概率 $B$: 模型根据当前状态获得各个观测值的概率，通常记为矩阵 $B = [b_j(k)]$。其中，$b_j(k)$ 表示在任意时刻 $t$，若状态为 $S_j$，则观测值 $v_k$ 被获取的概率。
相对于马尔可夫模型: 隐马尔可夫只是多了一个各状态的观测概率
三个问题
评估（Evaluation）问题： 给定一个HMM和一个观察序列，求这个观察序列出现的概率。
示例： 假设有一个描述天气变化的隐马尔可夫模型，包括第一天的天气概率分布、天气转移概率矩阵以及特定天气下树叶湿度的概率分布。现在要求得在第一天湿度为1，第二天湿度为2，第三天湿度为3的情况下，这一系列观察出现的概率。
解码（Decoding）问题： 给定一个HMM和一个观察序列，求解能够最好地解释这个观察序列的状态序列。
示例： 继续使用上述天气的隐马尔可夫模型，已知连续三天的树叶湿度观测值分别为1、2和3。现在的目标是找出这三天最可能的天气情况。
学习（Learning）问题： 给定观察序列，如何调整模型参数使得这个模型能够最好地解释观察数据。
示例： 已知连续三天的树叶湿度观测值分别为1、2和3，如何确定一个天气的隐马尔可夫模型，包括最开始的天气概率分布、天气转移概率矩阵以及在特定天气下树叶湿度的概率分布。
前向算法
用于解决：评估问题
评估（Evaluation）问题： 给定一个HMM和一个观察序列，求这个观察序列出现的概率。
示例： 假设有一个描述天气变化的隐马尔可夫模型，包括第一天的天气概率分布、天气转移概率矩阵以及特定天气下树叶湿度的概率分布。现在要求得在第一天湿度为1，第二天湿度为2，第三天湿度为3的情况下，这一系列观察出现的概率。
下面是前向算法的步骤：
初始化： 对于每一个状态 $i$，计算观察序列的第一个符号被观察到，并且模型处于开始状态 $i$ 的概率。这可以用初始状态概率 $\pi_i$ 乘以给定状态下第一个观察符号的概率来表示。即，计算前向概率 $\alpha_1(i) = \pi_i b_i(O_1)$，其中 $O_1$ 是观察序列的第一个观察值，$b_i(O_1)$ 是在状态 $i$ 观察到 $O_1$ 的概率。
递归： 对于每一个时间点 $t = 2, 3, …, T$（$T$ 是观察序列的总长度）和每一个状态 $i$，计算时刻 $t$ 处于状态 $i$ 的概率，考虑所有可能到达状态 $i$ 的路径。这可以通过前一时间点所有状态的前向概率与状态转移概率和当前观察值的概率乘积的总和来实现。即，计算 $\alpha_t(i) = \left[\sum_{j=1}^{N} \alpha_{t-1}(j) a_{ji}\right] b_i(O_t)$，其中 $N$ 是状态的总数。
终止： 计算最终的概率，即在所有可能的结束状态上，将最后一个观察值的前向概率相加。即，求得观察序列概率 $P(O|\lambda) = \sum_{i=1}^{N} \alpha_T(i)$，其中 $\lambda$ 是模型参数。
状态集合：$S = \{晴天, 雨天\}$
观察集合：$V = \{伞, 无伞\}$
初始状态概率：$\pi = [0.6, 0.4]$（意味着开始时有 60% 的概率是晴天，40% 的概率是雨天）
状态转移概率矩阵：$A = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$（意味着从晴天转为晴天的概率为 0.7，晴天转为雨天的概率为 0.3，以此类推）
观察概率矩阵：$B = \begin{bmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{bmatrix}$（意味着在晴天时无伞的概率为 0.9，携带伞的概率为 0.1，以此类推）
假设观察到的序列为：“伞，伞，无伞”，表示连续三天中，前两天携带伞，第三天没有携带伞。
计算步骤：
初始化：
- 对于晴天：$\alpha_1(晴天) = \pi_{晴天} \times b_{晴天}(伞) = 0.6 \times 0.1 = 0.06$
- 对于雨天：$\alpha_1(雨天) = \pi_{雨天} \times b_{雨天}(伞) = 0.4 \times 0.8 = 0.32$
递归（计算第二天的概率）：
- 晴天：$\alpha_2(晴天) = [\alpha_1(晴天) \times a_{晴天,晴天} + \alpha_1(雨天) \times a_{雨天,晴天}] \times b_{晴天}(伞) = [0.06 \times 0.7 + 0.32 \times 0.4] \times 0.1 = (0.042 + 0.128) \times 0.1 = 0.017$
- 雨天：$\alpha_2(雨天) = [\alpha_1(晴天) \times a_{晴天,雨天} + \alpha_1(雨天) \times a_{雨天,雨天}] \times b_{雨天}(伞) = [0.06 \times 0.3 + 0.32 \times 0.6] \times 0.8 = (0.018 + 0.192) \times 0.8 = 0.168$
递归（计算第三天的概率）：
- 晴天：$\alpha_3(晴天) = [\alpha_2(晴天) \times a_{晴天,晴天} + \alpha_2(雨天) \times a_{雨天,晴天}] \times b_{晴天}(无伞) = [0.017 \times 0.7 + 0.168 \times 0.4] \times 0.9 = …$
- 雨天：$\alpha_3(雨天) = [\alpha_2(晴天) \times a_{晴天,雨天} + \alpha_2(雨天) \times a_{雨天,雨天}] \times b_{雨天}(无伞) = …$
终止： 计算最终概率，即将第三天的概率相加。
后向算法
初始化： 对于每一个状态 $i$，在时间 $T$（观察序列的末尾），后向概率 $\beta_T(i) = 1$，对于所有 $1 \leq i \leq N$。
循环计算： 对于每个时间点 $t = T-1, T-2, \ldots, 1$ 和每个状态 $i$，计算时刻 $t$ 的后向概率：
这里，$a_{ij}$ 是从状态 $i$ 转移到状态 $j$ 的概率，$b_j(O_{t+1})$ 是在状态 $j$ 观察到 $O_{t+1}$ 的概率，$\beta_{t+1}(j)$ 是在时间 $t+1$ 且在状态 $j$ 的后向概率。
结束： 最终，计算整个观察序列的概率 $P(O|\mu)$ 通过累加所有可能的起始状态的后向概率：
这里，$\pi_i$ 是开始时在状态 $i$ 的概率，$b_i(O_1)$ 是在状态 $i$ 观察到第一个观察值 $O_1$ 的概率。
Viterbi搜索算法
用于：解码问题
解码（Decoding）问题： 给定一个HMM和一个观察序列，求解能够最好地解释这个观察序列的状态序列。
示例： 继续使用上述天气的隐马尔可夫模型，已知连续三天的树叶湿度观测值分别为1、2和3。现在的目标是找出这三天最可能的天气情况。
算法步骤：
初始化： 对于每一个状态 $i$，计算在时间 $t=1$ 观察到 $O_1$ 且处于状态 $i$ 的最大概率，并记录路径。这可以用初始状态概率 $\pi_i$ 乘以给定状态 $i$ 下观察 $O_1$ 的概率 $b_i(O_1)$ 来计算。即，
同时初始化最优路径的回溯指针：
递归： 对于每个时间点 $t=2, \ldots, T$ （$T$ 是观察序列的长度）和每个状态 $i$，计算到达时间点 $t$ 的状态 $i$ 的最大概率，并记录到达该状态的最优路径：
更新回溯指针：
终止： 找到最终时间点 $T$ 的最大概率及其对应的状态：
这里，$P^$ 是最优路径的概率，$q_T^$ 是最终状态。
路径回溯： 从最终状态 $q_T^*$ 开始，使用回溯指针 $\psi_t(i)$ 寻找最优路径：
最终，$q^ = (q_1^, q_2^, \ldots, q_T^)$ 是最有可能产生观察序列 $O$ 的状态序列。
模型参数如下：
状态集合：$S = \{晴天, 雨天\}$
观察集合：$V = \{伞, 无伞\}$
初始状态概率：$\pi = [0.6, 0.4]$（意味着开始时有 60% 的概率是晴天，40% 的概率是雨天）
状态转移概率矩阵：$A = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$（意味着从晴天转为晴天的概率为 0.7，晴天转为雨天的概率为 0.3，以此类推）
观察概率矩阵：$B = \begin{bmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{bmatrix}$（意味着在晴天时无伞的概率为 0.9，携带伞的概率为 0.1，以此类推）
给定观察序列为：“伞，无伞，伞”，我们要找出最可能的天气序列。
应用Viterbi算法:
初始化：计算第一天观察到“伞”时各状态的最大概率。
- 晴天：$\delta_1(晴天) = \pi_{晴天} \cdot b_{晴天}(伞) = 0.6 \times 0.1 = 0.06$
- 雨天：$\delta_1(雨天) = \pi_{雨天} \cdot b_{雨天}(伞) = 0.4 \times 0.8 = 0.32$
递归：
第二天观察到“无伞”：
- 晴天：
$\delta_2(晴天) = \max[\delta_1(晴天) \cdot a_{晴天,晴天}, \delta_1(雨天) \cdot a_{雨天,晴天}] \cdot b_{晴天}(无伞) = \max[0.06 \times 0.7, 0.32 \times 0.4] \times 0.9 \approx \max[0.042, 0.128] \times 0.9 = 0.1152$ - 雨天：
$\delta_2(雨天) = \max[\delta_1(晴天) \cdot a_{晴天,雨天}, \delta_1(雨天) \cdot a_{雨天,雨天}] \cdot b_{雨天}(无伞) = \max[0.06 \times 0.3, 0.32 \times 0.6] \times 0.2 \approx \max[0.018, 0.192] \times 0.2 = 0.0384$
- 晴天：
第三天观察到“伞”：
这一步将重复上述计算，考虑第二天的所有$\delta$值，转移到第三天的每个状态，并乘以第三天观察到“伞”的观察概率。
终止：在第三天结束时，找到$\delta_3(晴天)$和$\delta_3(雨天)$中的最大值，这将给出最终的最大概率。
回溯：根据最终天的最大概率状态，通过$\psi$矩阵回溯以找到最可能的天气序列。
参数学习
解决隐马尔可夫模型（HMM）的学习问题，即从观察序列中估计模型参数（状态转移概率、观察概率和初始状态概率），通常使用Baum-Welch算法，也称为前向-后向算法。这是一种基于期望最大化（EM）算法的迭代算法，用于找到使观察序列出现概率最大化的HMM参数。
Baum-Welch算法步骤：
初始化：随机选择HMM的参数（状态转移概率矩阵 $A$、观察概率矩阵 $B$ 和初始状态概率向量 $\pi$）或使用先验知识进行初始化。
E步骤（Expectation）：使用当前的模型参数，对于每一对状态 $i$ 和 $j$，以及每个时间 $t$，计算：
- 前向概率 $\alpha_t(i)$ 和 后向概率 $\beta_t(i)$。
- 在时刻 $t$ 处于状态 $i$ 的概率 $\gamma_t(i)$。
- 在时刻 $t$ 从状态 $i$ 转移到状态 $j$ 的概率 $\xi_t(i, j)$。
这些概率用于计算状态转移和观察发生的期望次数。
M步骤（Maximization）：更新模型参数：
- 更新状态转移概率矩阵 $A$ 的元素 $a_{ij}$，以最大化下一步的期望对数似然。
- 更新观察概率矩阵 $B$ 的元素 $b_j(k)$，以最大化对数似然。
- 更新初始状态概率向量 $\pi$，以反映观察序列开始时各状态的估计概率。
重复E步骤和M步骤，直到模型参数的改变或似然函数的增加低于某个阈值，表示已经达到收敛。
HMM在NLP中的应用
当我们有标注语料时，可以直接统计语料中的信息来计算HMM的参数。
- 计算初始状态概率分布：通过统计语料中每个句子第一个词的开始位置出现的频率来估计。
计算转移概率矩阵：通过统计语料中词边界从一个状态转移到另一个状态的频率来估计。在中文分词中，状态通常代表词的开始（B）、词中（M）、词结束（E）以及单字成词（S）。
计算输出概率矩阵：通过统计语料中每种字符在各状态下出现的频率来估计。
使用Viterbi算法解码：利用上述计算得到的参数，对新的未标注文本序列使用Viterbi算法找出最有可能的状态序列，即分词结果。
当没有标注语料时，可以通过无监督学习，如EM算法，来估计HMM的参数。
获取词的个数：根据一定的启发式规则或假设来估计或设定词的个数。
确定状态的个数：中文分词通常可以分为四个状态——词的开始（B）、词中（M）、词结束（E）、单字成词（S）。
参数学习：利用EM算法迭代地估计HMM的参数。在E步骤，根据当前参数估计每个状态序列出现的概率；在M步骤，更新模型参数以最大化观察数据的似然函数。
- E步骤（Expectation）：计算或更新每个时间点字符处于各个状态的期望值。
- M步骤（Maximization）：根据E步骤计算的期望值来更新初始状态概率、转移概率和输出概率。
使用Viterbi算法解码：使用EM算法学习得到的参数，对新的文本数据进行分词。