[DL輪読会]Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks

DEEP LEARNING JP [DL Papers] Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks (ICLR2019) Kazuki Fujikawa, DeNA http://deeplearning.jp/ 1

• http://deeplearning.jp/

サマリ • 書誌情報 – Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks • ICLR2019（Best paper） • Yikang Shen, hawn Tan, Alessandro Sordoni, Aaron Courville • 概要 – 系列データから抽出される特徴量が階層化されて学習されるように設計された ”ON-LSTM” (Ordered Neuron LSTM) を提案 • Forget gate / Input gate が階層的に動作するような ”Ordered Neuron (Gate)” を導入 – 言語モデルや教師なし構文解析などのタスクで有効性を確認 2

アウトライン • 背景 • 提案手法 • 実験・結果 3

アウトライン • 背景 • 提案手法 • 実験・結果 4

背景 • 自然言語は、単純な系列ではなく階層構造で考えることができる • ニューラル言語モデルにも階層構造を導入することが重要である可能性がある – DNNでは階層を重ねることで抽象度の高い特徴量を獲得できることが知られている – 長期に渡った依存関係を学習しやすくできる可能性がある – 良い帰納バイアスはモデルの汎化、データ効率の改善に貢献する 図: 人手でアノテーションされた構文木の例 [Shen+, ICLR2019] 5

アウトライン • 背景 • 提案手法 • 実験・結果 6

ON-LSTM • 着想 – 一般的なRNNと同様、系列データを順々に入力して特徴抽出する過程で、(a) のような 木構造や各ノードの特徴が学習されるようにしたい – (a) の構文木は (b) の Block と見なすこともできる – LSTMのメモリ状態が (c) のように変化していれば、階層性を学習できたと考えられる • トークン 𝑥𝑡 のEmbedding入力時のLSTMのメモリ状態が、構文木上での各階層の特徴量を示す • 構文木で変化が無い階層（ex. 𝑥2, 𝑥3 の “S”, “VP”）は、対応するLSTMのメモリ状態にも変化が無い • 構文木で上の階層が変化する場合（ex. 𝑥1, 𝑥2 の “NP” → “VP” ）、それより下の階層に対応する LSTMのメモリ状態は全て更新される 7

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – 標準のLSTMのメモリ更新 ① 過去の情報𝑐𝑡−1をどの程度利用するかを制御する𝑓𝑡 (forget gate) を導出 ② 新規の情報𝑐Ƹ𝑡 をどの程度利用するかを制御する𝑖𝑡 (input gate) を導出 ③ 過去の情報𝑐𝑡−1と新規の情報𝑐Ƹ𝑡 を𝑓𝑡 と𝑖𝑡 で重み付けしてメモリを更新する 図引用: https://colah.github.io/posts/2015-08-Understanding-LSTMs/ 8

• https://colah.github.io/posts/2015-08-Understanding-LSTMs/

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTM • 下図 “ON GATES” の部分以外は標準のLSTMと同様 ON GATES 図引用: https://colah.github.io/posts/2015-08-Understanding-LSTMs/ 9

