A Tree-based Decoder for Neural Machine Translation

# 書誌情報
著者 : Xinyi Wang1, Hieu Pham1,2, Pengcheng Yin1 , Graham Neubig1

所属
- 1 Language Technology Institute, Carnegie Mellon University, Pittsburgh, PA 15213
- 2 Google Brain, Mountain View, CA 94043

学会，publish date
- EMNLP2018
- arXiv 2018/8/28

# 概要
- 翻訳先言語の**任意の木構造を生成しつつ**，翻訳するNMTモデルを提案
    - 従来の syntactic information を用いるモデルは seq2seq の decoder をそのまま用いたものであった
    - dependency tree を生成しながら翻訳するモデルも一つあるが，適用先が dependency tree に制限される
    - 今回提案モデルを様々な木構造について実験
- 言語知識なしに構築した binary-tree を用いたモデルが先行研究に比べて優位に高いパフォーマンスを示した．


# TrDec モデル

![スクリーンショット 2018-12-01 19.03.11.png](https://qiita-image-store.s3.amazonaws.com/0/140539/c738ceca-d190-10a0-1169-3b4b5fa73a6c.png)

ノード

- terminal nodes：subword unit を示す葉ノード
- nonterminal nodes：non-leafノード, subwords の結節ノード
- preterminal nodes：全ての子ノードが葉ノードであるノード (図中緑ノード)

**処理手順**

1. 入力文を RNN encoder でエンコード
2. rule RNN で root node から木構造の生成を開始
   - rurle RNN は encoder の最終隠れ状態で初期化される
   - 左側が root な 全てのCFGルールを生成する確率分布を計算
   - 図の例では $Root \mapsto S $ が選択されている
3. rule RNN はtop-down, left-to-right の順番で CFG rule を生成
    - preterminal node が生成されるまで rule を生成
    - 図の例では次に 左側が S な全てのCFGルールの生成確率を計算 -> $S \mapsto NP,VP,PUNC$
    - 同様にして次に NPに対して $NP \mapsto pre$ を生成
4. preterminal node を生成したら TrDec を word RNN に切り替えて，subword 生成
    - encoder の最終隠れ状態で初期化
    - <eop> が生成されるまで subword を生成 -> rule RNN に切り替え
    - word RNN が生成を続ける間，rule RNN の隠れ状態も更新(図を参照)
5. CFG の生成途中から CFG の続きを生成
    - 図の例では VP から生成 -> $VP \mapsto pre NP$
6. rule RNN が <eos> を生成するまで 3 ~ 5 を繰り返す


## Rule RNN

<img src="https://qiita-image-store.s3.amazonaws.com/0/140539/b2d6b2fc-479d-5d81-9694-32b02dc62a71.png" width=60%>

- $s_t^{tree}$：rule RNN の隠れ状態
- $y_{t-1}^{CFG}$：前ステップで生成したCGG のembedding 
- $c_{t-1}$：$s_{t-1}^{tree}$ から計算された attention で計算したコンテキスト
- $s_p^{tree}$：部分木内の現在のノードの親ノードを生成した時の隠れ状態
- $s_t^{word}$：サブワードを生成した直近のtimestep のword RNN隠れ状態
 

## Word RNN
<img src="https://qiita-image-store.s3.amazonaws.com/0/140539/37eb9b61-4355-8107-e383-5e8ed6cc713d.png" width=60%>

## SoftMax
$$W\cdot tanh[s_t^{tree},s_t^{word}]$$
- 各ステップでのsoftmax 計算には rule RNN, word RNN 両方の隠れ状態を使用？


# 用いる木構造
TrDec は任意の木構造に対応可能なので，４つ異なる木構造に対して適用し，比較を行った．
- syntactic trees ３種類と Balanced Binary Treeの Version1,2 を一まとまりにしたもの

![スクリーンショット 2018-12-01 21.51.38.png](https://qiita-image-store.s3.amazonaws.com/0/140539/f188cd9c-9905-860f-db3a-ef3b8bdf9fd6.png)

## Syntactic Trees
- Fig2. 左上 Constituency parse tree. Berkeley parser を用いて生成. (TrDec-con)
- Fig2. 右上 非終端ノードのタグを全て null にしたバージョンも作成 (TrDec-con-null)
- Fig3. dependency parse Trees を constituency に変換したもの (TrDec-dep)
    - 各ノードに対して null tag をもった親ノードを作成, 親ノードを，かかり先の親ノードとつなげることでツリーを作成

## Balanced Binary Tree (TrDec-binary)
- 言語特徴による制限等のない syntax-free tree
- Fig2. 左下 Version1 ターゲットセンテンスを再帰的に二分して作成
- Fig2. 右下 Versino2 version1 を単語ごとではなく，連続する単語がひとまとまりになったノード毎に実行して作成
    - 詳細は補足参照


# 実験
## 実験設定
- 3つのデータセットに対して評価
    - KFTT (ja-en) dataset
        - Japanese-English Wikipedia 記事
    - IWSLT2016 German-English (de-en) dataset
        - TED の字幕データ
    - LORELEI Oromo-English (or-en) dataset
        - Bible からのテキストが大部分を占める
- 英文parser には Ckylark(Constituency parser), Stanford Parser(Dependency parser) を使用
- BPE(ja-en:8K, or-en:4K, de-en:24K Merge operation) を使用
    - 語彙サイズではなく統合の数？で示していあるのは一般的？

<img src="https://qiita-image-store.s3.amazonaws.com/0/140539/099bdf79-60b1-76ab-655a-a2acc5e72109.png" width=60%>

## 結果
Syntax free tree を用いた場合(TrDec-binary), ja-en, or-en でベースラインに対して優位に高いパフォーマンスを示した

- or-en は学習データが少ない文，乱数シードの影響が大きかったので６つの異なる乱数シードで検証した結果の平均で比較
- de-en はベースラインの CCG-null に負けているが有意差はなかった


<img src="https://qiita-image-store.s3.amazonaws.com/0/140539/f2ed91fd-511d-fd92-b7bc-072ca3ff1c97.png" width=60%>

正解文の長さが長いほど，TrDec がベースラインに比べて優れていた(Fig.4)

- TrDec は長距離の依存関係をより捉えられていると考えられる
- 言語特徴を全く考慮しない binatry tree を用いた TrDec-binary が Tr-Dec-con を常に上回っているのは驚き
    - binary tree はデータ数が version1, 2 で合わせて倍になっているからでは？？

Tr-Dec-con の方が分布がなだらか（出力と，正解文の長さが違うケースが多い）なのは，センテンスの語数が一緒でも,Consituency parse tree の深さが大きく異なり翻訳が難しくなったためか

- binary tree は分割数，深さは一定になる


<img src="https://qiita-image-store.s3.amazonaws.com/0/140539/60255de2-1d21-e064-448f-4446076a9227.png" width=60%>


## 感想
- ターゲット側だけでなく，ソース側の構造も考えてみてもよいのでは？ 
- 言語情報は必要なく binary tree を作るほうが良いのはなぜか・・データ数の関係もありそう．


# 参考
[Predicting Target Language CCG Supertags Improves Neural MachineTranslation](http://www.aclweb.org/anthology/W17-4707)

- 比較対象ベースライン(CCG)論文

[Difference between constituency parser and dependency parser](https://stackoverflow.com/questions/10401076/difference-between-constituency-parser-and-dependency-parser)