1、.HMM的理論基礎(chǔ)一、 HMM定義1.N：模型中狀態(tài)的數(shù)目,記t時(shí)刻Markov鏈所處的狀態(tài)為2.M：每個(gè)狀態(tài)對(duì)應(yīng)的可能的觀察數(shù)目,記t時(shí)刻觀察到的觀察值為3.：初始狀態(tài)概率矢量,4.A：狀態(tài)轉(zhuǎn)移概率矩陣,5.B：觀察值概率矩陣適用于離散HMM,；對(duì)于連續(xù)分布的HMM,記t時(shí)刻的觀察值概率為一個(gè)離散型的HMM模型可以簡(jiǎn)約的記為。二、關(guān)于語(yǔ)音識(shí)別的HMM的三個(gè)基本問題1. 已知觀察序列和模型參數(shù),如何有效的計(jì)算。a. 直接計(jì)算 2-1當(dāng)N=5,T=100時(shí)大概需進(jìn)行次乘法!b. 前向算法定義t時(shí)刻的前向變量forward variable,可以通過迭代的方法來(lái)計(jì)算各個(gè)時(shí)刻的前向變量：1 初始化I

2、nitialization當(dāng)t=1時(shí) 2-22 遞歸Induction當(dāng)時(shí)即： 2-33 終結(jié)Termination 2-4乘法次數(shù)大約為：N2Tc. 后向算法定義t時(shí)刻的后向變量backward variable,可以通過迭代的方法來(lái)計(jì)算各個(gè)時(shí)刻的后向變量：1初始化Initialization當(dāng)t=T時(shí), 2-52遞歸Induction當(dāng)時(shí)即：, 2-63終結(jié)Termination 2-7乘法計(jì)算次數(shù)約為：N2T2. 已知觀察序列和模型參數(shù),在最佳意義上確定一個(gè)狀態(tài)序列。定義一個(gè)后驗(yàn)概率變量posteriori probability variable 2-7則最優(yōu)序列可以通過, 2-7求得

3、。不過,這樣求得的最優(yōu)序列有些問題。如果,那么這個(gè)最優(yōu)序列本身就不存在。這里討論的最佳意義上的最優(yōu)序列,是使最大化時(shí)的確定的狀態(tài)序列。即,使最大化時(shí)確定的狀態(tài)序列。定義為t時(shí)刻沿一條路徑,且,輸出觀察序列的最大概率,即： 2-8下面介紹迭代計(jì)算的Viterbi算法：1初始化Initialization,回溯變量：,2遞歸Induction即： 2-8 2-93終結(jié)Termination 2-10 2-114回溯狀態(tài)序列, 2-123. 已知觀察序列和模型參數(shù),如何調(diào)整模型參數(shù)使最大。定義3.1 給定訓(xùn)練序列和模型,時(shí)刻Markov鏈處在狀態(tài)和時(shí)刻處在狀態(tài)的概率定義如下 3-1定義3.2 給定訓(xùn)

4、練序列和模型,時(shí)刻Markov鏈處在狀態(tài)的概率定義如下 3-2定義3.3 給定訓(xùn)練序列和模型,從狀態(tài)轉(zhuǎn)移出去的概率為定義3.4給定訓(xùn)練序列和模型,從狀態(tài)轉(zhuǎn)移到狀態(tài)的概率為利用Baum-Welch重估算法可以得到使局部最大時(shí)的參數(shù)更新公式。1. Baum-Welch重估公式的理論基礎(chǔ)引理3.1 設(shè),為正實(shí)數(shù),為非負(fù)實(shí)數(shù),那么,由對(duì)數(shù)函數(shù)的凹特性,有如下結(jié)論 3-3定義輔助函數(shù)如下 3-4其中,為更新前模型參數(shù),為更新后模型參數(shù),為訓(xùn)練序列,為可能的狀態(tài)序列。利用和引理3.1易得 3-5式3-5構(gòu)成了重估公式得理論基礎(chǔ),對(duì)輔助函數(shù),只要能夠找到,使,從而,這樣,更新后的模型在擬和訓(xùn)練序列方面就比更

5、新前的模型要好,使最大而得到的的參數(shù)更新公式就稱之為Baum-Welch重估公式。引理3.2 ,在的約束條件下,函數(shù)的唯一最大值點(diǎn)為。證明如下求最大值令得：,同理可證：利用凹函數(shù)特性可知此最大值唯一。2.離散HMM模型的重估公式HTK內(nèi)存管理一、HTK內(nèi)存管理概述C語(yǔ)言編程中,遇到的關(guān)于內(nèi)存分配和釋放的問題主要有如下兩個(gè)方面。第一是指針維護(hù)問題。試想,你寫的一個(gè)程序執(zhí)行了一系列內(nèi)存空間分配通常是由malloc函數(shù)完成操作,為了能夠在以后適當(dāng)?shù)臅r(shí)候通常是你不再需要那些內(nèi)存時(shí)可以將分配的內(nèi)存空間釋放通常是由free函數(shù)完成,你必須小心謹(jǐn)慎的維護(hù)好這些指向分配的內(nèi)存空間的指針。有經(jīng)驗(yàn)的程序員大概都會(huì)

6、有這樣的感受,維護(hù)這些指針并非易事！特別是當(dāng)程序比較復(fù)雜時(shí),尤為如此。如果你一不小心其實(shí)這很容易丟掉了某些指針,那么操作系統(tǒng)將無(wú)法回收那些內(nèi)存這便是我們常說的內(nèi)存泄漏問題,除非你的程序死了。第二就是關(guān)于內(nèi)存分配釋放操作本身。如果你的程序會(huì)相當(dāng)頻繁的執(zhí)行malloc和free函數(shù),那么程序?qū)?huì)費(fèi)去大量的CPU時(shí)間來(lái)執(zhí)行它們。為了解決以上兩個(gè)問題,盡可能的提高內(nèi)存利用率,HTK設(shè)計(jì)了一個(gè)內(nèi)存管理子系統(tǒng),利用自定義的堆結(jié)構(gòu)Heap來(lái)進(jìn)行內(nèi)存分配和釋放。HTK內(nèi)存分配和釋放的主要思想是一次向操作系統(tǒng)要大一些的內(nèi)存塊,然后在將它分成小塊供上層程序使用,不需要時(shí)只需釋放那個(gè)大內(nèi)存塊。HTK把堆結(jié)構(gòu)分為三大

