基于加權有限狀態機的動態匹配詞圖生成算法

郭宇弘 黎 塔 肖業鳴 潘接林 顏永紅

?

基于加權有限狀態機的動態匹配詞圖生成算法

郭宇弘*黎 塔 肖業鳴 潘接林 顏永紅

(中國科學院語言聲學與內容理解重點實驗室 北京 100190)

由于現有的加權有限狀態機(WFST)解碼網絡沒有精確詞尾標記，導致當前已有的詞圖生成算法不含精確的詞尾時間點，或者僅是狀態、音素級別的詞圖，無法應用到關鍵詞檢索中。該文提出在WFST靜態解碼器下的語音識別詞圖生成算法。首先從理論上分析了WFST解碼音素圖和詞圖的可轉換關系，然后提出了字典的動態音素匹配方法解決了WFST網絡中詞尾時間點對齊的問題，最后通過令牌傳遞的遍歷方法生成了詞圖。同時，考慮到計算量優化，在令牌傳遞過程中引入了剪枝算法，使音素圖轉詞圖的耗時不到解碼耗時的3%。得到的詞圖，不僅可以用于語言模型重打分，由于含有精確的詞尾時間點，還可以直接應用到關鍵詞檢索系統中。實驗結果表明，該文的詞圖生成算法具有較高的計算效率；和已有動態解碼器的詞圖相比，詞圖中包含更多解碼信息，在大詞匯連續語音識別的重打分結果和關鍵詞檢索中都能取得更好的性能。

自動語音識別；加權有限狀態機；詞圖生成；關鍵詞檢索

1 引言

作為大詞表連續語音識別的核心模塊，語音識別解碼器負責利用上下文相關的聲學模型、字典和語言模型等知識源把語音信號轉換為文本。評價語音識別解碼器性能的一項關鍵指標就是識別器的準確率。在非常理想的情況下，語音識別應具有非常高的識別準確率，此時僅僅選用語音識別的解碼首選結果就可以使語音搜索、關鍵詞檢錯等應用的準確率非常高。然而，考慮到現實應用經常出現的信道不匹配、說話人不匹配或者說話人發音不標準的問題，導致大詞表連續語音識別(Large Vocabulary Continuous Speech Recognition, LVCSR)的首選結果在電話環境一類語音的識別錯誤率通常在40%左右。在這種較低準確率的情況下僅僅使用解碼的首選結果往往是不夠的。識別結果可以以多候選(N-Best)或者詞圖等形式輸出，這種多候選或者詞圖結果保留了識別中的更多識別信息，把它們交由后處理模塊能有效提高識別結果的準確性。常見的后處理技術包括：基于詞圖的重打分[1]、多遍解碼[2]、混淆網絡[3]等。

和多候選結果相比，詞圖形式包含了更多的信息，它不僅有多個識別詞序列結果，更包含了每個詞、音素的聲學得分、語言得分以及時間點等信息，并且它合并了多候選的冗余信息，其表示也更加高效[4]。因此，詞圖在語音識別后處理中得到非常廣泛的應用。例如：可以從詞圖里面直接抽取多候選結果；另外詞圖本身已經具有了圖的性質，在某些場合第1遍解碼用比較精細的模型會帶來計算量過高的問題，此時可以用簡單的模型在第1遍解碼時生成詞圖，再用精細的模型在詞圖上進行2遍解碼或者重打分則可獲得更好的效果；而在關鍵詞檢索的應用中，詞圖或者詞圖的混淆網絡形式可以作為檢索器的輸入。因此，詞圖成為了語音識別中第1遍解碼和后處理模塊之間的橋梁。

