DLM：微信大規模分散式n-gram語言模型系統

AI1002019-09-16 11:27:07

來源 | 微信後臺團隊

Wechat & NUS《A Distributed System for Large-scale n-gram Language Models at Tencent》分散式語言模型，支援大型n-gram LM解碼的系統。本文是對原VLDB2019論文的簡要翻譯。

摘要

n-gram語言模型廣泛用於語言處理，例如自動語音識別(ASR)。它可以對從發生器（例如聲學模型）產生的候選單詞序列進行排序。大型n-gram模型通常可以提供良好的排名結果，但這需要大量的記憶體空間。將模型分佈到多個節點，可以解決記憶體問題，同時會產生很大的網路通訊開銷並引入了不同的瓶頸。

本文我們將介紹一套分散式系統，它採用新穎的優化技術來降低網路開銷，包括分散式索引、批處理和快取，可以減少網路請求並加速每個節點上的操作。同時還提出了一種級聯容錯機制，可根據故障的嚴重程度自適應地切換到小型n-gram模型。對9種自動語音識別（ASR）資料集的實驗研究證實，我們的分散式系統可以高效、有效、穩健地擴充套件到大型模型。我們已成功將其部署到騰訊的微信ASR系統中，網路流量峰值達到每分鐘1億次查詢。

關鍵字

n-gram語言模型，分散式計算，語音識別，微信

1.介紹

語言模型用於估計單詞或標記序列的概率。通常，它們為罕見序列或具有語法錯誤的序列分配低概率。例如，通過電腦科學文章訓練的語言模型可能為s1分配更高的概率：“VLDB is a database conference” ，而不是s2：“VLDB eases a data base conference”。語言模型廣泛用於自然語言處理[15]，特別是在生成文字的應用中，包括自動語音識別，機器翻譯和資訊檢索。

通常，語言模型可以用於對生成器生成的候選輸出進行排名。例如，在ASR中，生成器是聲學模型，其接受音訊然後輸出候選詞序列。對於來自聲學模型的若干個類似分數的候選者，例如s1和s2，語言模型對於選擇正確的答案至關重要。

n-gram是一種簡單且非常有效的語言模型。它基於對序列n-gram的統計（例如頻率）來估計單詞序列的概率。n-gram是n個單詞的子序列。

例如，“VLDB”和“database”是1-gram; “VLDB is”和“VLDB eases”是2-gram。n-gram語言模型為頻繁出現的n-gram的序列賦予更高的概率分數。最終概率統計資料是由特定文字語料庫計算出來。統計的概率反映了序列從訓練文字語料庫生成的可能性。對於樣本序列s1和s2，3-gram模型會給s1一個更高的概率，因為“VLDB is a”比“VLDB eases a”更常見，同樣，“a database conference”比“data base conference”在電腦科學文章中更常見。

使用n-gram語言模型的一個重要問題是其儲存成本高。首先為了準確性，n-gram中的n越大越好。例如，1-gram模型會給s2一個比s1更大的分數，因為“data”和“base”比“database”都要出現更頻繁。相比之下，2-gram語言模型可能給s1提供比s2更高的概率，因為“database conference”比“data base conference”更常見。

其次，較大的n-gram集合包括更多的n-gram（會有更好的覆蓋），因此對相對不常見的n-gram序列也能給出更好的概率估計。例如，如果n-gram集合中不包含“database conference”，則會基於其後綴即“conference”來估計s1的概率。此過程稱為回退（參見第2.2節），準確度會有所下降。實驗證實，較大的模型確實具有更好的效能。但是，大型模型在單個計算機的記憶體儲存不容易，且快速訪問的效率非常低。

通過將統計概率資訊分佈到多個節點來處理大型n-gram模型，我們稱為分散式語言模型。實現分散式n-gram模型的一個挑戰是高通訊開銷。例如，如果文字語料庫中不包含n-gram，則會產生O（n）的訊息查詢（因為需要通過[5]中的“回退”來計算其最終概率）。考慮到每個輸入（句子）可能有多達150,000個候選n-gram [5]，通訊成本變得非常昂貴。實現分散式n-gram模型的另一個挑戰與網路故障有關，網路故障經常發生在具有大量網路通訊的分散式系統中[23]。如果某些n-gram訊息丟失，則該模型將產生對概率的不準確計算。

在本文中，我們提出一種高效，有效和健壯的分散式系統技術，可以支援大規模的n-gram語言模型。

首先，我們在本地節點上快取短n-gram的統計資料（如1-gram和2-gram）。如此可以消除了低階n-gram的通訊成本。

其次，我們提出適合n-gram檢索的兩級分散式索引。全域性索引將相關n-gram概率的統計資訊分發到遠端同一節點。因此，每次完整n-gram只發出一次網路訊息就能得到完整資料。本地級索引將統計資訊儲存在後綴樹結構中，這有助於快速搜尋並節省儲存空間。

