如果你曾為《十面埋伏》中章子怡“聽音辨鼓”的神技所驚艷，那么你也許就會(huì)被語音識(shí)別工具Kaldi的神通廣大所傾倒。作為當(dāng)前最流行的開源語音識(shí)別開發(fā)框架，Kaldi集成了多種語言識(shí)別模型，并被工業(yè)界、學(xué)術(shù)界幾乎所有語音團(tuán)隊(duì)所采用。

Daniel Povey博士，作為譽(yù)滿業(yè)界的Kaldi之父，他對(duì)下一代Kaldi以及其中所包含技術(shù)的發(fā)展又有何新的思考呢？在2020北京智源大會(huì)的主題報(bào)告《可微分的加權(quán)有限狀態(tài)機(jī)及其機(jī)器學(xué)習(xí)應(yīng)用》中，Daniel Povey為我們揭曉了答案。

Daniel Povey，開源語音識(shí)別工具Kaldi之父，前約翰霍普金斯大學(xué)語言與語音處理中心研究型副教授，現(xiàn)任小米集團(tuán)語音首席科學(xué)家。

在演講中，Daniel Povey首先指出了當(dāng)前版本Kaldi的一些缺陷，并提出了一些下一代Kaldi發(fā)展方向的戰(zhàn)略構(gòu)想；其次，就“加權(quán)有限狀態(tài)機(jī)”這一關(guān)鍵技術(shù)以及其在下一代Kaldi中如何應(yīng)用進(jìn)行了闡述；在報(bào)告的尾聲，Daniel歷數(shù)傳統(tǒng)確定化算法的優(yōu)缺點(diǎn)并闡述了其算法的主要思想。

整理：智源社區(qū) 李維

?

Kaldi，得名于傳說中發(fā)現(xiàn)了咖啡樹的埃塞俄比亞牧羊人，其誕生于2009年約翰霍普金斯大學(xué)（Johns Hopkins University）的一個(gè)名為“新語言和新領(lǐng)域的低開發(fā)成本和高質(zhì)量語音識(shí)別”的研討會(huì)。作為語音識(shí)別領(lǐng)域的后起之秀，Kaldi已被工業(yè)界和學(xué)術(shù)界的從業(yè)者所廣泛接受，儼然成為當(dāng)前最流行的開源語音識(shí)別工具。Kaldi主要使用C及C++進(jìn)行開發(fā)編寫，在此之上使用Bash和Perl以及Python腳本調(diào)用C++代碼進(jìn)行工具開發(fā)。

Kaldi有著與HTK相仿的目標(biāo)和受眾，擁有很多處理實(shí)際任務(wù)的實(shí)例以及大量可以復(fù)用的腳本是其廣受歡迎的眾多原因之一，其鮮明特色主要包括：

1）與有限狀態(tài)傳感器（FSTs）的代碼級(jí)集成；

2）廣泛的線性代數(shù)支持，包括一個(gè)封裝了標(biāo)準(zhǔn)的BLAS和LAPACK例程的矩陣庫；

3）可擴(kuò)展設(shè)計(jì)；

4）開放式許可。

Kaldi的優(yōu)點(diǎn)不可否認(rèn)，但其十分復(fù)雜以及沒有專長技能作為前提則不易學(xué)會(huì)的缺點(diǎn)也飽受詬病。此外，因?yàn)镵aldi本身不支持整數(shù)化，故很難在手機(jī)上實(shí)現(xiàn)產(chǎn)品化。雖說Kaldi使用的是自己的深度學(xué)習(xí)框架，但這個(gè)框架并不容易使用。

Daniel Povey也在本次報(bào)告中直言不諱地指出“盡管Kaldi擁有自己的神經(jīng)網(wǎng)絡(luò)框架，但其通用程度卻不及PyTorch和TensorFlow”，故他便有了將PyTorch應(yīng)用到下一代Kaldi深度神經(jīng)網(wǎng)絡(luò)中且允許在PyTorch和TensorFlow之間實(shí)現(xiàn)靈活切換的想法。如若這個(gè)想法在下一代Kaldi中得以實(shí)現(xiàn)，那將使得Kaldi與標(biāo)準(zhǔn)框架PyTorch和TensorFlow實(shí)現(xiàn)更好的結(jié)合。