詞圖的生成過程是由解碼器搜索解碼網絡，記錄下搜索路徑從而轉化成相應的詞圖。解碼網絡是由各個知識源構成的一個搜索空間，一般來講可以分為動態構建的解碼網絡和靜態網絡。基于動態網絡的解碼器，以前綴樹的發音詞典作為搜索網絡，語言模型則通過動態查詢的方式把得分引入解碼過程之中，然后利用重入字典樹或者字典樹拷貝的方式對整個解碼網絡進行搜索[5]。動態網絡解碼器的優勢在于，由于字典和語言模型是分離的，其占用內存較少，同時，由于搜索空間為一個前綴樹的字典，字典里面有準確的詞尾節點，這樣，在進行詞圖生成的時候，可以準確地獲取到詞尾時間點。然而，動態網絡解碼器的最大缺點在于它的時間復雜度較高[6]，相對于靜態網絡解碼器，它的速度較慢。對于當今的大規模的語音識別應用，往往需要更快的響應速度，因而解碼速度更快的靜態網絡解碼器更加適合。靜態網絡的解碼器基于加權有限狀態機(Weighted Finite State Transducer, WFST)[7]。WFST 解碼器的特點是實現簡單，解碼速度快，對于知識源有統一的建模方式，并且它具有完善的理論框架以及成熟的優化算法。應用在語音識別的WFST 網絡輸入一般為上下文相關的三音素或者隱馬爾科夫模型(HMM) 狀態，輸出為識別詞。為了讓解碼器網絡得到充分優化加快解碼速度和降低解碼的內存占用，解碼網絡中不含詞邊界信息，這就為WFST 解碼器生成含有精確時間點的詞圖造成了一定困難。文獻[8]中提出了最早的WFST 解碼器的詞圖生成算法，準確說文獻[8]是介紹了一種記錄WFST 格式的解碼路徑的算法，它并不包含詞的邊界和時間信息，它產生的詞圖主要用于語言模型重打分。文獻[6]提出了在構建解碼網絡的時候插入額外的詞尾標記用于找回詞尾時間信息，但額外的詞尾標記會導致解碼網絡得不到充分優化，從而網絡變大，并且，解碼網絡格式的變化也導致解碼網絡的使用缺乏兼容性，需要為生成詞圖的解碼器重新構建網絡。Povey 等人[9]提出了一種WFST 的詞圖生成算法并應用在開源項目Kaldi[10]中。但是這種算法產生的是一種HMM 狀態級別的詞圖，仍然不是標準的詞圖。文獻[9]在文中提到不同解碼器產生的詞圖在格式上不統一的問題，要做統一的比較和解釋比較困難。

本文在給出了語音識別標準詞圖和WFST 的解碼音素圖的定義之后，探索了兩者之間的聯系，提出在WFST解碼器下的詞圖生成算法。本文首先提出了一種動態字典匹配的方法，此方法可以用來進行詞的時間點對齊，解決了WFST解碼網絡沒有精確詞尾節點的問題。然后提出了一種基于令牌傳遞(token passing)的方法，把WFST 的解碼音素圖轉換為標準詞圖。由于本文提出的WFST 詞圖生成算法生成的是標準的詞圖，可以應用到已有的重打分、關鍵詞檢索等一系列后處理應用中而無需額外操作，且由于沒有對網絡進行特殊處理，本算法在網絡使用上具有兼容性，無需重新構建解碼網絡。

本文的組織結構如下：第2節介紹背景知識，給出了WFST 的定義和解碼框架以及標準詞圖的定義；第3節揭示了WFST 音素圖和詞圖的聯系和映射關系；第4節和第5節分別給出了詞圖的生成算法和相應的實驗結果及分析；最后，第6節給出結論。

2 背景知識

2.1 基于WFST 的解碼框架

在語音識別中常用的權值半環有Log半環和Tropical半環[7]，為了達到更精確的識別率，本文采用Log半環。最終的靜態解碼網絡的構建可以表示成為

2.2 標準詞圖

標準詞圖是一個含有解碼信息的有向無環圖，可以定義為一個五元組：

3 WFST音素圖和標準詞圖的轉換關系

3.1 WFST解碼音素圖

3.2 WFST的音素圖和標準詞圖的聯系

圖1 音素圖起始狀態的權重處理

圖2 音素圖終止狀態集的歸一處理

4 WFST的詞圖生成算法

4.1 動態詞匹配

詞圖生成的理論基礎由文獻[4]提出，其中的一個假設是詞對無關假設，即：任何一對詞的詞時間點和這對詞的歷史無關，只與這對詞本身有關。這個假設是針對于動態網絡解碼器提出的。對于本文上下文相關音素級別的WFST 解碼器，由于WFST 做了網絡優化，詞的歷史可能不會唯一，但WFST輸入為上下文相關的三音素模型，詞對無關假設可以變為音素對無關假設，即：任何一對音素的時間點和其歷史無關。因此，由WFST 解碼器記錄下來的音素圖中音素的時間點是準確的。但WFST 的解碼網絡缺乏明確的詞尾標記，解碼時候產生的音素圖的詞輸出可能在其發音音素的任何位置，需要一個詞時間點對齊的方式來重新找回準確的時間點。