第三，我們把即將傳送到同一伺服器的訊息優化為單個訊息，顯著降低了通訊成本。

最後，我們提出了一種級聯容錯機制。兩級快取分別為2-gram大模型子集，4/5-gram小模型。前者使用於網路輕微故障，如偶爾丟包，後者使用於重大網路故障，如節點故障。

本文貢獻歸納如下：

提出了快取、索引和批處理優化技術，以減少大規模分散式n-gram語言模型的通訊開銷和加速概率估計過程。
提出了一種級聯容錯機制，該機制適應於網路故障的嚴重程度。它在兩個區域性n-gram模型之間進行切換，給出了健壯的概率估計。
實現了一套分散式系統，並以語音識別為應用，對9個數據集進行了廣泛的實驗。該系統擴充套件為5-gram模型應用。實驗結果證實了較大的n元模型具有較高的計算精度。我們已經將其應用於微信ASR系統，每天有1億條語音，峰值網路流量為每分鐘1億次查詢。

本文的其餘部分安排如下：第2節介紹了n-gram語言模型；第3節介紹了系統的細節，包括優化技術和容錯機制；第4節對實驗結果進行了分析；第5節回顧了相關工作；第6節總結了論文。

2.相關基礎

在本節中，我們首先簡單介紹如何使用n-gram語言模型估計單詞序列的概率，然後簡要描述下訓練和推理過程。

2.1語言模型

給定m個單詞序列，表示為wm =（w1，w2，...，wm），來自詞彙表V，語言模型提供該序列的概率，表示為P（w1...m）。

根據概率論，聯合概率可以分解如下：

通常，在自然語言處理（NLP）應用中，等式4中的概率與來自序列生成器的得分可以組合，來對候選序列進行排名。例如，ASR系統使用聲學模型來生成候選句子。聲學得分與來自語言模型的得分（等式4）組合，對候選句子進行排名。具有語法錯誤或奇怪單詞序列的那些將從語言模型得到較小的分數，因此被排在較低的位置。

n-gram語言模型假設序列中的單詞僅取決於先前的n-1個單詞。形式上表達為

在公式4中應用假設（公式5，稱為Markov假設[15]），我們得到了

例如，3-gram模型估計4個單詞序列的概率，

(省略examples)

2.2 平滑技術

基於頻率的統計（方程7）有一個問題：當n-gram沒有出現在訓練語料庫中時（例如當訓練語料庫很小時，頻率計數為0），條件概率（公式7）為零，這導致聯合概率為0（公式6）。平滑是解決這種“零頻率”問題的一種技術。有兩種流行的平滑方法，即回退模型和插值模型。一般的想法是將一些概率質量從頻率高的n-gram轉移一部分到

，頻率低的n-gram，並基於字尾來估計它們的概率。

回退平滑模型：

在方程8中

表示（頻繁）n-gram的折扣概率。例如，一種流行的平滑技術，稱為Kneser-Ney平滑，計算

其中D是超引數。

插值Kneser-Ney平滑

我們應用Kneser-Ney插值平滑，如公式9。通過簡單的操作（[6]的第2.8節），插值模型（例如公式9）可以轉換為相同的公式8，因此兩種平滑方法共享相同的推理演算法。

在本文的其餘部分，我們使用回退模型（公式8）來介紹推理演算法。

2.3 訓練和推理

n-gram語言模型的訓練過程會對訓練文字語料庫中的頻率進行計數，可以得到所有1-gram，2-gram，...，n-gram的所有條件概率（等式4）並計算係數。例如，5-gram模型的統計資料為1-gram至5-gram。

訓練語料庫中只會出現訓練語料庫中出現的單詞。有兩個原因：

a）對於給定的n和一個單詞n詞彙V，完整的n-gram集，其大小為

當V很大時會消耗大量的記憶體。

b）從未使用過一些x-gram記錄，例如“is be do”，無需預先計算和儲存其統計資訊。在本文中，我們關注推理階段的表現，從而跳過有關培訓的細節。

（請注意，對大型文字語料庫（如TB級）的訓練也非常具有挑戰性。與[5]一樣，我們使用分散式框架（即Spark）來加速培訓過程。）

推理過程接受由其他模組（例如ASR系統的聲學模型）生成的n-gram w1...n作為輸入，並返回P (wn|wn−1)。如果n-gram出現在訓練語料庫中，則其訓練過程中已經計算出條件概率，可以直接檢索；否則，我們使用平滑技術來計算替代的概率（公式8）。

從訓練階段生成的所有概率和係數都儲存在磁碟上，並在推理期間載入到記憶體中。ARPA [27]是n-gram語言模型的通用檔案格式。

2.4 本文問題定義

