WFST解碼器詞圖生成算法中的非活躍節(jié)點檢測與內存優(yōu)化*

丁佳偉，劉 加?，張衛(wèi)強，馮運波，劉利軍，于 樂

(1 清華大學電子工程系， 北京 100084； 2 中國移動通信信息安全管理與運行中心， 北京 100053)(2017年12月22日收稿； 2018年3月2日收修改稿)

大詞匯量連續(xù)語音識別(large vocabulary continuous speech recognition, LVCSR)技術是目前互聯(lián)網諸多語音識別系統(tǒng)的主流技術，在語音檢索、語音識別輸入法、關鍵詞檢測以及人機交互領域均有廣泛的應用。語音識別解碼器是語音識別系統(tǒng)的核心模塊，在語音識別中起到舉足輕重的作用[1]。它以由預處理的語音信號提取出的特征作為輸入，通過特定的解碼算法對輸入特征進行解碼，獲得解碼結果。

語音識別中的解碼器根據(jù)解碼網絡的構造方式可以分為兩大類，即動態(tài)網絡解碼器(簡稱動態(tài)解碼器)與靜態(tài)網絡解碼器(簡稱靜態(tài)解碼器)。在動態(tài)解碼器中，解碼的搜索網絡是在解碼過程中通過預測算法動態(tài)生成的，一般根據(jù)動態(tài)生成的聲學和語言模型實現(xiàn)解碼搜索。動態(tài)解碼器的一個典型代表是使用詞法前綴樹(lexical prefix tree)的方法[2]。動態(tài)解碼器的特點是內存消耗較少，而且可以幾乎不受限制地使用龐大的高階語言模型。德國亞琛工業(yè)大學開發(fā)的RWTH ASR系統(tǒng)是具有代表性的動態(tài)解碼器[3]。

在靜態(tài)解碼器中，系統(tǒng)提前將聲學模型與語言模型靜態(tài)結合，構造一個完整的解碼網絡，解碼器所有的過程均在該靜態(tài)網絡中進行，并生成完整的搜索空間。其特點是解碼速度相較動態(tài)解碼器大大提升，但由于其生成的解碼網絡相當龐大，搜索過程中所需的搜索空間也隨之增大，因此在實際應用中會占用大量的機器資源。靜態(tài)解碼器的代表是約翰霍普金斯大學的Kaldi系統(tǒng)[4]和瑞士IDIAP的Juicer系統(tǒng)[5]。靜態(tài)解碼器的一個典型模式是基于加權有限狀態(tài)機(weighted finite state transducers, WFST)的解碼器[6-7]。本文從工程應用的角度出發(fā)，對基于WFST的語音識別解碼器進行資源優(yōu)化，明顯改善了其資源占用的情況。

1 WFST語音識別解碼器

加權有限狀態(tài)機是自動機理論的一個擴展[8]，在語音識別解碼網絡的構建上得到了較好的應用。一個典型的語音識別網絡構成如下式所示：

fact(πε(min(det(H°C°det(L°G))))).

(1)

式中：“°”表示兩個WFST的合成；det、min、πε、fact分別為確定化、最小化、空邊去除以及簡化運算，其目的是優(yōu)化最終的網絡結構，使其盡可能化簡，且不改變原始網絡的功能。式子中G表示語言模型，定義詞到句子的映射；L表示發(fā)音詞典，定義音素到詞的映射；C定義上下文相關音素到單音子的映射；H定義HMM狀態(tài)到上下文相關音素的映射。式子中的H、C、L、G均代表一個WFST，通過式(1)中一系列的操作將其級聯(lián)合并，最終就可以獲得HMM狀態(tài)到句子的映射，以語音信號對應的HMM狀態(tài)序列作為輸入時，就可以直接得到對應的句子(詞序列)，也就是解碼器的功能。

