隐马尔科夫模型HMM（一） -- 模型介绍

小灰灰 2022-01-22 23:07 311阅读 0赞

目前在工作中使用到了jieba分词，主要是对文章进行切词，在深入理解jieba切词原理的时候，发现其采用了隐马尔科夫模型HMM，因此对HMM进行了研究，这里就自己学习到的知识进行记录。文章主要参考了宗成庆老师的《统计自然语言处理》第二版，非常感谢宗老师！

## 一、马尔科夫模型 ##

马尔可夫模型是一类随机过程。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。  
       **马尔科夫假设**：随机过程中各个状态 O t O\_\{t\} Ot 的概率分布，只与它前一个状态 O t − 1 O\_\{t-1\} Ot−1有关，即  
 P ( O t ∣ O 1 , O 2 , O 3 . . . O t − 1 ) = P ( O t ∣ O t − 1 ) P\\left ( O\_\{t\}|O\_\{1\},O\_\{2\},O\_\{3\}...O\_\{t-1\} \\right )=P\\left ( O\_\{t\}|O\_\{t-1\} \\right ) P(Ot∣O1,O2,O3...Ot−1)=P(Ot∣Ot−1)  
       **一阶马尔可夫链**：符合马尔可夫假设的随机过程，即随机过程中各个状态 O t O\_\{t\} Ot 的概率分布，只与它前一个状态 O t − 1 O\_\{t-1\} Ot−1有关。  
![在这里插入图片描述][20190601113220548.jpg]

**马尔可夫模型形式化表述**：  
 μ = ( S , π , A ) \\mu =\\left ( S,\\pi ,A \\right ) μ=(S,π,A)  
S：所有可能的状态集合  
 π \\pi π：初始状态概率  
A：转移状态概率

## 二、隐马尔科夫模型HMM ##

#### 1、HMM举例 ####

在马尔科夫模型中，每个状态代表了一个可观察的事件，所以马尔科夫模型又称为可视马尔科夫模型。在 隐马尔科夫模型HMM中，我们不知道模型所经历过的状态序列，只知道状态的概率函数，也就是观察到的事件是状态的随机函数。因此，HMM是一个双重的随机过程，其中模型的状态转换过程是隐藏的，可观察事件的随机过程是隐藏状态转换过程的随机函数。  
       如下图所示为HMM的基本原理：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]  
       下面举例对HMM的含义进行说明。假如一个暗室中有N个口袋，每个口袋中有M个不同颜色的球。一个实验员根据某一概率分布随机地选取一个初始口袋，从中根据不同颜色的球的概率分布，随机取出一个球，并向室外的人报告该球的颜色。然后，再根据口袋的概率分布选择另一个口袋，根据不同颜色的球的概率分布从中随机的选择另一个球，重复这个过程。对于室外的人来说，可观察到的只是不同颜色的球的序列，而口袋的序列是不可观察的。在这个过程中，每个口袋对应于HMM中的**状态**，球的颜色对应于HMM中**状态的输出符号**，从一个口袋转移到另一个口袋对应于**状态转换**，从口袋中取出球的颜色对应于从**一个状态输出的观察符号**。  
       因此，一个HMM由以下几部分组成：  
（1）模型中状态的数目N（口袋的个数）  
（2）从每个状态可能输出的不同符合的数目 M（球的不同颜色的数目）  
（3）状态转移概率矩阵 A = \{ a i j \} A=\\left \\\{ a\_\{ij\} \\right \\\} A=\{ aij\}（ a i j a\_\{ij\} aij是实验员从一个口袋 s i s\_\{i\} si转向另一个口袋 s j s\_\{j\} sj取球的概率），其中，  
 a i j = P ( q t = s j ∣ q t − 1 = s i ) , 1 ≤ i , j ⩽ N a i j ⩾ 0 ∑ j = 1 N a i j = 1 a\_\{ij\}=P\\left ( q\_\{t\}=s\_\{j\} |q\_\{t-1\}=s\_\{i\}\\right ),1\\leq i,j\\leqslant N\\\\a\_\{ij\} \\geqslant 0\\\\\\sum\_\{j=1\}^\{N\}a\_\{ij\}=1 aij=P(qt=sj∣qt−1=si),1≤i,j⩽Naij⩾0j=1∑Naij=1  