在本文中，我們假設n-gram語言模型已經離線訓練好。我們的系統將ARPA檔案載入到記憶體中並進行線上推理，將其用於計算由其他模組生成的單詞序列的概率，例如ASR的聲學模型。我們提出的技術，可以利用大規模n-gram語言模型的進行高效和穩健的推理。

3.分散式系統

較大的n-gram語言模型在概率估計中更準確。然而，當語言模型具有太多太長的n-gram時，例如，一個具有400 GB儲存空間的大型ARPA檔案，我們無法將整個檔案載入到單個節點的主儲存器中。如果我們只將部分ARPA資訊載入到主記憶體中並將其餘部分（n-gram）放在磁碟上，則推理過程非常緩慢，因為它必須從磁碟中檢索n-gram的統計資訊。

我們採用分散式計算的方式來解決這個問題，將ARPA檔案分割成多個節點。每個節點的記憶體足夠大，可以儲存它的一部分。這樣的節點我們稱為伺服器節點。相應地，對應還有客戶端節點。客戶端節點如下執行：

首先，它使用其他模組生成單詞序列候選（如ASR的聲學模型）；

其次，它向伺服器傳送請求訊息，從序列中檢索每個n-gram的條件概率；一條n-gram就是一條查詢。如果查詢不儲存在伺服器上，則使用“回退”來估計概率，如演算法1所示。

最後，客戶端將概率與公式6結合起來。這個過程叫做解碼，這在3.3節中進行了闡述。

在本節中，我們首先介紹我們減少通訊開銷的優化技術，包括快取，分散式索引和批處理。在此之後，再描述了針對通訊故障的級聯容錯機制。我們的系統表示為DLM，是分散式語言模型的縮寫。

3.1 快取

快取廣泛應用於資料庫系統優化。在DLM中，我們快取短n-gram的概率資料，具體來說，1-gram和2-gram被快取在客戶端節點上。如果快取長n-gram，例如3-gram，將進一步降低網路成本。但是，它也會產生大量的記憶體成本。第4.2.2節詳細比較了儲存成本和通訊減少。通過快取這些資料，我們不僅可以降低通訊成本，還可以改善系統的其他部分。我們實現以下三個目標：

減少網路查詢的數量。例如對於2gram和1-gram查詢，使用本地快取統計資訊估計條件概率。因此，無需向遠端伺服器傳送訊息。
在演算法2（第3.2.1節）中支援超過2-gram的記錄，這使得伺服器上的資料更加平衡。
支援容災機制，將在3.4節中討論。

3.2 分散式索引

DLM中的分散式索引由兩個級別組成，即客戶端節點上的全域性索引和伺服器節點上的本地索引。

3.2.1 全域性索引

通過客戶端節點上的本地快取，客戶端可以估計本地1-gram和2-gram查詢的概率。對於長n-gram查詢，客戶端使用全域性索引來定位儲存計算P（wn | wn-1）的統計資訊的伺服器（根據演算法1），然後向這些伺服器傳送訊息。如果我們可以將所有必需的統計資訊放在同一臺伺服器上，則只會向伺服器傳送一條訊息。構建全域性索引（演算法2）可以實現該目標。

有兩個引數，即來自ARPA檔案的n-gram總集合A和伺服器B的數量。

對於每個1-gram和2-gram，我們在所有節點都放置其正向概率和回退概率（第3行）。

對於其他n-gram（n≥3），我們基於wn-2 和 wn-1的hash做key，分發正向概率（第5-6行）。基於wn-1和wn（線7-8）的hash做key，分發回退概率。第5行和第7行共享相同的hash函式。

在推理過程中，如果n≤2，我們在本地客戶端進行查詢而不傳送任何訊息；否則，我們只需將P（wn | wn-1）的請求訊息傳送到具有ID Hash（wn-2，wn-1）％B + 1的伺服器。執行演算法1以使用等式10和14之間的等式之一來獲得概率。全域性索引保證對於任何n-gram w1..n（n> 2），可以從同一伺服器訪問演算法1中使用的所有資料。(例如，假設 w=“a database”。

根據演算法2，以w（第7行和第8行）結尾的所有ngram的回退概率（例如，“is a database”）與所有子gram的正向條件概率都放在同一伺服器上（例如，“is a database conference“），其第三個和第二個字是w（第5行和第6行）。另外，公式13（相應的公式14）使用的P（wn | wn-1）和γ（wnn-21）（P（wn）和γ（wn-1））在所有的節點上都有（第3行）。

總之，公式10和14中使用的所有統計資料都可以從同一伺服器獲得。因此，演算法1的任何一個完整的n-gram都可以減少至只有一次網路查詢。)

如果我們只快取1-gram，負載均衡演算法1也能工作。然而，快取1-gram和2-gram的結果可以獲得更好的負載平衡。我們解釋如下。考慮到某些單詞非常流行，如“is”和“the”，基於單個單詞的雜湊分配n-gram可能會導致伺服器節點之間的負載不平衡。