生成解碼網絡后，就需要針對輸入特征在網絡中進行時間同步的搜索，尋找與輸入信息最匹配的狀態(tài)序列。這是一種廣度優(yōu)先的策略，通常使用維特比束搜索算法(Viterbi beam search)和令牌傳遞算法(token passing)進行搜索。在搜索結束后，得到的全局最優(yōu)路徑對應的詞序列就是解碼器的解碼結果，稱之為“1-best”結果。由于解碼器解碼過程中會同時生成一個包含全部中間節(jié)點的網絡(稱之為令牌圖)，因此除1-best結果以外，還可以通過對搜索生成的令牌圖進行后處理，獲得包含更多信息的詞格[9]或詞圖[10]等，用于進一步后處理后的其他應用[11-12]，如關鍵詞檢測等。

WFST解碼器中的詞圖(lattice)即是基于令牌圖生成的。詞圖的表現(xiàn)也為WFST模式，邊上的輸入和輸出為詞標簽，并附有對應的權重。文獻[10]提出一種根據(jù)WFST解碼器搜索結果直接生成詞級別詞圖的算法，首先在令牌圖中根據(jù)廣度優(yōu)先搜索確定詞邊界和對應的時間信息，并使用由詞對假設[13]引申而來的詞對過濾算法去除詞圖中的大量冗余，再利用確定化算法就可以得到確定化的，帶有準確時間標簽的詞圖。從上文可以看出，詞圖的質量直接由令牌圖的質量決定。

另外，根據(jù)后文需要，本文在此簡要介紹解碼過程中的實際搜索方式。

語音識別解碼器的搜索過程基于事先生成的WFST解碼網絡，該網絡以HMM狀態(tài)序列作為輸入，以詞標簽作為輸出。網絡中同時存在以HMM狀態(tài)作為輸入的非空邊，和無任何輸入的空邊。實際的搜索過程分為非空邊搜索與空邊搜索兩種。非空邊搜索是指，根據(jù)某一個語音幀的特征輸入，對當前所有待搜索節(jié)點進行非空邊的對應傳遞，一般只會向后傳遞至多一條邊的距離；空邊搜索則是指，對所有搜索節(jié)點進行空邊的自然擴張和傳遞，直到無法繼續(xù)基于空邊擴張為止。在實際的搜索過程中，首先應該對解碼網絡進行初始化，即進行一次從初始節(jié)點開始的空邊搜索。之后根據(jù)輸入語音對應的幀特征序列，交替進行空邊和非空邊的搜索，完成整個解碼的搜索過程。在整個解碼的搜索空間生成后，便可通過對權重最優(yōu)的終止節(jié)點進行回溯操作，獲得最優(yōu)路徑的解碼結果。

上文中提到，靜態(tài)解碼器由于其網絡龐大，其需求的內存資源也相對較多。但在實際的應用過程中發(fā)現(xiàn)，搜索過程中生成的中間節(jié)點所占用的資源要遠遠超出靜態(tài)解碼網絡的占用。其原因是中間節(jié)點中包含大量搜索的中間信息，例如前向累計權重和后向累計權重等等，這些信息的加入便造成節(jié)點空間相較靜態(tài)網絡會占用更多的空間。本文的內存優(yōu)化策略即針對節(jié)點空間進行，最終將解碼過程中的節(jié)點空間占用縮減至未優(yōu)化系統(tǒng)的25%左右。

2 解碼器的內存優(yōu)化策略

本文提到的語音識別解碼器中的內存優(yōu)化操作，實際上是指解碼搜索過程中的內存回收策略。由于解碼器的解碼過程是基于維特比束搜索的令牌傳遞算法，故而其在搜索過程中會不可避免地產生大量非活躍的節(jié)點(令牌)。為節(jié)省資源，在搜索過程中，應該實時地檢測這些非活躍節(jié)點的出現(xiàn)，并把其占用的空間及時地釋放。但直接進行非活躍節(jié)點的釋放會造成內存占用的碎片化，起不到節(jié)省機器資源的作用，因此還需要將當前的活躍節(jié)點重新排列，以滿足應用中對資源的實際需求。

2.1 數(shù)據(jù)結構的調整和優(yōu)化

一些開源的解碼器工具中已經存在相應的內存回收策略，例如kaldi。但kaldi中采用的分層結構在內存回收過程中會將內存碎片化，并且其占用的機器資源也并不固定，無法滿足實際的工程需求。圖1表示kaldi系統(tǒng)解碼器大致的數(shù)據(jù)結構。

