隐马尔可夫方法-育师

隐马尔可夫方法：

几个基本要素：隐状态的数量K，每个状态的概率向量Π，隐状态转移矩阵A，隐状态到观测的转换矩阵（即发射矩阵）B。模型可被定义为λ = [A,B, Π]。

隐马尔可夫就是要在基于模型λ成立的前提下，观测出现的概率最大，就是基于极大似然的思想，目标函数为L：

其实就是从某个初始状态开始Πq1，遍历所有可能生成所有观测的路径，所有路径的概率加和。

展示的这条路径就是，从q1的初始状态开始，转换产生观测O1；然后从q1转换到q2，转换产生O2；以此类推不断转换隐状态，并不断生成观测数据直到最后一个观测时间点OT。

上式也可以写成下面这个表达：

分解这个公式L(O, I|λ)：

对于一个序列

模型成立时，序列出现的概率：

模型成立，且序列为时，观测出现的概率如下：

复杂度：如果隐藏状态有N个，序列长度为T个，复杂度为O(TN^T)，就是执行时间和TN^T成正比。

基于已知的Π，A，B，计算似然更高效的算法：

1.前向算法

前向概率（给定隐马尔可夫模型，定义到时刻t的观测序列{o1, o2, o3, o4, ..., ot}，且状态为i的概率为前向概率，记作：

首先算出第一个时刻，隐藏状态为i，观测值为y1的概率：a_i(1) = Π_i*b_iy1；

第二时刻，隐藏状态为i，观测值为y2的概率：a_i(2) = (∑_j a_j(t)*a_ji)*b_iy2；

以此类推，第t时刻，隐藏状态为i，观测值为yt的概率：a_i(t) = (∑_j a_j(t-1)*a_ji)*b_iyt；

最终加和第t时刻，所有隐藏状态下，观测值为yt的概率

计算复杂度：O(N^2*T)

2.后向算法

后向概率：给定马尔可夫模型λ，定义在时刻t状态为i的条件下，从t+1到T的部分观测序列为o_t+1, o_t+2, ... o_T的概率为后向概率:

1.规定当t=T时，。其实这个只是一个方便的规定，后续可以看出来。

2.当t = T-1, T-2, ... , ..., 1

这个公式怎么理解？首先a_ij*b_j(o_t+1)即从t时刻的i状态出发，转换到t+1时刻的j状态，再发射出t+1时刻的观测o_t+1的概率。再之后*β_t+1(j)就是从t+1时刻的j状态出发，生成o_t+2, ... , o_T这个序列。总体来说就是从t时刻的i状态出发，生成o_t+1, o_t+2, ... , o_T序列。然后就是加总所有j状态的计算值。

这里其实可以看出来，当t = t-1时，本质上β_T(j)是不需要的，只需要aij*bj(oT)，只是为了方便，所以设置β_T(j) = 1。其实也可以如下：

递推到最终生成一整个观测序列的概率：

3.一些概率值的计算：

1.给定模型λ和观测序列O，在时刻t处于状态i的概率，记为：

可以进一步展开如下，分母是给定模型λ，出现观测序列O的概率；分子是给定模型λ，出现观测序列O且t时刻状态为i的概率。两个一除自然就是给定模型λ和观测序列O，在时刻t处于状态i的概率。

概率论条件概率公式：P(A|B) = P(A, B) / P(B)

又可以通过前向和后向概率得到分子。因为给定模型λ，出现观测序列O且t时刻状态为i的概率，自然就是α_t(i)（给定λ，定义到时刻t的观测序列{o1, o2, o3, o4, ..., ot}，且状态为i的概率）* b_t(i) （给定λ，定义在时刻t状态为i的条件下，从t+1到T的部分观测序列为o_t+1, o_t+2, ... o_T的概率）：

分母自然就是i取所有值的时候的和：

2.给定模型λ和观测O，在时刻t处于i状态，且在t+1时刻处于j状态的概率：

可变换公式如下：

分子可以变形为：

代入上式得：

几个期望值：

1.在观测O下状态i出现的期望：

2.在观测O下由状态i转移出去的期望：

3.在观测O下，由状态i转移到状态j的期望：

如何得到Π，A，B？

监督学习法：

假设我们已经有了多条观测序列和对应的状态序列，就可以首先计算不同状态的初始概率分布Π，然后算状态间的转移概率a_ij：

以及状态到观测的发射概率b_ij：

这样当我们得到新的观测数据之后，就可以得到对应的状态

非监督学习法：

Baum-Welch 算法：

假设我们只有观测序列，想要得到模型λ = (Π, A, B)，就要使用Baum-Welch。

Baum-Welch使用EM算法：

1.首先构造Q函数，这个是EM算法的E步（求期望），Q函数：

𝜆̂ 是模型参数的当前估计值， 𝜆是要求解的模型参数。上式公式需要注意𝑃(𝑂,𝐼|𝜆̂ )是在对数的外面。公式就是对于logP(O, I | λ)求期望，权值为P(O, I | λ尖)

这个公式相当于，当“假模型”λ尖对应的概率P高/低时，“真模型”λ的对应概率也是同高/同低。

展开Q函数：

2.第二步，即M步（求极大）m，要最大化Q函数，可以分别最大化这三项

第一项：

然后Π_i满足约束条件∑Π_i = 1，在条件下求极值，使用拉格朗日乘数法：

拉格朗日乘数法：要求使得待求函数f(x)取最小值时的自变量，并且服从于约束条件。通过拉格朗日乘数法，把N个自变量，M个约束条件的问题转换为无约束的N+M个自变量的问题。