例如，儲存以'the'結尾的n-gram的伺服器將具有更大的分片並從客戶端接收更多訊息。由於2-gram的分佈比1-gram（即單詞）的分佈更均衡，因此在演算法1中基於兩個單詞（wn-1+wn或wn-2+wn-1）分佈n-gram將使查詢更加均勻。事實上，我們不建議使用3-gram以上，以使分佈更加平衡。這樣需要在本地客戶端節點上快取3-gram並在每個伺服器節點上備份3-gram資訊，這會顯著增加儲存成本。

3.2.2 本地索引

伺服器節點從客戶端接收到n-gram查詢請求，它就會搜尋本地索引來得到統計資訊並將它們組合最終計算P（wn | wn-1）。伺服器上需要構建本地索引，以便有效地檢索概率資訊。我們使用字尾樹作為索引結構，其中每個邊表示來自語音的一個或多個單詞，每個節點通過連線邊表示一系列單詞。如圖1所示。

本地索引的構建演算法如演算法3。每個伺服器都有兩組從演算法2生成的統計資料，即表示為G = {}的回退權重和表示為P = {}。對於P中的每一對，如果它是1-gram，我們只需將它儲存在字典U（第8行）中;否則，我們沿著路徑wn-遍歷樹。1，wn-2，...，w1。如果我們在完成路徑之前到達葉節點，則建立剩餘單詞的新邊和節點。返回最後一個被訪問節點（第5行）。使用wn作為鍵（第6行）將概率插入到排序陣列中，從而啟用二分搜尋。

對於每一對引數中的g，我們沿著完整n-gram的反向序列路徑wn，wn-1，...，w1（第7行）來遍歷樹結構。遍歷期間插入新節點。γ（w1n）被分配給回退的節點（第8行）。注意，每個節點可能具有多個關聯概率；但是，它只能有一個回退權重。這是因為共享相同字首（即wn-1）的所有n-gram語法的概率**入到同一節點中;而回退權重與對應於完整n-gram的節點相關聯，且n-gram是唯一的。圖1給出了將4-gram插入索引的一個例子。這個4-gram的條件概率位於右下角。

在推理期間，我們執行演算法4來估計條件概率。它針對字尾樹3實現演算法1.演算法4遍歷（wn-1，...，w2，w1）（第2行）。當下一個單詞沒有邊緣或達到w1時，它會停止。返回的路徑是一組訪問過的節點。根節點位於底部，最後一個訪問節點位於頂部。然後它逐個彈出節點。所有型別的n-gram都是通過使用公式10和14之間的公式之一來計算概率。

3.3 Batch 處理

通常，生成器為每個輸出位置生成多個候選詞。因此，有許多待篩選的句子。當語言模型在生成新的候選者之後立即對新候選詞進行排名，它被稱為on-the-fly rescoring ;當語言模型被用於在完成所有位置之後對候選句子進行排名時，它被稱為multi-pass rescoring。與multi-pass rescoring相比，on-the-fly resocring會產生較小的儲存成本，並且通過過濾低分數的單詞來維持一小組候選句子，因此效率更高。在DLM中，我們採用on-the-fly recoring。

當前候選句子的尾部，可能產生新的若干個新候選詞。為了得到每個新候選詞的聯合概率，我們需要得到最後一個n-gram的正向條件概率（其它詞已經計算了n-gram的概率）。一開始，候選句子很短，只有一個單詞“START”代表一個句子的開頭。因此，第一組查詢n-gram是2-gram，如“START I”。隨著句子變得更長，查詢n-gram變得更長，例如5-gram。如果我們保持最多K個候選引數併為每個位置生成W個單詞，那麼我們需要查詢KW n-gram，即KW個訊息。這個數字可能非常大，如10,000，這會導致非常多的網路查詢。為了降低通訊消耗，我們嘗試將傳送到同一伺服器的訊息批量處理為單個訊息。

如果兩個n-gram共享相同的字首，根據演算法4（和公式10-14），它們可能在本地索引上共享類似的訪問模式，以便統計計算條件概率。假設我們使用4-gram模型對圖2中的候選詞進行排名，即“watch”，“wait”和“wash”。即使使用分散式索引，我們也需要為3個4-gram中的每一個提供一條訊息。

由於它們共享相同的字首“I Want To”，因此根據演算法2的第5行將這三條訊息傳送到同一伺服器。將這三條訊息合併為一條訊息。一旦伺服器節點收到訊息，演算法4就沿著公共字首“I Want To”的反向遍歷，然後遍歷返回以分別獲得3個n-gram的統計資料。結果將放入單個訊息中併發送回客戶端。對於此示例，我們將訊息數量減少至原來的1/3。換句話說，可以節省2/3的成本。