7、類：1.M-HEAPS：元素大小固定,new/free操作執(zhí)行次序無(wú)限制,可全局重置。2.M-STACK：元素大小可變,最后分配的空間必須先釋放,可全局重置。3.C-HEAPS：元素大小可變,new/free操作執(zhí)行次序無(wú)限制,全局重置無(wú)效直接使用malloc和free函數(shù)。二、數(shù)據(jù)結(jié)構(gòu)1. 堆數(shù)據(jù)結(jié)構(gòu)定義typedef enumMHEAP,MSTAK,CHEAP HEAPTYPE; / 堆類型定義typedef unsigned char* ByteP; / 無(wú)符號(hào)字符8位指針typedef void* Ptr;typedef struct _Block *BlockP;/* MHEAP和M

8、STAK塊數(shù)據(jù)結(jié)構(gòu)定義 */typedef struct _Block /* MHEAP ,MSTACK */ size_t numFree; /* 空閑元素?cái)?shù)目 ,空閑字節(jié)數(shù) */ size_t firstFree; /* 第一個(gè)空閑元素索引 ,棧頂索引 */ size_t numElem; /* 塊分配元素的個(gè)數(shù) ,塊分配的字節(jié)數(shù) */ ByteP used; /* 指向元素分配表指針,1bit/元素 ,不使用 */ Ptrdata; /* 指向數(shù)據(jù)區(qū)指針 ,指向數(shù)據(jù)區(qū)指針 */ BlockP next; /* 指向下一個(gè)塊指針 ,指向下一個(gè)塊指針 */Block;/* 堆數(shù)據(jù)結(jié)構(gòu)定義 *

9、/ typedef struct /* MHEAP ,MSTACK */ char* name; /* 堆的名稱 ,堆的名稱 */ HEAPTYPE type; /* 堆的類型 ,堆的類型 */ float growf; /* 增長(zhǎng)因子 ,增長(zhǎng)因子*/ size_t elemSize; /* 元素大小 ,總是1 */ size_t minElem; /*/ size_t maxElem; /* 每個(gè)塊最大允許分配的元素個(gè)數(shù) ,每個(gè)塊最大允許分配的字節(jié)數(shù) */ size_t curElem; /* 當(dāng)前塊元素個(gè)數(shù) ,當(dāng)前塊字節(jié)個(gè)數(shù) */ size_t totUsed; /* 已使用的元素總個(gè)數(shù)

10、,以使用的字節(jié)總個(gè)數(shù) */ size_t totAlloc; /* 分配的元素總數(shù) ,分配的字節(jié)總數(shù) */ BlockP heap; /* 指向當(dāng)前塊的指針 ,指向當(dāng)前塊的指針 */ Boolean protectStk; /* 僅適用于MSTAK */MemHeap;2. 堆數(shù)據(jù)結(jié)構(gòu)框圖 M-Heaps內(nèi)存堆結(jié)構(gòu)示意圖同一個(gè)M-Heaps內(nèi)存堆中分配的元素大小都是一樣的。堆結(jié)構(gòu)中的塊指針成員變量heap指向數(shù)據(jù)塊鏈的頭。數(shù)據(jù)塊鏈中的每個(gè)塊分配的內(nèi)存區(qū)大小由字節(jié)計(jì)算得到。每個(gè)塊中的BYTE型指針成員變量used指向記錄元素使用狀態(tài)的表數(shù)據(jù)結(jié)構(gòu),表中第i位記錄數(shù)據(jù)區(qū)中第i個(gè)元素的使用狀態(tài)：1表示

11、使用中、0表示空閑。每個(gè)塊中的firstFree成員變量的值表示數(shù)據(jù)區(qū)中第一個(gè)空閑元素的標(biāo)號(hào)。每個(gè)塊中的numFree成員變量的值記錄所在塊中空閑元素的個(gè)數(shù)。如果numFree為0表示塊滿,這時(shí)firstFree=numElem。 M-Stack內(nèi)存堆結(jié)構(gòu)示意圖三、算法1.接口描述1.定義：Export-void InitMem說明：初始化全局MSTAK堆變量gstack和全局CHEAP堆變量gcheap。該函數(shù)必須在調(diào)用任何其它堆操作函數(shù)前調(diào)用。參數(shù)：無(wú)返回值：無(wú)2.定義：Export-void CreateHeap說明：創(chuàng)建一個(gè)名稱為name、類型為type的內(nèi)存堆,elemSize指定內(nèi)

12、存堆中元素的大小,numElem指定塊中元素默認(rèn)個(gè)數(shù)。如果,內(nèi)存堆的類型是MSTAK或CHEAP,則elemSize必須為1。參數(shù)： x：指向給定的內(nèi)存堆 In,Out name：堆的名稱 In type：堆類型 In elemSize：對(duì)于MHEAP表示堆的每個(gè)塊中元素的大小,對(duì)于MSTAK和CHEAP,elemSize必須設(shè)為1 In growf： numElem：堆的每個(gè)塊默認(rèn)分配的元素個(gè)數(shù) In maxElem：堆的每個(gè)塊最大允許分配的元素個(gè)數(shù) In返回值：無(wú)3.定義：Export-void ResetHeap說明：釋放內(nèi)存堆x中所有元素,對(duì)CHEAP內(nèi)存堆無(wú)效。參數(shù)： x：指向給定的

13、內(nèi)存堆 In,Out返回值：無(wú)4.定義：Export-void DeleteHeap說明：釋放內(nèi)存堆x中所有元素,并刪除內(nèi)存堆x。參數(shù)： x：指向給定的內(nèi)存堆 In,Out返回值：無(wú)5.定義：Export-Ptr New說明：從內(nèi)存堆x中分配一大小為size的新元素并返回其指針。如果x類型為MHEAP則忽略參數(shù)size。如果分配失敗,程序?qū)?huì)異常退出,所以返回值永遠(yuǎn)不會(huì)為NULL。參數(shù)： x：指向給定的內(nèi)存堆 In,Out size：指定分配的元素大小 In返回值：返回指向新分配的元素的指針6.定義：void BlockRecorder說明：對(duì)于MHEAP堆,從塊p向后搜索有n個(gè)以上包括n個(gè)元

