NAACL2018 | 傑出論文：RNN作為識別器，判定加權語言一致性

選自arXiv，機器之心編譯。

4月11日，NAACL 2018公布了四篇傑出論文，分別關注於詞表徵、語句映射、文本生成和RNN。機器之心對最後一篇論文進行了編譯介紹，該論文探索了識別加權語言的RNN形式模型的計算複雜度。研究表明，大多數類似的RNN中存在的問題都是不可判定的，包括：一致性、等價性、最小化和最高權重字元串的確定。然而，對於連續一致的RNN來說，最後一個問題是可判定的。

循環神經網路（RNNs）是一種令人矚目的概率語言建模方法（Mikolov and Zweig, 2012）。近來，許多實驗都表明 RNN 在通過分配概率生成英語文本任務上顯著優於其他方法（Jozefowicz et al., 2016）。

簡單來說，RNN 的工作方式大致如下。在每一個時間步，它接收一個輸入詞項，更新它的隱狀態向量，然後通過生成一個基於辭彙表的概率分布來預測下一個時間步的詞項。輸入字元串的概率由構成字元串的詞項（後面跟隨一個終止符）的預測概率乘積得到。在這種模式下，每一個 RNN 都定義了一種加權語言，即一個從字元串到權重的全函數。

Siegelmann 和 Sontag 1995 年的一項工作表明使用了飽和線性激活函數的有合適權重的單層 RNN 可以計算任何可計算的函數。一個帶有 886 個隱單元的特定架構可以實時地模擬任何圖靈機（用 RNN 的每一個時間步來模擬圖靈機的每一步）。然而，其中使用的 RNN 會把全部輸入編碼為它的內部狀態，在接收到終止符時進行實際的計算，然後在一個特定的隱單元中編碼輸出。在這種方式下，RNN 在編碼輸入後可以有一定時間進行」思考」，這和圖靈機的計算時間是等價的。

我們考慮一種不同的 RNN 的變體，它被廣泛應用於自然語言處理的應用中。它使用 ReLU 作為激活函數，在每一個時刻接收輸入詞項，然後對下一個詞項的概率分布進行預測。接下來，在讀入上一個輸入詞項之後，它會立刻停下來，同時我們簡單地把每一個時刻的輸入詞項預測的積作為權重分配給輸入。

我們現在對於其他被用於概率語言建模的形式化方法，比如有限狀態自動機和上下文無關語法等已經有了充分的理解。它們的可用性很大程度上直接來源於較為完善的演算法屬性。舉例來說，加權有限狀態自動機計算出的加權語言在交（逐點乘積）和並（逐點和）下關閉，相應的未加權語言在交、並、差和補下關閉 (Droste et al., 2013)。此外，類似於 OpenFST (Allauzen et al., 2007) 和 Carmel1 的工具箱實現了許多基於自動機的高效演算法，比如：最小化、交、找到最高權重路徑和最高權重字元串。

RNN 從業者自然面對許多這些相同的問題。例如，基於 RNN 的機器翻譯系統應該提取由 RNN 生成的最高權重的輸出字元串（即最可能的翻譯）(Sutskever et al., 2014; Bahdanau et al., 2014)。目前，這項任務可以通過啟發式貪婪和束搜索等近似技術來解決。最小化技術對於在存儲空間有限的設備（如行動電話）上部署大型 RNN 是非常有益的。目前我們僅有像知識蒸餾 (Kim and Rush, 2016) 等啟發式方法。同時，我們是否能確定計算出的加權語言的一致性也尚不清楚（即它是否一組所有字元串的概率分布）。如果沒有確定分配給所有有限字元串的整體概率集群，就難以對語言模型的困惑度進行公平比較。

本文的目標是研究 RNN 的 ReLU 變體的上述問題。更具體地說，研究者提出並回答以下問題：

• 一致性：RNN 計算出的加權語言是否一致？計算出的加權語言的一致性是否可判定？
• 最高權重字元串：我們能否（有效）確定計算的加權語言中權重最高的字元串？
• 等價性：我們是否可以決定兩個給定的 RNN 是否計算相同的加權語言？
• 最小化：我們是否可以最小化給定 RNN 的神經元數量？

論文：Recurrent Neural Networks as Weighted Language Recognizers（使用循環神經網路作為加權語言識別器）

論文地址：https://arxiv.org/pdf/1711.05408.pdf

我們探索了不同問題下用於識別加權語言的循環神經網路形式模型的計算複雜度。我們主要關注被廣泛使用於自然語言處理任務中的單層的、使用 ReLU 作為激活函數的、被合理分配權重且帶有 softmax 層的循環神經網路。我們的工作表明，大多數類似的循環神經網路中存在的問題都是不可判定的，包括：一致性、等價性、最小化和最高權重字元串的確定。然而，對於連續一致的循環神經網路來說，儘管解決方案的長度會超過所有計算能力的上限，最後一個問題是可判定的。如果我們把字元串限定在多項式的長度，那麼這個問題就可以變成 NP 完全 和 APX-hard 問題。總的來說，這說明在這些循環神經網路的實際應用中，近似和啟發式的演算法是很有必要的。

圖 1：單字母的字母表的 RNN 採樣以及它們識別出的加權語言。M 是一個正的有理數，它取決於期望的誤差範圍。如果我們想用誤差範圍 δ 表示第二和第三種語言，則選擇 M 使得在第 2 列中 M > ? ln (δ/(1?δ))，且在第 3 列中 (1 + e^?M)^100 < 1/(1?δ)。

表 1：不同模型識別最可能的派生情況（最優路徑）和最高權重字元串（最優字元串）的難度比較。

推薦閱讀：