本文不采取直接的字典發音匹配進行詞時間點對齊(即只要當前的音素序列和詞的一個發音匹配即可進行對齊)。直接的字典發音匹配缺少通用性，其問題在于，當字典中的詞存在多發音且一個發音是另外一個發音的前綴的時候，前綴發音總會被優先匹配，而導致長的發音無法得到匹配。例如，英語中的縮寫單詞“Corp.”，其發音可以是縮寫的發音“k ao r p”也可以是完整發音“k ao r p er ey sh ah n ”，縮寫的發音是完整發音的前綴。

本文提出動態的詞匹配方式進行詞時間點對齊。此方法不僅僅是記錄一個詞就進行詞邊界的對齊，而是記錄多個詞和多個音素，動態進行發音匹配。其方法如下：(1)當記錄的詞序列長度達到3個詞時開始嘗試匹配，要求第1個和第2個詞的發音完全匹配，第3個詞中已記錄的發音要匹配(由于此時第3個詞的發音可能還未記錄完全，無需完全匹配)；(2)這種匹配的方式有且只有一種方法。滿足這兩個條件時可以確定第1個詞的邊界位置。示例如圖3所示，詞1包含兩個多發音，前綴發音含有4個音素，長發音有6個音素，詞2和詞3分別含有3個及2個音素的發音。在嘗試匹配時，如果某種匹配方式出現無法匹配的音素，則違背條件(1)，需要更換匹配方式，如圖3的錯誤1；如果匹配前兩個詞的方式不只一種，則違背了條件(2)，這有可能是因為第1個詞的發音去掉前綴發音后的部分剛好為第2個詞的前綴，如圖3中的錯誤2，此時需要加入后面更遠的詞輸入進行匹配(如：加入第4個或以上的詞)；只有條件(1)和條件(2)同時滿足的匹配方法才能確定第1個詞的邊界如圖3的正確匹配。

4.2 音素圖轉詞圖

圖3 動態詞匹配正確和錯誤的匹配示例

表1音素圖轉詞圖的算法描述

算法1. 音素圖轉詞圖 (1) 對音素圖的狀態集進行拓撲排序 (2) 初始化令牌，把令牌掛在的初始狀態上 (3) for all in do (4) for all in, s Token List do (5) if動態詞匹確認了詞邊界then (6) 在詞圖中連接舊狀態和目標狀態 (7) if 詞圖目標狀態已存在then (8) 刪除當前 (9) end if (10) end if (11) 傳播并加入經過邊的信息 (12) end for (13)end for

5 實驗結果和分析

5.1 實驗參數設置

本文實驗所采用的WFST 解碼器為文獻[14]描述的解碼器，參與對比的解碼器為動態網絡解碼器TDecoder[15]。測試任務包含了大詞匯連續語音識別和關鍵詞檢索兩種，每種任務各有兩個測試集。具體的測試集和模型參數如表2所示，其中電話語音和實網語音由于信道和環境的原因，語音效果較差。

5.2 詞圖的產生效率

本實驗采用電話語音測試集和對應的模型，因為電話語音的信道較差，語音的混淆性較大，解碼時產生的路徑也較多，能充分體現詞圖的產生算法的時間效率。對于轉詞圖過程中令牌傳遞剪枝和未剪枝的情況，本實驗記錄了這兩種情況下核心函數調用的平均次數。如表3所示，加入剪枝后，核心函數的調用次數從上百萬次降低到1000次左右，剪枝對于減少計算量有非常明顯的效果。加入剪枝后，轉詞圖部分所占實時率僅為0.0011，占整個解碼實時率的2.5%，相對解碼耗時的比例非常小。因此，本文提出的詞圖算法具有非常高的效率。仍然保持了WFST 解碼器在應用上快速的優勢。

表2測試集和模型參數

測試集名時長(h)詞典條數聲學模型語言模型(Million) 高斯數目HMM狀態數二元文法數三元文法數 LVCSR語音輸入法1.092k16865511M19M 電話語音1.043k12588429M33M 關鍵詞檢索實網語音3.443k16203099M35M 采訪對話2.5

表3 轉詞圖的時間效率

未剪枝調用次數加剪枝調用次數轉詞圖實時率轉詞圖時間比例 114277810720.00112.5%

5.3 大詞匯連續語音識別

