概率论与随机过程 论文.docx

题目：马尔科夫链的工程应用举例 摘 要在讨论马尔科夫链基本概念的基础上，分析了实践工程中两个应用马尔科夫链的实例，即隐马尔科夫模型在语音识别中的应用和用马尔科夫链对 Linux 进程行为的异常检测。前者通过建立隐马尔科夫模型（HMM），实现语音识别；后者将一个系统调用序列看作是由不同状态（系统调用）组成的一个马尔科夫链，再利用数学工具对Linux 的进程异常行为进行检测。关键词：马尔科夫链，隐马尔科夫模型（HMM），语音识别技术一 马尔科夫链的概念马尔科夫链，因安德烈马尔科夫（A.A.Markov，18561922）得名，是数学中具有马尔科夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。 马尔科夫链是随机变量X1,X2,X3.的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数，则 P(Xn+1=x|X0, X1, X2, , Xn) = P(Xn+1=x|Xn). 这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔科夫性质。 马尔科夫在1906年首先做出了这类过程 。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。 二马尔科夫链的工程应用举例（一）隐马尔科夫模型在语音识别中的应用1.隐马尔科夫模型的概念：隐马尔科夫模型（Hidden Markov Model，HMM）作为一种统计分析模型，创立于20世纪70年代。80年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。基本理论隐马尔科夫模型是马尔科夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有响应概率密度分布的状态序列产生。所以，隐马尔科夫模型是一个双重随机过程-具有一定状态数的隐马尔科夫链和显示随机函数集。自20世纪80年代以来，HMM被应用于语音识别，取得重大成功。到了90年代，HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”。近年来，HMM在生物信息科学、故障诊断等领域也开始得到应用。模型的表达隐马尔科夫模型可以用五个元素来描述：1） N，模型的隐状态数目。虽然这些状态是隐含的，但在许多实际应用中，模型的状态通常有具体的物理意义2） M，每个状态的不同观测值的数目。3） A ， 状态转移概率矩阵。描述了HMM模型中各个状态之间的转移概率。其中Aij = P(at+1 =Sj | qt=Si),1i,jN. (1)式（1）表示在t时刻、状态为Si的条件下，在t+1时刻状态是Sj的概率。4） B ，观测概率矩阵。其中Bj(k) = PVk(t) | qt = Sj; 1jN,1kM.表示在t时刻、状态是Sj条件下，观察符号为Vk(t)的概率。5） 初始状态概率矩阵 =j j= Pq1 = Sj;1jN.表示在出示t=1时刻状态为Sj的概率。一般的，可以用=(A,B,)来简洁的表示一个隐马尔科夫模型。给定了N,M,A,B,后，隐马尔科夫模型可以产生一个观测序列 O=O1O2O3Ot2.语音识别技术概述语音识别系统本质上是一种模式识别系统,目前有很多语音识别算法,但其基本原理和基本技术相似。一个完整的语音识别系统一般都包括有特征提取、模式匹配和参考模式库3个基本单元,它的基本结构如下图所示。(1)特征提取所谓特征提取就是从语音信号中提取用于语音识别的有用信息,其基本思想是将预处理过的信号通过一次变换,去掉冗余部分,而把代表语音本质特征的参数抽取出来,如平均能量、平均跨零率、共振峰、LPC系数、MFCC系数等。(2)模式匹配这是整个语音识别系统的核心,它是根据一定规则(如HMM)以及专家知识(如构词规则、语法规则、语义规则等),计算输入特征与参考模式库之间的相似度(如匹配距离、似然概率),判断出输入语音的语意信息,得到最佳的识别结果。(3)参考模式库在识别之前首先建立参考模式库,通过讲话者多次重复语音,从原始语音样本中去除冗余信息,保留关键数据,再按照一定规则对数据加以聚类,形成模式库。3. 隐马尔科夫模型HMM (H idden Markov Model)分析HMM方法现已成为语音识别的主流技术,目前大多数大词汇量、连续语音的非特定人语音识别系统都是基于HMM的。HMM算法很好地描述了语音信号的整体非平稳性和局部平稳性,是较为理想的一种语音识别模型。不足之处在于统计模型的建立需要依赖一个较大的语音库,这在实际工作中占有很大的工作量,且模型所需要的存储量和匹配计算(包括特征矢量的输出概率计算)的运算量相对较大。HMM的三个基本问题1) 评估问题。给定观察序列O= O1O2.OT和模型l = ( A, B,p )，计算P(O|l)。即给定模型和输出观察序列，如何计算从模型生成观察序列的概率。可以把它看作是评估一个模型和给定观察输出序列的匹配程度，由此可以用来在一系列候选对象中选取最佳的匹配。2) 解码问题。给定观察序列O= O1O2.OT和模型l = ( A, B,p )，求在某种有意义的情况下最优的相关状态序列Q= q1q2.qT 。该可以理解为对输出观察的最佳“解释”，它试图揭示模型的隐藏部分，比如说查找“正确”的状态序列，在应用中，通常都使用一个优化策略来最大可能的解决这个问题。3) 学习问题。如何调整模型参数l = ( A, B,p )，对于一个给定的观察序列O= O1O2.OT，使得P(O|l)最大。它试图优化模型的参数来最佳的描述一个给定的观察序列是如何得来的。对于三个基本问题典型的可以分别利用以下算法相应进行解决评估问题Forward-backward算法解码问题Viterbi算法学习问题Baum-Welch估计算法这样，语音识别的问题就可以表示成如下的方法步骤：已知标准语音序列w1w2wn，求待测序列c1c2cn 的含义HMM模型：将每句话为理解为状态将输入的待测样本为理解为观测值训练：统计状态转移矩阵aij和语言序列到观测序列的输出矩阵bik求解：Viterbi 算法步骤：声音采样傅立叶到频域频域特征向量提取输入样本构造HMM输入声音求解模型（二） 用马尔科夫链对 Linux 进程行为的异常检测应用马尔科夫链进行异常分析的主要思想是：将一个系统调用序列看作是由不同状态（系统调用）组成的一个马尔科夫链，将系统调用序列转化为多步转移矩阵，进行模式提取，然后根据最大转移概率原理进行预报，由预报准确度决定异常与否。分析过程主要由下列几个步骤组成：数据转化，模式提取，回代，测试，异常检测。实验数据由 login、ps、lpr、sendmail、inetd、named 等程序的正常和入侵数据集组成，每个数据集都是属于某一程序的，由多个进程的系统调用序列组成。1. 数据转化与模式提取程序可以看作是一个随机向量，它的p 次执行，即p 个进程可以看作是p 个样本向量。对每个进程的系统调用序列中状态间的转移进行频数统计，将进程序列分别转化为1,2,n 步转移频数矩阵，于是p 个进程序列就是p 个其元素为矩阵的样本向量，对这 p 个样本向量进行特征统计，得到其出现率，平均值和标准差3 个向量引入出现率是因为：一个状态转移ij，它只在10个序列中出现过和它在20 个序列中都出现过是不同的，前者在各序列中出现的可能性要小于后者，一般应选择出现可能性大的作为预报依据，这个量正好能够反映这种情况。当出现率相同时，我们就必须借助另外的量作预报，因此还引入了平均值，认为它是程序正常运行时状态转移对应的频数值，它将作为模式用来对未知序列进行状态预报。引入标准差则是为了衡量转移频数对平均值的偏差程度，当标准差过大时，对应的平均值已经不能反映实际的转移频数，应另作处理。这样，以一个程序向量的3 个特征作为模式就可用于预报，进行异常分析。2. 回代回代是指将形成模式的数据再输入给系统，看模式对自身的识别能力。显然，若连自身都无法识别，那么这个模式也就没有用了。回代过程主要是将产生模式的各序列分别输入，看预报结果，如果预报的识别效果好，就认为可以识别自身，可以进行测试和异常检测了。具体过程如下：首先设置两个计数器：“预报正确”计数器，“预报错误”计数器。当预报准确时，“预报正确”计数器增1；否则，“预报错误”计数器增1。要预报某一时刻的状态，根据最大转移概率原理用它前n 个已读入的状态作n 步预报：(1)用出现率值最大的作为预报结果；(2)若出现率相同,则用平均值最大的作为预报结果。为了简化处理，这里暂时没有考虑方差过大的情况，后面将看到这样处理所带来的影响。然后按预报结果修改转移矩阵，使转移矩阵随着状态的不断输入而改变，随时间不断适应随机过程的改变。3 存在的问题按上述步骤我们对各数据集进行了模式提取和回代。结果发现对各序列做状态预报时，在每个序列开始部分就出现了多个预报错误。跟踪模式形成过程发现，这主要是由于随着序列中各状态的输入，后面出现的状态转移，其统计性与前面部分的统计性不同，导致前面部分的统计性被覆盖。如果只取序列的前面部分，比如前60 个系统调用，作模式提取和回代，则预报错误明显降低。通常，如果将序列分成前后两部分处理，结果会好些，然而对于含有循环子序列的程序来说，这样的处理结果没有很大改善。比如程序lpr，它是Linux 下的打印程序，由于lpr 序列长度由打印文档的大小决定，会产生不定次数的循环子序列对read-write，在模式形成过程中，这两个状态间的转移对应标准差过大，因此无法进行准确预报。而这种循环子序列又是序列的主要组成部分，因此又必须加以考虑。考虑到循环子序列的影响以及序列分段会改善预报效果，我们对前面方法作了改进。4 改进后的模式提取和回代由于循环子序列对整个序列的统计性影响很大，所以决定从循环子序列处将序列隔开，进行分段，然后按照：(1)分段的不同；(2)段内起止状态的不同；(3)段内所含状态、状态个数的不同。将程序的多个进程分类。段内的处理则与前述的相同，这样将得到多个模式（分类）。比如lpr 的98 个正常序列，循环子序列是3，3、4 以及106、105、105、107（这里用整数表示系统调用，如3 表示系统调用read），经模式提取得到18个类，每类是由不同的段组成。各段就是一个由转移矩阵组成的向量加一个循环子序列。模式提取之后，下一步要进行回代，当然这次的回代过程有所不同，将用多个类同时作预报，在每一类内按顺序用每段作预报。如果有一个类可以识别出当前序列，也就是预报结果很好，那么当前序列就是可识别的，认为是正常序列。如果按“预报错误在10 个以下，且未出现连续M 个预报错误就可接受”的原则（M 是指预报步数），lpr 的所有训练序列都是可识别的。因此，可以看出这种分类方式对自身的识别能力很好。5. 测试与异常检测测试的目的是验证模式对正常行为变化的鲁棒性，异常检测则是检测其对异常行为的敏感性。测试和异常检测的过程是一样的，只是前者使用正常数据集，后者使用异常数据集。这里，异常判断的依据是：(1)起始状态无法匹配的是异常。我们认为某程序当它执行时