隐马尔可夫方法几个基本要素隐状态的数量K每个状态的概率向量Π隐状态转移矩阵A隐状态到观测的转换矩阵即发射矩阵B。模型可被定义为λ [A,B, Π]。隐马尔可夫就是要在基于模型λ成立的前提下观测出现的概率最大就是基于极大似然的思想目标函数为L其实就是从某个初始状态开始Πq1遍历所有可能生成所有观测的路径所有路径的概率加和。展示的这条路径就是从q1的初始状态开始转换产生观测O1然后从q1转换到q2转换产生O2以此类推不断转换隐状态并不断生成观测数据直到最后一个观测时间点OT。上式也可以写成下面这个表达分解这个公式L(O, I|λ)对于一个序列模型成立时序列出现的概率模型成立且序列为时观测出现的概率如下复杂度如果隐藏状态有N个序列长度为T个复杂度为O(TN^T)就是执行时间和TN^T成正比。基于已知的ΠAB计算似然更高效的算法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的条件下从t1到T的部分观测序列为o_t1, o_t2, ... o_T的概率为后向概率:1.规定当tT时。其实这个只是一个方便的规定后续可以看出来。2.当t T-1, T-2, ... , ..., 1这个公式怎么理解首先a_ij*b_j(o_t1)即从t时刻的i状态出发转换到t1时刻的j状态再发射出t1时刻的观测o_t1的概率。再之后*β_t1(j)就是从t1时刻的j状态出发生成o_t2, ... , o_T这个序列。总体来说就是从t时刻的i状态出发生成o_t1, o_t2, ... , 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的条件下从t1到T的部分观测序列为o_t1, o_t2, ... o_T的概率分母自然就是i取所有值的时候的和2.给定模型λ和观测O在时刻t处于i状态且在t1时刻处于j状态的概率可变换公式如下分子可以变形为代入上式得几个期望值1.在观测O下状态i出现的期望2.在观测O下由状态i转移出去的期望3.在观测O下由状态i转移到状态j的期望如何得到ΠAB监督学习法假设我们已经有了多条观测序列和对应的状态序列就可以首先计算不同状态的初始概率分布Π然后算状态间的转移概率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个约束条件的问题转换为无约束的NM个自变量的问题。设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]Tp [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博客(11 封私信) 负定矩阵主对角元素都为负数 - 知乎(11 封私信) 19.海森矩阵、特征值与函数的凹凸性的关系 - 知乎统计学习方法第二版最优化理论与算法 Convexity and uniqueness of optimizers — ECON2125/6012系列视频【研究生补基础】隐马尔可夫模型HMM超详解从天气预测到中文分词手把手实战NLP经典算法_哔哩哔哩_bilibili 隐马尔可夫方法
隐马尔可夫方法几个基本要素隐状态的数量K每个状态的概率向量Π隐状态转移矩阵A隐状态到观测的转换矩阵即发射矩阵B。模型可被定义为λ [A,B, Π]。隐马尔可夫就是要在基于模型λ成立的前提下观测出现的概率最大就是基于极大似然的思想目标函数为L其实就是从某个初始状态开始Πq1遍历所有可能生成所有观测的路径所有路径的概率加和。展示的这条路径就是从q1的初始状态开始转换产生观测O1然后从q1转换到q2转换产生O2以此类推不断转换隐状态并不断生成观测数据直到最后一个观测时间点OT。上式也可以写成下面这个表达分解这个公式L(O, I|λ)对于一个序列模型成立时序列出现的概率模型成立且序列为时观测出现的概率如下复杂度如果隐藏状态有N个序列长度为T个复杂度为O(TN^T)就是执行时间和TN^T成正比。基于已知的ΠAB计算似然更高效的算法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的条件下从t1到T的部分观测序列为o_t1, o_t2, ... o_T的概率为后向概率:1.规定当tT时。其实这个只是一个方便的规定后续可以看出来。2.当t T-1, T-2, ... , ..., 1这个公式怎么理解首先a_ij*b_j(o_t1)即从t时刻的i状态出发转换到t1时刻的j状态再发射出t1时刻的观测o_t1的概率。再之后*β_t1(j)就是从t1时刻的j状态出发生成o_t2, ... , o_T这个序列。总体来说就是从t时刻的i状态出发生成o_t1, o_t2, ... , 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的条件下从t1到T的部分观测序列为o_t1, o_t2, ... o_T的概率分母自然就是i取所有值的时候的和2.给定模型λ和观测O在时刻t处于i状态且在t1时刻处于j状态的概率可变换公式如下分子可以变形为代入上式得几个期望值1.在观测O下状态i出现的期望2.在观测O下由状态i转移出去的期望3.在观测O下由状态i转移到状态j的期望如何得到ΠAB监督学习法假设我们已经有了多条观测序列和对应的状态序列就可以首先计算不同状态的初始概率分布Π然后算状态间的转移概率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个约束条件的问题转换为无约束的NM个自变量的问题。设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]Tp [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博客(11 封私信) 负定矩阵主对角元素都为负数 - 知乎(11 封私信) 19.海森矩阵、特征值与函数的凹凸性的关系 - 知乎统计学习方法第二版最优化理论与算法 Convexity and uniqueness of optimizers — ECON2125/6012系列视频【研究生补基础】隐马尔可夫模型HMM超详解从天气预测到中文分词手把手实战NLP经典算法_哔哩哔哩_bilibili