机器学习系列：隐马尔可夫模型 (1)

关于隐马尔可夫模型由于内容比较多我们这里分三部分内容讲解这里是第1部分。一、 隐马尔可夫模型概述隐马尔可夫模型Hidden Markov ModelHMM是一种关于时间序列的概率统计模型它用来描述一个含有隐含未知参数的马尔可夫过程。 根据加州大学伯克利分校等海外权威机构的教学资料它最早由 Leonard E. Baum 等人在 20 世纪 60 年代提出([1])现在已成为语音识别、自然语言处理等领域的经典算法 。‌‌‌HMM‌可以用来处理‌按时间顺序排列的数据‌其核心逻辑是通过‌看得见的信号‌去推测‌看不见的状态‌ 即能做到“由表及里”的效果。一个HMM系统需要如下核心要素(1) 两大状态集合‌隐藏状态集合不可直接观测比如晴天/雨天但你看不到、观测状态集合可直接观测比如你朋友今天散步/购物/清理你能看到(2) ‌三个概率矩阵‌初始状态概率分布开始时处于各状态的概率、状态转移概率矩阵从一个状态变到另一个状态的概率、观测概率矩阵或发射概率矩阵在某个状态下产生某个观测的概率可简化用三元组λ(π,A,B)表示。一个HMM系统需要如下三大核心假设1齐次马尔可夫性任意时刻隐藏状态仅依赖前一时刻的隐藏状态2观测独立性任意时刻观测状态仅依赖当前时刻隐藏状态3时齐性概率分布不随时间变化。HMM‌通常用一组或几组长度相同的观测样本序列来训练模型其核心是通过‌所谓的Baum-Welch算法即EM算法的特例‌迭代优化模型参数让观测序列的生成概率最大化。训练好一个HMM模型后可以用所谓的Viterbi算法动态规划方法在某个观测序列上解码最优隐藏状态序列也可以在测试集上还原出对应的隐藏状态序列以计算出识别准确率、对数似然等指标从而来评估模型性能。HMM是‌在机器学习中是一种生成式模型。它通过学习观测序列和隐藏状态序列的联合概率分布P(X,Y)来建模数据生成过程而非直接学习条件概率P(Y|X)的判别模型这是生成模型的核心特征。HMM 最经典的应用领域是语音识别与处理用于将声音信号转换为文字 。早期采用 GMM-HMM 框架后来发展为 DNN-HMM 模型使用深度神经网络提升准确率 。如 Apple 的 Siri、Google 的语音搜索等背后都有 HMM 技术的身影 。‌‌在自然语言处理‌也是典型的应用场景它用于处理文本序列数据理解语言结构 如中文分词与词性标注中可将汉字作为观测分词标签作为隐藏状态。在生物信息学与金融‌中也扩展应用到基因分析和时间序列预测 。如用于 DNA 序列比对、基因预测和演化历程推论 。还有如股票价格预测、故障诊断等涉及时序变化的场景 。二、 模型的定义及相关问题1. 模型的定义HMM是关于时间序列的概率统计模型其中包含具有马尔可夫性的隐藏的状态序列(state sequence)以及由各个状态按一定概率生成可观测的观测序列(observation sequence这两个时间序列两个序列的每一个位置可以看作是一个时刻。HMM主要由初始状态概率分布、状态转移概率分布、观测概率分布确定。这里用Q表示是所有可能的状态的集合V表示是所有可能的观测的集合为便于用矩阵表示各个状态之间转移的概率这里我们用不同的数字表示不同的状态或观测结果即,也就是说Q中有N个不同的状态V中有M个不同的观测。记I是长度为T的状态序列O是对应的观测序列即,这里,。用A表示状态转移概率矩阵其中,即在时刻t处于状态i的条件下在时刻t1转移到状态​j的概率。用B表示观测概率矩阵(发射概率矩阵)其中, 即在时刻t处于状态j的条件下生成观测k的概率。用为初始状态概率向量其中,, 表示时刻t1处于状态i的概率。于是一个HMM的待估参数可以用三元组表示。注意MATLAB 统计工具箱的 HMM 函数如hmmdecode、hmmviterbi‌默认初始分布为确定性状态 1‌ 即。2. 两个基本假设HMM模型需要两个基本假设 1齐次马尔可夫性假设假设隐藏状态变量在任意时刻t的状态只依赖于其前一时刻的状态与其他时刻的状态及观测无关也与时刻t无关即:,2观测独立性假设即假设任意时刻的观测只依赖于该时刻的隐藏状态与其他的观测和状态无关即:,3. 三个基本问题1概率计算问题 已知模型参数和一组观测序列计算观测序列出现的慨率即。2学习问题 已知观测序列去估计模型参数使得在该参数下观测序列概率最大即用极大似然估计方法来估计参数。3解码问题预测问题: 已知模型参数和观测序列求对给定观测序列条件下使最大的状态序列, 即给定观测序列求最有可能对应的状态序列。三个基本问题中学习问题就是用样本(观测序列)去训练一个HMM模型是核心问题。而学习问题的计算过程中需要用到概率计算问题的结果。训练好一个HMM模型后就可以通过解码问题获得对应的状态序列。三、概率计算问题概率计算问题即给定模型和观测序列计算在模型参数下观测序列出现的概率。1. 直接计算法直接计算法就是利用全概率公式来计算它通过列举所有可能的长度为T的状态序列求各个状态序列和观测序列的联合概率然后对所有可能的状态序列求和得到, 即其中状态序列的概率为, (齐次马尔可夫性)详细推导过程如下...........对状态序列和模型参数给定的条件下观测序列的概率为(观测独立性假设)于是的计算如下然而这种计算方式的计算量非常大其复杂度为因此是不可行的。在实际应用中一般采用更有效的算法即前向-后向算法。2. 前向算法给定模型参数定义到达t时刻观测序列为且此时状态为的概率为前向概率即这里的可以通过向前递推获得概率流程如下1计算初值:,2递推 对条件概率公式观测独立性(全概率公式)条件概率公式,现在可以利用前向概率计算由于前向算法可以直接引用上一个时刻的计算结果其时间复杂度是比直接计算法小很多。3. 后向算法给定模型参数定义到达t时刻,状态为的条件下后续的观测序列为的概率称为向后概率即同样地这里的可以通过向后递推获得概率流程如下1计算初值:,2递推 对(全概率公式)(条件概率公式)(观测独立性假设)(条件概率公式)现在也可以利用后向概率计算也可以把前向概率和后向概率结合起来计算以下给出前向算法和后向算法的MATLAB实现function [alpha,beta]forwardbackward(Ok,PI,A,B) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %HMM模型之前向算法和后向算法的实现 %计算在某一个观测序列Qk下的前向概率alpha和后向概率beta %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %PI: 初始状态概率 %A 状态转移概率矩阵 %B 观测概率矩阵 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [s,T]size(Ok); numStatessize(PI,1); %% 前向概率alpha alphazeros(T,numStates); %初始时刻:t1 alpha(1,:)PI(:,1).*B(:,Ok(1,1)); %前推 for t2:T alpha(t,:)(alpha(t-1,:)*A).*B(:,Ok(1,t)); end %% 后向概率beta betazeros(T,numStates); %初始时刻:tT beta(T,:)1; %反推 for tT-1:(-1):1 beta(t,:)(A.*B(:,Ok(1,t1)))*beta(t1,:); end end‌4. 两个概率值的计算已知模型参数和观测序列在时刻t处于状态的概率(即状态占用概率)记为计算因为所以已知模型参数和观测序列在时刻t处于状态且在时刻t1处于状态的概率(状态转移概率)记为,利用前向概率和后向概率计算因为(条件概率公式)观测独立性假设(条件概率公式)(条件概率公式)。所以,5. 两个概率值的改进计算两个概率值和的计算由于涉及前向概率和后向概率的计算而前向概率和后向概率的计算都是一系列递推过程计算过程会带来舍入误差主要是下溢。以下给出一种改进的计算方法可以有效地避免计算过程中的溢出问题。改进的计算方法是用缩放因子法计算前向概率即每时刻 t计算​后立即除以该时刻的总和归一化并记录缩放因子。在计算时也用缩放因子来处理。 具体算法如下-------------------------------------------前向概率的改进计算-----------------------------------------------------------1 初始(t1) 计算,计算归一化因子,记。2对于 t2,3,..., T, 计算,,3的恢复,,-----------------------------------------------------------------------------------------------------------------------------------------------------------------------后向概率的改进计算----------------------------------------------------------------1 初始(tT),2 对于 tT-1,T-2,..., 2, 1, 计算3的恢复,------------------------------------------------------------------------------------------------------------------------------因为观测序列出现的概率 所以有了以上的准备这里就可以改进两个概率值和的计算了。,,以下给出MATLAB下的实现函数function [Gamma,Xi,logPseq,forwardS, backwardS, scale] myHMMGammaXi(O,PI,A,B) % myHMMGammaXi: 计算后验概率 P(i_t i |O,lambda) 和 P(i_tii_{t1}|O,lambda) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %输入 % O: 1*T, 长度是T的观测序列矩阵 % PI: N*1参数PI的初步状态概率向量 % A: N*N, 状态转移概率矩阵 % B: N*M观测概率矩阵(发射概率矩阵) %输出 % Gamma: N*T, 一个观测序列O下的状态后验概率(状态占用概率)即P(i_ti |O, lambda) % Xi: N*N*(T-1), 一个观测序列O下的状态转移后验概率即P(i_tii_{t1} |O, lambda) % forwardS: alpha的归一化 % backwardS: beta的归一化 % logPseq: 即P(O|lambda)的对数值 % scale 归一化因子 %2026.8.14 MiaoZhh %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [N,M] size(B); Tlength(O); %为避免数据乘积过程下溢引入缩放因子scale scale zeros(1,T); forwardSzeros(N,T); %% 前向概率计算(伸缩因子法) for i1:N forwardS(i,1)B(i,O(1))*PI(i,:); %forwardS(i,1)B(i,O(1))*A(1,i); (hmmtrain采用) end scale(1) sum(forwardS(:,1)); forwardS(:,1) forwardS(:,1)./scale(1); for t2:T for i 1:N forwardS(i,t) B(i,O(t)) .* (sum(forwardS(:,t-1) .*A(:,i))); end scale(t) sum(forwardS(:,t)); forwardS(:,t) forwardS(:,t)./scale(t); end %% 后向概率计算(伸缩因子法) backwardS ones(N,T); for t(T-1):(-1):1 for i 1:N backwardS(i,t) (1/scale(t1)) * sum(A(i,:).* backwardS(:,t1).*B(:,O(t1))); end end %% Gammar_t(i) 状态占用后验概率 Gamma forwardS.*backwardS; %% Xi 状态转移后验概率 Xizeros(N,N,T-1); for t1:T-1 for i1:N for j1:N Xi(i,j,t)forwardS(i,t)*A(i,j)*B(j,O(t1))*backwardS(j,t1)/scale(t1); end end end %% 观测概率P(O|lambda)的对数值 logPseq sum(log(scale)); end未完请继续参阅以下内容机器学习系列隐马尔可夫模型(2)参考文献[1] Baum L E , Petrie T .Statistical Inference for Probabilistic Functions of Finite State Markov Chains[J].Annals of Mathematical Statistics, 1966, 37(6):1554-1563.DOI:10.1214/aoms/1177699147.[2] 《统计学习方法第2版》 李航 著