本實驗在語音輸入法測試集和電話語音測試集上進行。參與對比的參數為解碼器的首選字錯誤率、詞圖錯誤率和用一個大的語言模型進行詞圖重打分后的首選字錯誤率。詞圖錯誤率是指用詞圖中和答案最匹配的路徑計算識別的錯誤率，它體現了詞圖用于重打分可以取得的錯誤率的下限。對于語音輸入法測試集，參與重打分的語言模型為一個三元文法語言模型(3-gram)含有2-gram 30 M和3-gram 58 M；對于電話語音進行重打分的模型為五元文法模型，含有2~5元文法共447 M。實驗結果分別見圖4和圖5。

從兩個測試集的縱向比較來看，由于電話語音的效果較差，錯誤率要比語音輸入法高很多。但是由于電話語音所采用的重打分語言模型更精準，因此，電話語音在重打分上錯誤率的下降要比語音輸入法更加明顯。從兩個解碼器的橫向比較來看，在語音輸入法測試集上，本文解碼器在首選的極限結果上略差于TDecoder，但是無論從重打分還是詞圖錯誤率都比TDecoder的錯誤率下降更為明顯；在電話語音測試集上本文解碼器首選結果的極限結果好于TDecoder，在重打分和詞圖錯誤率的下降仍然好于TDecoder。也就是說，本文的詞圖生成算法相對于TDecoder保留了更多了詞路徑，包含更多的解碼信息。

5.4 關鍵詞檢索

本文采用的關鍵詞檢索系統由文獻[16]所述。圖6給出了在兩個關鍵詞測試上，本文方法和TDecoder的關鍵詞的檢測誤差圖(Detection Error Tradeoff, DET)。關鍵詞有兩個重要的指標：等錯點和最大召回率。等錯點是DET圖中漏警率和虛警率相同的點。召回率的定義為

圖4 在語音輸入法測試集上的詞圖效果

圖5 在電話語音測試集上的詞圖效果

最大召回就是關鍵詞檢索系統所能夠實現的最大的召回率。DET圖和等錯點以及最大召回率均由圖6所示。為了方便比較，把本文的解碼器和TDecoder系統的等錯點調到相當的水平，可以看到，在等錯點相當的時候，基于本文的詞圖生成算法的關鍵詞系統具有較高的最大召回率，從而有效減少關鍵詞檢索時信息的丟失，同時仍然說明了本算法生成的詞圖具有更多的信息。

6 結束語

本文針對以往的WFST詞圖算法不含精確詞尾時間點的問題，提出了一種在WFST框架下的能產生含有精確詞尾時間點的詞圖的生成算法。本文從理論上分析了WFST解碼音素圖和標準詞圖的轉換關系，并從實際上提出動態詞匹配和基于拓撲排序及令牌傳遞的詞圖生成算法。從實驗結果上看，本文的詞圖生成算法具有較快的速度，同時，本算法生成的詞圖比已有動態網絡解碼器的詞圖包含更多的解碼信息，在關鍵詞，LVCSR重打分上具有更好的表現。

圖6 在關鍵詞測試集上的DET圖

[1] Shore T, Faubel F, Helmke H,.. Knowledge-based word lattice rescoring in a dynamic context[C]. Proceedings of Interspeech, Portland, 2012: 1337-1340.

[2] Zhang Hao and Gildea D. Efficient multipass decoding for synchronous context free grammars[C]. Proceedings of the Association for Computational Linguistics,Columbus, 2008: 209-217.

[3] Mangu L, Brill E, and Stolcke A. Finding consensus in speech recognition: word error minimization and other applications of confusion networks[J].&, 2000, 14(4): 373-400.

[4] Ortmanns S, Ney H, and Aubert X. A word graph algorithm for large vocabulary continuous speech recognition[J].&, 1997, 11(1): 43-72.

[5] Demuynck K, Duchateau J, Compernolle D V,.. An efficient search space representation for large vocabulary continuous speech recognition[J]., 2000, 30(1): 37-53.

[6] Rybach D, Schluter R, and Ney H. A comparative analysis of dynamic network decoding[C]. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, 2011: 5184-5187.

[7] Mohri M, Pereira F C N, and Riley M. Speech Recognition with Weighted Finite-State Transducers[M]. Handbook of Speech Processing, Verlag Berlin Heidelberg, Springer, 2008: 559-582.

