1、.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時刻的前向變量forward variable,可以通過迭代的方法來計算各個時刻的前向變量：1 初始化I

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

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

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

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

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

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

8、STAK塊數據結構定義 */typedef struct _Block /* MHEAP ,MSTACK */ size_t numFree; /* 空閑元素數目 ,空閑字節數 */ size_t firstFree; /* 第一個空閑元素索引 ,棧頂索引 */ size_t numElem; /* 塊分配元素的個數 ,塊分配的字節數 */ ByteP used; /* 指向元素分配表指針,1bit/元素 ,不使用 */ Ptrdata; /* 指向數據區指針 ,指向數據區指針 */ BlockP next; /* 指向下一個塊指針 ,指向下一個塊指針 */Block;/* 堆數據結構定義 *

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

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

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

12、存堆中元素的大小,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-void ResetHeap說明：釋放內存堆x中所有元素,對CHEAP內存堆無效。參數： x：指向給定的

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

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

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

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

17、or max elem in heap %s,name; if elemSize /元素大小必須大于0 HError; if /MSTAK的elemSize必須為1 HError; x-name = mallocstrlen+1; /為內存堆名稱分配內存 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; /記錄內存堆x if switch case MHEAP: c=M; break; case MSTAK: c=S; break; case CHEAP: c=C; break; printf; 1.內存堆的Trace為了跟蹤內存堆的使用情況,HTK使用一個叫MemHeapRec的數據結構來記錄創建的內存堆。MemHeapRec的數據結構如下所示：typedef struct _MemHeapRec MemHeap *heap; / 指向內存堆的指針 struct _MemHeapRec *nex

19、t; / 指向下一個MemHeapRec MemHeapRec;static MemHeapRec *heapList = NULL; /全局變量, MemHeapRec鏈表 MemHeapRec主要通過RecordHeap和UnRecordHeap兩個函數來完成內存堆的記錄和擦除操作。算法描述如下：static void RecordHeap/將內存堆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中擦除內存堆x記錄 MemHeapRec *p, *q; p = heapList; q = NULL; / 從heapList鏈頭向后尋找內存堆x while heap != x q = p; p = p-next; if HErrorname; /沒有找到 /將p從heapList中摘除 if heapList = p-next; else q-next = p-next; free; /釋放p2. 內存堆重置算法ResetHeap將p從heapList中摘除void ResetHeap BlockP cur

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

22、掉除第一個塊以外的所有塊 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. 內存堆刪除算法DeleteHeapvoid DeleteHeap/刪除指定的內存堆x if type = CHE

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

24、空間 HError; switch case MHEAP: if used = malloc/8 = NULL/分配使用狀態表空間 HError; /使用狀態表中所有項賦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個空閑元素的塊,并

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; /第一個空閑元素索引號 p-usedp-firstFree/8 |= 1firstFree&7; /使用狀態表中對應位置1 p-numFree-;/在使用狀態表中尋找下一個空閑塊 if numFree 0 for firstFree+1; inumElem;i+ if usedi/8 & 1 = 0 p-firstFree = i; break; else p-firstFree = p-numElem; /firstFree=最大元素索引號+1 return p-data+i

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

28、ize : * FWORD;void *New/返回從內存堆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: /如果能從現有的塊中找到空閑元素,則返回其指針。否則,就分配一個數據/區大小由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個字節 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的整數倍 if q = GetElemheap, size, x-type = NULL /空間不夠,加入一個新

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內存分配示意圖/返回從內存堆x分配大小為size的新元素指針,新分配的空間已清0Ptr CNew void *ptr; ptr = New ; if type = MHEAP & size =0 size = x-elemSize; memset ; return ptr;5. 從內存堆刪除空間的算法Disposevoid Dispose/從內存堆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指向的空間是由這個塊的分配的,則計算索引號,使用狀態表中相應位置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; /計算索引號 cur-usedindex/8 &= 1 ; if index firstFree cur-firstFree = index; cur-numFree+; x-totUsed-; if numFree = cur-numElem /釋放整個塊 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不在當前塊中,所以刪除該塊 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; /分配數據區的實際大小 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參數估計公式1.問題描述如何用一組觀察序列去訓練一個HMM模型比如：一個單音素模型。一種方法是：1.先對所有觀察序列均分分段段的數目與HMM模型輸出狀態數相同,然后估算各段觀察的中心和方差,并將此作為HMM模型的均值向量和協方差矩陣的初始值。2.用Viterbi算法對所有觀察序列分段Viterbi分段3.利用Viterbi分段的結果來估計其模型參數具體計算公式稍后給出4.如果收斂稍后會說明則輸出HMM參數,否則轉22. Viterbi算法Viterbi算法是經典的Viterbi算法,不過值得注意的是HTK中的HMM模型的開始和結束狀態為非輸出狀態non-emitting stat

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

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

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

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

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

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

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

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

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

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

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

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

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

53、T為觀察序列的幀數。嵌入式前后向算法FBFile這里首先要討論的算法就是：如何從轉移概率矩陣中得到模型的最小時長以幀為單位關鍵代碼：SetMinDurs;要說明的是HTK中提出的獲取最小時長的方法并不是最為簡便的。除了計算最小時長,算法還附帶的檢測了模型中是否存在無法到達結束狀態的狀態,如果有便給出警告。FindStateOrder構建了一個以結束狀態為根節點的狀態轉移路徑樹。從葉節點到根節點所經過的節點便是一條可能的到達結束狀態的路徑。上圖中,節點內數字為狀態標號,邊上數字為狀態計數值。狀態計數值的初始值為-1,調用FindStateOrder后,如果某個狀態的計數值還為-1則表明該狀態無法

54、到達結束狀態。計算最小時長時會使用狀態計數值。最小時長的計算有些類似于Vertibi算法,假設從開始狀態到第i個狀態的最小時長用表示。狀態計數值為的對應狀態號用表示。a. 初始條件b. 遞歸計算for if else 接下來,要討論的算法是：關于錐形Taper的前后向概率計算錐形表示計算時可能的模型路徑,通過使用錐形,可以大大提高前后向概率計算的速度。必須指出的是,錐形的使用并沒有降低數值計算的精度,這和剪枝是有區別的。涉及的數據結構：后向錐ab-pInfo-qLo1,.,T和前向錐ab-pInfo-qHi1,.,T隨時間變化的錐形陰影部分包括橫線記為第i個模型的最小時長值前向錐的計算公式當時

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

56、數完成的。下面給出對數尺度上的計算公式1 假設,計算即： 2假設,計算因為,所以,迭代計算a. b. ,c. FBFile是前后向算法的核心,下面給出其程序流圖1. 初始化AlphaBeta數據結構CreateInstsab用于記錄前后向概率計算所需的信息。ab-al_qList1,.,Q：當前拼接模型參數信息數組ab-qIds 1,.,Q：當前拼接模型的名稱數組ab-qDms1,.,Q：當前拼接模型最小時長數組2. 設置前后向錐SetBeamTaper詳細信息見前面關于錐形Taper的前后向概率計算的說明。錐信息記錄在剪枝信息數據結構中。p-qHi記錄前向錐的信息,p-qLo記錄后向錐的信息

57、。3. 計算后向概率SetBeta為了能夠將問題說明清楚,尤其是后向概率計算公式如何在代碼層次上實現的。筆者準備給出一份注釋的關鍵代碼,這里的關鍵代碼是指與后向概率計算公式對應的代碼段。下面先給出程序中一些變量和計算公式的對應關系ab-betatqj - ab-otprob存儲輸出概率,Setotprob函數負責計算t時刻的輸出概率值并存放到ab-otprob中,不過其存儲的方式有些特殊,解釋如下：ab-otprobtqj0 - 設數據流總數為,并且ab-otprobtqjs - 下面是注釋的SetBeta代碼片斷,為了能夠突出重點,舍棄了剪枝部分的代碼。static LogDouble Se

58、tBeta . . . . . . for =endq; q- hmm = ab-al_qListq; Nq = hmm-numStates; /第q個模型的狀態數 /bqt 相當于 bqt = betaTq = NewBetaVecabMem, Nq; /*相當于完成如下計算： */ bqtNq = ?0.0 : betaTq+1lNq+a1N; /*相當于完成如下計算：, */ for i=2;i bqti = hmm-transPiNq+bqtNq; outprob = ab-otprobTq; /outprob相當于/*相當于完成如下計算：*/ 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- . . . . . . /設置錐形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個模型的狀態數 /bqt相當于 bqt = betatq = NewBetaVecabMem,Nq; bqt1 = betat+1q; /bqt1相當于 bq1t1 = ?NULL:betat+1q+1; /bq1t1相當于 outprob = ab-otprobt+1q; / outprob相當于/*相當于完成如下計算：*/ bqtNq = ?LZERO:bq1t11;/*相當于完成如下計算：*/if qLSMALL bqtNq=LAdd;/*相當于完成如下計算：,*/ for 1;i- x = h