搜索
HMM的理论基础一、HMM定义1.N：模型中状态的数目，记t时刻Markov链所处的状态为2.M：每个状态对应的可能的观察数目，记t时刻观察到的观察值为3.：初始状态概率矢量，，，4.A：状态转移概率矩阵，，，5.B：观察值概率矩阵（适用于离散HMM），，，；对于连续分布的HMM，记t时刻的观察值概率为一个离散型的HMM模型可以简约的记为。二、关于语音识别的HMM的三个基本问题1.已知观察序列和模型参数，如何有效的计算。a.直接计算2-1当N=5，T=100时大概需进行次乘法!b.前向算法定义t时刻的前向变量（forwardvariable），可以通过迭代的方法来计算各个时刻的前向变量：1）初始化（Initialization）当t=1时2-22）递归（Induction）当时即：2-33）终结（Termination）2-4乘法次数大约为：N2Tc.后向算法定义t时刻的后向变量（backwardvariable），可以通过迭代的方法来计算各个时刻的后向变量：1）初始化（Initialization）当t=T时，2-52）递归（Induction）当时即：，2-63）终结（Termination）2-7乘法计算次数约为：N2T2.已知观察序列和模型参数，在最佳意义上确定一个状态序列。定义一个后验概率变量（posterioriprobabilityvariable）2-7则最优序列可以通过，2-7求得。不过，这样求得的最优序列有些问题。如果，那么这个最优序列本身就不存在。这里讨论的最佳意义上的最优序列，是使最大化时的确定的状态序列。即，使最大化时确定的状态序列。定义为t时刻沿一条路径，且，输出观察序列的最大概率，即：2-8下面介绍迭代计算的Viterbi算法：1）初始化（Initialization），回溯变量：，2）递归（Induction）即：2-82-93）终结（Termination）2-102-114）回溯状态序列，2-123.已知观察序列和模型参数，如何调整模型参数使最大。定义3.1给定训练序列和模型，时刻Markov链处在状态和时刻处在状态的概率定义如下3-1定义3.2给定训练序列和模型，时刻Markov链处在状态的概率定义如下3-2定义3.3给定训练序列和模型，从状态转移出去的概率为定义3.4给定训练序列和模型，从状态转移到状态的概率为利用Baum-Welch重估算法可以得到使局部最大时的参数更新公式。1.Baum-Welch重估公式的理论基础引理3.1设，，为正实数，，，为非负实数，那么，由对数函数的凹特性，有如下结论3-3定义辅助函数如下3-4其中，为更新前模型参数，为更新后模型参数，为训练序列，为可能的状态序列。利用和引理3.1易得3-5式3-5构成了重估公式得理论基础，对辅助函数，只要能够找到，使，从而，这样，更新后的模型在拟和训练序列方面就比更新前的模型要好，使最大而得到的的参数更新公式就称之为Baum-Welch重估公式。引理3.2，，在的约束条件下，函数的唯一最大值点为。证明如下求最大值令得：，同理可证：利用凹函数特性可知此最大值唯一。2.离散HMM模型的重估公式HTK内存管理一、HTK内存管理概述C语言编程中，遇到的关于内存分配和释放的问题主要有如下两个方面。第一是指针维护问题。试想，你写的一个程序执行了一系列内存空间分配（通常是由malloc函数完成）操作，为了能够在以后适当的时候（通常是你不再需要那些内存时）可以将分配的内存空间释放（通常是由free函数完成），你必须小心谨慎的维护好这些指向分配的内存空间的指针。有经验的程序员大概都会有这样的感受，维护这些指针并非易事！特别是当程序比较复杂时，尤为如此。如果你一不小心（其实这很容易）丢掉了某些指针，那么操作系统将无法回收那些内存（这便是我们常说的内存泄漏问题），除非你的程序死了。第二就是关于内存分配释放操作本身。如果你的程序会相当频繁的执行malloc和free函数，那么程序将会费去大量的CPU时间来执行它们。为了解决以上两个问题，尽可能的提高内存利用率，HTK设计了一个内存管理子系统，利用自定义的堆结构（Heap）来进行内存分配和释放。HTK内存分配和释放的主要思想是一次向操作系统要大一些的内存块，然后在将它分成小块供上层程序使用，不需要时只需释放那个大内存块。HTK把堆结构分为三大类：1.M-HEAPS：元素大小固定，new/free操作执行次序无限制，可全局重置(globalreset)。2.M-STACK：元素大小可变，最后分配的空间必须先释放，可全局重置。3.C-HEAPS：元素大小可变，new/free操作执行次序无限制，全局重置无效（直接使用malloc和free函数）。二、数据结构1.堆数据结构定义typedefenum{MHEAP,MSTAK,CHEAP}HEAPTYPE;//堆类型定义typedefunsignedchar*ByteP;//无符号字符（8位）指针typedefvoid*Ptr;typedefstruct_Block*BlockP;/*MHEAP和MSTAK块数据结构定义*/typedefstruct_Block{/*MHEAP,MSTACK*/size_tnumFree;/*空闲元素数目,空闲字节数*/size_tfirstFree;/*第一个空闲元素索引,栈顶索引*/size_tnumElem;/*块分配元素的个数,块分配的字节数*/BytePused;/*指向元素分配表指针,1bit/元素,不使用*/Ptrdata;/*指向数据区指针,指向数据区指针*/BlockPnext;/*指向下一个块指针,指向下一个块指针*/}Block;/*堆数据结构定义*/typedefstruct{/*MHEAP,MSTACK*/char*name;/*堆的名称,堆的名称*/HEAPTYPEtype;/*堆的类型,堆的类型*/floatgrowf;/*增长因子,增长因子*/size_telemSize;/*元素大小,总是1*/size_tminElem;/**/size_tmaxElem;/*每个块最大允许分配的元素个数,每个块最大允许分配的字节数*/size_tcurElem;/*当前块元素个数,当前块字节个数*/size_ttotUsed;/*已使用的元素总个数,以使用的字节总个数*/size_ttotAlloc;/*分配的元素总数,分配的字节总数*/BlockPheap;/*指向当前块的指针,指向当前块的指针*/BooleanprotectStk;/*仅适用于MSTAK*/}MemHeap;2.堆数据结构框图M-Heaps内存堆结构示意图同一个M-Heaps内存堆中分配的元素大小都是一样的。堆结构中的块指针成员变量heap指向数据块链的头。数据块链中的每个块分配的内存区大小由（字节）计算得到。每个块中的BYTE型指针成员变量used指向记录元素使用状态的表数据结构，表中第i位记录数据区中第i个元素的使用状态：1表示使用中、0表示空闲。每个块中的firstFree成员变量的值表示数据区中第一个空闲元素的标号。每个块中的numFree成员变量的值记录所在块中空闲元素的个数。如果numFree为0表示块满，这时firstFree=numElem。M-Stack内存堆结构示意图三、算法1.接口描述1.定义：Export--voidInitMem(void)说明：初始化全局MSTAK堆变量gstack和全局CHEAP堆变量gcheap。该函数必须在调用任何其它堆操作函数前调用。参数：无返回值：无2.定义：Export--voidCreateHeap(MemHeap*x,char*name,HeapTypetype,size_telemSize,floatgrowf,size_tnumElem,size_tmaxElem)说明：创建一个名称为name、类型为type的内存堆，elemSize指定内存堆中元素的大小，numElem指定块中元素默认个数。如果，内存堆的类型是MSTAK或CHEAP，则elemSize必须为1。参数：x：指向给定的内存堆[In,Out]name：堆的名称[In]type：堆类型[In]elemSize：对于MHEAP表示堆的每个块中元素的大小，对于MSTAK和CHEAP，elemSize必须设为1[In]growf：numElem：堆的每个块默认分配的元素个数[In]maxElem：堆的每个块最大允许分配的元素个数[In]返回值：无3.定义：Export--voidResetHeap(MemHeap*x)说明：释放内存堆x中所有元素，对CHEAP内存堆无效。参数：x：指向给定的内存堆[In,Out]返回值：无4.定义：Export--voidDeleteHeap(MemHeap*x)说明：释放内存堆x中所有元素，并删除内存堆x。参数：x：指向给定的内存堆[In,Out]返回值：无5.定义：Export--PtrNew(MemHeap*x,size_tsize)说明：从内存堆x中分配一大小为size的新元素并返回其指针。如果x类型为MHEAP则忽略参数size。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。参数：x：指向给定的内存堆[In,Out]size：指定分配的元素大小[In]返回值：返回指向新分配的元素的指针6.定义：voidBlockRecorder(BlockP*p,intn)说明：对于MHEAP堆，从块p向后搜索有n个以上（包括n个）元素的块，并将其移至块链表头。对于MSTAK堆，从块p向后搜索有n个以上（包括n个）字节数的块，并将其移至块链表头。参数：p指向给定的块[In,Out]n对于MHEAP，表示元素个数；对于MSTAK，表示字节数。[In]返回值：无7.定义：void*GetElem(BlockPp,size_telemSize,HeapTypetype)说明：如果type为MHEAP则从块p中返回一空闲元素指针，并将其在使用状态表中的对应项置1。如果type为MSTAK则从块p中返回一大小为elemSize字节数的区域指针，并对块p中firstFree和numFree变量进行相应的修改。参数：p：指向给定的块[In]elemSize：元素大小[In]type：所属堆的类型[In]返回值：如果成功，则返回大小为elemSize字节数的数据区，否则返回NULL。8.定义：BlockPAllocBlock(size_tsize,size_tnum,HeapTypetype)说明：分配一个数据区大小为size*num字节数的块，在进行必要的初始化后，返回该块的指针。参数：size：元素大小[In]num：元素个数[In]type：所属堆的类型[In]返回值：如果分配成功，则返回块指针，否则程序异常退出。9.定义：size_tMround(size_tsize)说明：返回大小=size并且整除FWORD（8）的值。参数：size输入大小[In]返回值：返回计算的大小10.定义：Export--PtrCNew(MemHeap*x,size_tsize)说明：从内存堆x中分配一大小为size的新元素清0后返回其指针。如果x类型为MHEAP则忽略参数size。如果分配失败，程序将会异常退出，所以返回值永远不会为NULL。参数：x：指向给定的内存堆[In,Out]size：指定分配的元素大小[In]返回值：返回指向新分配的元素的指针11.定义：Export--voidDispose(MemHeap*x,void*p)说明：从内存堆x中释放元素p参数：x指向给定的内存堆[In,Out]p元素指针[In]返回值：无2.接口实现1.内存堆创建算法CreateHeapvoidCreateHeap(MemHeap*x,char*name,HeapTypetype,size_telemSize,floatgrowf,size_tnumElem,size_tmax