（4）从状态 s j s\_\{j\} sj观察到符号 ν k \\nu\_\{k\} νk的概率分布矩阵 B = \{ b j ( k ) \} B=\\left \\\{ b\_\{j\}\\left ( k \\right )\\right \\\} B=\{ bj(k)\}（ b j ( k ) b\_\{j\}\\left ( k \\right ) bj(k)为实验员从第j个口袋中取出第k中颜色的球的概率），其中  
 b j ( k ) = P ( O t = υ k ∣ q t = s j ) , 1 ≤ j ⩽ N ; 1 ≤ k ⩽ M b j ( k ) ⩾ 0 ∑ k = 1 M b j ( k ) = 1 b\_\{j\}\\left ( k \\right )=P\\left ( O\_\{t\}=\\upsilon\_\{k\} |q\_\{t\}=s\_\{j\}\\right ),1\\leq j \\leqslant N;1\\leq k \\leqslant M\\\\b\_\{j\}\\left ( k \\right )\\geqslant 0\\\\\\sum\_\{k=1\}^\{M\}b\_\{j\}\\left ( k \\right )=1 bj(k)=P(Ot=υk∣qt=sj),1≤j⩽N;1≤k⩽Mbj(k)⩾0k=1∑Mbj(k)=1  
观察符号的概率又称符号发射概率。  
（5）初始状态概率分布 π = \{ π i \} \\pi =\\left \\\{ \\pi \_\{i\} \\right \\\} π=\{ πi\}，其中  
 π i = P ( q 1 = s i ) , 1 ≤ i ≤ N π i ≥ 0 ∑ i = 1 N π i = 1 \\pi \_\{i\}=P\\left ( q\_\{1\} =s\_\{i\}\\right ),1\\leq i\\leq N\\\\\\pi \_\{i\}\\geq 0\\\\\\sum\_\{i=1\}^\{N\}\\pi \_\{i\}=1 πi=P(q1=si),1≤i≤Nπi≥0i=1∑Nπi=1  
       一般地，一个HMM记为一个五元组 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)，其中S为状态的集合，K为输出符号的集合， π , A , B \\pi,A,B π,A,B分别是初始状态的概率分布、状态转移概率和符号发射概率。

#### 2、HMM的重要假设 ####

（1）**齐次马尔科夫假设**：任一时刻 t 的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻 t 无关。即  
 P ( q t ∣ q 1 , q 2 , q 3 . . . q t − 1 ) = P ( q t ∣ q t − 1 ) P\\left ( q\_\{t\}|q\_\{1\},q\_\{2\},q\_\{3\}...q\_\{t-1\} \\right )=P\\left ( q\_\{t\}|q\_\{t-1\} \\right ) P(qt∣q1,q2,q3...qt−1)=P(qt∣qt−1)  
（2）**观测独立性假设**：任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，与其它时刻的状态及观测无关。即  
 P ( O t ∣ q 1 , q 2 , q 3 . . . q t − 1 O 1 , O 2 , O 3 . . . O t − 1 ) = P ( O t ∣ q t ) P\\left ( O\_\{t\}|q\_\{1\},q\_\{2\},q\_\{3\}...q\_\{t-1\}O\_\{1\},O\_\{2\},O\_\{3\}...O\_\{t-1\} \\right )=P\\left ( O\_\{t\}|q\_\{t\} \\right ) P(Ot∣q1,q2,q3...qt−1O1,O2,O3...Ot−1)=P(Ot∣qt)

#### 3、HMM观察序列的生成 ####

输入：HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)，以及观察序列的长度T  
输出：观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT  
生成过程如下：  
（1）根据初始状态的概率分布 π i \\pi\_\{i\} πi选择一个初始状态 q 1 = s i q\_\{1\}=s\_\{i\} q1=si;  
（2）设t=1;  
（3）根据状态 s i s\_\{i\} si的输出概率分布 b i ( k ) b\_\{i\}\\left ( k \\right ) bi(k)输出 O t = ν k O\_\{t\}=\\nu \_\{k\} Ot=νk；  
（4）根据状态转移概率分布 a i j a\_\{ij\} aij，将当前时刻t的状态转移到新的状态 q t + 1 = s j q\_\{t+1\}=s\_\{j\} qt\+1=sj；  
（5）t=t+1，如果t<T，重复执行步骤（3）和（4），否则，结束算法。

#### 4、HMM中的三个基本问题 ####

（1）**估计问题**：给定一个HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)和观测序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，如何快速地计算出给定模型 μ \\mu μ的情况下，观察序列O的概率，即 P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)？  
（2）**序列问题**：给定一个HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)和观测序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，如何快速有效地选择在一定意义下“最优”的状态序列 Q = q 1 q 2 q 3 . . . q T Q=q\_\{1\}q\_\{2\}q\_\{3\}...q\_\{T\} Q=q1q2q3...qT，使得该状态序列“最好的解释”观察序列，也即是 P ( Q ∣ μ , O ) P\\left ( Q|\\mu,O \\right ) P(Q∣μ,O)最大？  
（3）**参数估计问题**：给定一个观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，如何根据最大似然估计来求模型的参数值？即如何调节模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)的参数，使得 P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)最大？

[20190601113220548.jpg]: /images/20220123/5a59782b11064102a75b8de0984b19c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]: /images/20220123/fe9465990dc344c0ae52cd3fd71048bf.png