• https://colah.github.io/posts/2015-08-Understanding-LSTMs/

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 活性化関数: 𝑐𝑢𝑚𝑎𝑥 (cumulative softmax) を利用 exp(𝒛𝑘 ) 𝑔ො𝑘 = σ𝑘′ exp(𝒛𝑘′ ) 𝑔𝑘 = ෍ 𝑔ො𝑘 𝑘′ ≤𝑘 𝑠𝑜𝑓𝑡𝑚𝑎𝑥(∙) 𝑐𝑢𝑚𝑎𝑥(∙) 10

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 𝑓ሚ𝑡 , 𝑖ǁ 𝑡 の特性 ▪ 𝑐𝑢𝑚𝑎𝑥 は 𝑠𝑜𝑓𝑡𝑚𝑎𝑥 の累積和 → ピークを迎えた後は1に近い値を連続して出力する ▪ 𝑓ሚ𝑡 , 𝑖𝑡ǁ は逆側の次元で1に近い値を持つ 𝑓ሚ𝑡 𝑖ǁ 𝑡 ▪ 構文木の上位階層が変化するノードでは、 𝑓ሚ𝑡 は0に近い 値が多く、𝑖ǁ𝑡 は1に近い値が多いことが期待される （学習で求まるものであり、陽に与えるものではない） ▪ 𝑓ሚ𝑡 , 𝑖ǁ𝑡 は足して1になる訳ではない → 重複している部分 = “不完全な” 部分 （一部更新が必要な部分？） 11

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 𝑓ሚ𝑡 , 𝑖ǁ 𝑡 の特性 ▪ 𝑐𝑢𝑚𝑎𝑥 は 𝑠𝑜𝑓𝑡𝑚𝑎𝑥 の累積和 → ピークを迎えた後は1に近い値を連続して出力する ▪ 𝑓ሚ𝑡 , 𝑖𝑡ǁ は逆側の次元で1に近い値を持つ 𝑓ሚ𝑡 𝑖ǁ 𝑡 ▪ 構文木の上位階層が変化するノードでは、 𝑓ሚ𝑡 は0に近い 値が多く、𝑖ǁ𝑡 は1に近い値が多いことが期待される （学習で求まるものであり、陽に与えるものではない） ▪ 𝑓ሚ𝑡 , 𝑖ǁ𝑡 は足して1になる訳ではない → 重複している部分 = “不完全な” 部分 （一部更新が必要な部分？） 12

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 ② 𝑓ሚ𝑡 と 𝑖ǁ 𝑡 の重複部分: 𝑤𝑡 を導出 = ° 𝑓ሚ𝑡 𝑖ǁ 𝑡 𝑤𝑡 13

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 ② 𝑓ሚ𝑡 と 𝑖ǁ 𝑡 の重複部分: 𝑤𝑡 を導出 ③ 𝑓ሚ𝑡 , 𝑤𝑡 , 𝑓𝑡 (標準のLSTMのforget gate) を使って 𝑓መ𝑡 (ON-LSTM forget gate) を導出 − 𝑓ሚ𝑡 = 𝑤𝑡 𝑖ǁ 𝑡 と重複していない部分 → 𝑓ሚ𝑡 をそのまま利用 14

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 ② 𝑓ሚ𝑡 と 𝑖ǁ 𝑡 の重複部分: 𝑤𝑡 を導出 ③ 𝑓ሚ𝑡 , 𝑤𝑡 , 𝑓𝑡 (標準のLSTMのforget gate) を使って 𝑓መ𝑡 (ON-LSTM forget gate) を導出 = ° 𝑓𝑡 𝑤𝑡 𝑖ǁ 𝑡 と重複している部分 → 𝑓𝑡 との合議で決定 15

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 ② 𝑓ሚ𝑡 と 𝑖ǁ 𝑡 の重複部分: 𝑤𝑡 を導出 ③ 𝑓ሚ𝑡 , 𝑤𝑡 , 𝑓𝑡 (標準のLSTMのforget gate) を使って 𝑓መ𝑡 (ON-LSTM forget gate) を導出 ④ 𝑖ǁ 𝑡 , 𝑤𝑡 , 𝑖𝑡 (標準のLSTMのinput gate) を使って 𝑖Ƹ 𝑡 (ON-LSTM input gate) を導出 16

ON-LSTM • LSTMのメモリ状態の更新プロセスを変えることで実現 – ON-LSTMのメモリ更新 ① 消去 / 書込すべき領域 𝑓ሚ𝑡 （master forget gate）𝑖ǁ 𝑡 (master input gate) を導出 ② 𝑓ሚ𝑡 と 𝑖ǁ 𝑡 の重複部分: 𝑤𝑡 を導出 ③ 𝑓ሚ𝑡 , 𝑤𝑡 , 𝑓𝑡 (標準のLSTMのforget gate) を使って 𝑓መ𝑡 (ON-LSTM forget gate) を導出 ④ 𝑖ǁ 𝑡 , 𝑤𝑡 , 𝑖𝑡 (標準のLSTMのinput gate) を使って 𝑖Ƹ 𝑡 (ON-LSTM input gate) を導出 ⑤ 過去の情報𝑐𝑡−1と新規の情報𝑐Ƹ𝑡 を𝑓𝑡 と𝑖𝑡 で重み付けしてメモリを更新する 17

アウトライン • 背景 • 提案手法 • 実験・結果 18

実験1: 言語モデル • 言語モデル（次の単語を予測するタスク）を学習し、Perplexity で評価 – データセット: Penn TreeBank (PTB) – ハイパーパラメータはAWD-LSTM [Merity+, 2017] に合わせた • 結果・考察 – レイヤー数などのハイパーパラメータを Merity+ と統一していながら、Perplexityを改善 – AWD-LSTM-MoS [Yang+, 2017] には負けているものの、Softmaxレイヤーの改善であり、 本研究とは共存可能 19

実験2: 教師なし構文解析 • 言語モデルの学習済みモデルを使い、構文解析木を推定 𝐷𝑚 ሚ ① 各時刻𝑡について、𝑑𝑡 = 𝐷𝑚 − σ𝑘=1 𝑓𝑡𝑘 を算出 𝐷𝑚 ሚ （𝐷𝑚 : 隠れ層の次元数、σ𝑘=1 𝑓𝑡𝑘 : master forget gateのactivationの総和） ② 𝑑𝑡 についてソートし、この値が大きな𝑡, 𝑡 + 1の組から順に分割して木を構築する ex. “She enjoys playing tennis .“ の𝑑𝑡 の値が以下のようになっていた場合の構築手順 𝑑1 𝑑2 𝑑3 𝑑4 She enjoys playing tennis . She enjoys playing tennis . 20