14、素的塊,并將其移至塊鏈表頭。對(duì)于MSTAK堆,從塊p向后搜索有n個(gè)以上包括n個(gè)字節(jié)數(shù)的塊,并將其移至塊鏈表頭。參數(shù)： p 指向給定的塊 In,Out n 對(duì)于MHEAP,表示元素個(gè)數(shù)；對(duì)于MSTAK,表示字節(jié)數(shù)。 In返回值：無(wú)7.定義：void* GetElem說明：如果type為MHEAP則從塊p中返回一空閑元素指針,并將其在使用狀態(tài)表中的對(duì)應(yīng)項(xiàng)置1。如果type為MSTAK則從塊p中返回一大小為elemSize字節(jié)數(shù)的區(qū)域指針,并對(duì)塊p中firstFree和numFree變量進(jìn)行相應(yīng)的修改。參數(shù)： p：指向給定的塊 In elemSize：元素大小 In type：所屬堆的類型 In返回

15、值：如果成功,則返回大小為elemSize字節(jié)數(shù)的數(shù)據(jù)區(qū),否則返回NULL。8.定義：BlockP AllocBlock說明：分配一個(gè)數(shù)據(jù)區(qū)大小為size*num字節(jié)數(shù)的塊,在進(jìn)行必要的初始化后,返回該塊的指針。參數(shù)： size：元素大小 In num：元素個(gè)數(shù) In type：所屬堆的類型 In返回值：如果分配成功,則返回塊指針,否則程序異常退出。9.定義：size_t Mround說明：返回大小=size并且整除FWORD8的值。參數(shù)： size 輸入大小 In返回值：返回計(jì)算的大小10.定義：Export-Ptr CNew說明：從內(nèi)存堆x中分配一大小為size的新元素清0后返回其指針。如

16、果x類型為MHEAP則忽略參數(shù)size。如果分配失敗,程序?qū)?huì)異常退出,所以返回值永遠(yuǎn)不會(huì)為NULL。參數(shù)： x：指向給定的內(nèi)存堆 In,Out size：指定分配的元素大小 In返回值：返回指向新分配的元素的指針11.定義：Export-void Dispose說明：從內(nèi)存堆x中釋放元素p參數(shù)： x 指向給定的內(nèi)存堆 In,Out p 元素指針 In返回值：無(wú)2.接口實(shí)現(xiàn)1. 內(nèi)存堆創(chuàng)建算法CreateHeapvoid CreateHeap / 一致性檢查 if growf /growf必須大于等于0 HError; if maxElem /默認(rèn)的元素個(gè)數(shù)不能大于最大允許的元素個(gè)數(shù) HErr

17、or max elem in heap %s,name; if elemSize /元素大小必須大于0 HError; if /MSTAK的elemSize必須為1 HError; x-name = mallocstrlen+1; /為內(nèi)存堆名稱分配內(nèi)存 strcpyname, name; x-type = type; x-growf = growf; x-elemSize = elemSize; x-maxElem = maxElem; x-curElem = x-minElem = numElem; x-totUsed = x-totAlloc = 0; x-heap = NULL; x-

18、protectStk = ? FALSE : protectStaks; RecordHeap; /記錄內(nèi)存堆x if switch case MHEAP: c=M; break; case MSTAK: c=S; break; case CHEAP: c=C; break; printf; 1.內(nèi)存堆的Trace為了跟蹤內(nèi)存堆的使用情況,HTK使用一個(gè)叫MemHeapRec的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄創(chuàng)建的內(nèi)存堆。MemHeapRec的數(shù)據(jù)結(jié)構(gòu)如下所示：typedef struct _MemHeapRec MemHeap *heap; / 指向內(nèi)存堆的指針 struct _MemHeapRec *nex

19、t; / 指向下一個(gè)MemHeapRec MemHeapRec;static MemHeapRec *heapList = NULL; /全局變量, MemHeapRec鏈表 MemHeapRec主要通過RecordHeap和UnRecordHeap兩個(gè)函數(shù)來(lái)完成內(nèi)存堆的記錄和擦除操作。算法描述如下：static void RecordHeap/將內(nèi)存堆x加入到heapList鏈表中 MemHeapRec *p; if p = mallocsizeof = NULL HError; p-heap = x; /將p插入到heapList鏈表頭前 p-next = heapList; heapLi

20、st = p;static void UnRecordHeap/從heapList中擦除內(nèi)存堆x記錄 MemHeapRec *p, *q; p = heapList; q = NULL; / 從heapList鏈頭向后尋找內(nèi)存堆x while heap != x q = p; p = p-next; if HErrorname; /沒有找到 /將p從heapList中摘除 if heapList = p-next; else q-next = p-next; free; /釋放p2. 內(nèi)存堆重置算法ResetHeap將p從heapList中摘除void ResetHeap BlockP cur

21、,next;switchtype case MHEAP:if printfname;cur = x-heap; /cur指向塊鏈表頭/刪除所有的塊 while next = cur-next; freedata; /釋放cur塊數(shù)據(jù)區(qū)內(nèi)存 freeused; /釋放cur塊元素使用狀態(tài)表內(nèi)存 free; /釋放cur塊 cur = next; /cur指向下一個(gè)塊 x-curElem = x-minElem; x-totAlloc = 0; x-heap = NULL; break; case MSTAK: if printfname;cur=x-heap; /cur指向塊鏈表頭 if / 刪

22、掉除第一個(gè)塊以外的所有塊 while next != NULL next = cur-next; x-totAlloc = x-totAlloc-cur-numElem; freedata; free; cur = next; x-heap = cur; x-curElem = x-minElem; if cur-numFree = cur-numElem; cur-firstFree = 0; break; case CHEAP: HError; x-totUsed = 0;3. 內(nèi)存堆刪除算法DeleteHeapvoid DeleteHeap/刪除指定的內(nèi)存堆x if type = CHE