圖1 Kaldi中的數(shù)據(jù)結構簡圖Fig.1 Data structure diagram in Kaldi

在工程應用中，一般希望解碼器占用固定且盡量小的機器資源，針對這種需求，考慮到WFST的節(jié)點-邊結構，可設計如圖2所示的數(shù)據(jù)結構，其中節(jié)點空間和邊空間均為連續(xù)的數(shù)據(jù)塊，而每一個節(jié)點則對應邊空間中的連續(xù)塊，具體表現(xiàn)為對每一個節(jié)點添加對應邊在邊空間內的起始位置和終止位置。這樣既可保證后續(xù)的回收和重排操作仍然在該空間中進行，且經過回收后仍能保持如圖所示的連續(xù)結構，保證解碼器的資源穩(wěn)定性。

圖2 本文設計的數(shù)據(jù)結構簡圖Fig.2 Our data structure diagram

2.2 數(shù)據(jù)結構的動態(tài)維護

本文提出的數(shù)據(jù)結構雖然能夠保證解碼器的資源穩(wěn)定性，但其要求節(jié)點和邊空間中的節(jié)點和邊必須按照起始位置升序排列。搜索過程生成的中間節(jié)點按照生成順序排列，可以直接滿足該要求；但由于搜索過程由空邊搜索和非空邊搜索組成，因此生成的邊并不按照起始位置順序排列，因此需要適時地對邊按照起始位置進行排序，保證數(shù)據(jù)結構不被破壞。為保證搜索過程的正常進行，這樣的排序操作應當在每一個數(shù)據(jù)幀都進行一次。下面提出一個排序策略：在每一幀的非空邊搜索后，對上一幀的空邊搜索和該幀的非空邊搜索生成的邊按照邊起始位置進行升序排序，并存放在邊空間中的相同位置?；谶@種排序策略即可實時地維護整個邊空間的數(shù)據(jù)結構，下面對其進行證明：

該策略的可行性基于兩個命題：第一，經過一次非空邊搜索時，所有生成的新節(jié)點并不產生以這些節(jié)點為起始節(jié)點的邊；第二，經過一次非空邊搜索時，所有既存的節(jié)點的全部可能邊均已生成完畢。根據(jù)第1節(jié)提到的空邊與非空邊搜索的概念，不難發(fā)現(xiàn)這兩個命題顯然是成立的。如圖3所示，圖3(a)的節(jié)點和邊空間經過一次空邊搜索和一次非空邊搜索后，得到的數(shù)據(jù)結構分別如圖3(b)和圖3(c)所示。可以看出，在空邊搜索結束時，第n幀的節(jié)點全部生成完畢，且在下一次非空邊搜索結束時，第n幀的邊空間也全部生成完畢。因此在某一幀的非空邊搜索后，其之前生成的所有節(jié)點和邊均已穩(wěn)定，此時進行數(shù)據(jù)結構維護在保證整個邊空間有序的同時，也避免了重復排序帶來的時間浪費。

圖3 第n幀的解碼搜索過程示意圖Fig.3 Diagram of the n-th frame decoding search process

2.3 解碼過程中的內存回收策略

如上文所提到的，內存的回收操作應該在解碼搜索的過程中實時進行，因此本文提出如下的回收策略：以一個給定的時間長度為間隔，對每一個間隔對應的時間段內所生成的所有節(jié)點和邊進行活躍性檢測和回收，取出該段時間內產生的非活躍節(jié)點與邊并將當前的所有活躍節(jié)點與邊在數(shù)據(jù)結構內重新調整，以滿足后續(xù)搜索過程的需求。

解碼過程中的非活躍節(jié)點，確切來說應該稱作“失活節(jié)點”。它一般在解碼搜索中被作為活躍的新節(jié)點生成，但在后續(xù)的搜索中發(fā)現(xiàn)其無法繼續(xù)向下搜索，如果不對其進行處理，其將繼續(xù)占用內存資源直到解碼完畢為止。在WFST解碼器框架下，這些非活躍節(jié)點會一直保留在令牌圖中，使令牌圖結構肥大化。由于前文提到，詞圖生成算法的基礎是令牌圖，而非活躍節(jié)點的檢測與回收即是對令牌圖進行的結構精簡操作，因此其對與詞圖的生成算法也具有正面的作用。