Daniel Povey表示，下一代Kaldi將非常不同，幾乎沒有與現(xiàn)有Kaldi通用的代碼，他希望下一代Kaldi能實(shí)現(xiàn)以下目標(biāo)：

1）用少量代碼就實(shí)現(xiàn)像聯(lián)結(jié)主義時(shí)間分類算法（CTC）這樣的功能；

2）輕松有效地整合“離散”信息源，如詞匯及電話序列信息等；

3）將“傳統(tǒng)”自動(dòng)語音識(shí)別（ASR）解碼與PyTorch模型以簡單的方式集成；

4）有效地操作序列和序列集合；

5）使用通用而不是過于具體的工具來執(zhí)行操作。

盡管下一代Kaldi注定會(huì)有所變革，但Daniel表示在創(chuàng)造一系列工具用以實(shí)現(xiàn)這一目標(biāo)之前，有限狀態(tài)機(jī)是一個(gè)不得不解釋的概念。

二、有限狀態(tài)機(jī)

2.1 何為有限狀態(tài)機(jī)

有限狀態(tài)機(jī)，也被簡稱為FSA（Finite State Acceptors），其主要被用以研究具有有限內(nèi)存的計(jì)算過程，并根據(jù)一定的規(guī)則響應(yīng)外界輸入值，對(duì)研究對(duì)象的狀態(tài)變化進(jìn)行枚舉，得出狀態(tài)變化序列。作為一種依據(jù)對(duì)象行為建模的工具，其被廣泛應(yīng)用于電路設(shè)計(jì)、軟件工程、網(wǎng)絡(luò)協(xié)議和語言研究等計(jì)算機(jī)科學(xué)中的眾多領(lǐng)域。

如圖2所示即為一個(gè)極為簡單的有限狀態(tài)機(jī)，圖中兩個(gè)圓圈稱為節(jié)點(diǎn)，用以表示兩種狀態(tài)，并分別用0和1記之。在任意時(shí)刻有限狀態(tài)機(jī)均處于有限狀態(tài)集合的某一狀態(tài)，其中有限狀態(tài)集合可被一般地表示為{狀態(tài)1，狀態(tài)2，…，狀態(tài)m}，m需為一有限數(shù)，這是其之所以被稱之為有限狀態(tài)機(jī)的原因和要求。

從圖中不難看出，從每個(gè)節(jié)點(diǎn)或是狀態(tài)出發(fā)都有一條邊，復(fù)雜的有限狀態(tài)機(jī)則有多條邊并通向多種狀態(tài)。處于某一狀態(tài)的有限狀態(tài)機(jī)在獲得輸入字符時(shí)會(huì)引起狀態(tài)轉(zhuǎn)換，將從當(dāng)前狀態(tài)轉(zhuǎn)換到下一狀態(tài)或是仍然保持當(dāng)前狀態(tài)不變化，其依據(jù)就是輸入字符是否跟該節(jié)點(diǎn)出發(fā)的某條邊的內(nèi)容一致。例如，若有限狀態(tài)機(jī)目前正處于狀態(tài)0且輸入字符也為0，那么該有限狀態(tài)機(jī)則會(huì)從狀態(tài)0進(jìn)入狀態(tài)1。對(duì)于狀態(tài)1而言，若輸入的字符為1，則其會(huì)保持當(dāng)前狀態(tài)不變。倘若當(dāng)前狀態(tài)不存在與輸入字符對(duì)應(yīng)的輸出邊，那么該有限狀態(tài)機(jī)就會(huì)進(jìn)入消亡狀態(tài)（Doom state）。例如，當(dāng)有限狀態(tài)機(jī)處于狀態(tài)0時(shí)輸入字符1或是在狀態(tài)1時(shí)輸入字符0。此外，對(duì)圖示有限狀態(tài)機(jī)而言，輸入任何非0和1的字符均會(huì)導(dǎo)致該狀態(tài)機(jī)進(jìn)入消亡狀態(tài)。為方便和直觀，一般繪制如表1所示狀態(tài)轉(zhuǎn)換表。