実験2: 教師なし構文解析 • 言語モデルの学習済みモデルを使い、構文解析木を推定 𝐷𝑚 ሚ ① 各時刻𝑡について、𝑑𝑡 = 𝐷𝑚 − σ𝑘=1 𝑓𝑡𝑘 を算出 𝐷𝑚 ሚ （𝐷𝑚 : 隠れ層の次元数、σ𝑘=1 𝑓𝑡𝑘 : master forget gateのactivationの総和） ② 𝑑𝑡 についてソートし、この値が大きな𝑡, 𝑡 + 1の組から順に分割して木を構築する ex. “She enjoys playing tennis .“ の𝑑𝑡 の値が以下のようになっていた場合の構築手順 𝑑1 𝑑2 𝑑3 𝑑4 She enjoys playing tennis . She enjoys playing tennis . 21

実験2: 教師なし構文解析 • 言語モデルの学習済みモデルを使い、構文解析木を推定 𝐷𝑚 ሚ ① 各時刻𝑡について、𝑑𝑡 = 𝐷𝑚 − σ𝑘=1 𝑓𝑡𝑘 を算出 𝐷𝑚 ሚ （𝐷𝑚 : 隠れ層の次元数、σ𝑘=1 𝑓𝑡𝑘 : master forget gateのactivationの総和） ② 𝑑𝑡 についてソートし、この値が大きな𝑡, 𝑡 + 1の組から順に分割して木を構築する ex. “She enjoys playing tennis .“ の𝑑𝑡 の値が以下のようになっていた場合の構築手順 𝑑1 𝑑2 𝑑3 𝑑4 She enjoys playing tennis . She enjoys playing tennis . 22

実験2: 教師なし構文解析 • 言語モデルの学習済みモデルを使い、構文解析木を推定 𝐷𝑚 ሚ ① 各時刻𝑡について、𝑑𝑡 = 𝐷𝑚 − σ𝑘=1 𝑓𝑡𝑘 を算出 𝐷𝑚 ሚ （𝐷𝑚 : 隠れ層の次元数、σ𝑘=1 𝑓𝑡𝑘 : master forget gateのactivationの総和） ② 𝑑𝑡 についてソートし、この値が大きな𝑡, 𝑡 + 1の組から順に分割して木を構築する ex. “She enjoys playing tennis .“ の𝑑𝑡 の値が以下のようになっていた場合の構築手順 𝑑1 𝑑2 𝑑3 𝑑4 She enjoys playing tennis . She enjoys playing tennis . 23

実験2: 教師なし構文解析 • 言語モデルの学習済みモデルを使い、構文解析木を推定 𝐷𝑚 ሚ ① 各時刻𝑡について、𝑑𝑡 = 𝐷𝑚 − σ𝑘=1 𝑓𝑡𝑘 を算出 𝐷𝑚 ሚ （𝐷𝑚 : 隠れ層の次元数、σ𝑘=1 𝑓𝑡𝑘 : master forget gateのactivationの総和） ② 𝑑𝑡 についてソートし、この値が大きな𝑡, 𝑡 + 1の組から順に分割して木を構築する ex. “She enjoys playing tennis .“ の𝑑𝑡 の値が以下のようになっていた場合の構築手順 𝑑1 𝑑2 𝑑3 𝑑4 She enjoys playing tennis . She enjoys playing tennis . 24

実験2: 教師なし構文解析 • 結果・考察 – 3層ON-LSTMの各層のmaster forget gateの値を用いてParsingした結果を比較 • 2層目のmaster forget gateでparsingした場合が最も良い結果となった • 1, 3層目は言語モデルのタスクに対してより有用な特徴表現になっていて、抽象化されていなかった 可能性が考えられる ON-LSTM 2nd-layer Human expert annotations 25

結論 • RNNに対する新しい帰納バイアスの与え方としてordered neuronsを提案 – 新規のRecurrent unit: ON-LSTM、活性化関数: cumaxを含む – 長期 / 短期の情報がRNNのメモリの別領域に書き込まれるようにすることで、木構造の ようなデータ構造を表現できるようにした • 言語モデル、教師なし構文解析のタスクで有効性を検証 – ON-LSTMは言語モデルの学習過程で文構造を暗に学習することができ、それによって 言語モデル自体の性能を改善することができた 26

References • Yikang Shen, hawn Tan, Alessandro Sordoni, Aaron Courville. Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks. In ICLR2019. • Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and Optimizing LSTM Language Models. In ICLR2018. • Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W Cohen. Breaking the softmax bottleneck: A high-rank rnn language model. In ICLR2018. 27