[8] Ljolje A, Pereira F, and Riley M. Efficient general lattice generation and rescoring[C]. Proceedings of 6th European Conference on Speech Communication and Technology, Budapest, 1999: 1251-1254.

[9] Povey D, Hannemann M, Boulianne G,..Generating exact lattices in the WFST framework[C]. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, 2012: 4213-4216.

[10] Povey D, Ghoshal A, Boulianne G,.. The Kaldi speech recognition toolkit[C]. Proceedings of Automatic Speech Recognition and Understanding Workshop, Hawaii, 2011: 10.1109/ASRU.2011.6163923.

[11] Young S, Russell N, and Thornton J. Token passing: a simple conceptual model for connected speech recognition systems [R]. Report of University of Cambridge, Department of Engineering, 1989: 1-23.

[12] Nolden D, Rybach D, Ney H,.. Joining advantages of word-conditioned and token-passing decoding[C]. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, 2012: 4425-4428.

[13] Satoshi K, Takaaki H, Yoshikazu Y,.. Efficient beam width control to suppress excessive speech recognition computation time based on prior score range normalization [C]. Proceedings of Interspeech, Portland, 2012: 1649-1652.

[14] Guo Yu-hong, Li Ta, Si Yu-jing,.. Optimized large vocabulary WFST speech recognition system[C]. Proceedings of 9th International Conference on Fuzzy Systems and Knowledge Discovery, Chongqing, 2012: 1243-1247.

[15] Shao Jian, Li Ta, Zhang Qing-qing,.. A one-pass real-time decoder using memory-efficient state network[J]., 2008, 91(3): 529-537.

[16] 張鵬遠, 韓疆, 顏永紅. 關鍵詞檢測系統中基于音素網格的置信度計算[J]. 電子與信息學報, 2007, 29(9): 2063–2066.

Zhang Peng-yuan, Han Jiang, and Yan Yong-hong. Phoneme lattice based confidence measures in keyword spotting[J].&, 2007, 29(9): 2063-2066.

郭宇弘： 男，1985年生，博士生，研究方向為語音識別、音頻信號處理.

黎 塔： 男，1983年生，助理研究員，研究方向為大詞匯連續語音識別.

肖業鳴： 男，1983年生，博士生，研究方向為語音識別、聲學模型.

潘接林： 男，1965年生，研究員，博士生導師，主要研究領域包括大詞匯連續語音識別、聲學模型建模、搜索算法等.

顏永紅： 男，1967年生，研究員，博士生導師，2002年入選中科院百人計劃，現為中科院語言聲學與內容理解重點實驗室主任和所長助理.

Exact Word Lattice Generation in Weighted Finite State Transducer Framework

Guo Yu-hong Li Ta Xiao Ye-ming Pan Jie-lin Yan Yong-hong

(,,100190,)

The existing lattice generation algorithms have no exact word end time because the Weighted Finite State Transducer (WFST) decoding networks have no word end node. An algorithm is proposed to generate the standard speech recognition lattice within the WFST decoding framework. The lattices which have no exact word end time can not be used in the keyword spotting system. In this paper, the transformation relationship between WFST phone lattices and standard word lattice is firstly studied. Afterward, a dynamic lexicon matching method is proposed to get back the word end time. Finally, a token passing method is proposed to transform the phone lattices into standard word lattices. A prune strategy is also proposed to accelerate the token passing process, which decreases the transforming time to less than 3% additional computation time above one-pass decoding. The lattices generated by the proposed algorithm can be used in not only the language model rescoring but also the keyword spotting systems. The experimental results show that the proposed algorithm is efficient for practical application and the lattices generated by the proposed algorithm have more information than the lattices generated by the comparative dynamic decoder. This algorithm has a good performance in language model rescoring and keyword spotting.

Automatic speech recognition; Weighted Finite State Transducer (WFST); Lattice generation; Keyword spotting

TP391.42

A

1009-5896(2014)01-0140-07

10.3724/SP.J.1146.2013.00422

2013-04-01收到，2013-07-18改回

國家自然科學基金(10925419, 90920302, 61072124, 11074275, 11161140319, 91120001, 61271426)，中國科學院戰略性先導科技專項(XDA06030100, XDA06030500)，國家863計劃項目(2012AA012503)和中科院重點部署項目(KGZD-EW-103-2)資助課題

郭宇弘 guoyuhong@hccl.ioa.ac.cn