Daniel Povey指出，有限狀態(tài)機(jī)中有兩個(gè)特殊的狀態(tài)，被稱為起始狀態(tài)和結(jié)束狀態(tài)。當(dāng)有限狀態(tài)機(jī)開始工作，輸入字符會(huì)導(dǎo)致狀態(tài)機(jī)的狀態(tài)不斷變化，但只要最后輸入的那個(gè)字符使得狀態(tài)機(jī)能轉(zhuǎn)化到結(jié)束狀態(tài)，那么該狀態(tài)機(jī)就會(huì)結(jié)束工作，識(shí)別出所輸入的所有字符序列。例如，在圖1中假定狀態(tài)0和狀態(tài)1分別為起始和結(jié)束狀態(tài)，那么該有限狀態(tài)機(jī)就會(huì)接收“0”，“0 1”，“0 1 1”，“0 1 1 1”等字符串。由于該狀態(tài)機(jī)設(shè)置得較為簡單，故其在該種情況下只能接受類似的有限字符串。倘若輸入的字符串為“0 1 0”，那么由于字符0導(dǎo)致狀態(tài)機(jī)會(huì)進(jìn)入消亡狀態(tài)，故該字符串將被狀態(tài)機(jī)所拒絕。?

除了有限狀態(tài)機(jī)之外，加權(quán)有限狀態(tài)機(jī)作為有限狀態(tài)機(jī)的一種特殊形式亦是構(gòu)建快速語音識(shí)別系統(tǒng)的主流技術(shù)。

2.2?加權(quán)有限狀態(tài)機(jī)

在語音識(shí)別領(lǐng)域有著廣泛應(yīng)用的加權(quán)有限狀態(tài)機(jī)（Weighted Finite State Acceptors，WFSA）事實(shí)上是以有限狀態(tài)機(jī)為藍(lán)本，顧名思義，在其輸出邊或弧上擁有權(quán)值信息。

如圖3所示即為一個(gè)簡單的加權(quán)有限狀態(tài)機(jī)，不難發(fā)現(xiàn)其是一個(gè)有向圖。連接各狀態(tài)之間的狀態(tài)轉(zhuǎn)移弧上分別標(biāo)示著輸入符號(hào)、輸出符號(hào)以及相應(yīng)的權(quán)值信息。圖中所示的輸入和輸出符號(hào)有所不同，但在現(xiàn)實(shí)情況中允許一個(gè)加權(quán)有限狀態(tài)機(jī)具有相同的輸入和輸出符號(hào)。圖中的狀態(tài)機(jī)會(huì)在輸入小寫英文字母之后輸出相應(yīng)的大寫字母，而在實(shí)際的語音識(shí)別應(yīng)用中，可能是以發(fā)聲的聲韻母作為輸入符號(hào)，并以漢字或是詞語作為輸出。

一般而言，加權(quán)有限狀態(tài)機(jī)除了以狀態(tài)轉(zhuǎn)移弧和結(jié)束狀態(tài)賦有權(quán)值為顯著特點(diǎn)之外，還需要半環(huán)代數(shù)理論作為支撐。一個(gè)簡單的半環(huán)代數(shù)結(jié)構(gòu)通常由元素集合、兩個(gè)二元運(yùn)算和兩個(gè)基本單元構(gòu)成，可被形式化表示為。應(yīng)當(dāng)特別指出，這里的0和1并不是真正的實(shí)數(shù)0和1，而是代指零元和幺元。半環(huán)代數(shù)需滿足的公理和條件有加法的結(jié)合律和交換律、乘法的結(jié)合律、分配律等。具體如表2所示：

表3則顯示了一些常用的半環(huán)。在語音識(shí)別領(lǐng)域使用頻率較高的半環(huán)有Log半環(huán)（Log semiring）和熱帶半環(huán)（Tropical semiring）。在Log半環(huán)中，權(quán)值被當(dāng)作負(fù)對(duì)數(shù)概率來處理，概率在并行路徑上求和。在熱帶半環(huán)中，權(quán)重值被視為類似于成本之類東西（例如，距離），并以使成本最小化作為合并并行路徑時(shí)的語義。

在談及加權(quán)有限狀態(tài)機(jī)在下一代Kaldi中的應(yīng)用時(shí)，Daniel Povey表達(dá)了以下想法：

1）在下一代中，會(huì)將權(quán)重與有限狀態(tài)機(jī)的結(jié)構(gòu)分開，并盡可能忽略權(quán)重；