23、AP HErrorname; ResetHeap; /釋放所有的數(shù)據(jù)塊 if heap != NULL freeheap-data; freeheap; if printfname;UnRecordHeap; /擦除內(nèi)存堆x的Trace freename; /釋放分配的名稱內(nèi)存4. 從內(nèi)存堆分配空間的算法New、CNewstatic BlockP AllocBlock/分配塊 BlockP p; ByteP c; int i; if printf;if p = mallocsizeof = NULL /分配塊空間 HError; if data = malloc = NULL /分配塊的數(shù)據(jù)區(qū)

24、空間 HError; switch case MHEAP: if used = malloc/8 = NULL/分配使用狀態(tài)表空間 HError; /使用狀態(tài)表中所有項(xiàng)賦0 for used; i /8; i+,c+ *c = 0; break; case MSTAK: p-used = NULL; break; default: HError; p-numElem = p-numFree = num; p-firstFree = 0; p-next = NULL; return p;AllocBlock分配的MHEAP塊示意圖/BlockReorder: 從塊p向后尋找=n個(gè)空閑元素的塊,并

25、將其移至塊鏈表頭static void BlockReorder BlockP head, cur, prev; if return; head = cur = *p; prev = NULL; while if numFree = n /找到,那么就將其移至塊鏈表頭 if prev-next = cur-next; cur-next = head; *p = cur; return; prev = cur; cur = cur-next; /GetElem: 從塊中分配新元素static void *GetElem int i,index; if return NULL; switch ca

26、se MHEAP: if numFree = 0 return NULL; index = p-firstFree; /第一個(gè)空閑元素索引號(hào) p-usedp-firstFree/8 |= 1firstFree&7; /使用狀態(tài)表中對(duì)應(yīng)位置1 p-numFree-;/在使用狀態(tài)表中尋找下一個(gè)空閑塊 if numFree 0 for firstFree+1; inumElem;i+ if usedi/8 & 1 = 0 p-firstFree = i; break; else p-firstFree = p-numElem; /firstFree=最大元素索引號(hào)+1 return p-data+i

27、ndex*elemSize; /返回分配的數(shù)據(jù)區(qū)指針 case MSTAK:/從棧頂取elemSize字節(jié)數(shù)的區(qū)域 if numFree return NULL; index = p-firstFree; p-firstFree += elemSize; p-numFree = p-numFree - elemSize; return p-data + index; /返回分配的數(shù)據(jù)區(qū)指針 default: HError; return NULL;#define FWORD 8 / size of a full word = 基本的分配量size_t MRound return = 0 ? s

28、ize : * FWORD;void *New/返回從內(nèi)存堆x分配大小為size的新元素指針 void *q; BlockP newp; size_t num,bytes,*ip,chdr; Boolean noSpace; Ptr *pp; /一致性檢查 if elemSize HError5174, New: heap %s not initialised, name=NULL ? Unnamed : x-name; switchtype case MHEAP: /如果能從現(xiàn)有的塊中找到空閑元素,則返回其指針。否則,就分配一個(gè)數(shù)據(jù)/區(qū)大小由curElem,growf以及maxElem決定的

29、新塊。 if elemSize /檢查size的合法性 HErrorname , x-elemSize; noSpace = x-totUsed = x-totAlloc; /如果totUsed=totAlloc則沒有空閑元素 if noSpace | q = GetElemheap , x-elemSize , x-type = NULL if BlockReorder&heap, 1; /x-heap沒有空閑元素,則向后尋找 if noSpace | q = GetElemheap, x-elemSize, x-type = NULL num = x-curElem * growf + 1

30、.0 + 0.5; if x-maxElem num = x-maxElem; newp = AllocBlockelemSize, num, x-type; /分配新塊 x-totAlloc += num; x-curElem = num; /將新分配的塊置于塊鏈表頭 newp-next = x-heap; x-heap = newp; if q=GetElemheap, x-elemSize, x-type = NULL HErrorname; x-totUsed+; if printfname, size, q; return q; case CHEAP: chdr = MRoundsi

31、zeof; /多分配chdr個(gè)字節(jié) q = malloc; /直接使用malloc分配 if HError; x-totUsed += size; x-totAlloc += size+chdr;/在起始部分中記錄分配的空間大小 ip = q;*ip = size; if printfname, chdr, size, q; return q+chdr; case MSTAK:if protectStk size += sizeof; size = MRound; /size必須是8的整數(shù)倍 if q = GetElemheap, size, x-type = NULL /空間不夠,加入一個(gè)新

32、塊 bytes = x-curElem * growf + 1.0 + 0.5; if x-maxElem bytes = x-maxElem; x-curElem = bytes; if bytes bytes = size; bytes = MRound; newp = AllocBlocktype; x-totAlloc += bytes; /新分配的塊置于塊鏈表頭 newp-next = x-heap; x-heap = newp; if q=GetElemheap, size, x-type = NULL HErrorname; x-totUsed += size; if print

33、fname, size, q; if protectStk pp = q + size - sizeof; *pp = q; return q; return NULL;C-Heaps內(nèi)存分配示意圖/返回從內(nèi)存堆x分配大小為size的新元素指針,新分配的空間已清0Ptr CNew void *ptr; ptr = New ; if type = MHEAP & size =0 size = x-elemSize; memset ; return ptr;5. 從內(nèi)存堆刪除空間的算法Disposevoid Dispose/從內(nèi)存堆x中釋放p BlockP head , cur , prev; B

34、oolean found = FALSE; ByteP bp; size_t size,chdr; size_t num,index, *ip; Ptr *pp; if totUsed = 0 HErrorname; switchtype case MHEAP: /*從塊鏈表頭向后搜索塊,如果data=p=data+*elemSize,表示p指向的空間是由這個(gè)塊的分配的,則計(jì)算索引號(hào),使用狀態(tài)表中相應(yīng)位置0。*/ head = x-heap; cur=head; prev=NULL; size = x-elemSize; while num = cur-numElem; found = cur