2.3.1 非活躍節(jié)點的檢測

在回收過程中，對于非活躍邊的檢測相對容易，因為只要其起始或終止節(jié)點中至少含有一個非活躍節(jié)點，那么其就應被判為非活躍邊。而非活躍節(jié)點的判定相對復雜，由于段內最后一幀的后續(xù)狀態(tài)未知，因此只能假設其均為活躍節(jié)點。對于其之前的段內節(jié)點，本文在此引入兩種動態(tài)檢測非活躍節(jié)點的策略。

一種是連通性檢測。這種策略的判據(jù)是，無法通過任何路徑到達當前最終節(jié)點的節(jié)點即被標注為非活躍節(jié)點。具體的操作方式為：在生成的解碼網絡中，對某一個間隔中的時間段，以該時間段內最后一幀的所有活躍節(jié)點作為起始點進行回溯，無法被回溯到的節(jié)點即是應該被回收的非活躍節(jié)點。這種方法簡單直觀，但因其未考慮語音識別解碼器中維特比束搜索算法的特性，因此并不能盡可能充分地對非活躍節(jié)點進行標注。下面介紹一種更加適用于語音識別解碼過程的回收策略。

在這種策略中，對每一個中間節(jié)點添加一個“額外權重”，其計算方式如下：

Cti=min({W({L|tiinL})})-

min({W({L})})，

(2)

式中：Cti是第i個節(jié)點ti的額外權重，W({L})表示對路徑集合L求權重獲得的權重集合。簡單說，一個節(jié)點的額外權重，是指其所在的所有完整路徑的最小權重和當前全部路徑的最小權重的差值。圖4給出一個節(jié)點空間的路徑示例，其中最優(yōu)的路徑是0-1-3-6-9，其權重為1.3，則這條路徑上的所有中間點，即1、3、6的額外權重即為0；而假設要計算節(jié)點4的額外權重，則需要找到包含該節(jié)點的最優(yōu)路徑，即0-1-4-7-6-9，其權重為1.4，故節(jié)點4的額外權重即為1.4-1.3=0.1。這一權重描述一個節(jié)點在整個節(jié)點空間中的可信程度。如果該權重越大，則表示該節(jié)點的可信度越低，此時即可人為定義一個閾值，將超過該值的節(jié)點也視為非活躍節(jié)點。由于無法到達最終節(jié)點的節(jié)點該額外權重為無窮大，因此這種策略最終包含連通性檢測的全部非活躍節(jié)點，并擁有更好的標記性能。本文應用的即是這種標記方法。一些開源工具中也包含相近的額外權重計算方法，例如kaldi等。

圖4 解碼器搜索空間示例Fig.4 Decoder search space example

2.3.2 段時間長度的選擇

本節(jié)給出回收長度段的選擇方案。回收長度段是指，對某段時間內生成的節(jié)點和邊進行回收操作時該段時間的長度，這里記作Tn。Tn的長度選取一般根據(jù)實際需要進行調節(jié)，但是對固定的解碼系統(tǒng)而言，其一般擁有一個最優(yōu)值。下面對其原因進行說明。

首先考慮計算速度。較大的Tn段內的節(jié)點和邊數(shù)較多，每次回收的計算量較大但總回收次數(shù)少；反之較小的Tn每次回收的計算量較小但總回收次數(shù)多，因此在計算量方面一般難以產生明顯的差別；如果考慮回收數(shù)量，較小的Tn由于可操作的段內節(jié)點數(shù)和邊數(shù)均較少，因此其回收的效率并不高；較大的Tn可以獲得很高的回收效率，但較大的時間容許量很可能導致節(jié)點和邊空間在段內時間內嚴重膨脹，造成短時的大量資源占用。因此一定存在一個Tn的取值，既能防止短時的資源膨脹，又能獲得較高的回收效率。而在實際應用中，可以進行調節(jié)最終獲得Tn的最優(yōu)取值。