2）用相反的符號(hào)存儲(chǔ)權(quán)重，比如負(fù)定的Cost或Logprob之類的，并稱之為“分?jǐn)?shù)”；

3）獲取權(quán)重信息的操作支持兩種類型：一個(gè)相當(dāng)于“熱帶半環(huán)”（取最大值），另一個(gè)相當(dāng)于“Log半環(huán)”（取Log Sum Exp或Soft Max）；

4）或許將采用更一般的權(quán)重類型，但其或只能通過標(biāo)量與核心算法交互，例如Pruning算法。

三、有限狀態(tài)機(jī)確定化

有限狀態(tài)機(jī)確定化（FSA determination）是對(duì)有限狀態(tài)機(jī)的基本操作之一，其他基本操作還有合并操作、組合操作以及權(quán)重推移操作等等。對(duì)一個(gè)有限狀態(tài)機(jī)進(jìn)行確定化操作的目的是為去除原始有限狀態(tài)機(jī)的冗余，得到一個(gè)等效的確定的有限狀態(tài)機(jī)，使得該狀態(tài)機(jī)能接收與原始狀態(tài)機(jī)一樣的路徑集。

3.1 確定化操作的意義

對(duì)于確定化有限狀態(tài)機(jī)的每一個(gè)狀態(tài)來說，同一個(gè)輸入符號(hào)有且只有一個(gè)轉(zhuǎn)移弧。例如，在圖4的原始加權(quán)有限狀態(tài)機(jī)中，對(duì)于狀態(tài)3來說有兩條具有同樣輸入和輸出字符但不同權(quán)重的狀態(tài)轉(zhuǎn)移弧與之對(duì)應(yīng)，而被確定化之后得到的圖5所示的加權(quán)有限狀態(tài)機(jī)則不會(huì)出現(xiàn)類似情況。

那么，由此可見，進(jìn)行確定化操作之后的加權(quán)有限狀態(tài)機(jī)相較原始狀態(tài)機(jī)而言就具有了非冗余性。當(dāng)給一個(gè)確定化的有限狀態(tài)機(jī)輸入符號(hào)序列時(shí)，該狀態(tài)機(jī)最多只有一條路徑與輸入字符序列相對(duì)應(yīng)，如此以來搜索算法的時(shí)間和空間復(fù)雜度就會(huì)被降低，這也是確定化操作的作用之所在。

Daniel Povey在談及有限狀態(tài)機(jī)確定化時(shí)指出其是一個(gè)非平凡的且具有不規(guī)則結(jié)構(gòu)的算法，并希望就該算法而言能做到以下幾點(diǎn)：

1）期望能夠在GPU上將其實(shí)現(xiàn)；

2）可闡述計(jì)劃在下一代Kaldi中使用的一些數(shù)據(jù)類型和抽象概念；

3）期望下一代Kaldi比有限狀態(tài)機(jī)更加通用；

4）試圖擴(kuò)展能在GPU上實(shí)現(xiàn)輕松編碼的范圍。

3.2?確定化算法間的比較

Daniel Povey在介紹他的基于熱帶半環(huán)的確定化算法前列舉了一些傳統(tǒng)算法的特點(diǎn)和不足，其中包括傳統(tǒng)的不加權(quán)算法以及加權(quán)算法。關(guān)于傳統(tǒng)的不加權(quán)算法，Daniel Povey認(rèn)為它有如下特點(diǎn)：

1）輸出中的每個(gè)狀態(tài)對(duì)應(yīng)于輸入中的一個(gè)狀態(tài)子集；

2）輸出中的初始狀態(tài)對(duì)應(yīng)于{0}，即輸入中的起始狀態(tài)；

3）需維護(hù)要處理的輸出狀態(tài)隊(duì)列；

4）需維護(hù)從輸入狀態(tài)ID到輸出狀態(tài)ID的映射。

關(guān)于傳統(tǒng)的加權(quán)算法，Daniel Povey指出：

1）加權(quán)后映射是從輸入狀態(tài)ID的加權(quán)集合到輸出狀態(tài)ID；

2）權(quán)重需要以某種方式標(biāo)準(zhǔn)化，例如，在傳統(tǒng)的熱帶半環(huán)中，權(quán)重要使最小成本為0；

