隐马尔科夫模型HMM（四） -- 参数估计问题

忘是亡心i 2022-01-21 01:11 255阅读 0赞

最后，我们研究第三个问题，参数估计问题。也即是给定一个观察序列 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∣μ)最大？

## 最大似然估计 ##

模型的参数是指构成 μ \\mu μ的 π i , a i j , b j ( k ) \\pi\_\{i\},a\_\{ij\},b\_\{j\}(k) πi,aij,bj(k)。最大似然估计方法可以作为HMM参数估计的一种选择。如果产生观察序列O的状态序列 Q = q 1 q 2 . . . q T Q=q\_\{1\}q\_\{2\}...q\_\{T\} Q=q1q2...qT已知，根据最大似然估计，HMM的参数可以通过如下公式计算：  
 π i ˉ = δ ( q 1 , s i ) \\bar\{\\pi \_\{i\}\}=\\delta (q\_\{1\},s\_\{i\}) πiˉ=δ(q1,si)  
 a i j ˉ = Q 中 从 状 态 q i 转 移 到 q j 的 次 数 Q 中 所 有 从 状 态 q i 转 移 到 另 一 状 态 （ 包 括 q j 本 身 ） 的 次 数 = ∑ t = 1 T − 1 δ ( q t , s i ) × δ ( q t + 1 , s j ) ∑ t = 1 T − 1 δ ( q t , s i ) \\bar\{a\_\{ij\}\}=\\frac\{Q中从状态q\_\{i\}转移到q\_\{j\}的次数\}\{Q中所有从状态q\_\{i\}转移到另一状态（包括q\_\{j\}本身）的次数\}\\\\=\\frac\{\\sum\_\{t=1\}^\{T-1\}\\delta (q\_\{t\},s\_\{i\})\\times \\delta (q\_\{t+1\},s\_\{j\})\}\{\\sum\_\{t=1\}^\{T-1\}\\delta (q\_\{t\},s\_\{i\})\} aijˉ=Q中所有从状态qi转移到另一状态（包括qj本身）的次数Q中从状态qi转移到qj的次数=∑t=1T−1δ(qt,si)∑t=1T−1δ(qt,si)×δ(qt\+1,sj)  
 b j ( k ) ˉ = Q 中 从 状 态 q j 输 出 到 符 号 ν k 的 次 数 Q 中 到 达 q j 次 数 = ∑ t = 1 T δ ( q t , s j ) × δ ( O t , ν k ) ∑ t = 1 T δ ( q t , s j ) \\bar\{b\_\{j\}(k)\}=\\frac\{Q中从状态q\_\{j\}输出到符号\\nu \_\{k\}的次数\}\{Q中到达q\_\{j\}次数\}\\\\=\\frac\{\\sum\_\{t=1\}^\{T\}\\delta (q\_\{t\},s\_\{j\})\\times \\delta (O\_\{t\},\\nu \_\{k\})\}\{\\sum\_\{t=1\}^\{T\}\\delta (q\_\{t\},s\_\{j\})\} bj(k)ˉ=Q中到达qj次数Q中从状态qj输出到符号νk的次数=∑t=1Tδ(qt,sj)∑t=1Tδ(qt,sj)×δ(Ot,νk)  
       其中， δ ( x , y ) \\delta (x,y) δ(x,y)为克罗奈克函数，当 x = y x=y x=y时， δ ( x , y ) = 1 \\delta (x,y)=1 δ(x,y)=1；否则 δ ( x , y ) = 0 \\delta (x,y)=0 δ(x,y)=0。 ν k \\nu \_\{k\} νk是HMM输出符号集中的第k个符号。  
       但是在实际中，由于HMM中的状态序列Q是观察不到的（隐变量），因此，这种最大似然估计的方法不可行。

## 期望最大化（EM） ##