3 實驗和結果

本文的實驗基于美國國家標準與技術研究所(National Institute of Standards and Technology, NIST)在2015年的語音關鍵詞檢索(OpenKWS)評測任務。在實驗中，以NIST OpenKWS 2015斯瓦西里語關鍵詞檢索的評測數(shù)據(jù)集作為實驗數(shù)據(jù)。其中，供訓練的語料為受限低資源數(shù)據(jù)集(very limited language pack, VLLP)，僅包含原始帶標注語料3 h和無標注語料40 h，開發(fā)集語料10 h。實驗首先采用該數(shù)據(jù)集訓練的DNN聲學模型，并使用fbank特征基礎上擴展pitch特征作為聲學特征；之后對聲學模型、發(fā)音詞典以及一個三音子語言模型進行聯(lián)合建模獲得靜態(tài)WFST解碼網絡，并使用上文提到的搜索和詞圖生成算法對測試數(shù)據(jù)進行解碼并生成詞圖。其中測試數(shù)據(jù)包含10 813條語音，分別來自60個不同的說話人。評測的評價指標來自關鍵詞檢測中的最大查詢詞加權值(maximum term-weighted value, MTWV)，該值越大說明系統(tǒng)的性能越好。本實驗只對解碼器的資源占用情況和運行效率進行評估，MTWV僅作為驗證算法準確性的依據(jù)。

實驗首先按照上文所示的解碼器系統(tǒng)結構構建基線系統(tǒng)，并在其基礎上添加內存回收策略。實驗的評價指標為內存占用量和實時率(RTF)兩項，其中內存占用量使用解碼過程中的實時最大節(jié)點數(shù)(MaxTokens)和邊數(shù)(MaxArcs)表示，其值越小說明解碼器占用內存越低；實時率為解碼器運行耗時與輸入語音長度的比值，其值越小說明解碼效率越高。對非活躍節(jié)點的標記策略采用2.3.1中添加額外權重的方法，判定閾值固定為8.0，調整不同的Tn值后的實驗結果如表1所示。

表1 實驗結果Table 1 Experimental results

表中的結果表明，在實時率方面，選取不同的Tn值對系統(tǒng)實時率的影響并不大，由于數(shù)據(jù)結構維護和內存回收策略的計算耗時引入，因此實時率相對基線系統(tǒng)(Tn等效地為無窮大)均有損失，均在15%左右。而在內存占用量上，Tn的選取影響顯著：隨著Tn值的逐漸增大，系統(tǒng)的內存占用量(定量映射為實時最大節(jié)點數(shù)和邊數(shù))呈現(xiàn)明顯先降后升的趨勢；另外從表中看出，當Tn=300時系統(tǒng)的內存占用量最低，為基線系統(tǒng)的25.2%，系統(tǒng)占用內存得到極大縮減。而且根據(jù)其在表中的變化規(guī)律，也能說明在Tn=300幀(即3 s)左右的范圍內應存在一個令該系統(tǒng)內存占用量最低的值。而MTWV的結果沒有發(fā)生變化，證明系統(tǒng)是穩(wěn)定且正確的。

另外，本文提出的回收策略僅應用在解碼器的搜索階段，其只作用于WFST結構的令牌圖上，對解碼器的具體識別任務(例如語種，語言模型建模等)沒有實質的約束。因此對于其他的LVCSR WFST靜態(tài)解碼器，該方法也能起到標記并回收非活躍節(jié)點的作用，這也體現(xiàn)了該方法的泛用性。

4 結論

本文從應用角度出發(fā)，針對基于WFST的語音識別解碼器提出在解碼搜索過程中實時地檢測并回收非活躍節(jié)點和邊的策略，相比無回收的解碼系統(tǒng)可以獲得顯著的機器資源節(jié)約。最后在OpenKWS 15評測上的實驗中，表明該回收策略相較不進行回收策略的基線系統(tǒng)獲得約75%的內存節(jié)省，且在實時率方面僅有15%的損失。添加內存回收策略的解碼器系統(tǒng)能夠更加滿足工程以及實際應用的需要，同時適合單個PC運行以及服務器端的多線程應用。