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

摘要：4月11日，NAACL
2018公佈了四篇傑出論文，分別關注於詞表徵、語句映射、文本生成和RNN。機器之心對最後一篇論文進行了編譯介紹，該論文探索了識別加權語言的RNN形式模型的計算複雜度。研究表明，

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

NAACL2018傑出論文。

循環神經網絡（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：不同模型識別最可能的派生情況（最優路徑）和最高權重字符串（最優字符串）的難度比較。

本文僅代表作者觀點，不代表百度立場。
本文係作者授權百度百家發表，未經許可，不得轉載。

相關推薦