35、-data = p & cur-data+*size = p; if prev=cur; cur=cur-next; if HErrorname; index = p-cur-data/size; /計(jì)算索引號(hào) cur-usedindex/8 &= 1 ; if index firstFree cur-firstFree = index; cur-numFree+; x-totUsed-; if numFree = cur-numElem /釋放整個(gè)塊 if prev-next = cur-next; else head = cur-next; x-heap = head; x-totAllo

36、c -= cur-numElem; freedata; freeused; free; if printfname, size, p;return; case MSTAK: / 與MHEAP同樣的方法先確定p所在的塊 cur = x-heap; if protectStk if firstFree 0 / s-top in current block pp = cur-data+cur-firstFree-sizeof; else / s-top in previous block if next = NULL HError; pp = cur-next-data+cur-next-first

37、Free-sizeof; if HErrorname, *pp, p; / if protectStk while / check current block num = cur-numElem; found = cur-data = p & cur-data+num p; if / p不在當(dāng)前塊中,所以刪除該塊 x-heap = cur-next; x-totAlloc -= cur-numElem; x-totUsed -= cur-firstFree; freedata; free; cur = x-heap; if printfname; if HErrorname; size = c

38、ur-data + cur-firstFree - p; /分配數(shù)據(jù)區(qū)的實(shí)際大小 if size HErrorname; cur-firstFree -= size; cur-numFree += size; x-totUsed -= size; if printfname, size, p;return; case CHEAP: chdr = MRoundsizeof; bp = p-chdr; ip = bp; x-totAlloc -= ; x-totUsed -= *ip; free; if printfname, chdr, *ip, bp; return; HTK之基于分段k-me

39、ans的HMM參數(shù)估計(jì)公式1.問題描述如何用一組觀察序列去訓(xùn)練一個(gè)HMM模型比如：一個(gè)單音素模型。一種方法是：1.先對(duì)所有觀察序列均分分段段的數(shù)目與HMM模型輸出狀態(tài)數(shù)相同,然后估算各段觀察的中心和方差,并將此作為HMM模型的均值向量和協(xié)方差矩陣的初始值。2.用Viterbi算法對(duì)所有觀察序列分段Viterbi分段3.利用Viterbi分段的結(jié)果來(lái)估計(jì)其模型參數(shù)具體計(jì)算公式稍后給出4.如果收斂稍后會(huì)說明則輸出HMM參數(shù),否則轉(zhuǎn)22. Viterbi算法Viterbi算法是經(jīng)典的Viterbi算法,不過值得注意的是HTK中的HMM模型的開始和結(jié)束狀態(tài)為非輸出狀態(tài)non-emitting stat

40、e。一個(gè)5狀態(tài)的HMM模型所以HTK中Viterbi算法公式與經(jīng)典算法中的公式稍微有些不一樣。在下面公式中,為時(shí)刻t沿一條路徑,且輸出的最大概率,即。用于狀態(tài)回溯。a.初始化,b.遞歸,c. 終結(jié)d. 狀態(tài)序列求取回溯,總似然值通過如下公式計(jì)算：我們記第i次迭代得到的總似然值為,如果相繼總似然值之差的絕對(duì)值小于設(shè)定的域值,即,那么表示參數(shù)訓(xùn)練已收斂。3. HMM模型參數(shù)的更新公式這里不去證明下面將要列出的HMM模型參數(shù)更新公式,詳細(xì)的證明可以參考L. R. RABINER在1990發(fā)表的文章The Segmental K-Means Algorithm for Estimating Param

41、eters of Hidden Markov Models。設(shè)代表對(duì)觀察序列集進(jìn)行Viterbi分段后從狀態(tài)i到狀態(tài)j總的出現(xiàn)次數(shù)。轉(zhuǎn)移矩陣的估計(jì)公式如下所示：設(shè)表示的歸屬,當(dāng)=1表示屬于數(shù)據(jù)流s在狀態(tài)j的第m個(gè)輸出分量的觀察,否則為0。狀態(tài)j的參數(shù)估計(jì)公式如下所示：4. HInit模塊HInit模塊實(shí)現(xiàn)了分段k-means的HMM模型參數(shù)訓(xùn)練算法。程序流程大致如下：值得注意的是,參數(shù)估計(jì)的計(jì)算需要對(duì)觀察序列進(jìn)行循環(huán)累加計(jì)算見參數(shù)估計(jì)公式,這個(gè)計(jì)算主要依靠一個(gè)被稱為累加器的數(shù)據(jù)結(jié)構(gòu)完成的。具體的說,HLink中的均值向量、轉(zhuǎn)移矩陣、協(xié)方差矩陣、混合成份的權(quán)重的Hook關(guān)于Hook見HTK中的向

42、量、矩陣的表示中的關(guān)于共享向量矩陣的說明分別指向MuAcc、TrAcc、VaAcc和WtAcc數(shù)據(jù)結(jié)構(gòu)。HTK之基于單個(gè)HMM模型參數(shù)估計(jì)Baum-Welch算法1. 問題描述如何用一組觀察序列,去訓(xùn)練一個(gè)HMM模型比如：一個(gè)單音素模型。一種方法是：1.初始化HMM模型參數(shù)2.利用前后向算法計(jì)算所有觀察序列的,3.利用2的結(jié)果以及Baum-Welch算法來(lái)重新估計(jì)HMM模型參數(shù)4.如果收斂稍候會(huì)說明,就輸出估計(jì)的HMM模型參數(shù),否則轉(zhuǎn)22. 前后向算法Forward/Backward Algorithm前后向算法是經(jīng)典的前后向算法,不過值得注意的是HTK中的HMM模型的開始和結(jié)束狀態(tài)為非輸出狀

