GRAPHSEQ2SEQ: GRAPH-SEQUENCE-TO-SEQUENCE FOR NEURAL MACHINE TRANSLATION

# 書誌情報
ICLR 2019 Under Open Review

# 概要
- **GraphSeq2Seq** モデルを提案
    - **Graph2Seq(Graph state LSTM)** を利用し，単語間の依存関係グラフ構造を encodeし, Seq2Seq モデルで翻訳する
    - 先行研究では依存関係を単に追加特徴量 として word embeddig に concat する形でSeq2Seqモデルに入力しており，グラフ構造情報が失われていた．
- IWSLT 2014 German to English タスクにて従来SoTAを上回るBLUEスコア 30.66 を出した．
    - 比較対象にTransformer等が入っていないのでどれくらい優れているかは比較が難しい
    - ちなみに，[MULTI-AGENT DUAL LEARNING](https://qiita.com/kayamin/items/505cd06275f66b5cb126) では 35.44 pt を達成
    - **単語間の依存関係グラフ情報を用いることで翻訳パフォーマンスが向上した という事実が重要か**


# Graph state LSTM について
- Daniel Gildea, Zhiguo Wang, Yue Zhang, and Linfeng Song. A graph-to-sequence model for amrto-text
generation. In Proc. ACL, pp. 1616–1626, 2018.
- GraphSeq2Seq では 単語（ノード）と単語間の依存関係（エッジ）からなるグラフ情報を Graph state LSTM を用いて encode する

![スクリーンショット 2018-11-04 14.33.41.png](https://qiita-image-store.s3.amazonaws.com/0/140539/6eafc978-4276-c862-bde5-d0d3d0d5ae9b.png)
 
Gildea et al. (2018)から引用

- 各ノードとエッジはそれぞれノード表現 $x_i$, ノード隠れ状態 $h_i(t)$ エッジ表現 $e_l$ を持つ．ノード隠れ状態はハイパーパラメータとして定める初期値 $h_0$ からLSTM を用いて更新されていく
    - ノード：図中の丸
    - エッジ：図中の矢印
    - 翻訳モデルにおいては $x_i$ : 単語Embedding, $e_l$ : 判定された単語間の依存関係 one hot ベクトル を用いる

- n 番目のノード $x_n$のサブグラフ$g(n)$に対して, 下記を定義
    - $x_n^{in}$ : サブグラフへの入力の表現 式(3)
    - $x_n^{out}$ : サブグラフからの出力の表現 式(4)
    - $h_n^{in}$ : サブグラフへ入力するノード群の前ステップで計算された隠れ状態重み付き和 式(13)
    - $h_n^{out}$ : サブグラフからの出力を受けるノード群の前ステップで計算された隠れ状態重み付き和 式(14)
    ![スクリーンショット 2018-11-04 11.37.21.png](https://qiita-image-store.s3.amazonaws.com/0/140539/42dbd006-ec44-69bc-dab0-6edafed7a2c8.png)
![スクリーンショット 2018-11-04 15.14.40.png](https://qiita-image-store.s3.amazonaws.com/0/140539/c400749f-5d60-8e6a-a2da-d6ce6dc2f580.png)

## 各ノードの隠れ状態を LSTM で計算
式(6) ~ (11) で定義されるLSTM式 (12) で各ノードの隠れ状態を計算する．Gildea et al. (2018) Fig2 のように $g^0 -> g^1 ... -> g^t$ とLSTMを用いてグラフの隠れ状態をアップデートしていく(各ステップにおいて全てのノードの隠れ状態を更新する)．
LSMTのステップを重ねるほど，グラフ内で各ノードの情報が伝達され，生成される各ノードの隠れ状態はグラフ全体の情報を考慮したものになる．

**n番目のノードのステップｔにおける隠れ状態更新**

- 入力：$x_n^{in}, x_n^{out}, h_n^{in}(t), h_n^{out}(t)$
    - 各ノードの隠れ状態初期値　$h_n(0)$ はハイパーパラメーターを用いて初期化
- 出力：$h_n(t)$
  
   

![スクリーンショット 2018-11-04 11.37.33.png](https://qiita-image-store.s3.amazonaws.com/0/140539/5a5f99cc-e18e-2980-ef03-1afc10a54640.png)
![スクリーンショット 2018-11-04 15.33.36.png](https://qiita-image-store.s3.amazonaws.com/0/140539/6524b188-32aa-6524-bbd0-574e5b6c577a.png)

# Graph2Seq2Seq モデル
- 双方向Encoder で入力センテンス X のグラフ構造情報と単語情報を Encode し，Attention 付き Decoder で出力センテンス Y を生成する
![スクリーンショット 2018-11-04 12.00.41.png](https://qiita-image-store.s3.amazonaws.com/0/140539/be158220-a39c-9421-d3db-6b9d1013e18f.png)

**入力センテンス X が与えられたときの処理手順**

1. Sub-Graph Encoder で入力のセンテンスの単語情報，単語間の依存関係を Encode した graph representation $r_n$を取得
    - 各単語 $x_n$ への入力ノード $x_i$ 出力ノード $x_o$ を含むサブグラフ $g_n$ を取得し，sub graph encoder (graph state LSTM) を用いて $g_n$ を encode した $h_n^{in}, h_n^{out}, h_n$ を取得
    - 単語表現 $x_n$と，sub-graph state $h_n$, incoming representation $h_n^{in}$, outgoing representation $h_n^{out}$ を組み合わせて full graph representation $r_n$ を取得

2. graph representation $r_n$ を双方向sequence encoder へ入力

3. Attention メカニズムを用いた decoder で出力センテンスY を生成

## sub graph encoder
センテンス内の単語遺贈構造（グラフ構造）をencodeしたベクトル $r_n$ を全てのノードに対して計算する

- センテンスX 内の単語の依存構造グラフ G はパーサ Spacy を用いて取得

![スクリーンショット 2018-11-04 15.45.59.png](https://qiita-image-store.s3.amazonaws.com/0/140539/304326f2-977d-3d67-eede-3f69acdc6587.png)


- $h_n^{in}, h_n^{out}, h_n$ : graph state LSTM を用いて計算
- $H_n$ : Highway network (Srivastava et al., 2015) 式(15)，を用いて計算した各ノードの初期表現 $x_n$ の情報を保持したベクトル

    ![スクリーンショット 2018-11-04 15.50.51.png](https://qiita-image-store.s3.amazonaws.com/0/140539/ef538e26-f77a-9853-571a-eb515a1c8973.png)

## 双方向Encoder & Attention 付き Decoder
- 従来の Attention 付き Seq2Seq モデルと同様
![スクリーンショット 2018-11-04 16.04.49.png](https://qiita-image-store.s3.amazonaws.com/0/140539/fa2605ab-3120-6726-ca55-4224c7faf1d6.png)

# 実験設定
## タスク
- IWSLT 2014 Germanto-English, English-to- German, IWSLT 2015 English-toVietnamese 翻訳タスクで評価

## モデル詳細設定
- sub graph encoder
    - graph state LSTM のステップ数は 9 で固定
    - 各ノードは最大５つの隣接ノードから情報を受けるとする
    - graph state LSTM の隠れ状態次元数は 300
    - ３層 Highway network を用いて $H_n$を計算
    - edge label には 50 次元のベクトルを使用
- sequence encoder and decoder 
    - sequence encoder には 1層双方向LSTMを使用
    - decoder には 2層LSTMを使用
        - 隠れ状態の次元数は512

- Word Embedding
    - 200次元ベクトルを使用
    - 事前学習した Word2Vec embedding を使用

# 実験結果(IWSLT 2014 English-to-German のみ)

- 従来のSoTA 翻訳モデルに比べて高い BLEUスコアを示した．
    - **Graph2Seq の情報を Encode した結果パフォーマンスが向上した という事実が重要**
        - Transformer 等と比較していないのでこのモデル自体がどれくらい優れているのかは不明
 
![スクリーンショット 2018-11-04 16.22.16.png](https://qiita-image-store.s3.amazonaws.com/0/140539/2d22de43-9ebe-ae1c-1fd3-86cb5acc2e1b.png)

- Highway Layers の総数を変えることでモデルの精度は多少変化した
    - 本モデルでは，単語Embedding の情報を伝える役割を担っており重要
![スクリーンショット 2018-11-04 16.32.50.png](https://qiita-image-store.s3.amazonaws.com/0/140539/c4563a4f-fa47-efe8-4339-3a169b4ad2ca.png)

- 式(13), 式(14) の各ノード隠れ状態の和を求める時に重み付けの有無によるパフォーマンスの違いを検証した結果，重みによって BLEUスコアが最大 1pt 程改善されていることがわかった

![スクリーンショット 2018-11-04 16.32.57.png](https://qiita-image-store.s3.amazonaws.com/0/140539/d530f45f-d8fc-92b1-6926-d536e98366a0.png)