對於不共享相同字首的n-gram，只要將它們目的地是同一伺服器，我們仍然可以合併它們的請求訊息。假設“Want To”和“Do Not”具有相同的雜湊值，則在圖3中，根據演算法1的第5行，可以將所有4-gram的訊息合併（批處理）為單個訊息。在伺服器端，共享相同字首的n-gram由演算法4一起處理。兩種批處理方法是正交的，因此可以組合在一起。

3.4 容錯(容災)

容錯對於分散式系統至關重要。根據網路故障的嚴重程度，我們提供級聯容錯機制。圖4顯示了我們系統的架構。連線測試程式不斷向伺服器傳送心跳。當故障率很高時，例如，超過0.1％的訊息超時或網路延遲加倍，我們將所有查詢重定向到本地小語言模型。

在我們的實驗中，我們使用一個50 GB統計的小型（5-gram）模型，通過基於熵的裁剪從完整的模型中裁剪得到[25]。當故障率處於非常低的水平，我們正常去遠端查詢大模型概率，如果查詢失敗，我們將使用本地2-gram子集模型的分數。（注意，這個子集模型和50G小模型是不一樣的，兩者獨立分開訓練）。因此，我們不能混合他們的統計資料來估計句子概率（方程6）。

4.0 實驗

在本節中，我們將基於多個數據集的來評估ASR的DLM技術。結果表明，我們的分散式語言模型DLM，可以有效地擴充套件到大型模型（例如，具有400 GB ARPA），並且通訊開銷很小。具體來說，當輸入音訊增加一秒時，DLM的開銷僅增加0.1秒，這對於微信中的實時系統來說足夠小。

4.1實驗設定

4.1.1 硬體

我們通過每個節點上具有Intel（R）Xeon（R）CPU E5-2670 V3（2.30GHz）和128 Giga Bytes（GB）記憶體的叢集進行實驗。節點通過10 Gbps網絡卡連線。我們使用開源訊息傳遞庫(Github：phxrpc)

4.1.2 資料

我們收集一個大的文字語料庫（3.2TB）來訓練使用插值Kneser-Ney平滑的5-gram語言模型。經過訓練，我們得到一個500 GB的ARPA檔案，進一步修剪，生成50GB，100GB，200GB和400GB的實驗模型。如果沒有明確的描述，則實驗將在200GB模型上進行，該模型是當前部署的模型。為了評估語言模型的效能，我們使用ASR作為我們的應用程式。收集9個數據集作為測試資料。我們將這9個數據集命名為test-1到test-9，詳細資訊如表1所示。我們可以看到測試資料是在不同的環境下記錄的，並且在長度方面有所不同。mix 表示音訊具有閱讀和自發語音。noise 意味著音訊被記錄在實際應用場景的公共場所。

4.1.3評估指標

我們評估DLM在支援ASR方面的有效性，效率和儲存成本。為了有效性，我們使用單詞錯誤率（WER），這是ASR的常用度量。為了計算WER，我們從測試資料集中手動生成每個音軌的參考單詞序列（即標準答案）。給定輸入音軌，我們將模型生成的單詞序列與參考單詞序列對齊，然後應用公式15計算WER。

在公式15中，D; S和I是刪除，替換和插入操作的數量，分別涉及在Levenshtein距離之後對齊兩個序列.N是參考序列中的詞的總數。例如，轉換圖5中的預測詞序列對於參考序列，我們需要D = 1刪除操作，S = 2替換操作，I = 1插入操作。相應的WER是(1 + 2 + 1)/5 = 0.8

為了提高效率，我們測量每秒語言模型輸入音訊所花費的平均處理時間。分散式n-gram模型會產生通訊開銷。我們還測量網路訊息的數量，這是通訊開銷的主要原因。

4.2可伸縮性和效率評價

我們首先研究DLM的整體效率和可擴充套件性。之後，我們對每種優化技術的效能進行細分分析。

4.2.1可擴充套件性測試

我們根據吞吐量測試DLM的可擴充套件性，即每秒伺服器處理的訊息數量。我們使用具有400GB資料的大型模型，並測量DLM處理的每分鐘訊息數。通過控制從客戶端到伺服器的訊息速率，所有伺服器上的最大CPU利用率保持在75％。

我們執行兩組工作負載：a）實際工作負載，表示為DLM-Real，其訊息由解碼器生成，無需任何調節; b）平衡工作負載，表示為DLM-Balanced，其訊息在DLM的所有伺服器之間手動平衡。對於DLM-Real，向伺服器分發訊息是不平衡的。因此，一些伺服器將接收更少的訊息，並且整體吞吐量受到影響。圖6中的結果顯示DLM-Balanced和DLM-Real很好擴充套件，差異很小。良好的可擴充套件性是得益於本文提出的技術，將在以下小節中詳細分析。

