HMM模型范文（精选7篇）
HMM模型 第1篇
关键词：隐马尔可夫模型(HMM),数学模型,语音识别
1 引言
语音识别是自然语言理解的基础性课题,旨在使计算机能够在一定程度上识别理解人类的语音。从20世纪50年代初,一些学者试图设计了第一个自动语音识别系统及孤立词的数字识别系统研究开始,到60年代中期才逐步取得实质性的进展,Reddy利用音素的动态跟踪技术在连续语音识别中的初步研究,到70年代日本学者提出的动态时间弯折算法DTW(Dynamic Time Warping)对小词表的研究获得了成功;以及在语音编码中使用的线性预测编码(LPC)技术成功的应用到语音识别系统中,再到了80年代从基于模板匹配的方法到统计模型的方法的转换,尤其是隐马尔可夫模型HMM(Hidden Markov Model)技术被应用到语音识别中,由于该模型具有把从声学语言学到句法等统计知识全部集成在一个统一框架中的优点,因此它被广泛地应用到语音识别研究中,到目前为止,HMM技术仍然是语音识别研究中的主流技术。
2 隐马尔可夫模型
HMM模型是一个双重的随机过程,即一个隐藏的(不可观察的)具有有限状态的马尔可夫链和一个与马尔可夫链状态相关联的随机函数集(可观察的)。这样,语音等时变信号的功率谱可以唯一地由模型对应的状态的随机函数决定,而信号频谱时间的变化则由隐藏的马尔可夫链的转移概率规律决定,因此非常适合建立语音信号的统计模型。
2.1 马尔可夫链
对于某一个随机试验,设Ω是由所有样本点{w}构成的样本空间,ξ是Ω上随机事件构成的事件集合,称为σ代数,P是定义在ξ上的概率。则称定义在概率空间(Ω,ξ,P)上的随机变量族X={x,(w),t∈T}为随机过程。其中,T为一参数集。可将随机过程看为二个变量的函数xt(w)=x(w,t),其中,t∈T;w∈Ω。对于固定的w,xt(w)是个随机变量,记为xt。若将参数t看作时间,那么xt就表示随机系统在时刻t所处的状态。若T是一个含有可列元素的无限集,则称该随机过程为离散随机过程或随机序列。一个随机过程所有可能取值的集合称为该过程的状态空间,记为S。若S是可列集或有限集,则称此过程为链。
设随机过程X={xn,n=0,1}是定义在(Ω,ξ,P)上的离散随机过程,其状态空间S为有限集或可列集。并且X具有无后效性即马尔可夫性:
对任意非负整数n,及任意状态i0,i1,in+1∈S;
只要P(x0=i0,x1=i1,,xn=in)>0
总有P(xn+1=in+1|x0=i0,,xn=in)=P(xn+1=in+1|xn=in)
则称此过程为马尔可夫链。
2.2 HMM状态随机过程
一个隐马尔夫模型是由一系列转移弧连接起来的状态的集合。每个转移弧包含两个概率:转移概率,即为经过这条转移弧的概率。输出概率密度,是在这条弧上发射固定的符号的概率。一个HMM可以由它的三个特征参数矢量或矩阵π,A,B完全确定。定义为:
λ={π,A,B}
其中,π是初始概率分布;A={αi,j}是状态转移概率分布矩阵,其中αi,j是从状态i到状态j的转移概率;B={bi,j(k)}是输出概率分布矩阵,其中bi,j(k)是从状态i到状态j的转移弧上发射的输出概率。
HMM的过程是:
1)根据初始状态分布概率π,选择一个初始状态。置观察时间为t=1;
2)根据B,得出在qt状态下(t时刻),观察符号的概率分布;
3)根据A,由t时的qt状态转移到t=t+1时的状态,并置t=t+1;
4)如果t﹤T(观察时间序列为t=1,2,,T),则回到第2)步,否则结束。
3 隐马尔可夫模型在语音识别研究中的应用
根据前面对隐马尔可夫模型原理的介绍,已知它是一个双重的随机过程,在语音识别中,这两个随机过程共同描述语音信号的统计特性。一个是用具有有限状态数的马尔可夫链来模拟语音信号变化的隐含的随机过程,另一个是与马尔可夫链的每一状态相关联的观察矢量的随机过程。这样,语音等时变信号某一段的特征就由对应状态观察符号的随机过程描述,而信号随时间的变化由隐马尔可夫链的转移概率描述。基于隐马尔可夫模型的语音识别算法通过对大量语音数据进行数据统计,建立识别统计模型,然后从待识别语音中提取特征值,与这些模型进行相似性量度比较,将相似度最高的模式所属的类别作为识别结果输出。一般来说,用隐马尔可夫模型构成语音识别系统,要解决3个基本问题。
3.1 观察输出概率P(О|λ)的计算
对于给定的观察序列О(o1,o2,o3,ot)和模型λ={ξ,A,B},模型λ产生О的概率可采用前向概率、后向概率,可以使其计算量降低到N2T次运算。
定义l:前向概率用T时刻以前出现的观察序列来推算到当前时刻t时出现某个观察值的概率,即用出现o1,o2,o3,ot-1的概率来推算出现o1,o2,o3,ot-1,ot的概率,用αt(i)表示。
前向概率计算算法:
1)初始化:α1(i)=πibi(o1),1≤i≤N
2)递归:
3)结束:
定义2:后向概率用ot+2,ot+3,,oN去推算ot+1,ot+2,,oN的概率,用βt(i)表示。
后向概率算法如下:
1)初始化:βT(i)=1,1≤i≤N
2)递归
3)结束:
在定义了前向概率、后向概率和它们的算法后,观察输出概率P(О|λ)便很容易得到:
3.2 最佳状态序列的寻找
对于HMM系统,外界观察到的某个序列О在系统内部对应的状态序列Q不是唯一的,但是不同的Q产生О的可能性不一样。最佳状态序列寻找的任务就是根据系统输出О寻找最有可能的状态序列Q,使得该状态序列产生О的可能性达到最大。其常用的算法是Viterbi算法。Viterbi算法是动态规划算法的一种变形,它可用如下递推算法求得:
1)初始化:δ1(i)=πibi(o1),1≤i≤N
φ1(i)=0,1≤i≤N
2)递归:
3)结束:
4)状态序列求取:qT*=φi+1(q*i+1),t=T-1,T-2,,1由此便可求得P(О|λ)的最佳状态序列:q1*,q2*,,qt*。
3.3 模型参数的估计
模型参数的估计是HMM模型的训练问题,即如何根据系统所给的若干输出来确定模型λ={ξ,A,B},使P(О|λ)最大。研究者一般采用Baum-Welch重估算法来进行HMM模型的训练。
Baum-Welch算法可描述如下:
令ξt(i,j)=P(qt=Si,qt+1=Sj/О,λ),
γt(i)=P(qt=Si/О,λ)
则
由此得出了Baum-Welch算法中著名的重估公式:
即是重估后的模型参数,且
复杂的语音识别问题就是这样通过隐含马尔可夫模型简单地被表述、解决,让我们不得不感叹数学模型之妙,隐马尔可夫模型识别系统之所以优于其它系统,在于隐马尔可夫模型识别系统中保留了更多训练数据的统计信息,并解决了训练和分类上的困难,可以说隐马尔可夫模型在语音识别上是个极大的成功。
3.4 语音识别中常用的几种HMM拓扑结构
语音识别中常用的几种HMM的拓扑结构如图1所示。其中每个圆表示一个状态,从圆到圆的有向弧表示从一个状态到另一个状态的过渡,称之为转移弧。
4 结语
隐马尔可夫模型在语音识别中的应用,使得语音识别有了长足的发展。目前基于HMM模型开发了许多特定人大词汇量连续的语音识别系统,但这些系统在有噪声的环境下工作时,性能明显下降,所以有必要进一步深入研究,通过改善HMM模型增强语音识别系统Robust性。
参考文献
[1]谢锦辉.隐Markov模型(HMM)及其在语音处理中的应用[M].武汉:华中理工大学出版社,1995.
[2]胡航.语音信号处理[M].哈尔滨:哈尔滨工业大学出版社,2000.
[3]段红梅,汪军,马良河,等.隐马尔可夫模型在语音识别中的应用[J].工科数学,2002(6):16-20.
[4]蔡莲红,黄德智,蔡锐.现代语音技术基础与应用[M].北京:清华大学出版社,2003.
HMM模型 第2篇
上世纪70年代, 研究人员开始了对无线移动自组织 (Ad hoc) 网络技术的开发, 当时是因美国出于军事需要而开始研究无线网, 让其能适应战场的需要进行数据通信。Ad hoc网络与以往的无线网格有着明显的不同, 它的网络结构是随意的、非固定的。与此同时, 它也不需专门固定的基站或路由器当做管理中心。到了上世纪末, 研究无线移动自组织网络的工作就已经在世界各国开始陆续展开, 并且从无线通信领域里的一个分支, 慢慢扩大到一个单独的领域。当前关于Ad hoc网络的学术会议越来越多。由于移动自组网络的任意一节点都能随机移动, 因此组网非常灵活, 那么相应的网络开发的难度就大大增加了[1]。当前研究[2,3]中遇到了Ad hoc网络发展瓶颈:移动节点在子网中进行切换过程中, 基本上无法避免通信中断, 而且还会带来很大的延时。上述问题急需对其移动的方位完成评估及确定所需链接的路由器, 这样即可让移动节点时刻做好发生切换的预备工作, 进而缩短或避免中断, 并做好延时, 争取时间[4]。处理这一问题的广泛处理方式是采用人工神经网络, 然而人工网络模型固然可构造出相对更精确的分类界面, 但仍需非常多的训练数据才可做参数估计, 并且运算相对复杂, 收敛较慢[5]。本文针对上述问题, 进行了一种对移动节点的路径新预测模型设计, 采用了隐马尔科夫模型 (HMM) 处理, 这一研究对于Ad hoc网络实际应用的拓展具有一定的价值。
1 HMM实现Ad网络问题处理
1.1 3个基本问题的求解实现
在确定HMM模型情况下, 需要实现以下3个关键问题才可以较好地运用在实际项目中: (1) 如果指定的一组观察序列O=O1, O2, , OT、模型λ= (A, B, π) , 在此条件下, 怎样科学合理地运算出概率P (O|λ) ; (2) 条件与 (1) 相同, 怎样选取一个对应的状态序列S=q1, q2, , qT, S可以非常明晰地阐述O; (3) 怎样调整模型参数λ= (A, B, π) , 能够满足P (O|λ) 最大。通常情况下, 这3个问题都是在一个实际项目的应用中被总结出的。
解决问题 (1) 的方法:若直接做运算, 即:
若按照该方法直接运算, 就会用到全部可能的状态序列, 复杂度以及指数巨大, 运算难度相对高, 所以就会采用前向的方法进行运算。前向算法做运算, 首先要定义前向变量αt (i) :
在已知的模型λ前提下, 从最初时刻到时刻t局部的观察序列O1O2Ot, 和时刻t状态Si形成的概率为αt (i) 。解决问题 (2) 的方法:使用Viterbi Algorithm方法是一个比较好的选择。这里, 将Viterbi变量定义为:
δt (i) 是已知的观察序列, 从最初时刻到t时刻, 同时最大概率状态序列的状态是Si。其中, φt (i) 是概率最大途径中此刻状态的之前状态。求解问题 (2) 的步骤是:
(1) 初始化
(2) 传递公式
(3) 最后数据结果
(4) 返回路径
解决问题 (3) 的方法:实质上即是求解HMM模型参数做优化处理的问题。如今已有的大量算法都能够解决该问题, 本文通过使用Baum Welch算法, 同时将变量定义成:
假设已有的模型参数为λ= (A, B, π) , 那么经过改进后的模型参数 为, 这里有:
按照上述的运算方式, 即可推出:
把新模型参数当做是现存模型参数, 重复前面的步骤, 一直到能获得最优的HMM模型参数, 这样问题就迎刃而解。
1.2 移动节点观察模型的设计
若有一移动节点MN, 它在与自己已建立无线连接的接入路由器AR所覆盖的无线信号区域内移动, 可定期对信号强度等有关移动路径的信息进行测量。假设MN处在离散时间n△t (n=1, 2, ) 时, 能够测得与AR之间的信号强度, 还能够得到按照信号强度为观察值的观察序列O1, O2, , OT。若△t很小, 则可看成该时间段里, MN移动的速度是一个不变的值。可将该定值用vn (n=1, 2) 来表示。为使移动预估目标MN进入子网, 所以会将AR涉及到的范围区域分块成一些子域, 见图1。此外, 还要使得每个子区域所包涵的范围都满足r1=r2==rN。还将该子区域当成MN移动的过程中的每一种状态Qi, i=1, 2, , N。若MN按照其中一路径进行移动, 那么可以得到其观察序列是O=O1, O2, , OT, 如图1所示。因为一些因素会使得观察序列是随机的。其一, 是在观察的最初时间就不具备确定性, MN移动速度的随机性也会影响观察位置的确定;其二, 由于存在噪音、测量方式的错误等原因, 会导致观察值存在误差;其三, 即使MN会按照某种路径移动, 可移动在某种程度上还是随机的。
假设M为此时AR的邻居子网数, 对于离散参数的HMM初始值只有一个, 即统一分布, 所以, 模型的初始值的设置方法可以表述成MN按照等概率的方式从一状态切换成另一种邻近的状态, 以获得λij= (Aij, Bij, π) , 1≤i, j≤M, A、B、π分别代表状态转移概率矩阵、符号输出概率矩阵、初始状态分布。在进入AR时, 对于之前属于AR的哪个邻居子网, MN是可以知道的, 假设是子网Θ, 通过AR, MN可以得到HMM模型集{λΘj|1≤Θ≤M, j=1, 2, , M}。如果MN得到了观察序列, 则按照以下公式进行计算:
此时, j为AR的邻居子网, 也就是MN接下来要进入的子网。训练、观察、判别是以上预测模型的预测过程, 通过Baum Welch算法求解训练过程, 若观察序列就是因已经指定的模型而形成的, 那么这种算法的效果是能够达到的, 这在多个领域 (如语音识别) 已被证实, 所以, 模型训练所采用的是Baum Welch算法。MN移动预测模型的预测判别方法主要是找出一个模型λx, 使得P (O|λx) 最大。
离散HMM训练样本及其可取值空间并不是无限的, 但上面提到在一定范围内, MN移动预测HMM模型中的观察值任意取值, 所以一定要先将观察序列在观察符号空间进行量化, 再对观察值与观察符号输出概率之间的关系进行确定。图2是观察符号空间与量化的过程图。观察符号空间的确定所采取的是径向划分法, 也就是将AR作为中心, 在其径向上的各状态范围内进行等间隔区域的划分, 同时, 将中心信号的强度值作为观察符号空间中的符号, 从而构成观察符号空间。假设yk*为观察值, 且包含在 (oi, oi+1) 中, 当|yk*-oi|>|yk*-oi+1|时, yk=oi+1。
虽然在量化过程中会有一定的误差, 但经过量化的观察值对应的状态和符号输出概率是不变的, 所以, 量化误差对于与MN将连接的AR的预测并无太大影响。
2 设计模型的抗毁性分析
在Ad网络系统中, 抗毁性是一个最为关键的特点, 抗毁性强弱所体现的是对某些节点之间的通信进行中断所需破坏的链接数。主要从两个角度来分析抗毁性, 即黏聚度与连通度。这里仅分析去掉部分节点后的网络连通度。通常情况下, 网络的连通度越好, 其抗毁性就越强, 反之则亦然。
2.1 信道抗毁性
通过计算机的帮助可获得区域划分方式, 采用有湖与无湖两种划分方式进行对应的信道模型方案的结果表述, 如图3、图4所示。
图3、图4可得, 此时最小半径相加所得总和分别为4034.4、4213.5。研究表明, 只需要最小半径相加小于10 000, 则Ad网络的连通性是良好的, 即抗毁性较强。图中结果表明了模型的抗毁性优势。
2.2 网络的连通度
定量原理:假设有一无向图G, 那么G为k的连通图的充分必要条件是:G的定点数不小于k+1。在任一通信区域中, 假设这个区域有M个节点, k是其连通度, 那么区域连通的充要条件是:M不小k+1;926是正方形通信区域附表中所定的节点数, 那么其连通的充要条件是:
只要节点的连通度不超过925, 通信网络就是连通的。根据数学概率理论可将网络节点的连通概率计算出来。随机将节点集合中的2%、5%、10%、15%等数量的节点去掉, 由设计模型可得到当前网络的连通度, 那么网络节点的连通概率也就可以计算出来了。表1所描述的是其抗毁性算法应用的节点数。
由表1可见, 节点的数量与抗毁性的强度是成正比的, 相交面积大小与抗毁性的强度成反比。同时由原理可知, 设计模型的Ad Hoc网络具有较强的抗毁性。
由以上分析可知, 节点最多的是公共区域, 其网络连通性比较强, 设计模型的Ad Hoc网络具有较强的抗毁性, 同样解决了Ad Hoc网络的延时问题。
3 结论
作为一种随机概率模型, HMM表示的是与时间序列有关联的有效模型, 所涉及的知识包括概率与统计学, 目的是对参数不同的短时平稳信号段进行识别, 并实现信号之间的转化, 该模型应用中的一切实际问题均能以HMM模型中的3个问题来表示。在这里, 采取仿真对HMM预测移动进行了可行性研究, 在训练样本以及初始模型参数已知的前提下, 采取新的数据来检验模型, 从而确定模型预测的准确度。由仿真结果可知, 该模型是可行的, 且抗毁性具有一定的优势。
摘要：为了更高效地处理无线移动自组织 (Ad hoc) 网络中的延时问题, 采用了隐马尔科夫模型 (HMM) 进行移动方位的评估。HMM求解实现了Ad网络3个基本问题的求解, 设计了移动节点观察的模型, MATLAB仿真表明参数值完全正确, 符合观察要求。对模型进行抗毁性试验, 网络的连通度较好, 表明了抗毁性较强;节点最多发生在公共区域, 表明网络连通性比较强。这一研究对于Ad hoc网络实际应用的拓展具有一定的价值。
关键词：Ad hoc网络,隐马尔科夫模型,延时,抗毁性,连通性
参考文献
[1]Wang Hao, Liu Nan, Li Zhihang, et al.A unified algorithm for mobility load balancing in 3GPP LTE multi-cell networks[J].Science China (Information Sciences) , 2013, 56 (2) :118-128.
[2]Zhang Zhongshan, Huang Fuwei, Long Keping, et al.On the designing principles and optimization approaches of bio-inspired self-organized network:a survey[J].Science China (Information Sciences) , 2013, 56 (7) :5-32.
[3]Dan Yangqin, Hong Weili, Lin Ma, et al.An ant colony algorithm based congestion elusion routing strategy for mobile ad hoc networks[J].Journal of Harbin Institute of Technology, 2013, 20 (3) :99-103.
[4]WAKAMIYA N, LEIBNITZ K, MURATA M.Biologically inspired self-organizing networks[J].智能系统学报, 2009, 4 (4) :369-375.
HMM模型 第3篇
现有的个性化推荐系统一般多是利用用户或项目(文档、商品、服务)的属性进行基于内容的推荐,或是利用用户间、项目间的相似性进行的协同过滤推荐,主要的做法也多是利用向量空间模型(VSM)、TF/IDF、K-means等算法对对象属性进行聚类分析与建模,以及利用各异的协同推荐算法来实现推荐过程[6,7,8],而没有考虑到用户偏好的动态性以及上下文情境适应性的特征,且相关研究多是从用户与项目的二元关系(user×item)来建立相关的推荐模型,这将不能满足为用户提供高质量的实时个性化推荐的需求。
随着泛在网络和普适计算等应用的普及,在个性化推荐系统设计过程中考虑上下文信息对用户偏好的影响逐渐成为了一个新的研究热点。文献[9]提出将上下文信息融合到推荐系统中,扩展原有的二元关系,得到用户效用μ:(user×context×item→rating)的三元关系模型,由于上下文感知推荐系统融合了上下文环境对用户偏好的约束问题,因此在推荐精度上较以往传统方法具有良好的表现。虽然考虑上下文感知的推荐系统具有较好的应用前景,但仍存在用户偏好学习困难以及难以应对高维稀疏数据处理的问题,以至于不能快速响应用户的个性化需求,本文将针对这一问题展开研究。
1 相关工作
1.1 上下文与上下文感知
上下文有着丰富的表示内涵,泛指一切可以用来表征实体状态的信息。参照Dey的定义[10]:“上下文是环境本身以及环境中各实体所明示或隐含的可用于描述其状态(含历史状态)的任何信息,其中,实体既可以是人、地点等物理实体,也可以是诸如软件、程序、网络连接等虚拟实体”。目前在具体的研究过程中,一般会根据应用情境来对其进行自定义或选取与主题相关的上下文实例,如选取关键词检索关联主题、时间、位置、环境(天气、心情、设备状态)等[11,12]。由于用户行为的不可预测性以及上下文信息获取方式的多样性,往往会造成上下文数据的异构性和稀疏性,缺乏统一的表达方式,因此需要通过上下文感知计算对上下文数据进行建模,得到有利用价值的上下文知识表示。目前常见的有图模型、键值对模型、标记模式模型、面向对象模型、基于本体的模型等[13],相关方法取得了较好的应用效果,但在应对多维上下文数据处理方面变现乏力,为此,有人提出利用张量分解技术作为矩阵分解在多维数据空间的扩展[14]。
1.2 隐马尔科夫模型
隐马尔科夫模型(HMM)是建立在马尔科夫模型上的一种不完全数据统计模型,是一个双重随机过程,其中一个是Markov链,它通过状态转移概率来描述不同状态间的转移情况。另一个是一般随机过程,通过观察值概率来描述状态和观察序列之间的对应关系,通过HMM模型可以识别隐藏的状态及其结构信息[15]。一个HMM模型通常可以通过以下参数进行定义描述[16]:λ=(S,O,A,B,π),S表示模型中有限状态的集合,O表示每个状态可能的观察值数目,A表示状态转移概率矩阵,B表示观察值概率分布,π表示初始状态空间的概率分布。本文借助HMM模型的这种特征,通过对系统历史评分信息的处理(评分可以反映的用户偏好风格以及表征预推荐对象的质量情况),将用户偏好的提取过程抽象为一个HMM模型,来进行第一阶段的用户偏好集学习与推理,并可以跟踪用户偏好的转移情况,进而动态的推荐策略调整。
1.3 张量与张量分解
在处理包含上述上下文信息的个性化推荐过程中,使用的较多的是将三元关系转换成传统的二元关系来进行求解处理,降低数据的维度以便能够应用较为成熟的矩阵分解来进行处理,但在这种转换过程中会丢失部分相互关联的信息进而影响推荐的精度[17],而张量分解通过对多维张量数据进行降维处理将会最大程度上保存原本内在的关联关系,张量模型的两种表示形式如图1所示。为此,本文将在第一阶段用户偏好集学习与推理的基础上,通过引入反应用户实时偏好的上下文信息(主要通过隐式反馈评分的形式来对上下文信息进行量化处理),来设计一种基于改进的HOSVD模型的个性化推荐算法,从而进一步提升推荐质量,改善用户体验。
2 两阶段的用户偏好集推理与个性化推荐算法设计
为实现快速发现用户偏好项目集进而产生高质量的个性化推荐结果的目的,本节提出了一种基于两阶段的用户偏好项目集学习策略与考虑上下文的个性化推荐算法(HHRA),具体阐述过程如下:
2.1 基于历史评分与HMM的用户偏好集推理
一般来说,用户对项目的评价能够比较直观的反映用户的偏好,因此,我们认为可以利用一组带有评分权值的项目概率分布来描述推荐系统分发给用户的项目集的分布状态,进而可以按照项目的评分标准将其划归到不同的组中,其中组的选取遵循马尔科夫链来构造。由此,可以利用隐马尔科夫模型(HMM)来完成用户偏好的推理与个性化推荐,同时可以描述用户偏好的动态转移过程,并可对推荐系统的项目集质量进行监控,其具体定义与描述如下。
定义1λ=(S,O,A,B,π),S本文指按照评分标准划分得到的项目集样本的分组数,O本文指每个组中可能的样本数目,A本文指选定一个分组的情况下选中另一个组的概率,B本文指分组中样本的分布概率,π本文指初始选中某组的概率。
定义2假定用户评分的等级为很满意5分,满意3分,未评分默认1分,不满意-2分等4类,ri(i=1,2,3,4)分别表示相应评分出现的次数,为降低出现评分分布偏差过大的情况(如恶意评价或者刷分等),引入权重因子wi来进行调节,且∑wi=1,(i=1,2,3,4),则n个用户对样本Oj的评分均值可表示为Kj,同时为从不同维度考察样本的特性,引入Pj,Qj,三者的具体定义与说明如下。
式中,r1+r2+r3+r4=n,w1+w2+w3+w4=1,Kj体现样本满足用户偏好的程度,值越大反应样本的质量越高,Pj用来反应样本获得高评价的概率,是系统优先考虑推荐的对象。Qj用来表示样本的有效评价率,体现对样本进行评价的接受程度。
定义3确定HMM模型的Si状态集合,设θ1,θ2,θ3分别代表定义2中的Kj,Pj和Qj,规定θ1>1.8、1.8≥θ1≥1、θ1<1分别代表评分均值的高、中、低三个状态,θ2>0.5、0.5≥θ2≥0.2、θ2<0.2分别代表高评分概率的高、中、低三个状态,θ3>0.8、0.8≥θ3≥0.5、θ3<0.5分别代表有效评价率的高、中、低三个状态。据此将样本分为六种类别,具体特征描述见表1所示,同时随着用户评分的累积,上述六种状态会发生转移,其状态转移过程如图2所示。
注:h,m,l分别表示相应等级为高,中,低。
定义4设置每个用户的状态转移矩阵A及每组的样本的概率分布矩阵B,A为1×6的矩阵,状态Si被选中的概率PISi存入A1i中,则对于新用户,。B为1×m的矩阵,在一个状态组中样本Oi被选中的概率PIOi存入B1i中,则
为快速获得高质量的推荐样本集,我们对样本的概率随机选取规则进行优化(),假设在样本空间中产生的随机数i的值域范围为区间[Zs,Zt],那么可以根据样本Oi被选中的概率重新定义一个长度为的值域范围,当随机数i分布3的新的值域范围时将被优先选中,因此PIOi较大的样本将会较快速的涌现并被选中。
2.2 融入实时隐式反馈评分的上下文推荐算法设计
在上一阶段推荐的基础上,我们考虑融入用户实时偏好的处理策略,并结合上下文感知设计一种基于张量分解算法的个性化推荐算法,由改进的HOSVD分解算法处理高维稀疏的数据集,并优化得到紧凑估计值,进而为用户完成个性化的推荐,进一步提高推荐的精度,具体实现过程如下。
2.2.1 数据集预处理
用户的网络行为能够反映用户的偏好,但相比于传统的人机交互显式的获取用户偏好的做法,用户的实时隐式反馈是比较高效的分析用户偏好的一种途径。为便于分析和处理,我们对用户的典型操作行为进行定义并进行隐式数据搜集。相关的上下文与量化分值定义如下。
Action(none[0],click[1],collect[3],cart[4],purchase[5]),Action表示用户的在线操作行为上下文,并对每种具体行为的量化分值进行设定,同理,Vtime(8:00~11:30[1.5],11:30~14:00[2],14:00~17:30[1.5],17:30~22:00[3.5],22:00~8:00[1]),Vtime表示用户访问时段的上下文特征,Hiscore(θ1>1.8[5],1.8≥θ1≥1[3],θ1<1[1]),Hiscore表示项目的历史评分上下文特征。其形式化的数据集处理规则如表2所示。
2.2.2 建立张量分解模型
数据预处理后,我们以获得的用户、项目、上下文的稀疏观测值建立相应的张量模型,设rui c1,…,ck是用户u对于项目i在上下文c1,c2,…,ck环境下的评价,若ruic1,…,ck≠Φ,则可用R={(u,i,c1,c2,…,ck)|ruic1,…,ck≠Φ}来存储带有上下文偏好的数据集,相应的带有上下文变量的推荐结果的形式化评分描述为:
则具有观察评分的稀疏张量Y∈yn×m×k,其中n表示用户的数量,m表示项目的数量,k表示第i个上下文变量ci的量化值。
本文采用HOSVD分解来对张量Y进行张量分解建模,对于存在多个上下文变量参数CK1,CK2,…,CKe的情况,N维的张量模型的HOSVDN分解把张量Y近似为核张量G和e+2个因子矩阵的mode-n乘积形式[18]。
式(2)中,,其元素定义为
所建模型的计算复杂度为O(nmkk|kl=k),特别的是,此处核张量G如果是单位张量,则HOSVD将退化成为相应维数的CP张量分解模型。
2.2.3 模型优化与求解
对于2.2.2小节所建模型,会存在计算复杂度呈指数上升以及数据过度拟合的问题,为此,本文通过引入l1和l2矩阵范数来对模型进行优化,具体做法如下。
为使得估计值和观察值Y尽可能的近似,引入损失函数
式(4)中,‖*‖l是l1矩阵范数,被用以控制核张量G的规模;B是属于{0;1}n×m×k的一个二进制张量,if yijk≠,then Bijk=1,else Bijk=0;l:yR→R是一个逐点损失函数,用以惩罚估计值与观察值之间的差距;由上式(3)定义,yijk是观察值。本文选取给出条件中位数的损失函数形式:,同时为了避免数据过度拟合和控制模型的计算复杂度,我们通过增加弗罗贝尼乌斯范数(Frobenius norm)来对因子矩阵U/V/C以及核张量G进行正则化,据此,本文建立目标优化函数如下。
式(5)中,‖·‖2Fro表示矩阵的弗罗贝尼乌斯范数,用以避免过度拟合的状况。λ与λG是基准正则化参数,其余参数上文中已有定义说明,在此不再赘述。
针对上述目标函数的求解,提出一种线上算法,在给定观察值后,利用随机梯度下降法来对因子U/V/C/G进行迭代与更新计算[18],具体思路如下。
对于一个训练集Y,为求解(5)式的局部最优值可以通过固定两个隐藏特征向量,然后每一步交替使用一个隐藏特征向量进行梯度上升的求解方法来进行计算,损失函数U/V/C/G的梯度计算由式(6)定义的规则来完成。
式(6)中,定义了两种张量运算,一是张量-矩阵乘法运算(如×UU),另一种是张量外积运算(如),同时矩阵U的第i行标记为Ui*,Vj*、Ck*同理。在得到损失函数U/V/C/G的梯度后,再由式(7)定义的更新规则进行迭代。
式中t←t+1,迭代步长η由进行更新,通过迭代更新因子最终得到目标函数的最优解,并带入式(8)。
得到估计评分张量,填补观察张量的稀疏缺省值,得到最优TOP-N推荐集。
3 实验设计与结果分析
本节选取3种不同的测试数据集作为实验分析样本,对比分析本文所提算法与Slop One算法、SVD算法、CP算法等[7]在推荐质量上的表现,验证本文所提算法的有效性和推荐质量表现。
3.1 测试数据集选取
本实验的数据源主要下载自国外公开的用于测试推荐算法性能的真实数据集,包括:Movie Lens、Last.fm和Book Crossing。同时,为适应本实验研究的环境,我们通过引入上下文变量并对原始数据集进行了预筛选,具体的数据集预处理规则见表2所示,具体的样本规模及特征如表3所示。
3.2 算法评价指标
从分类准确度方面选取准确率—召回率作为评估指标[19],具体的定义如下:准确率—召回率(Precision-Recall):准确率反映的是系统推荐的项目集中用户实际上偏好的项目数所占的比例,召回率描述的是有多少比例的用户偏好项目包含在最终的推荐列表中。
对其进行了一些调整,具体定义如下:假设P(u)为待预测的测试用户的偏好项目,T(u)为系统为用户提供的TOP-N推荐列表,R(u)为系统交互中用户的实际偏好的项目,则Precision=T(u)∩P(u)/N,Recall=T(u)∩R(u)/P(u)∩R(u)。
3.3 实验结果与分析
本小节实验选取上节的3种不同数据集为实验样本,设定上下文个数为3,采用精确率—召回率(precision-recall)作为推荐结果的评估指标,将本文的HHRA算法与Slop One算法、SVD算法、CP算法等进行实验对比。考虑到性能比对的一致性,选取TOP-N=[3,4,5,6,7,8,9,10],并将每个训练数据集划分为50%和100%两个子集,分别对上述的8种情形进行10次的反复实验,然后对其最优值进行平均化处理,作为最终的评估结果进行统计,目的是尽量降低数据分布与参数调整对算法性能的影响,实验结果如图3所示,其中Slop One算法是属于传统的处理二元关系的经典协同过滤算法,因此在此将不考虑上下文维度对其所起的作用。
图3中(a)(b)、(c)(d)、(e)(f)分别是几种不同的推荐算法在Movie Lens、Last.fm、Book Crossing实验数据集上的推荐质量表现。实验结果表明,本文提出的HHRA算法在P-R推荐评价指标下对三种不同的数据集均表现出了较好的适应性,推荐质量也要好于其他几种经典的算法。另外,从实验结果的对比可以看出:
(1)随着TOP-N的增大,Precision和Recall呈现出一对矛盾的关系,即N较小时,预测结果的Precision较大,但Recall则较低,而随着N的增大,预测结果的Precision开始降低,但Recall更高,这主要是由于评价指标Precision-Recall(P-R)的性质所决定的,但具体到每种不同的算法,其在P-R指标上均呈现出各异的结果,因此P-R仍不失为一种衡量算法推荐质量的评价标准。
(2)几种算法中,Slop One算法受数据稀疏度的影响较大,在数据分布较为稠密的情况下推荐质量较好,在数据分布较为稀疏情况下推荐质量较差,推荐质量不够稳定,这也与文献[20]中所得出的结论相一致。
(3)相比于Slop One算法,由于SVD算法是一种基于全局目标函数优化的思想,因此其在推荐质量上要好于前者,但其在处理收敛性方面,一要对学习速率进行优化,太小则收敛速度较缓,太大则容易造成发散,另一方面初始随机值不能太大。
(4)传统的CP算法作为一种经典的张量分解算法,在一般情况下能够表现出良好的性能,但在处理高维稀疏性数据集上往往不能够很好的控制其复杂度。
(5)HHRA算法通过两阶段的用户偏好学习能够获得更为精确的用户偏好,并且可以对多维张量数据进行实时降维处理并最大限度的保留其原本内在的关联关系,能够较为准确的反应上下文对用户偏好的影响,推荐质量相对于其他几种算法来说要高一些。
4 结论
针对个性化推荐系统中用户偏好的学习策略及相应的推荐算法设计问题进行了研究,提出了一种考虑上下文的两阶段用户偏好集推理策略的个性化推荐算法。通过构建反应用户历史偏好的隐马尔科夫模型(HMM),来进行第一阶段的用户偏好集学习与推理,快速识别预推荐项目集的特征,然后结合用户当前的上下文情境,构建融入用户实时偏好的张量模型,并采用一种改进的HOSVD张量分解方法进行模型求解,生成最优推荐结果集。通过实验对比分析,验证了本文所提出的推荐算法(HHRA)具有较好的适应性和推荐质量表现,但在研究过程中也存在一些问题,如考虑的用户上下文还不够丰富,在算法评价方面还需要尝试新颖性、多样性等一些其他的评估指标,这些问题将是下一步研究的方向。
摘要：针对个性化推荐系统中用户偏好的进化学习与高维稀疏数据处理的问题。受隐马尔科夫模型(HMM)结构特征启发,提出了一种考虑上下文感知的两阶段用户偏好集推理策略的个性化推荐算法(HHRA算法)。通过对系统历史评分信息的处理,将用户偏好的提取过程抽象为一个HMM模型,来进行第一阶段的用户偏好集学习与推理。然后在此基础上,引入用户的实时上下文信息,构建了一种融入用户实时偏好的张量模型,并基于一种改进的高阶奇异值分解算法来处理高维稀疏的数据集,对模型进行优化求解,生成最优推荐集合。实验设计在3个具有不同特征的真实数据集上将HHRA算法与传统经典推荐算法进行对比分析,结果显示HHRA算法具有较好的适应性和推荐质量。
HMM模型 第4篇
1 隐式马尔科夫模型
隐式马尔科夫模型 (Hidden Markov Models, 简称HMM) 可以表示为:
λ= (N, M, π, A, B)
上述参数:N为Markov链的状态数目;M为每个状态θ对应的可能出现的观测值数目;π为初始状态概率矢量;A为状态转移概率矩阵;B为观察值概率矩阵。
应用HMM可以解决以下三个方面的问题:
(1) 评估问题:对于给定的模型λ和观察值序列O, 求这个观察值序列O的概率P (0|λ) 。常用算法是前向算法和后向算法。 (2) 解码问题:对于给定的观察值序列和模型λ, 求出现可能性最大的状态序列。常用算法是Viterbi算法。 (3) 训练问题:对于给定的观察值序列O, 调整参数λ, 使观察值出现概率 (0|λ) 最大。常用算法Baum-Welch算法。
2 CPU性能异常检测系统模型
CPU性能异常检测系统模型如图1所示, 该模型主要由两部分组成:
2.1 数据收集与处理:
利用Windows系统提供的性能监控器收集CPU的性能计数器日志数据, 通过图形帮助显示性能监视数据。
2.2 HMM模型部分:
HM M模型主要由HM M训练与异常检测两部分组成。
(1) 正常状态下的HMM训练。通过导入处理过的、多个或大量正常状态下的性能日志数据, 训练CPU正常状态下的参考模型, 运用到Baum-Welch算法和前向-后向算法确定λ= (N, M, π, A, B) 与正常状态阈值。 (2) 异常检测部分。往参考模型导入检测的CPU性能日志数据, 利用前向-后向算法计算P (0|λ) 值, 并与阈值比较, 判断该日志数据的状态。
3 基于HMM模型的CPU性能异常检测实验
本实验主要运用基于一维HMM的异常检测, 必须选择具有最佳的异常检测效果的计数器。由于Processor time显示的是CPU处于用户模式和特权模式之下, 执行非闲置线程总的百分比;经过数据记录分析证明, Processor Time的计数值等于Privileged Time和User Time的计数值之和。因此, Processor Time的数据能够反映出Processor Time和User Time的数据特征。考虑Processor Time是由CPU的工作状态所决定, 我们进一步用“轻负荷”、“中度负荷”, “高度负荷”来描述CPU的三种工作状态, 并假设CPU的工作状态符合Markov链特性。即状态的跳转代表CPU工作状态的变化。由于CPU的真实工作状态并不可见, 只能通过可观测过程Processor Time来估计, 因此, 我们可以通过隐马尔科夫模型来描述CPU的工作过程。
3.1 CPU性能日志数据收集和处理
首先, 有目的性地进行CPU性能日志数据收集, 即Processor time在正常状态和异常状态下收集两种并分别标记, 以便于HM M可行性的判断。
在正常状态下, CPU一般处于低占用率的过程之中, CPU还有大量的空闲资源没有使用;而在异常状态下, 异常进程无节制占用CPU的资源, 导致占用率一直处于较大的过程, 这是CPU性能降低的征兆。
实验中采集了100份实验样本, 将Processor time的计数值作为观察值, 将日志数据进行离散化处理, 确定观察值O, 可得到离散化处理后的正常状态和异常状态下观察值概率分布如表1所示:
正常状态下观察值主要处于1、2、3之中, 分布比较集中;而在异常状态下, 观察值大部分集中于10、11、12, 也有高于10%的一部分分布比较分散。正常状态, 观察值较小;异常状态, 观察值较大。
将性能计数器的计数值分段作为观察值, 确定状态值Q, 根据状态值, 将Processor time的计数值分为“轻负荷”、“中度负荷”, “高度负荷”三个部分。
3.2 正常状态下基于HMM训练CPU性能检测
将CPU的行为看成HMM过程, 在MATLAB 7.1的操作平台中, 将开始的时候每一种情况的状态认为都处于“低负荷”状态之中, 即初始状态概率默认为π=[1 0 0]。A作为状态转移矩阵, 是状态Q“低负荷”、“中度负荷”和“高度负荷”三种状态之间转移概率的集合;B作为观察值概率矩阵, 是在状态Q的前提下出现特定观察值O的概率集合, 即:
通过随机分布确定出A0矩阵, 根据状态的分布变换, 归纳、分析获得B0矩阵, 从而可以得到参考模型的初始参数λ0= (π0, A0, B0) 。
3.2.1 正常状态与异常状态下的P (0|λ) 的分析
将正常状态验证样本和异常状态样本验证样本的日志数据分别平均分成n组数据, 然后将数据组导入训练好的HMM之中, 统计出各组数据的Pn (0|λ) 。本实验得到正常样本和异常样本的平均对数或然概率log (Pn (0|λ) ) /1, 并经四舍五入后的分布如表2所示:
由实验数据可以得出, CPU异常状态下异常序列的或然概率P (O|λ) 小于正常时的概率, 其分布主要位于更小的区间之中。
3.2.2 基于HMM的CPU性能异常检测
检测率[1] (简称DR) 与误报率[2] (简称FPR) 是异常检测系统的两个重要性能衡量标准。根据异常状况的判断标志, 正常阈值pF是整个异常检测系统的核心。若pF过小, 容易造成误检;若pF过大, 则容易漏检。表3为实验取阈值p F=-30～40后的或然概率、检测率和误报率, 可见当阈值取-34.5时, 检测率DR为97%, 误报率FPR为2%。因此, 对于正常状态下的CPU性能特性HM M, 正常阈值pF=-34.5, 则或然概率大于或等于-34.5的CPU行为特性是属于正常状态, 这时候系统的DR=97%, FPR=2%。
3.2.3 从正常状态样本和异常状态样本中选取多份样本, 根据观察值序列得到的平均或然概率, 我们对正常状态样本的平均或然概率小于正常阈值pmin进行统计, DR=95%。
异常状态样本中多份异常状态的或然概率都大于正常阈值pmin, 误报率恰恰为0.01, 因此异常检测的效果十分明显。
4 结束语
通过Windows系统性能监视器进行记录CPU的行为日志数据, 依靠HMM实现行为特征的分析与辨识, 从而达到主机的初期监控, 具有简单性、直观性、扩展性、普遍性的特点。本试验中也存在:使用的性能监视器比较简陋, 得到的日志数据仅仅是最原始的计数值;训练模型所得的观察值概率矩阵B存在零值, 需要作微小量的添加处理, 导致误差不断叠加;CPU的状态设定只有“正常”和“异常”两种, 设定的状态类型太少等缺陷, 还待有进一步的改进, 这里就不在赘述。
摘要：传统的系统防御方法是基于特征库的被动防御, 它们无法实时发现零日攻击。本文基于隐马尔科夫模型建立描述系统CPU行为的模型。该方法根据系统用户的行为习惯动态调整模型参数, 利用观测序列相对于代表正常行为轮廓的模型的似然概率衡量系统CPU行为的正常度。由于该方法不需要特征库, 可以更有效地应用于未知主机威胁的早期检测。
关键词：HMM模型,CPU,性能,异常检测
参考文献
[1]谢逸, 余顺争.基于Web用户浏览行为的通缉异常检测[N].软件学报, 2007年6月.
基于HMM的主题爬虫问题研究 第5篇
1 HMM主题爬虫框架
将HMM引入到主题爬虫后, 增加了爬虫对网页主题的识别能力, 使用训练好的HMM可以很好地预测爬取路径。但是, 经过对隐马尔科夫数学模型和基于隐马尔科夫主题爬虫的理论进行分析研究, 可以发现在传统的HMM模型中有部分不合理的地方。
HMM爬虫运行主要有3个阶段: (1) 初始阶段, 对相关参数进行设置, 选定初始网页初始训练集, 进行页面预处理等; (2) 学习阶段, 对网页进行文本相关度计算、类型聚类和构建隐马尔科夫模型训练优化; (3) 运行阶段, 用优化后的隐马尔科夫模型对查找到的主体相关的站点进行分析, 主要包括网页内容相关度判断和超链接分析处理, 将分析结果储存起来, 根据网址路径爬取网页到本地服务器。
经过研究发现, 传统的隐马尔科夫模型爬虫存在以下几个缺点: (1) 和一些经典爬虫算法相比, HMM爬虫时间消耗较大, 其建模方法和算法有待改进; (2) 在HMM爬虫抓取的网页中, 主题相关度还有待提高; (3) 对训练集处理过于简单, 影响了爬行过程精确度, 导致主题相关度降低很多。
2改进HMM模型聚类策略
网页数据聚类是将网页数据按照相似性进行分类的过程, 不同类中的网页对象有很大的相异性。具体过程是:首先需要一个给定的分类体系和训练样本集, 如“天眼舆情分析系统”中的中文网页分类体系, 其将所有网页分为15个大类, 即任何网页都可以根据内容归属到某一类样本, 这种利用已标记样本集对未知样本进行类别划分的方法称作“有监督的学习方法”[1]。
K-means算法对网页进行聚类的主要思想是认为两个链接越近的网页其相似度越大, 这一思想看似简单, 但要确定划分类别的数量K, 同类的相似度高, 不同类的相似度低。通常K的值是用户给定的, 而K值大小对爬虫抓取的效率和准确度有很大的影响, 很多用户难以确定K值的大小。目前, 很多学者致力于K值获取方法的改进研究, 比如利用图论、距离代价函数和遗传算法等。
3改进HMM模型页面采集方法
3.1页面与主题相关度判定
在传统的HMM爬虫系统中, 采用空间向量模型 (VSM) 进行网页主题相关度计算, 通过计算用户给出的字出现在页面中的位置也是衡量权值的重要因素。
将网页页面分成4个部分:页面标题、副标题、重点强调文字和普通正文。权重分配如下:
式 (1) 中, Wpage (keywords) 表示关键词keywords出现在网页page中不同位置时对应的权值。将这个关键词出现在页面所有位置的权值累加起来就是在这个页面的权值, 即∑Wpage (keywords) 。
例如, 关键字“Apple”在某个网页P的主标题中出现了1次, 正文中出现了5次, 且强调字体出现3次, 那么关键词“Apple”在网页P中的权重计算方法为:
3.2 HMM爬虫建模方法改进
HMM爬虫基本工作原理是根据页面与查询主题的相关度来抓取网页, 如果相关则抓取, 并且提取储存此网页的链接地址。如果不相关就舍弃, 读取下一个网页。此方法最大弊端就是爬虫经过判断丢弃了不相关网页, 而这些网页中有可能存在着指向与主题相关度很高的超链接, 这个问题使爬虫丢失了部分有价值的页面。这与HMM的假设条件和算法的不合理有关。HMM中存在如下2个假设。
假设1:系统状态从t时刻向t+1时刻转移时, 其转移概率只与t时刻状态有关, 与历史状态无关, 即:
假设2:系统在时刻t输出观察值的概率只取决于当前时刻1所处的状态而与之前的状态无关, 即:
由于上述假设将网页之间的链接关系割裂了, 所以处理网页之间的关系并不合理, 如果和主题相关的网页指向该网页的概率大, 那么就认为这个网页上的链接也有很大的概率指向该网页。为了挖掘出页面当前状态与历史状态之间的联系, 对上文两个假设进行如下修改。
假设1:系统状态从t时刻向t+1时刻转移时, 其转移概率依赖于t和t-1时刻的状态, 即:
假设2:系统在时刻t输出观察值的概率取决于系统当前状和系统前一时刻的状态, 即:
本文在假设条件 (5) 和 (6) 的基础上对HMM的学习算法Forward和Backward算法进行了改进, 此算法是在模型λ下计算产生观察序列O=O0, O1…, Oi的概率, 即P (O|λ) 。
3.2.1 Forward算法。首先定义Forward变量∂, 如式 (7) 所示:
式 (7) 中, ∂t (i, j) 表示在模型λ中, 时刻为t时, 部分观察值序列为P (O0, …, Oi) 的概率。Forward变量∂t (i, j) 可以递归求解, 步骤如下:
3.2.2 Backward算法。类似地定义Backward变量β, 如式 (8) 所示:
式 (8) 中, 1<t<T-1, 0<i, j<N-1, Backward变量β (i, j) 递归求解步骤如下:
由此, 根据Forward-Backward算法, 在给定模型的情况下, 产生观察值序列的概率为:
4结语
在传统HMM爬虫的基础上, 对K-means算法中的K值的设置方法做了改进。首先, 通过训练集聚类策略, 解决了用户通过经验来定义K值带来的诸多问题;其次, 在传统的方法上优化了相关度的判别统计方法;最后, 针对HMM爬虫爬取来的网页与主题相关度不高的问题, 对两个假设条件进行了修改, 从而改进了HMM的建模方式。
摘要：对HMM爬虫中K-means算法的K值选取方法作出相应改进, 然后针对爬取网页的内容与主题相关度不高的问题, 对隐马尔科夫模型的假设条件进行修改, 完成改进后的隐马尔科夫爬虫设计。
关键词：网络爬虫,算法,改进
参考文献
基于HMM的交通事件检测探讨 第6篇
事件检测系统自20世纪60年代发展起来以后, 形成了各种各样的检测方法和技术, 如图1所示。自动事件检测 (Automatic Incident Detection, AID) 技术 (或算法) , 以其低成本, 能够全天候、全程地发挥作用, 且检测率高的优势成为了当今检测系统所采用的最主要的方法。AID技术从根本上来说都是模式识别问题, 或更准确地说是分类问题。本文提出用隐马尔可夫模型 (HMM) 方法来进行交通事件的识别。马尔可夫模型在语音识别、人脸识别和网络入侵等领域已经有了成功的应用, 可以预见HMM也是解决交通事件分类和识别的一个有效的方法。
2 HMM建模
2.1 HMM原理
HMM是一个二重马尔可夫随机过程, 它包括具有状态转移概率的马尔可夫链和输出观察值的随机过程, 其状态是不确定或不可见的, 只有通过观察序列的随机过程才能表现出来。
一个具有N个状态 (S1 , S2 , , SN) 的HMM可以用三元组参数λ={π, A, B}表示, N表示模型中马尔可夫链状态数目, 记t时刻马尔可夫链所处的状态为qk, 显然qk∈ (S1 , S2, , SN) 。所定义的3个概率参数含义如下:
π:初始分布矢量π=[π1, π2, , πN]用于描述给定的观察序列O=o1, o2, , oT在t=1时刻状态q1属于模型中各状态的概率分布。即πi=P{q1=Si}, i=1, 2, , N, 它满足:undefined;
A:状态转移概率矩阵A=[aij]NN, 其中, aij=P (qI+1=Sj|qi=Si) , i, j=1, 2, , N, 它表示当前处于状态Si, 下一时刻处于状态Sj的概率, 它满足:undefined;
B:观察序列的概率集合B=[bij]MM, 其中M为每个状态对应的可能的观察值数目。记M个观察值为V1, V2, , Vm, t时刻的观察值为ot, 其中ot∈{V1, V2, , VM};B为观察序列O中的任意观察, 它是随机变量或随机矢量在各状态的观察概率空间中的分布。这里的分布有离散型和连续型两类。bj (ot) =P (Ot=Vk|qj=Sj) , j, k=1, 2, , N, 它表示t时刻、 状态时, 观察序列符号的概率分布。
2.2 HMM的三个基本问题
在HMM的实际应用中有以下3个中心问题需要解决。
(1) 评估问题:
对应给定模型λ= (A, B, π) 和观察值序列O={O1, O2, , OT}, 求产生给定观察值序列的概率P (O︱λ) 。用它可衡量给定模型与此观察值序列之间的匹配情况。
(2) 解码问题:
对于给定模型和观察值序列, 选择最优的隐含状态序列来最佳地解释观察序列, 使P (O︱λ) 最大化。
(3) 学习问题:
对于给定的一个观察值序列, 调整参数λ, 使得观察值的输出概率P (O︱λ) 最大。也就是, 用给定的观察值序列去训练HMM模型, 优化模型参数。
2.3 基于HMM的正常 (异常) 交通行为建模
要建立正常 (异常) 的交通行为模型, 就是用在正常 (异常) 的交通情况下检测到的数据来确定HMM的参数λ= (A, B, π) , 也就是解决HMM的3个基本问题中的学习问题。本文使用标准的Baum-Welch (BW) 算法进行参数估计, 以解决HMM中的学习问题。在本实验中, 由于读取数据类型的顺序不变, 参数A与π可以直接给定, 因此只需对输出概率进行估计, 以此可以提高准确率以及节约训练时间。
建立HMM需要确定状态数N。在本实验中, 共有六个状态, 分别是上下游的车流量, 占有率和平均速度。
3 实证研究
3.1 HMM算法实现
计算输出概率P (O︱λ) 首先要解决评估问题, 这可以通过“前向-后向”算法来实现。定义前向变量αt (i) 为给定HMM参数λ, 输出部分观察序列{O1, O2, , OT}, 则在t时刻处于状态Si的概率αt (i) =P (O1Ot, qt=Si|λ) ;定义后向变量βt (i) 为给定HMM参数λ, 观察序列在t时刻处于状态Si, 则系统输出部分观察序列{Ot+1, Ot+2, , OT}的概率βt (i) =P (Ot+1, Ot+2, , OT, qt=Si|λ) 。
通过前向、后向变量, 可以得到输出概率
undefined
在用BW算法训练HMM时, 还需要定义另外2个变量εt (i, j) 和γt (i) 。εt (i, j) 为给定模型λ和观测序列O在t时刻处于状态Si, 而在t+1时刻处于状态Sj的概率, 即
undefined
γt (i) 为给定模型λ和观测序列O在t时刻处于Si状态的概率, 即
undefined
从εt (i, j) 和γt (i) 的定义可以得出, 如果定义Eij为从状态Si转移到状态Sj的期望次数, Eif为从状态Si转移的期望次数, Ei为处于状态Si的期望次数, 则有
undefined (4)
undefined (5)
undefined (6)
利用式 (4) ～式 (6) 就可以得到HMM参数重估的方法。定义Ejvk为处于状态Sj并且观测值为vk的期望次数, 一种新的重估模型undefined可以通过下面的等式得到, 即
undefined (7)
undefined (8)
undefined (9)
根据给定的A, π和随机给定的B, 得到初始模型λ= (A, B, π) , 利用训练的交通数据序列O, 通过式 (7) ～式 (9) 可以计算重估后的模型undefined。从而得知, undefined将比λ更接近实际模型, 即undefined。用undefined代替λ, 并重复进行上述重估过程, 直到满足某一限制条件为止, 例如undefined的值小于某个给定阈值。可以看出, 重复进行重估计算, 就可以提高训练序列O的输出概率, 这个重估程序的最终结果被称为HMM的最大似然估计。训练结束后, 得到的λ= (A, B, π) 即为正常交通行为的HMM模型。
3.2 实验结果及分析
实验一: (1) 建立正常的HMM, 用采集到的正常的交通流数据对模型进行训练。 (2) 通过训练得到正常的HMM, 用采集到的任意交通流数据进行测试。 (3) 测试输出loglik (模型和数据吻合似然度) , 如果loglik > -12.0000, 正常, 无交通事件发生;否则异常, 即发生了交通事件。
实验二: (1) 建立正常HMM1, 用采集到的正常的交通流数据对模型进行训练。 (2) 建立异常HMM2, 用采集到的异常的交通流数据对模型进行训练。 (3) 通过训练得到正常的HMM1和异常的HMM2, 用采集到的任意交通流数据分别用HMM1和HMM2进行测试。 (4) 测试分别输出loglik1和loglik2, 如果loglik1 > loglik2正常, 无交通事件发生;否则异常, 即发生了交通事件。
4 结论
提出一种基于HMM的交通事件检测新方法。利用HMM可以跟踪状态转移的特点, 通过实验一与实验二比较, 可知实验二方法较好。
实验结果表明, 建立HMM模型用于交通事件检测是可行的, 此方法简单明了, 模型训练时间短。测试中可发现在较低的误警率下, 有较高的检测率且检测时间较短。在接下来的研究中, 将着重于降低交通事件的误识率。给定一组交通数据, 确实难以判断是否有交通事件发生, 误识率会相对较高, 在今后的研究工作中, 会考虑结合多组数据, 来进一步降低模型的误识率。
参考文献
[1]Wei Wang, Shuyan Chen, Gaofeng Qu.Incident detection algo-rithm based on partial least squares regression.Transportation research part C, 16, pp.54-70.
[2]张敬磊, 王晓原.交通事件检测算法研究进展[J].武汉理工大学学报, 2005, 29 (2) :215-218.
[3]Shuyan Chen, Wei Wang.Decision tree learning for Freeway Au-tomatic Incident Detection.Expert systems with applications, 2008.
[4]Alexander Seward.Afast HMM match algorithmfor very large vocabulary speech recognition.Speech Communication[R], 2004, 42 (2) :191-206.
[5]Min-Sub Kim, Daijin Kimand Sang-Youn Lee.Face recognition u-sing the embedded HMM with second-order block-specific obser-vations[J].Pattern Recognition, 2003, 36 (11) :2723-2735.
基于HMM的哈萨克语词性标注研究 第7篇
新疆地区的哈萨克语言使用人数有一百三十多万,是哈萨克语系跨境语言,属于阿尔泰语系突厥语族的克普恰克语支,拼音文字,是黏着语类型;具有自己独特的特点,不同于汉语、英语、维吾尔语等。
在自然语言中,词是语言的基本单位,是组成各国语言的基础。在词的处理过程中,词性(POS)是词汇最重要的特性。词性标注是实现自然语言分析和理解的一个重要中间环节,其任务是为文本中的每一个词标注一个正确的标记。
在词性标注中出现的早期错误,将在后续处理链中被放大。例如在机器翻译中,词性标注错误有时会导致错误地理解整句话。词性标注的正确率将直接影响计算机翻译系统的应用性能,从而最终影响用户对机器处理自然语言的应用,如信息抽取、信息检索、文本分类、机器翻译等都依赖于词性标注的精确结果才能最终取得理想的效果[6]。
词性标注的方法分为手工标注和自动标注。手工标注主要是人根据自身对语言知识的掌握、工作经验等,使用主观意识,思考并判断词性。自动标注是指完全用计算机实现词性标注。
目前哈萨克语的词性标注基本上采用基于规则和统计的方法,本文重点研究基于统计的HMM在哈萨克语词性标注中的应用。
1 基于HMM的词性标注模型
1.1 HMM原理
HMM是一种用参数表示的用于描述随机过程统计特性的概率模型,是一个双重随机过程,由两个部分组成:一个可观察层和一个隐藏层。
其中可观察层是待识别的观察序列,隐藏层是一个马尔可夫过程,即一个有限状态机,其中每个状态转移都带有转移概率。对于 HMM 模型,其状态转换过程是不可观察的,因而称之为“隐” 马尔可夫模型。
HMM的理论基础是,假设自然语言中词的出现排列服从隐马尔科夫模型,将自然语言中的语法单位(例如词性)看成是隐马尔科夫模型过程的一个“状态”。并且认为第n个语法单位(本文指词性)只与它的前n-1(n>1)个语法单位相关。通过这些语法单位间潜在关系及出现概率,也就是隐马尔科夫模型中的“状态”间的变化来进行词性标注。
隐马尔科夫模型是描述某种连续符号序列的条件概率的一个统计模型, 可以定义一个五元组来描述隐马尔科夫模型[1,2]:λ=(S, V, A, B, π),其中:
(1) S代表一组状态集合S={1, 2,, n},n为状态数。
(2) V代表一组可观察到的符号集合V={v1,v2,,vm},m为状态数。
(3) A代表状态转移矩阵A={aij}是一个n行n列的矩阵,其中aij=p(qt+1=j|qt=i),1≤i,j≤n。
(4) B代表可观察符号的概率分布B={bj(k)}。bj(k)是状态j输出符号k的概率。则有:bj(k)=p(vk|j),1≤k≤m,1≤j≤n。
(5) π代表初始状态的概率分布π={πi},表示在初始时刻选择某个状态i的概率。则有πi=p(q=i)。
1.2 HMM用于词性标注
已知单词序列w1w2wn,求词性序列c1c2cn 。
HMM 模型:将词性理解为状态,将单词理解为输出值。
训练:统计词性转移矩阵[aij]和词性到单词的输出矩阵[bjk]。
求解:Viterbi算法。
设T为标注集,W为词集,词性标注就是寻找一个词性序列T={t1,t2,,tn},使得它对于单词序列W={W1,W2,,Wn}是最优的。其中ti为wi的词性。如果假设词性序列是一个隐马尔科夫模型,这个模型在每次进行状态转移时都产生一个单词,具体产生哪个单词由其所处的状态决定。这样,可以很容易把词性标注和上述的隐马尔科夫模型联系起来,很自然地可以定义一个HMM词性标注模型(T,W,A,B,π),其中参数A,B,和π可通过已标注训练语料估计得到。
在上述模型下,模型的状态是词性标记;输出符号是词。词性序列T={t1,t2,,tn},对应于模型的状态序列,而标注集对应于状态集,词性之间的转移对应于模型的状态转移。假设词性序列的隐马尔科夫模型是1阶的,即每个词的词性都只依赖前面一个词性而决定,因此有状态转移概率p(ti|tj),这对应于模型中的状态转移概率aij。而单词为模型的观察值,不同的词性状态对不同的单词有不同的输出概率。设词性ti产生单词wi的概率是p(wi|ti),它对应于模型中描述产生输出的概率bij。在己知输入词序列w1,n的条件下,寻找最可能标记序列t1,n的任务,可看作在给定观察序列w1,n条件下搜索最可能的HMM状态序列的问题,词性标注的任务可以等价于求解下式: argmaxp(T|W)。
即对于特定的W寻找最可能的T,在此之前,需要利用已标注语料获得模型参数。首先,引入独立性假设,认为词序列中的任意一个词的出现概率只与当前词的词性标记有关。而与周围(上下文)的词、词类标记无关;其次,采用二元假设,即认为任意词类标记的出现概率只与它紧邻的前一个词类标记有关[3]。之后利用Viterbi算法解决此问题。
1.3 HMM参数计算方法
一个确定的隐马尔科夫模型,它的状态数目是确定的。HMM在词性标注任务中词性标注集是确定的。HMM的五元组中A、 B、 π这三个参数是通过统计计算得到的。设有w=w1w2w3wjwn是待标注词串。t=t1t2t3tjtn是标注串。那么,我们所要求的解是:当输入为w的时候,输出为t的概率p(t|w)。根据贝叶斯公式,可以写成:
t1,n=argmaxp(t1,n|w1,n)
=argmaxp(t1,n)p(w1,n|t1,n) (1)
假定模型p(t1,n)可以由Bi-gram实现,并且假定
式(2)中p(ti|ti-1)为词性状态转移概率,p(wi|ti)为词汇发射概率。
对p(ti|ti-1)和p(wi|ti)的概率使用极大似然估计(MLE)来计算,即:
式(3)至式(5)中,count(ti,ti-1)表示在训练语料中词性ti-1出现在ti后面的次数;count(wi,ti)表示在训练语料中,wi被标注为词性ti的次数;count(ti)表示在训练语料中词性ti出现的次数;count(q1=ti)表示在训练预料中句首出现词性ti的次数;count(q1)表示在训练预料中句首的个数。
2 词性标注过程
2.1 预处理
在词性标注之前首先要进行训练,本文训练使用的语料为08年《新疆日报》。为了获得熟语料需要将文本进行切分,提取词干与词典比较得到词性。从形式上说, 词干是哈萨克语文本中的词去除构形语素以后在词典中的原形词。所以,在进行词性标注之前首先要完成词干提取,它包括两个内容:首先从哈萨克语文本中提取出词,进行词的切分,同时去除词中的构形语素;其次是将去除了构形语素的部分还原为词典中的原形词[5]。之所以要“还原”是因为在哈萨克语词干上附加构形语素时,受到一些语音规律的影响,词干本身的元音或者辅音要发生某些变化,所以必须要将其还原成词典中的原形词。
将文本进行词干提取后得到的形式如图1所示。
其中pos表示单词的词性,stem表示单词的词干,affix表示单词的附加成分,var为词类标记符号(var为0时表示系统自动标注单一词性;var为1时表示兼类词;var为2、3时表示实体名;var为4时表示人工修改的词性)。由于本文中词典数量有限,对系统中没有匹配成功的单词要进行人工标注,对文中少量标注错误的单词也要进行人工修改。修改完成后此表即为要训练的语料形式。
2.2 数据平滑
建立统计语言模型时所使用的训练语料都是有一定规模的,不可能是无限的,这就导致了一个问题:在现实世界中出现的语言现象没有在训练语料中出现。当然通过扩大训练语料的规模可以在一定程度上缓解这个问题,但是训练语料的规模不能无限的扩大,即便是训练数据扩展到很大规模,也还是不能捕捉到许多在现实中出现的小概率的语言现象。
平滑技术是解决上述问题的一个方案。其主要思想就是调整有极大似然估计得到的概率分布,从而得到一个更准确、更合理的概率分布。平滑技术通常会使较低的概率值(比如0)升高,同时使较高的概率值降低,从而使得整个概率分布更加平滑和均衡。常见的参数平滑技术有[7]:Additive平滑方法、Jelinek-Mercer平滑方法、n-Dirichlet平滑方法、Absolute-Discounting平滑方法等。Additive平滑方法中假设每一个词的出现次数都比它实际的出现次数多δ(δ为0到1之间的任意实数);Jelinek-Mercer平滑方法的思想是利用低阶语言模型的信息来对高阶语言模型进行线性插值;n-Dirichlet平滑方法将语言模型假设为一个多项式分布,在该方法中利用了贝叶斯分析方法,通常还使用Dirichlet先验概率。
本文采用Absolute-Discounting平滑方法,它的基本思想就是将训练语料中出现的词对的频率减去一个常量。然后将这些扣除的概率分配给没有在训练语料中出现的词对。与Jelinek-Mercer方法类似,Absolute-Discounting平滑方法也是将高阶语言模型和低阶语言模型通过插值的方式得到一个混合模型;其方法是在高阶模型中直接减去一个常量D,即词性转移概率和词汇发射概率如下:
式(6)、式(7)中,D≤1。同时,为了使概率和为1,必须有:
N(ti-1)=|{ti:count(ti,ti-1)>0}|
λ1=e-count(ti,ti-1)λ2=e-count(wi,ti)
∑ticount(ti,ti-1)表示ti出现的次数;
∑wcount(wi,ti)表示wi出现的次数;
count为训练实例的个数。
2.3 生词处理方法
在进行开放测试时,会出现在训练语料中没有出现的生词(或称为未登录词)。在本文中采用文献[8]中的一种基于隐马尔科夫模型的处理生词的方法。解决未登录词xj的词性tj问题实质上是确定xj的词汇发射概率p(xj|tj)的问题。假设有输入句子S=w1,, wj-1xjwj+1,wN,其中S表示整个句子。wi(1≤i≤N)表示单个的词,xj为生词。
假设把S加入训练集中,由于加入的只有一个句子,因此对其他词的发射概率和整个模型的词性转移概率的影响可以忽略不计。遵循HMM的假设,xj的词性tj由wj-1的词性决定。即可得词汇发射概率:
式(8)即为我们将要测试的生词词汇发射概率估算模型。
3 实验结果及分析
实验选用的是2008年《新疆日报》的部分标注语料作为训练语料,内容涉及政治、经济、体育、卫生、文化、艺术、娱乐等多种题材。本文从中抽取了10万、20万、25万词的语料进行了训练。测试时从训练集中随机抽取3万语料作为封闭测试集,从训练集外随机抽取了3万语料作为开放测试集。采用词性标注的正确率对模型进行评价。结果如表1所示。
从上表中可以看出随着训练集大小的增加,模型标注效果会越来越好,正确率逐渐增大,但是增大的趋势是逐渐减小的。
4 结论及展望
本文利用基于统计的HMM实现了哈萨克语的词性标注,并且有比较可观的准确率。但是由于训练语料库本身存在着很多不足,如语料库规模不够大;再者经过切分的熟语料中词性标注的准确率不够高,因为里面有一些词与词典匹配未成功,导致标注过程中没有词性,还有一些兼类词的词性不确定,进而影响了训练参数的值。其次,传统的HMM也有它的不足之处:对一个词语出现概率的估计是建立在其前面的历史信息上的,即只考虑到了上文对当前词的依赖关系,没有考虑到该词后面即下文与该词的依赖关系。
为了进一步提高标注的准确率,下一步的工作应该是扩大语料库的规模,完善熟语料的标注(尽量达到完全准确),找到改进的HMM模型,使之不仅考虑到上文对当前词的依赖关系,而且考虑到该词下文与该词的依赖关系,或者加大HMM的阶数。
摘要：词性标注在自然语言信息处理领域中扮演着重要角色,是句法分析、信息抽取、机器翻译等自然语言处理的基础,对于哈萨克语同样如此。在基于词典静态标注的基础上分析了隐马尔科夫模型HMM(H idden M arkovModel)模型参数的选取、数据平滑以及未登录词的处理方法,利用基于统计的方法对哈萨克语熟语料进行训练,然后用V iterb i算法实现词性标注。实验结果表明利用HMM进行词性标注的准确率有所提高。
关键词：隐马尔科夫模型,哈萨克语,词性标注,自然语言处理
参考文献
[1]Andrew W Moore.H idden Markov Models[D].Professor School ofComputer Science Carnegie M ellon Un iversity,2004.
[2]Rab iner L.A tutorial on h idden markov models and selected applica-tionsin speech recogn ition[C]//Proceed ings of IEEE,1989.
[3]袁里驰.基于统计的自然语言处理[D].北京邮电大学,2005.
[4]王敏.基于改进的隐马尔科夫模型汉语词性标注[J].计算机应用,2006,12(26).
[5]刘艳,古丽拉.阿东别克,伊力亚尔.哈萨克语词性自动标注研究初探[J].计算机工程与应用,2008,44(20):242-244.
[6]买合木提.买买提.基于统计的维吾尔语词性标注研究与实现[D].新疆大学,2009.
[7]Mann ing.统计自然语言处理基础[M].北京:电子工业出版社,2005.