43、態(tài)non-emitting state且,一個(gè)從左向右的5狀態(tài)HMM模型所以HTK中前后向算法公式與經(jīng)典算法中的公式稍微有些不一樣。下面給出計(jì)算概率的前后向算法前向概率的公式,a.初始條件,b. 遞歸計(jì)算,c. 終結(jié)后向概率的公式,即：a. 初始條件,b. 遞歸計(jì)算,c. 終結(jié)總似然值通過如下公式計(jì)算：我們記第i次迭代得到的總似然值為,如果相繼總似然值之差的絕對(duì)值小于設(shè)定的域值,即,那么表示參數(shù)訓(xùn)練已收斂。3. 單HMM模型參數(shù)估計(jì)的Baum-Welch算法這里不去詳細(xì)追究估計(jì)算法的來(lái)源與證明,而是直接給出公式,只在必要的時(shí)候討論一下公式的含義。用一組觀察序列,去訓(xùn)練一個(gè)連續(xù)混合高斯分布的HM

44、M模型參數(shù)。先定義一些下面公式中將要用到的符號(hào)：狀態(tài)數(shù)目數(shù)據(jù)流的數(shù)目數(shù)據(jù)流中混合成份的數(shù)目觀察序列的幀數(shù)嵌入式訓(xùn)練中拼接模型的數(shù)目拼接模型中第個(gè)模型的狀態(tài)數(shù)目觀察序列集時(shí)刻的觀察時(shí)刻的數(shù)據(jù)流的觀察,從狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率狀態(tài)j的數(shù)據(jù)流s的第m個(gè)混合分量的輸出概率的均值向量狀態(tài)j的數(shù)據(jù)流s的第m個(gè)混合分量的權(quán)重狀態(tài)j的數(shù)據(jù)流s的第m個(gè)混合分量的輸出概率的協(xié)方差矩陣 HMM模型參數(shù)集先給出轉(zhuǎn)移概率矩陣的重估公式,假設(shè)這里的HMM模型輸出的觀察共有S條數(shù)據(jù)流,記狀態(tài)j的第s條數(shù)據(jù)流的混合成份的數(shù)目為。這里的默認(rèn)為1.0,現(xiàn)在的HTK不能估計(jì)這個(gè)參數(shù)設(shè)第r個(gè)觀察序列在t時(shí)刻處在狀態(tài)j的第s個(gè)數(shù)據(jù)流

45、的第m個(gè)混合成份中的占有概率為其中：對(duì)于單混合成份的HMM下面給HMM模型參數(shù)的均值向量、協(xié)方差矩陣以及混合權(quán)重的重估公式其中：4. HRest模塊HRest模塊實(shí)現(xiàn)了單個(gè)HMM模型參數(shù)訓(xùn)練的Baum-Welch算法。程序流程大致如下：值得注意的是,參數(shù)估計(jì)的計(jì)算需要對(duì)觀察序列進(jìn)行循環(huán)累加計(jì)算見參數(shù)估計(jì)公式,這個(gè)計(jì)算主要依靠一個(gè)被稱為累加器的數(shù)據(jù)結(jié)構(gòu)完成的。具體的說,HLink中的均值向量、轉(zhuǎn)移矩陣、協(xié)方差矩陣、混合成份的權(quán)重的Hook關(guān)于Hook見HTK中的向量、矩陣的表示中的關(guān)于共享向量矩陣的說明分別指向MuAcc、TrAcc、VaAcc和WtAcc數(shù)據(jù)結(jié)構(gòu)。Baum-Welch參數(shù)估計(jì)算

46、法都可以歸結(jié)為如下的形式：比如：累加器的數(shù)據(jù)結(jié)構(gòu)中都有一個(gè)occ的成員變量,它記錄的就是累加的總占有數(shù)。為了方便大家讀HRest源程序,這里給出程序中一些變量和計(jì)算公式的對(duì)應(yīng)關(guān)系：outprobjt - alphajt - betajt - stropttjs - mixoutpitsm - HTK之嵌入式HMM模型參數(shù)估計(jì)Baum-Welch算法1. 問題描述在單HMM模型參數(shù)估計(jì)的Baum-Welch算法中,使用硬邊界,即使用模型對(duì)應(yīng)音段的開始和結(jié)束時(shí)間。這里的嵌入式HMM模型參數(shù)估計(jì)Baum-Welch算法,忽略觀察序列對(duì)應(yīng)的模型之間的邊界,即使用所謂的軟邊界。訓(xùn)練時(shí),將對(duì)應(yīng)的模型假設(shè)有

47、個(gè),按時(shí)間先后順序拼接起來(lái)構(gòu)成一個(gè)復(fù)合模型,模型與模型之間的轉(zhuǎn)移概率為1.0。對(duì)這個(gè)復(fù)合模型整體使用Baum-Welch算法來(lái)達(dá)到重估個(gè)子模型參數(shù)的目的。雖然這里使用的Baum-Welch算法還是經(jīng)典的算法,但由于使用了復(fù)合模型,其形式和經(jīng)典的相差甚遠(yuǎn)。采用這樣的訓(xùn)練方式,其好處主要有兩個(gè)。第一,語(yǔ)音信號(hào)的音素切分問題本身就是個(gè)不平凡的問題,至今還沒有一個(gè)準(zhǔn)確標(biāo)準(zhǔn)也不好定的音素自動(dòng)切分程序,使用嵌入式訓(xùn)練恰好避開了這個(gè)麻煩,模型在訓(xùn)練過程中自身會(huì)收斂到一個(gè)合適的邊界。第二,只要給定一個(gè)合適的模型初始值,使用軟邊界訓(xùn)練,得到的模型參數(shù)將會(huì)更為精確和一致。事實(shí)上,利用嵌入式訓(xùn)練收斂的HMM參數(shù),可

48、以反過來(lái)完成音段的自動(dòng)切分。這就避免了雞生蛋、蛋生雞的困擾。2. 前后向算法本節(jié)描述在嵌入式訓(xùn)練中前后向概率計(jì)算的公式,注意HTK中模型的特殊性,即開始和結(jié)束狀態(tài)為非輸出狀態(tài)。并且,注意：1. 拼接模型的第一個(gè)和最后一個(gè)模型不能是Tee模型Tee模型是指存在從開始狀態(tài)到結(jié)束狀態(tài)的轉(zhuǎn)移概率的HMM模型,即：2. 拼接模型中不能出現(xiàn)相繼的Tee模型。前向概率上指標(biāo)為拼接模型中的模型標(biāo)號(hào),下同,a. 初始條件,即：b. 遞歸計(jì)算,推導(dǎo),如下又,所以：,c. 終結(jié)總的似然值：后向概率,a. 初始條件,即：b. 遞歸計(jì)算,推導(dǎo)如下：而,所以：,推導(dǎo)公式如下：其中,c. 終結(jié)總的似然值：3. 嵌入式HMM