3）標(biāo)準(zhǔn)化刪除的額外權(quán)重（Extra weight）將成為輸出弧上的權(quán)重；

4）會(huì)破壞并行性并具有糟糕的浮點(diǎn)數(shù)舍入屬性。

這里所謂的并行化包含（1）批量確定狀態(tài)；（2）首批僅有一個(gè)元素；（3）批量處理的規(guī)模取決于有限狀態(tài)機(jī)拓?fù)浣Y(jié)構(gòu)；（4）可在實(shí)際中的某個(gè)小批量中并行處理多個(gè)有限狀態(tài)機(jī)等特性。

關(guān)于Daniel Povey所提出的確定化算法，他總結(jié)到：

1）將狀態(tài)子集表示為（起始狀態(tài)，符號(hào)序列）這種形式是映射的關(guān)鍵；

2）子集是從起始狀態(tài)通過符號(hào)序列可到達(dá)的狀態(tài)的集合；

3）標(biāo)準(zhǔn)化過程包括刪除符號(hào)序列前綴和推進(jìn)初始狀態(tài)；

4）輸出弧上的“分?jǐn)?shù)”將是標(biāo)準(zhǔn)化中刪除的輸入弧的“分?jǐn)?shù)”之和；

5）需要進(jìn)行確定化操作的有限狀態(tài)機(jī)將更少。

3.3 數(shù)據(jù)結(jié)構(gòu)：列表套列表

在報(bào)告中Daniel Povey還提及一種名為列表套列表（ListOfList）的數(shù)據(jù)結(jié)構(gòu)，其在存儲(chǔ)一組固定類型的（大小可變）列表時(shí)，采用類似圖6（a）所示將其連接在一起的形式，并按圖6（b）的形式存儲(chǔ)與每個(gè)子數(shù)組開頭相對(duì)應(yīng)的索引，再加上一個(gè)子數(shù)組結(jié)束后的索引。此外，利用此思想還可以處理三維及多維不規(guī)則數(shù)組，只需額外增加索引數(shù)量即可，圖6（c）所示。通常來講，列表套列表型結(jié)構(gòu)有兩種檢索方式：其一為分層索引（Hierarchical indexing），比如list[i][j]，就像通常索引向量<vector<X>>一樣；其二為平面索引（Flat indexing），比如list.elems[k] ，其中l(wèi)ist.elems是元素的展開列表。

?

四、總結(jié)

在報(bào)告的尾聲，Daniel表示其已經(jīng)以有限狀態(tài)機(jī)確定化操作為例，設(shè)計(jì)用于處理不規(guī)則結(jié)構(gòu)的并行計(jì)算框架，愿景是使其能夠拓展PyTorch乃至TensorFlow等框架平臺(tái)。此外，他還提到已經(jīng)開始了關(guān)于非GPU實(shí)現(xiàn)的工作，并希冀該工作不僅局限于設(shè)計(jì)一個(gè)自動(dòng)語音識(shí)別（ASR）工具包。

從有限狀態(tài)機(jī)到加權(quán)有限狀態(tài)機(jī)，從Kaldi到其下一代，技術(shù)的不斷發(fā)展進(jìn)步促使著工具的不斷更新演變，而工具使用中所暴露出的問題又是下一次技術(shù)進(jìn)步的動(dòng)力和源頭。正是在這樣的互相促進(jìn)中，Daniel Povey博士及其團(tuán)隊(duì)醞釀著Kaldi這一語音識(shí)別工具持續(xù)向更好、更優(yōu)、更加完美的方向發(fā)展。但“金無足赤，人無完人”，正如Kaldi作為“后浪”曾席卷了它的前任們一樣，未來會(huì)不會(huì)有另一工具成為Kaldi的下一個(gè)繼任者呢？會(huì)不會(huì)有另一巨匠能夠站在Daniel Povey的肩膀之上呢？讓我們拭目以待！?

附：2020智源大會(huì)視頻回放鏈接

https://hub.baai.ac.cn/view/1573

關(guān)于我們

北京智源人工智能研究院（Beijing Academy of Artificial Intelligence，簡稱BAAI）成立于2018年11月，是在科技部和北京市委市政府的指導(dǎo)和支持下，由北京市科委和海淀區(qū)政府推動(dòng)成立的新型研發(fā)機(jī)構(gòu)。