可擴充套件的系統應該最小化伺服器增多時產生的開銷。在圖7中，我們通過在伺服器數量增加時查詢時間和每秒音訊生成的訊息數量的變化來衡量開銷。我們將DLM與兩種基線方法進行比較，表示為基線A [5]和基線B [20]。

基線A基於每個n-gram的最後兩個字的雜湊來分配回退權重和概率。文中簡要提到了批處理，省略了細節。我們對基線A使用相同的DLM批量處理方法。基線B根據n-gram中所有單詞的雜湊分配概率和回退權重;另外，它在本地快取短的ngram。我們遵循與DLM相同的快取機制實現Baseline B，即快取1-gram和2-gram。

DLM和基線的每秒輸入音訊的處理時間如圖7a所示。我們可以看到，當伺服器數量增加時，DLM和Baseline A在查詢時間方面的開銷（或變化）很小。基線B的查詢時間仍然很長，並且對於不同數量的伺服器幾乎相同。這可以通過從客戶端到伺服器每秒音訊的訊息數來解釋（圖7b）。注意，圖7b的y軸與圖6中的y軸不同，圖6表示伺服器每秒處理的訊息。演算法A和DLM比演算法B產生的訊息少，主要是因為批量處理。對於Baseline A和DLM，當伺服器數量增加時，傳送到同一伺服器的兩條訊息的機會減少。

因此，訊息數量和處理時間增加。此外，DLM的分散式索引保證一個n-gram的所有統計資訊都在一臺伺服器上。基線A它只能保證在n-gram的回退過程中使用的所有概率被分配到同一伺服器（因為等式8中的字尾gram共享相同的最後兩個字），而回退權重可以被分發到不同的伺服器。因此，DLM生成的訊息比演算法A少。

為了瞭解時間的消耗，我們在表2中測量單個網路通訊的每個階段所花費的時間。我們可以看到，使用優化的本地索引，大部分時間花在訊息傳輸，編碼和解碼上，這需要優化訊息傳遞庫。在本文中，我們專注於減少訊息的數量。接下來，我們研究了我們提出的優化技術在通訊減少方面的有效性。

4.2.2 Caching

DLM在客戶端快取2-gram和1-gram。因此，1-gram和2-gram查詢在本地回答，而不向伺服器節點發送訊息。從表3中，我們可以看到可以直接發出16.09％的2-gram查詢。因此，我們通過在本地快取2-gram查詢來減少16.09％的訊息（不考慮批處理）。只有一個1-gram的查詢，即“START”，它對效能沒有影響。

我們不會快取3-gram和4-gram，因為它們非常大，如表4所示。此外，只有一小部分3-gram和4-gram查詢可以直接回答而無需回退。其餘的3-gram和4-gram查詢必須由遠端伺服器計算。換句話說，快取3-gram和4-gram會降低通訊成本。5-gram的大小並不大，因為訓練演算法修剪了許多5-gram，可以使用4-gram或3-gram精確估算，以節省儲存空間。我們不快取5-gram，因為只有2.5％的5-gram查詢（表3）可以使用ARPA檔案中的5-gram來應答；其他5-gram查詢需要回退，這會導致網路通訊。

4.2.3 分散式索引

我們進行了一項消融實驗，以分別評估全域性和本地 DLM 索引（第3.2節）的表現。我們不考慮此實驗的批處理和快取優化。DLM的全域性索引將用於估計n-gram概率的所有資料放在同一伺服器節點中，從而將訊息數量減少到每個n-gram 1次。為了評估這種減少的效果，我們在表3中列出了查詢分佈。只有一個1-gram查詢，即“START”。因此，我們不會在表格中列出它。

我們可以看到所有查詢中有33.39％已命中。換句話說，這些33.39％的查詢不需要回退，每個查詢只會產生一條訊息。其餘查詢至少需要一次回退，這至少會再產生一次訊息。使用全域性索引，我們始終為每個查詢發出一條訊息，這至少可以節省（1-33.39％）= 66.61％的成本。

全域性索引將ARPA檔案中的資料分割槽到多個伺服器上。我們評估伺服器之間的負載平衡。負載平衡如下計算：

其中S表示所有伺服器節點上的本地索引大小集，max（avg）計算最大（相應的平均值）索引大小。圖8通過對單個單詞和兩個單詞進行雜湊來比較全域性索引的負載平衡。我們可以看到，當對兩個單詞進行雜湊時，伺服器之間的資料分佈更加平衡。

為了評估DLM的本地索引（即字尾樹）的效能，我們建立了一個n-gram查詢集，並使用我們的本地索引與使用儲存條件概率和回退權重的基線索引來比較搜尋時間。兩個單獨的Hash函式都以整個n-gram為關鍵字。表5顯示DLM的本地索引比雜湊索引快得多（參見總時間）。這主要是因為本地索引通過減少搜尋次數來節省時間。具體而言，平均而言，每個n-gram需要2.27倍的回退才能達到獲得最終資料。DLM每n-gram搜尋一次本地索引（字尾樹），然後遍歷以獲取回退過程所需的所有資訊。