设f(x, y) = a，当a不同时，可以画出f(x, y)不同的等高线。当且仅当等高线与约束条件g(x,y) = 0相切的时候，有f(x,y)取极值点（可能极大，可能极小，可以想象约束条件是一个椭圆，等高线的两个切点就是极大和极小值）

怎么求极值点？构造拉格朗日函数：L(x, y, λ) = f(x,y) + λg(x,y)。然后L分别对自变量x/y和参数λ求偏导，之后求解出令偏导等于0的自变量和参数。

为什么可以这样求？因为当目标函数f(x,y)的等高线和约束函数g(x,y)相切，f(x,y)和g(x,y)切点的梯度平行（梯度与等高线（等值线）的切线垂直，与等高线的法线同向（同济版高等数学））。在极值点处，目标函数与约束函数相切。

也就是说：取到极值点——>f(x, y)和g(x,y)一定相切——>相切一定f(x)和g(x)梯度平行。

而且梯度（法向量）平行，可以推出f(x,y)和g(x,y)一定相切。梯度同向等价于f(x)和g(x)相切(11 封私信) 如何理解拉格朗日乘子法？ - 知乎（法向量平行，两曲线在切平面也平行，然后两曲线相交，自然切平面重合，也就相切了）。

不过相切不一定取得极值点：相切点只是一个驻点，未必是极值点，也可能是鞍点（所以在使用拉格朗日极值法时，需要判断求得的是鞍点还是极值点，还要判断求得的极值点是极大还是极小值点）

再之后，L(x,y, λ)对自变量x求偏导，则得到：，即满足f(x,y)和g(x,y)在(x,y)处梯度在同一直线上的要求（两个梯度方向相同或相反）。

L(x,y,λ)对λ求偏导，则得到g(x,y) = 0，即约束条件。

逻辑可以用于任意自变量数。

以下拉格朗日乘数法具体实现展开摘自：隐马尔可夫模型之Baum-Welch算法详解-CSDN博客和统计学习方法（第二版）

对于第一项，拉格朗日函数就是：

约束条件：

求偏导数，偏导数为0求得极值：

得到：

又基于约束条件，对i求和得到γ：

最后得到：

第二项：

约束条件：∑_i aij = 1

仅对于i：

对于aij求偏导：

令偏导数为零：

对所有j求和有：

最后有：

第三项：

约束条件：这也意味着对于每个状态j要单独求导。

上式可以变形为：

交换求和顺序得：

拉格朗日方程：

其中：

然后L_j对b_j(k)求偏导得：

得：

所有k = 1, ... , M求和：

对指示函数I求和之后，得到：

又：

得到：

最后：

这样我们就可以得到新的模型参数，作为新一轮EM算法迭代的模型设定。

现在我们有三类参数：

这三类参数都依赖当前假设的模型λ尖，计算各种概率值，怎么计算？

基于上面提到的各种期望值：

对于a_ij:

分子就是在观测O下，由状态i转移到状态j的期望，分母就是从状态i进行转移的期望，则有：

对于b_j(k)：

分母就是在观测O下状态i出现的期望，分子就是再加上一个指示变量，则有：

对于Π_i：

则有：

拓展：如果涉及同时基于多条观测序列的似然进行参数优化的话，可以在每一次迭代整合所有观测得到的概率计算参数 (RABINER, et al., 1989)：

似然变成了联合所有观测的似然：

Π_i同理，就是分子分母分别对所有被试求和。

EM算法每一步都可以增加观测数据关于模型参数的对数似然函数。（见统计学习方法（第二版））

问题：1.为什么这里用拉格朗日乘子法可以求得极大值？而不是极小值或者鞍点？2.为什么说可以得到全局最大值？

首先Q函数的子函数的海森矩阵是负的对角矩阵，也就是负定的 (11 封私信) 负定矩阵主对角元素都为负数 - 知乎。而海森矩阵负定意味着Q函数是严格凹函数(11 封私信) 19.海森矩阵、特征值与函数的凹凸性的关系 - 知乎。而在三个子函数的约束函数下，可行域又全是凸集，例如，设Π = [Π_1, ... , Π_n]T，p = [1, ... , 1]，pTΠ = 1，则这个约束函数就是凸集（最优化理论与算法）。而只要目标函数是严格凹的且可行域是凸集，驻点就只会是全局最大值。所以拉格朗日乘子法得到驻点，一定是全局最大值。📖 Convexity and uniqueness of optimizers — ECON2125/6012 严格凹函数 · 知经百科 · 卓越的经济金融统计考研辅导

推断产生隐状态：

1.近似算法：直接选取每个时刻最可能发生的状态。

基于这γ，求得在每一个t时刻最可能出现的状态：

近似算法的问题：虽然整体上可以算得最高效率的状态序列，但是可能存在前后时间点的状态之间的转移概率为0的情况，这也是不实际的。

2.维特比算法：从t时刻起，递推计算每条可能路径的概率，选择最大概率的那条路径，直到时刻T。然后从最后一个时刻，递推出前面的时刻的状态。其实也还是看哪条路径让观测数据出现概率更大，并且这样肯定能规避得到的状态序列前后两个状态转移概率为0的情况。

公式：

两个变量：δ和Ψ。δ_t(i)就是使t时刻下最可能出现状态i的序列的概率；Ψ_t(i)是使得t时刻最可能出现状态i的t-1时刻的状态。

终止：到达最后一个时间点，总计哪一条路径的概率最高，以及求得最后一个时间点的状态。

最优路径回溯：

参考文献

(11 封私信) 拉格朗日乘子(Lagrange Multiplier)法总结 - 知乎

隐马尔可夫模型之Baum-Welch算法详解-CSDN博客