49、模型參數(shù)估計(jì)的Baum-Welch算法這里不去詳細(xì)追究估計(jì)算法的來(lái)源與證明,而是直接給出公式,只在必要的時(shí)候討論一下公式的含義。用一組觀察序列,去訓(xùn)練連續(xù)混合高斯分布的HMM模型參數(shù)集。先給出輸出狀態(tài)間的轉(zhuǎn)移概率矩陣的重估公式,從非輸出初始狀態(tài)到輸出狀態(tài)的轉(zhuǎn)移概率矩陣的重估公式,從輸出狀態(tài)到非輸出結(jié)束狀態(tài)的轉(zhuǎn)移概率矩陣的重估公式,最后給出從非輸出初始狀態(tài)到非輸出結(jié)束狀態(tài)的轉(zhuǎn)移概率矩陣的重估公式輸出概率分布的重估公式與單HMM模型的重估公式類似見HTK之基于單個(gè)HMM模型參數(shù)估計(jì)Baum-Welch算法,只需在公式中加上上標(biāo)以及作如下更改假設(shè)這里的HMM模型輸出的觀察共有S條數(shù)據(jù)流,記模型中的狀

50、態(tài)j的第s條數(shù)據(jù)流的混合成份的數(shù)目為。這里的默認(rèn)為1.0,現(xiàn)在的HTK不能估計(jì)這個(gè)參數(shù)設(shè)第r個(gè)觀察序列在t時(shí)刻處在模型中的狀態(tài)j的第s個(gè)數(shù)據(jù)流的第m個(gè)混合成份中的占有概率為對(duì)于單混合成份的HMM下面給HMM模型參數(shù)的均值向量、協(xié)方差矩陣以及混合權(quán)重的重估公式其中：4. HEREST模塊HEREST完成嵌入式HMM模型參數(shù)的計(jì)算。嵌入式HMM主要用于連續(xù)語(yǔ)音子詞模型的訓(xùn)練,訓(xùn)練時(shí)先載入觀察序列和對(duì)應(yīng)的標(biāo)注文件,然后計(jì)算其前后向概率并更新其累加器,當(dāng)對(duì)所有的觀察序列循環(huán)一次后,就通過使用Baum-Welch算法更新HMM集中所有模型的參數(shù)。數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ),弄清HEREST模塊中為完成嵌入式訓(xùn)

51、練算法而專門設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu),對(duì)于理清HEREST在代碼層次上工作細(xì)節(jié)是有幫助的。前后向概率計(jì)算主要是通過FBInfo數(shù)據(jù)結(jié)構(gòu)協(xié)助完成的。顧名思義,FBInfo便是Forward Backward Information的縮寫,記錄計(jì)算前后向概率時(shí)所需的相關(guān)信息。靜態(tài)的說明FBInfo數(shù)據(jù)結(jié)構(gòu)中成員變量的含義并不能很好的說明其在程序中的作用,所以本節(jié)預(yù)備在介紹算法的同時(shí)穿插介紹相關(guān)的數(shù)據(jù)結(jié)構(gòu)。先給出HEREST模塊的程序流程圖HEREST模塊的程序流程圖1. 裝入標(biāo)注信息LoadLabs關(guān)鍵代碼：utt-tr = LOpentransStack, labfn, lff;utt-Q = CountL

52、abstr-head;說明：utt-tr為指向標(biāo)注文件信息的指針,labfn為與觀察序列對(duì)應(yīng)的標(biāo)注文件名稱字符串。事實(shí)上,標(biāo)注信息以鏈表的形式存儲(chǔ),utt-tr-head指向鏈表頭。utt-Q為拼接模型的個(gè)數(shù)。2. 裝入觀察序列LoadData關(guān)鍵代碼：utt-pbuf = OpenBufferdataStack, datafn, . . .;utt-T = ObsInBufferpbuf;說明：一次性將datafn參數(shù)文件中所有的觀察序列裝入到utt-pbuf中。實(shí)際上觀察序列以表格的形式存儲(chǔ)在utt-pbuf-main數(shù)據(jù)塊中,utt-pbuf-nRows記錄讀入的觀察序列的幀數(shù)。utt-

53、T為觀察序列的幀數(shù)。嵌入式前后向算法FBFile這里首先要討論的算法就是：如何從轉(zhuǎn)移概率矩陣中得到模型的最小時(shí)長(zhǎng)以幀為單位關(guān)鍵代碼：SetMinDurs;要說明的是HTK中提出的獲取最小時(shí)長(zhǎng)的方法并不是最為簡(jiǎn)便的。除了計(jì)算最小時(shí)長(zhǎng),算法還附帶的檢測(cè)了模型中是否存在無(wú)法到達(dá)結(jié)束狀態(tài)的狀態(tài),如果有便給出警告。FindStateOrder構(gòu)建了一個(gè)以結(jié)束狀態(tài)為根節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移路徑樹。從葉節(jié)點(diǎn)到根節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)便是一條可能的到達(dá)結(jié)束狀態(tài)的路徑。上圖中,節(jié)點(diǎn)內(nèi)數(shù)字為狀態(tài)標(biāo)號(hào),邊上數(shù)字為狀態(tài)計(jì)數(shù)值。狀態(tài)計(jì)數(shù)值的初始值為-1,調(diào)用FindStateOrder后,如果某個(gè)狀態(tài)的計(jì)數(shù)值還為-1則表明該狀態(tài)無(wú)法