相反，基線方法在回退過程（演算法1）期間重複呼叫雜湊索引以獲得回退權重和概率。儘管每次搜尋的雜湊索引的速度很快，但總體效率差距主要取決於搜尋次數的巨大差異。請注意，表5中每次搜尋的時間小於表2中的時間。這是因為在表2中，我們測量每條訊息的時間，其中包括一批n-gram。這些n-gram中的一些可以共享相同的字首（參見第3.3節），因此一起處理。因此，搜尋時間更長。表5中的時間僅適用於單個n-gram。

本地索引還能節省儲存，因為字尾樹僅在共享該字首的所有n-gram中儲存字首一次。圖6比較了ARPA檔案，DLM（即本地索引）和另一種用於儲存語言模型的流行資料結構（即WFST [22]）的儲存成本。我們可以看到DLM節省了近一半的空間。

4.2.4 batch處理

3.3節中提出的批處理將傳送到同一伺服器的訊息合併為單個訊息，以減少開銷。圖9比較了DLM與批處理和沒有批處理的DLM兩組n-gram查詢。y軸是每個查詢集的訊息總數。我們可以看到批處理顯著減少了網路訊息的數量。實際上，幾乎一半的訊息都被消除了。因此，它節省了很多時間。圖7中DLM和Baseline B之間的巨大差距也主要是由於批處理。

4.3 容錯(容災)評估

我們的分散式系統具有兩個用於容錯的備用模型，這有助於使系統對網路故障具有魯棒性。但是，由於我們使用的是部分或小型語言模型，因此識別效能可能會降低。為了比較這些模型的準確性，我們獨立地在9個測試資料集上執行每個模型。圖10顯示了小模型，部分和完整模型的WER。完整模型的ARPA檔案具有200 GB資料。部分模型包括完整模型的所有1-gram和2-gram。小模型是在文字語料庫的子集上訓練的5-gram語言模型。ARPA檔案大小為50 GB。

我們可以看到完整模型具有最小的WER，這證實了我們的假設，即較大的模型具有更好的效能。此外，小模型優於部分模型，並且在某些測試資料集上與完整模型可以競爭。這是因為小型模型通過複雜的修剪策略從完整模型中修剪[25]，而部分模型只需通過移除3-gram，4-gram和5-gram得到。

請注意，輕度網路故障時呼叫部分模型，這對執行時的整體WER影響非常有限。儘管小型模型在多個測試資料集（環境）上具有與完整模型類似的效能，但仍然值得使用完整模型，因為完整模型在不同環境中更加健壯，包括具有多個揚聲器的嘈雜環境，這對於商業部署非常重要。

總結

n-gram語言模型在NLP應用非常廣泛。分散式計算使我們能夠以更高的準確度執行更大的n-gram語言模型。由於通訊成本和網路故障，使系統可擴充套件是一項挑戰。面對挑戰，我們提出了一個分散式系統來支援大規模的n-gram語言模型。為了減少通訊開銷，我們提出了三種優化技術。

首先，我們在客戶端節點上快取低階n-gram以在本地提供一些請求。其次，我們提出了一個分散式索引來處理其餘的請求。索引將每個n-gram查詢所需的統計資訊分配到同一伺服器節點上，這將每n-gram的訊息數量減少到只有一個。此外，它在每個伺服器上構建字尾樹索引，以便快速檢索和估計概率。第三，我們將傳送到同一伺服器節點的所有訊息批量處理為單個訊息。除了效率優化之外，我們還提出了一種級聯容錯機制，它可以自適應地切換到本地小語言模型。實驗結果證實，我們的系統可以高效，有效，穩健地擴充套件到大型n-gram模型。

參考文獻

[1] C. Allauzen, M. Riley, and B. Roark. Distributed representation and estimation of wfst-based n-gram models. In Proceedings of the ACL Workshop on Statistical NLP and Weighted Automata (StatFSM), pages 32-41, 2016.

[2] D. Amodei, R. Anubhai, E. Battenberg, C. Case,J. Casper, B. Catanzaro, J. Chen, M. Chrzanowski,A. Coates, G. Diamos,E. Elsen, J. Engel, L. Fan,C. Fougner, T. Han, A. Y. Hannun, B. Jun, P. LeGresley, L. Lin, S. Narang, A. Y. Ng, S. Ozair, R. Prenger, J. Raiman, S. Satheesh, D. Seetapun,S. Sengupta, Y. Wang, Z. Wang, C. Wang, B. Xiao,D. Yogatama, J.Zhan, and Z. Zhu. Deep speech 2:End-to-end speech recognition in english and mandarin. CoRR, abs/1512.02595, 2015.