期望最大化（EM）算法可以用于含有隐变量的统计模型的参数最大似然估计。其基本思想是，初始化时随机地给模型的参数赋值，该赋值遵循模型对参数的限制，例如，从某一状态出发的所有转移概率的和为1。给模型的参数赋初值以后，得到模型 μ 0 \\mu \_\{0\} μ0，然后，根据 μ 0 \\mu \_\{0\} μ0可以得到模型中隐变量的期望值。例如，从 μ 0 \\mu \_\{0\} μ0得到某一状态转移到另一状态的期望次数，用期望次数来替代最大似然中的实际次数，这样可以得到模型参数的新估计值，由此得到新的模型 μ 1 \\mu \_\{1\} μ1。从 μ 1 \\mu \_\{1\} μ1又可以得到模型中隐变量的期望值，然后重新估计模型的参数，执行这个迭代过程，直到参数收敛于最大似然估计值。  
       前向后向算法可以用于具体实现这种EM算法。  
       给定HMM的参数 μ \\mu μ和观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，在时间t的状态是 s i s\_\{i\} si，时间t+1的状态是 s j s\_\{j\} sj的概率 ξ t ( i , j ) = P ( q t = s i , q t + 1 = s j , O ∣ μ ) P ( O ∣ μ ) = α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( i ) P ( O ∣ μ ) = α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( i ) ∑ i = 1 N ∑ j = 1 N α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( i ) \\xi \_\{t\}(i,j)=\\frac\{P(q\_\{t\}=s\_\{i\},q\_\{t+1\}=s\_\{j\},O|\\mu )\}\{P(O|\\mu )\}\\\\ =\\frac\{\\alpha \_\{t\}\\left ( i\\right )a\_\{ij\}b\_\{j\}(O\_\{t+1\})\\beta \_\{t+1\}\\left ( i\\right )\}\{P(O|\\mu )\}\\\\ =\\frac\{\\alpha \_\{t\}\\left ( i\\right )a\_\{ij\}b\_\{j\}(O\_\{t+1\})\\beta \_\{t+1\}\\left ( i\\right )\}\{\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha \_\{t\}\\left ( i\\right )a\_\{ij\}b\_\{j\}(O\_\{t+1\})\\beta \_\{t+1\}\\left ( i\\right )\} ξt(i,j)=P(O∣μ)P(qt=si,qt\+1=sj,O∣μ)=P(O∣μ)αt(i)aijbj(Ot\+1)βt\+1(i)=∑i=1N∑j=1Nαt(i)aijbj(Ot\+1)βt\+1(i)αt(i)aijbj(Ot\+1)βt\+1(i)  
       下图给出了前向变量 α t ( i ) \\alpha \_\{t\}(i) αt(i)、后向变量 β t + 1 ( j ) \\beta \_\{t+1\}(j) βt\+1(j)与概率 ξ t ( i , j ) \\xi \_\{t\}(i,j) ξt(i,j)之间的关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]

给定HMM的 μ \\mu μ参数和观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，在时间t位于状态 s i s\_\{i\} si的概率 γ t ( i ) \\gamma \_\{t\}(i) γt(i)为：  
 γ t ( i ) = ∑ j = 1 N ξ t ( i , j ) \\gamma \_\{t\}(i)=\\sum\_\{j=1\}^\{N\}\\xi \_\{t\}(i,j) γt(i)=j=1∑Nξt(i,j)  
       由此， μ \\mu μ的参数可以由下面的公式重新估计：  
 π i ˉ = P ( q 1 = s i ∣ O , μ ) = γ 1 ( i ) \\bar\{\\pi \_\{i\}\}=P(q\_\{1\}=s\_\{i\}|O,\\mu )=\\gamma \_\{1\}(i) πiˉ=P(q1=si∣O,μ)=γ1(i)  
 a i j ˉ = Q 中 从 状 态 q i 转 移 到 q j 的 期 望 次 数 Q 中 所 有 从 状 态 q i 转 移 到 另 一 状 态 （ 包 括 q j 本 身 ） 的 期 望 次 数 = ∑ t = 1 T − 1 ξ t ( i , j ) ∑ t = 1 T − 1 γ t ( i ) \\bar\{a\_\{ij\}\}=\\frac\{Q中从状态q\_\{i\}转移到q\_\{j\}的期望次数\}\{Q中所有从状态q\_\{i\}转移到另一状态（包括q\_\{j\}本身）的期望次数\}\\\\=\\frac\{\\sum\_\{t=1\}^\{T-1\}\\xi \_\{t\}(i,j)\}\{\\sum\_\{t=1\}^\{T-1\}\\gamma \_\{t\}(i)\} aijˉ=Q中所有从状态qi转移到另一状态（包括qj本身）的期望次数Q中从状态qi转移到qj的期望次数=∑t=1T−1γt(i)∑t=1T−1ξt(i,j)  
 b j ( k ) ˉ = Q 中 从 状 态 q j 输 出 到 符 号 ν k 的 期 望 次 数 Q 中 到 达 q j 的 期 望 次 数 = ∑ t = 1 T γ t ( j ) × δ ( O t , ν k ) ∑ t = 1 T γ t ( j ) \\bar\{b\_\{j\}(k)\}=\\frac\{Q中从状态q\_\{j\}输出到符号\\nu \_\{k\}的期望次数\}\{Q中到达q\_\{j\}的期望次数\}\\\\=\\frac\{\\sum\_\{t=1\}^\{T\}\\gamma \_\{t\}(j)\\times \\delta (O\_\{t\},\\nu \_\{k\})\}\{\\sum\_\{t=1\}^\{T\}\\gamma \_\{t\}(j)\} bj(k)ˉ=Q中到达qj的期望次数Q中从状态qj输出到符号νk的期望次数=∑t=1Tγt(j)∑t=1Tγt(j)×δ(Ot,νk)  
       根据上述思路，给出**前向后向算法**：  
（1）初始化，随机地给参数 π i , a i j , b j ( k ) \\pi\_\{i\},a\_\{ij\},b\_\{j\}(k) πi,aij,bj(k)赋值，使其满足如下约束条件：  
 ∑ i = 1 N π i = 1 ∑ j = 1 N a i j = 1 , 1 ≤ i ≤ N ∑ k = 1 M b j ( k ) = 1 , 1 ≤ j ≤ M \\sum\_\{i=1\}^\{N\}\\pi \_\{i\}=1\\\\ \\sum\_\{j=1\}^\{N\}a\_\{ij\}=1,1\\leq i\\leq N\\\\ \\sum\_\{k=1\}^\{M\}b\_\{j\}(k)=1,1\\leq j\\leq M i=1∑Nπi=1j=1∑Naij=1,1≤i≤Nk=1∑Mbj(k)=1,1≤j≤M  
