[譯] 使用 WFST 進行語音識別
之前，我的部落格文章都是關於深度學習方法或者它們在 NLP 中的應用。而從幾周前，我開始研究自動語音識別（ASR）。因此，我現在也會發布一些語音相關的文章。
ASR 的邏輯非常簡單（就是貝葉斯理論，如同機器學習領域的其它演算法一樣）。本質上，ASR 就是對給定的語音波形進行轉換，比如識別與波形對應的文字。假設 Y 表示從波形中獲得的特徵向量（注意：這個“特徵提取”本身是一個十分複雜的過程，我將在另一篇文章中詳述）， w 表示任意字串的話，可以得出以下公式：
公式中的兩個似然率是分開訓練的。第一個分量，稱為 聲學建模 ，使用包含話語和語音波形的平行語料庫進行訓練。第二個分量，稱為 語言建模 ，通過無監督的方式從大量文字中進行訓練。
雖然 ASR 訓練從抽象層面看起來很簡單，但實現它的實現卻遠要複雜得多。我們通常會使用加權有限狀態轉換機（WFST）來實現。在這篇文章中，我將介紹 WFST 及其基礎演算法，並簡要介紹如何將它用於語音識別。
加權有限狀態轉換機（Weighted Finite State Transducer，WFST）
如果你之前上過計算機理論課程（譯者注：大多數人可能是在編譯原理這門課上學的），你可能已經瞭解了 自動機 的概念。從概念上來說，有限自動機接受一種語言（一組字串）作為輸入。它們由有向圖表示，如下所示。
每個自動機由一個開始狀態，一個或多個最終狀態，以及用於連線狀態的帶有標號的邊組成。如果字串在遍歷圖中的某個路徑後以最終狀態結束，則接受該字串。例如，在上述 DFA（deterministic finite automata，確定有限狀態自動機）中， a 、 ac 和 ae 會被接受。
因此 接受器 將任何輸入字串對映成二進位制類 {0,1}，具體取決於字串是否被接受。而 轉換機 在每條邊上有 2 個標籤 —— 輸入標籤和輸出標籤。 加權 狀態轉換機，則更進一步，具有對應於每個邊和每個最終狀態的權重。
因此，WFST 是從字串對到權重和的對映。該字串對由沿著 WFST 的任何路徑的輸入/輸出標籤形成。對於圖中不可達的節點對，對應邊的權重是無窮大。
實際上，絕大部分語言都有對應的實現 WFST 的庫。在 C++ 中，OpenFST 是個較為流行的庫，在Kaldi 語音識別工具中也有用到。
原則上，我們可以不使用 WFST 實現語音識別演算法。但是，這種資料結構具有多種經過驗證的結果和演算法，可直接用於 ASR，而無需擔心正確性和複雜度。這些優點使得 WFST 在語音識別中幾乎無可匹敵。接下來我會總結 WFST 上的一些演算法。
WFST 中的基礎演算法
合併
顧名思義，合併是指將 2 個 WFST 組合形成單個 WFST 的過程。如果我們有發音和單詞級語法的轉換機，這種演算法將使我們能夠輕鬆地搭建一個語音轉文字的系統。
合併遵循以下 3 個原則：
- 將原先的 WFST 的初始狀態結合成對，形成新 WFST 的初始狀態。
- 類似地，將最終狀態結合成對。
- 如果存在第一個 WFST 的輸出標籤等於第二個 WFST 的輸入標籤這種情況，從起點對新增一條邊到終點對。邊的權重為原始權重之“和”。
以下是一個合併示例：
對於邊的權重來說，“總和”的定義很重要。藉助於半環的概念，WFST 可以接受廣義上的“語言”。從基本概念上來講，它是一組具有 2 個運算子的元素，即 ⊕ 和 ⊗。根據半環的型別，這些運算子可以有不同的定義。例如，在熱帶半環中，⊕ 表示取最小值，⊗ 表示相加。此外，在任意 WFST 中，一整條路徑的權重之和等於沿路徑的各條邊的權重相 ⊗（注意：對於熱帶半環來說這裡的“相乘”意味著相加），多條路徑的權重之和等於具有相同的符號序列的路徑相 ⊕。
這裡是 OpenFST 中對於合併的實現。
確定化
確定自動機是每個狀態中每種標籤只有一個轉移的自動機。通過這樣的表示式，確定化的 WFST 消除了所有冗餘並大大降低了基礎語法的複雜性。那麼，是不是所有 WFST 都可以確定化呢？
孿生屬性：假設有一個自動機 A，A 中有兩個狀態 p 和 q 。如果 p 和 q 都具有相同的字串輸入 x ，並有相同標籤的迴圈 y ，則稱 p 和 q 為兄弟狀態。從概念上講，到該狀態為止的路徑（包括迴圈在內）的總權重相等，則這兩個兄弟狀態是孿生的。
當所有兄弟狀態是孿生的時，這個 WFST 是可以被確定化的。
這是我之前所說的關於 WFST 是 ASR 中使用的演算法的有效實現的一個例子。有幾種方法可以確定化 WFST。其中一種演算法如下所示：
該演算法簡化後的步驟如下：
- 在每個狀態下，對於每個輸出標籤，如果該標籤有多個輸出邊，則將其替換為單個邊，其權重為包含該標籤的所有邊的權重的 ⊕ 總和。
由於這是一種本地演算法，因此可以高效地在記憶體中實現。要了解如何在 OpenFST 中進行確定化，請參閱此處。
最小化
儘管最小化不如確定化那樣重要，但它仍然是一種很好的優化技術。它用於最小化確定的 WFST 中的狀態和轉移的數量。
最小化的步驟分為兩步：
- 權重推移：所有權重都被推往開始狀態。請參閱以下示例。
- 完成此操作後，我們將到最終狀態的路徑相同的狀態組合。例如，在上述 WFST 中，狀態 1 和 2 在權重推移後變得相同，因此它們被組合成了一個狀態。
在 OpenFST 中，可以在這裡找到最小化的具體實現。
下圖（來自）展示了 WFST 優化的完整流程：
WFST 在語音識別中的應用
在語音識別中，多個 WFST 會被序列組合，順序如下：
- 語法（ G ）：使用大型語料庫訓練的語言模型。
- 詞彙表（ L ）：用於將不包含上下文的語音的似然度的資訊編碼。
- 依賴上下文的語音處理（ C ）：類似 n 元語言模型，唯一的不同點是它作用於語音處理。
- HMM 架構（ H ）：用於處理波形的模型。
總體上，將轉換機按 H o C o L o G 組合可以表示完整的語音識別的流程。其中每個部分都可以單獨改進，從而改善整個 ASR 系統。
WFST 是 ASR 系統的重要組成部分，這篇文章只是簡要地對 WFST 作了介紹。在其它與語音相關的帖子中，我會討論諸如特徵提取，流行的 GMM-HMM 模型和最新的深度學習進展之類的事情。我也在閱讀這些論文，以便更好地瞭解 ASR 多年來的發展歷程。