Chen et al. - 2018 - Recurrent Neural Networks as Weighted Language Recognizers

Transcript

1. Recurrent Neural Networks as Weighted Language Recognizers Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight (NAACL 2018) 紹介者: Tosho Hirasawa 26 July, 2018
2. 目次 0. この論文について 1. Introduction 2. Definitions and notations 3. Consistency 4. Highest-weighted string 5. Equivalence 6. Minimization 7. Conclusion
3. この論文について • 選定基準 ◦ NLPでよく使用されるRNNの性質をきちんと把握しておきたい ◦ （Domain Adaptation 関係であまり面白そうなものがなかったので） • Guiding Questions ◦ この論文の結果は、 NLPタスクの既存手法にどのような影響を与えるか？ ▪ greedy/beam search ◦ この論文の結果から、新しい手法が考えられるか？
4. 1. Introduction • RNNは自然言語の多くの分野で利用されている（LM、MT、...） • 886次元のRNNはTuring Machineをシミュレートすることができる • 他の確率的LMの手法で研究されてきた問題はRNNでも問題となるだろう ◦ 有限状態オートマトンや文脈自由文法などの手法 ◦ Minimization, Intersection, Highest-weighted path/string などの問題 ◦ 例１）MTでは highest-weighted string の問題を greedy や beam search で解いているが、これら は近似解である ◦ 例２）RNNがLanguageの要素に与える重みが、確率となる (consist)かどうかは不明である • この論文では４つの問題を扱う ◦ Consistency ◦ Highest-weighted string ◦ Equivalence ◦ Minimization
5. 1. Introduction 補足：オートマトン • これ • 各頂点は『状態』、辺は『遷移』を表す。 • 上の例では、(0, 1) の状態が存在し、(0, 1) が入力される。一度でも1が入力される と終了する。
6. 1. Introduction 補足：Language ある集合Σをあり、そこに含まれる要素をゼロ個以上組み合わせて作られる文字列の集 合のことを、Σのクリーネ閉包と呼び、Σ*と書く。 このクリーネ閉包の部分集合のことをLanguageと呼ぶ。 MTでは、Σは語彙集合であり、Languageは文集合である。
7. 2. Definitions and notations 簡単のため、以下では語彙・文ではなく、文字・文字列で考える。 • Σ ：有限個のシンボルで構成された集合 • |Σ| ：Σの要素数 • s ：Σから繰り返しゼロ個以上の要素を取り出して作る文字列 • |s| ：sを構成するシンボルの数 • ＄ ：終端記号
8. 2. Definitions and notations　RNNの定義 RNNは7個のパラメータで定義する。 • ◦ 入力されるシンボル ◦ セル集合（サイズはRNNの次元数に相当する） ◦ activation vector の初期状態 ◦ 重み ◦ シンボルごとに定義されたバイアスの集合 ◦ 出力層の重み ◦ 出力層のバイアス • 活性化関数
9. 2. Definitions and notations　RNNの定義 RNNの計算はいつものとおりに行う。 t-1の隠れ状態と入力から次の隠れ状態を計算する 隠れ状態から各シンボルのスコアを計算する softmax で確率に変換する 文字列の確率を計算する 時刻 t に、時刻 t+1 のシンボルの生成確率を計算
10. RNN(s) = if s が空, s = a^n 2. Definitions and notations　RNNのサンプル 以下のようなRNNを考える。
11. 2. Definitions and notations　様々なRNNとweight すべてΣは{a} RNNの変数を変化させることで、 様々な重みをシミュレーションできる
12. 3. Consistency 問題：Given an RNN R, return “yes” if R is consistent and “no” otherwise. consistentとは以下の２つを満たす性質のことである。 • すべての重みが 0 以上 • 重みの合計が 1 である
13. 3. Consistency (Example 3) Example 3：RNNのセル{1,2,3,n,n’}について以下のような関係を仮定した場合、 の挙動により、RNNの重みの合計が変わる。
14. 3. Consistency (Example 3) Example 3：RNNのセル{1,2,3,n,n’}について以下のような関係を仮定した場合、 の挙動により、RNNの重みの合計が変わる。 の場合 (Lemma 15 より) RNNの重みの合計が1にならないので、consistentではない。 q-pochhammar
15. 3. Consistency (Example 3) Example 3：RNNのセル{1,2,3,n,n’}について以下のような関係を仮定した場合、 の挙動により、RNNの重みの合計が変わる。 の場合 RNNの重みの合計が1となるので、consistentである。 (Lemma 16 より)
16. 3. Consistency (Theorem 4) 任意の決定性Turing Machineについて、以下のようなRNNが存在する。 ここでは、以下の活性化関数を使用する。
17. 3. Consistency (Corollary 5) Theorem 4 の活性化関数は以下のように書き直せる。 これを使い、このRNNは別のReLUを使用したRNNに書き換える。 　　このRNNでTheorem4を書き直すと
18. 3. Consistency (Theorem 6) 問題：Given an RNN R, return “yes” if R is consistent and “no” otherwise. 定理：The consistency problem for RNNs is undecidable. • Example 3のRNNは、特定のセルの状態に依存し、consistentとなる • このセルの状態は、適当なTuring Machineを使用して、シミュレートできる (Theorem 4, Corollary 5) • Turing Machineの停止問題は undecidable である 適当に選んだTuring Machineが停止するかどうかはundecidableであるので、それに 対応するRNNのconsistency problemもundecidableとなる。
19. 3. Consistency (Theorem 7) 定理：A two-layer RNN trained to a local optimum using BPTT on a finite corpus is not necessarily consistent. • 下に定義したRNNでは、各パラメータに対する勾配がゼロになる １層目： ２層目：
20. 4. Highest-weighted string 問題：Given an RNN R and c ∈ (0, 1), does there exist s ∈ Σ* with R(s) > c? （最も重みが大きい文字列を求める問題を決定問題に書き直している。） • Highest-weighted string はNLPにおいて以下のことに相当する ◦ 言語モデル：最も尤もらしい文 ◦ 機械翻訳：デコーダーが出力する最も尤もらしい文
21. 4. Highest-weighted string (Theorem 8) 問題：Given an RNN R and c ∈ (0, 1), does there exist s ∈ Σ* with R(s) > c? 定理：The best string problem for RNNs is undecidable. ここでもExample 3を考える。 • RNNがconsistentでなければ、R(s) は高々0.12である • RNNがconsistentであれば、R(s)は0.25以上である • ＝＞RNNがconsistentであるかどうかにより、best string のスコアが変わってくる • ＝＞RNNのconsistent problemはundecidableであるから、この問題も undecidableとなる
22. 4. Highest-weighted string (Theorem 8) • RNNがconsistentであれば、R(s)は0.25以上である
23. 4. Highest-weighted string (Theorem 9) 問題：Given a consistent RNN R and c ∈ (0, 1), does there exist s ∈ Σ* with R(s) > c? 定理：The consistent best string problem for RNNs is decidable. 以下のアルゴリズムによって、探索することができる。 • 候補となる文字列 s_i は数え上げることができる • R(s_i) を計算し、R(s_i) > c なら yes、sum(R(s_i)) > 1 - c なら no を返す 探索アルゴリズムが存在するため、問題はdecidableである。
24. 4. Highest-weighted string (Theorem 10) best string を検索するときに、s の長さの上限を設定できない。 ＝＞Theorem 9 のアルゴリズムの計算時間の上限が存在しない。 ：RNNのセル数
25. 4. Highest-weighted string (Theorem 11) 問題：Given a consistent RNN R, polynomial P with P(x) ≥ x for x ∈ N + , and c ∈ (0, 1), does there exist s ∈ Σ ∗ with |s| ≤ P(|R|) and R(s) > c? 定理：Identifying the best string of polynomial length in a consistent RNN is NP-complete • 3-SAT 問題(NP困難)をこの問題に還元できる • 問題がNP＝特定のsとcを入力した場合、多項式時間で検証できることは自明？ 長さを多項式と仮定しても、best string を探索する問題はNP完全であるため、計算は 難しい。
26. 4. Highest-weighted string (Comparison) • PFSA: Probabilistic Finite State Automata • PCFG: Probabilistic Context Free Grammar • Det.: Deterministic • Nondet.: Nondeterministic
27. 4. Highest-weighted string RNN の best string 探索について、以下のことがわかった。 • 一般に、RNNの best string 探索は undecidable である • consistent な RNN に限定した場合、best string 探索は decidable であるが、計 算時間の上限は存在しない • 探索対象の文字列を多項式なサイズに限定すると、NP完全な問題となる つまり... • 真の best string を探索するのは現実的に無理なので、ヒューリスティックな方法 で、近似解を求めるのが良い
28. 5. Equivalence (Theorem 12) 問題：Given two RNNs R and R’ , return “yes” if R(s) = R’ (s) for all s ∈ Σ* , and “no” otherwise. 定理：The equivalence problem for RNNs is undecidable. • R を M’ をシミュレーションするRNNとする • R’ を以下のような計算を行うRNNとする • 問題を解くMが存在すると仮定する。M<R, R’> が yes を返せば、M’が停止しない ことが分かるが、M’の停止問題はundecidableなので、矛盾する M’が停止しない場合 M’が停止する場合
29. 6. Minimization (Theorem 13) 問題：Given RNN R and non-negative integer n, return “yes” if ∃ RNN R’ with number of hidden units |N’| ≤ n such that R(s) = R’(s) for all s ∈ Σ* , and “no” otherwise. 定理：RNN minimization is undecidable. • Theorem 12と同じ R を定義する • 0 を、常に同じ確率を返すRNNとする ◦ R の M’ が停止しない場合、RNN 0と同じ値を返す • 問題を解くMが存在すると仮定する。M<R, 0> が yes を返すと、Rが停止しないこ とが分かるが、M’の停止問題はundecidableなので、矛盾する
30. 7. Conclusion 分かったこと • Consistency ◦ InconsistentなRNNは存在する ◦ RNNのconsistency problemはundecidableである • Highest-weighted string ◦ 任意のRNNにおいて、best string探索問題はundecidableである ◦ consistentなRNN条件下のbest string探索問題はdecidableであるが、計算時間の上限は存在し ない ◦ 多項式サイズ条件下の best string探索問題はNP完全である • Equivalence, Minimization ◦ ともにundecidableである
31. 7. Conclusion • RNNの問題は凡そundecidableだし、高々NP完全である ◦ これまで使用されてきた FSAやCFGの複雑性はPであったこととは対照的 • 単純なRNNを使用したが、より複雑なRNNでも状況は同じと予測される ◦ LSTMとか • 種々の問題に対して効率的なアルゴリズムが存在しないことがわかったので、近似 解法が重要であることを再確認できた ◦ greedy/beam search ◦ ヒューリスティックな手法