由此得到模型 μ 0 \\mu \_\{0\} μ0，令 i = 0 i=0 i=0，执行下面的EM估计。  
（2）EM计算：  
**E步骤**：由模型 μ i \\mu\_\{i\} μi，根据  
 ξ t ( i , j ) = α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( i ) ∑ i = 1 N ∑ j = 1 N α t ( i ) a i j b j ( O t + 1 ) β t + 1 ( i ) \\xi \_\{t\}(i,j) =\\frac\{\\alpha \_\{t\}\\left ( i\\right )a\_\{ij\}b\_\{j\}(O\_\{t+1\})\\beta \_\{t+1\}\\left ( i\\right )\}\{\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha \_\{t\}\\left ( i\\right )a\_\{ij\}b\_\{j\}(O\_\{t+1\})\\beta \_\{t+1\}\\left ( i\\right )\} ξt(i,j)=∑i=1N∑j=1Nαt(i)aijbj(Ot\+1)βt\+1(i)αt(i)aijbj(Ot\+1)βt\+1(i)  
和 γ t ( i ) = ∑ j = 1 N ξ t ( i , j ) \\gamma \_\{t\}(i)=\\sum\_\{j=1\}^\{N\}\\xi \_\{t\}(i,j) γt(i)=j=1∑Nξt(i,j)计算出期望值 ξ t ( i , j ) \\xi \_\{t\}(i,j) ξt(i,j)和 γ t ( i ) \\gamma \_\{t\}(i) γt(i)；  
**M-步骤**：用E步骤得到的期望值，根据  
 π i ˉ = P ( q 1 = s i ∣ O , μ ) = γ 1 ( i ) \\bar\{\\pi \_\{i\}\}=P(q\_\{1\}=s\_\{i\}|O,\\mu )=\\gamma \_\{1\}(i) πiˉ=P(q1=si∣O,μ)=γ1(i)  
 a i j ˉ = ∑ t = 1 T − 1 ξ t ( i , j ) ∑ t = 1 T − 1 γ t ( i ) \\bar\{a\_\{ij\}\}=\\frac\{\\sum\_\{t=1\}^\{T-1\}\\xi \_\{t\}(i,j)\}\{\\sum\_\{t=1\}^\{T-1\}\\gamma \_\{t\}(i)\} aijˉ=∑t=1T−1γt(i)∑t=1T−1ξt(i,j)  
 b j ( k ) ˉ = ∑ t = 1 T γ t ( j ) × δ ( O t , ν k ) ∑ t = 1 T γ t ( j ) \\bar\{b\_\{j\}(k)\}=\\frac\{\\sum\_\{t=1\}^\{T\}\\gamma \_\{t\}(j)\\times \\delta (O\_\{t\},\\nu \_\{k\})\}\{\\sum\_\{t=1\}^\{T\}\\gamma \_\{t\}(j)\} bj(k)ˉ=∑t=1Tγt(j)∑t=1Tγt(j)×δ(Ot,νk)  
重新估计参数 π i , a i j , b j ( k ) \\pi\_\{i\},a\_\{ij\},b\_\{j\}(k) πi,aij,bj(k)的值，得到模型 μ i + 1 \\mu \_\{i+1\} μi\+1；  
（3）循环计算：  
       令 i = i + 1 i=i+1 i=i\+1，重复执行EM计算，直到 π i , a i j , b j ( k ) \\pi\_\{i\},a\_\{ij\},b\_\{j\}(k) πi,aij,bj(k)收敛。  
       HMM在自然语言处理研究中有着非常广泛的应用。除了上述讨论的理论问题外，在实际应用中还有若干实现技术上的问题需要注意。例如多个概率连乘引起的浮点数下溢问题。在维特比算法中只涉及到乘法运算和求最大值问题，因此可以对概率相乘的算式取对数运算，使得乘法运算变成加法运算，这样一方面避免了浮点数下溢的问题，另一方面，提高了运算速度。在前向后向算法中，也经常采用如下对数运算的方法判断参数 π i , a i j , b j ( k ) \\pi\_\{i\},a\_\{ij\},b\_\{j\}(k) πi,aij,bj(k)是否收敛：  
 ∣ l o g P ( O ∣ μ i + 1 ) − l o g P ( O ∣ μ i ) ∣ < ϵ |logP(O|\\mu \_\{i+1\}) - logP(O|\\mu \_\{i\})|<\\epsilon ∣logP(O∣μi\+1)−logP(O∣μi)∣<ϵ  
其中， ϵ \\epsilon ϵ为一个足够小的实数值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]: /images/20220121/bf5edd0f82f54400a18bc0d16eb9f788.png