54、到達(dá)結(jié)束狀態(tài)。計(jì)算最小時(shí)長(zhǎng)時(shí)會(huì)使用狀態(tài)計(jì)數(shù)值。最小時(shí)長(zhǎng)的計(jì)算有些類似于Vertibi算法,假設(shè)從開始狀態(tài)到第i個(gè)狀態(tài)的最小時(shí)長(zhǎng)用表示。狀態(tài)計(jì)數(shù)值為的對(duì)應(yīng)狀態(tài)號(hào)用表示。a. 初始條件b. 遞歸計(jì)算for if else 接下來(lái),要討論的算法是：關(guān)于錐形Taper的前后向概率計(jì)算錐形表示計(jì)算時(shí)可能的模型路徑,通過使用錐形,可以大大提高前后向概率計(jì)算的速度。必須指出的是,錐形的使用并沒有降低數(shù)值計(jì)算的精度,這和剪枝是有區(qū)別的。涉及的數(shù)據(jù)結(jié)構(gòu)：后向錐ab-pInfo-qLo1,.,T和前向錐ab-pInfo-qHi1,.,T隨時(shí)間變化的錐形陰影部分包括橫線記為第i個(gè)模型的最小時(shí)長(zhǎng)值前向錐的計(jì)算公式當(dāng)時(shí)

55、ab-pInfo-qHit = q當(dāng)時(shí)ab-pInfo-qHit = Q后向錐的計(jì)算公式當(dāng)時(shí)ab-pInfo-qLot = q當(dāng)時(shí)ab-pInfo-qLot = 1時(shí)刻需要計(jì)算的前后向概率的模型范圍：HTK中由SetBeamTaper函數(shù)完成前后向錐的計(jì)算。關(guān)于對(duì)數(shù)尺度上的計(jì)算問題由于計(jì)算中所涉及的概率值都是小于1的,并且大多數(shù)計(jì)算又涉及到乘法,這樣經(jīng)過多次迭代計(jì)算,很容易出現(xiàn)數(shù)值下溢的問題。為了避免這種現(xiàn)象的出現(xiàn),HTK中使用對(duì)數(shù)尺度,也就是說,所有概率值一律先取其對(duì)數(shù),然后進(jìn)行計(jì)算,這樣乘法、除法就變成對(duì)數(shù)尺度上的加法和減法,而加法和減法則轉(zhuǎn)化為對(duì)數(shù)尺度上的遞歸計(jì)算在HTK中是由LAdd函

56、數(shù)完成的。下面給出對(duì)數(shù)尺度上的計(jì)算公式1 假設(shè),計(jì)算即： 2假設(shè),計(jì)算因?yàn)?所以,迭代計(jì)算a. b. ,c. FBFile是前后向算法的核心,下面給出其程序流圖1. 初始化AlphaBeta數(shù)據(jù)結(jié)構(gòu)CreateInstsab用于記錄前后向概率計(jì)算所需的信息。ab-al_qList1,.,Q：當(dāng)前拼接模型參數(shù)信息數(shù)組ab-qIds 1,.,Q：當(dāng)前拼接模型的名稱數(shù)組ab-qDms1,.,Q：當(dāng)前拼接模型最小時(shí)長(zhǎng)數(shù)組2. 設(shè)置前后向錐SetBeamTaper詳細(xì)信息見前面關(guān)于錐形Taper的前后向概率計(jì)算的說明。錐信息記錄在剪枝信息數(shù)據(jù)結(jié)構(gòu)中。p-qHi記錄前向錐的信息,p-qLo記錄后向錐的信息

57、。3. 計(jì)算后向概率SetBeta為了能夠?qū)栴}說明清楚,尤其是后向概率計(jì)算公式如何在代碼層次上實(shí)現(xiàn)的。筆者準(zhǔn)備給出一份注釋的關(guān)鍵代碼,這里的關(guān)鍵代碼是指與后向概率計(jì)算公式對(duì)應(yīng)的代碼段。下面先給出程序中一些變量和計(jì)算公式的對(duì)應(yīng)關(guān)系ab-betatqj - ab-otprob存儲(chǔ)輸出概率,Setotprob函數(shù)負(fù)責(zé)計(jì)算t時(shí)刻的輸出概率值并存放到ab-otprob中,不過其存儲(chǔ)的方式有些特殊,解釋如下：ab-otprobtqj0 - 設(shè)數(shù)據(jù)流總數(shù)為,并且ab-otprobtqjs - 下面是注釋的SetBeta代碼片斷,為了能夠突出重點(diǎn),舍棄了剪枝部分的代碼。static LogDouble Se

58、tBeta . . . . . . for =endq; q- hmm = ab-al_qListq; Nq = hmm-numStates; /第q個(gè)模型的狀態(tài)數(shù) /bqt 相當(dāng)于 bqt = betaTq = NewBetaVecabMem, Nq; /*相當(dāng)于完成如下計(jì)算： */ bqtNq = ?0.0 : betaTq+1lNq+a1N; /*相當(dāng)于完成如下計(jì)算：, */ for i=2;i bqti = hmm-transPiNq+bqtNq; outprob = ab-otprobTq; /outprob相當(dāng)于/*相當(dāng)于完成如下計(jì)算：*/ x = LZERO; for j=2;

59、j a = hmm-transP1j; y = bqtj; if LSMALL & y LSMALL x = LAdd; bqt1 = x; lNq = Nq; a1N = hmm-transP1Nq; . . . . . ./for =endq; q-for =1;t- . . . . . . /設(shè)置錐形startq = p-qHit+1; endq = qLot+1 = 1?1:qLot=p-qLot+1?p-qLot:p-qLot+1-1; while 1 & ab-qDmsendq-1=0 /Tee模型 endq-; . . . . . . for =endq; q- . . . .

60、. . hmm = ab-al_qListq; Nq = hmm-numStates; /第q個(gè)模型的狀態(tài)數(shù) /bqt相當(dāng)于 bqt = betatq = NewBetaVecabMem,Nq; bqt1 = betat+1q; /bqt1相當(dāng)于 bq1t1 = ?NULL:betat+1q+1; /bq1t1相當(dāng)于 outprob = ab-otprobt+1q; / outprob相當(dāng)于/*相當(dāng)于完成如下計(jì)算：*/ bqtNq = ?LZERO:bq1t11;/*相當(dāng)于完成如下計(jì)算：*/if qLSMALL bqtNq=LAdd;/*相當(dāng)于完成如下計(jì)算：,*/ for 1;i- x = h