[3] P. Bailis, E. Gan, S. Madden, D. Narayanan, K. Rong, and S. Suri. Macrobase: Prioritizing attention in fast data. In SIGMOD, pages 541-556, 2017.

[4] Y. Bengio, R. Ducharme, P. Vincent, and C. Janvin. A neural probabilistic language model. J. Mach. Learn. Res., 3:1137-1155, Mar. 2003.

[5] T. Brants, A. C. Popat, P. Xu, F. J. Och, and J. Dean. Large language models in machine translation. In EMNLP-CoNLL, pages 858-867, Prague, Czech Republic, June 2007.

[6] S. F. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4):359-394, 1999.

[7] D. Crankshaw, X. Wang, G. Zhou, M. J. Franklin, J. E. Gonzalez, and I. Stoica. Clipper: A low-latency online prediction serving system. In NSDI, pages 613-627, Boston, MA, 2017. USENIX Association.

[8] A. Emami, K. Papineni, and J. Sorensen. Large-scale distributed language modeling. In ICASSP, volume 4, pages IV-37-V-40, April 2007.

[9] A. Graves and N. Jaitly. Towards end-to-end speech recognition with recurrent neural networks. In ICML - Volume 32, ICML'14, pages II-1764-II-1772. JMLR.org, 2014.

[10] A. Graves, A. Mohamed, and G. E. Hinton. Speech recognition with deep recurrent neural networks. CoRR, abs/1303.5778, 2013.

[11] G. Hinton, L. Deng, D. Yu, G. E. Dahl, A. r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 29(6):82-97, Nov 2012.

[12] S. Ji, S. V. N. Vishwanathan, N. Satish, M. J. Anderson, and P. Dubey. Blackout: Speeding up recurrent neural network language models with very large vocabularies. CoRR, abs/1511.06909, 2015.

[13] J. Jiang, F. Fu, T. Yang, and B. Cui. Sketchml: Accelerating distributed machine learning with data sketches. In SIGMOD, SIGMOD '18, pages 1269-1284, New York, NY, USA, 2018. ACM.

[14] R. Jozefowicz, O. Vinyals, M. Schuster, N. Shazeer, and Y. Wu. Exploring the limits of language modeling. CoRR, abs/1602.02410, 2016.

[15] D. Jurafsky and J. H. Martin. Speech and Language Processing (2nd Edition). Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 2009.

[16] D. Kang, J. Emmons, F. Abuzaid, P. Bailis, and M. Zaharia. Noscope: Optimizing neural network queries over video at scale. PVLDB, 10(11):1586-1597, 2017.

[17] R. Kneser and H. Ney. Improved backing-o for m-gram language modeling. In ICASSP, volume 1,pages 181-184 vol.1, May 1995.

[18] Y. Lu, A. Chowdhery, S. Kandula, and S. Chaudhuri. Accelerating machine learning inference with probabilistic predicates. In SIGMOD, SIGMOD '18, pages 1493-1508, New York, NY, USA, 2018. ACM.

[19] A. L. Maas, A. Y. Hannun, D. Jurafsky, and A. Y. Ng. First-pass large vocabulary continuous speech recognition using bi directional recurrent dnns. CoRR, abs/1408.2873, 2014.

[20] C. Mandery. Distributed n-gram language models : Application of large models to automatic speech recognition. 2011.

[21] T. Mikolov, S. Kombrink, L. Burget, J. Cernocky, and S. Khudanpur. Extensions of recurrent neural network language model. pages 5528 - 5531, 06 2011.

[22] M. Mohri, F. Pereira, and M. Riley. Weighted nite-state transducers in speech recognition. Comput. Speech Lang., 16(1):69-88, Jan. 2002.

[23] Y. Shen, G. Chen, H. V. Jagadish, W. Lu, B. C. Ooi, and B. M. Tudor. Fast failure recovery in distributed graph processing systems. PVLDB, 8(4):437-448, 2014.

[24] D. Shi. A study on neural network language modeling. CoRR, abs/1708.07252, 2017.

[25] A. Stolcke. Entropy-based pruning of backo language models. CoRR, cs.CL/0006025, 2000.

[26] W. Williams, N. Prasad, D. Mrva, T. Ash, and T. Robinson. Scaling recurrent neural network language models. In ICASSP, pages 5391-5395, April 2015.

[27] S. Young, G. Evermann, M. Gales, T. Hain, D. Kershaw, X. Liu, G. Moore, J. Odell, D. Ollason, D. Povey, V. Valtchev, and P. Woodland. The HTK book. 01 2002.

[28] Y. Zhang, A. S. Hildebrand, and S. Vogel. Distributed language modeling for n-best list re-ranking. In EMNLP, EMNLP '06, pages 216-223, Stroudsburg, PA, USA, 2006.

PS：本文首先用微信翻譯引擎完成了全文的翻譯，然後再由人工對部分影響閱讀的句子做了修改。