Decomposable Attentionアルゴリズムの解説と実装

下記論文のアルゴリズム解説と実装です．

- Title: A Decomposable Attention Model for Natural Language Inference
- Author: Ankur P.Parikh, et al.
- Year: 2016
- URL: https://arxiv.org/abs/1606.01933

どういう話かというと，前提と仮定， 受け答え，既出のネタかどうかなど２つの文章の関係を調べたいときに，Decomposable Attention[^1]アルゴリズムが使えそうなので，どうやって性能を改善しているのかを紹介しつつ，Kerasで実装してみた[^4]という話です．

## Decomposable Attention[^1]とは

- 自然言語推論(Natural Language Inference: NLI)用のネットワーク
- 2つの文書を入力とするクラス分類問題に利用
- Attention[^1]をネットワークに組み込むことで従来より性能を改善
- KaggleのQuora Question Pairs[^3](同一の質問か判断するコンペ)で優勝者[^5]も利用

![image.png](https://qiita-image-store.s3.amazonaws.com/0/107399/01feecba-22bd-90ef-e5ee-0f8852ac06b5.png)
図: A Decomposable Attention for Natural Language Inference[^1]より


## アルゴリズム

このアルゴリズムを利用するためには各単語をGloVe[^7]やWord2Vec[^8]で分散表現に変換しておく必要があります．

### ❏ 流れ

- Attend(整列?)
    - 互いの文書に関係のある単語ほど重みを高くつつ並び替える．
- Compare(比較)
    - 整列させた二文を比較し，2つの特徴ベクトルに変換
- Aggregate(集約)
    - 特徴ベクトル同士を結合させクラスごとの尤度を算出

### ❏ 入力変数

入力文章のペアを

```math
\bar{a} = (a_1, ..., a_{l_a})^\mathrm{T} \\
\bar{b} = (b_1, ..., b_{l_b})^\mathrm{T} \\
```

とする．ここで$l_a, l_b$は文書の長さを表す．

また，$a_i,b_j\in \mathbb{R}^d$は何らかの分散表現したもの．

- 実験ではGloVe[^7]で300次元の分散ベクトルに変換
- 分散ベクトル$\bar{a},\bar{b}$は$1$の$l_2$ノルムに正規化 

### ❏ Attend

attentionの重みは下記で計算．こうすることで，重要な単語同士は相関が高くなるように並び替える．

```math
e_{ij} := F'(\bar{a_i}, \bar{b_j}) := F(\bar{a})^{\mathrm{T}}F(\bar{b})
```

とする．このattentionの重み$e_{ij}$によって文書$a$と$b$の関係の深い単語同士は重みが強くなるようになる．

実装時の関数$F$は単なるニューラルネットワーク．

$F'$で計算してしまうと，入力変数の次元が$l_a \times l_b$となり大きいので，
実際に計算する際には$l_a + l_b$の入力次元数で$F$と簡略化している．

この$F$は実装時は全結合のニューラルネットワーク．

計算したattentionの重み$e_{ij}$をもとに$\bar{a_i},\bar{b_j}$を正規化した値$\alpha_i, \beta_j$を求める．

```math
\beta_i := \sum_{j=1}^{l_b} \frac{ \exp(e_{ij}) }{ \sum_{k=1}^{l_b} \exp(e_{ik})} \bar{b}_j \quad \forall i \in \left\{1,...,l_a \right\} \\

\alpha_j := \sum_{i=1}^{l_a} \frac{ \exp(e_{ij}) }{ \sum_{k=1}^{l_b} \exp(e_{kj})} \bar{a}_j \quad \forall j \in \left\{1,...,l_b \right\} 
```

### ❏ Compare

```math
v_{1,i} := G([\bar{\alpha_i}, \beta_i]) \quad \forall i \in \left\{1,...,l_a \right\} \\
v_{2,j} := G([\bar{\beta_j}, \alpha_i]) \quad \forall j \in \left\{1,...,l_b \right\}
```

ここで$G$は実装時にはニューラルネットワーク．

### ❏ Aggregate

```math
v_1 = \sum_{i=1}^{l_a} v_{1,i} \\
v_2 = \sum_{j=1}^{l_b} v_{2,j} \\
\hat{y} = H([v_1, v_2])
```

### ❏ Intra-Sentence Attention(任意)

単語埋め込み部分で，単に単語ごとに変換するのではなくニューラルネットを使うことで文としての意味も取り込めるのではないかと考えた機能．

```math
f_{ij} := F_{\rm{intra}}(a_i)^{\mathrm{T}}F_{\rm{intra}}(a_j)
```

ここで，$F_{\rm{intra}}$はフィードフォワードネットとして，$\bar{a_i},\bar{b_i}$を以下に変更にする．

```math
\bar{a_i} := [a_i, a'_i]\\
\bar{b_i} := [b_i, b'_i]
```

ここで，$a'_i$は

```math
a'_i := \sum_{j=1}^{l_a} \frac{\exp(f_{ij} + d_{i-j})}{\sum_{k=1}^{l_a} \exp(f_{ik + d_{i-k}})} a_j
```

としています．この$d_{i-j} \in \mathbb{R}$はバイアス． $b'_i$についても同様


## 実装[^4]

コード[^2] [^6] [^10]を参考にKeras[^9]で作成しています．

https://gist.github.com/namakemono/f4f273dbc63fc2174940415a9f689a6f

## References

[^1]: Parikh, [A Decomposable Attention for Natural Language Inference](https://arxiv.org/abs/1606.01933), 2016.

[^2]: Dang, [Quora Question Pairs - DL models](https://www.kaggle.com/lamdang/dl-models), 2017.

[^3]: Kaggle, [Quora Question Pairs](https://www.kaggle.com/c/quora-question-pairs), 2017.

[^4]: namakemono, [Decomposable Attention with Keras](https://gist.github.com/namakemono/f4f273dbc63fc2174940415a9f689a6f), 2017.

[^5]: Maximilien@DAMI, [Quora Question Pairs - 1st place solution](https://www.kaggle.com/c/quora-question-pairs/discussion/34355), 2017.

[^6]: explosion, [spaCy](https://github.com/explosion/spaCy/tree/master/examples/keras_parikh_entailment), 2017.

[^7]: Pennington et al., [Glove: Global vectors for word representation.](http://llcao.net/cu-deeplearning15/presentation/nn-pres.pdf), 2014.

[^8]: Milkolov et al., [Efficient Estimation of Word Representations in Vector Space](https://arxiv.org/pdf/1301.3781.pdf), 2013.

[^9]: Chollet, [Keras](https://github.com/fchollet/keras), 2016.

[^10]: lystdo, [LSTM with word2vec embeddings](https://www.kaggle.com/lystdo/lstm-with-word2vec-embeddings), 2017.