ACL2021 best paper 紹介

# はじめに
[TDU_データ科学・機械学習研究室AdventCalendar](https://qiita.com/advent-calendar/2021/dsml-tdu)6日目
今回は, 2021年のACLにおいてbest paperに選出された論文を紹介する.
論文内における数式部分の紹介は後日修正してアップロードします.

ACL2021のbest paperは, Vocabulary Learning via Optimal Transport
for Neural Machine Translation という語彙の辞書作成に関する論文でした.

# 書誌情報

 - タイトル
    - Vocabulary Learning via Optimal Transport for Neural Machine Translation
 - 著者
    - Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, Lei Li
 - 出典
    - ACL-IJCNLP 2021
 - URL
    - [https://aclanthology.org/2021.acl-long.571.pdf](https://aclanthology.org/2021.acl-long.571.pdf)

# 概要
この論文は, 辞書を作成する手法の提案論文. 既存手法と比較して少ない語彙数で下流タスクのSOTAを達成し, 辞書作成にかかる時間も大幅に削減することが出来た.

# そもそも辞書って何？
自然言語処理において, 人間が理解できる文章を機会が理解できるデータに変換する必要がある. 
このとき, 何かしらのルールに則ってデータに変換しなければならない.
コンピュータ内での処理においても同様に変換ルールが存在し, 文字コードというものがある.
厳密に言えば, 文字コードは変換ルールを指すのではなく, 自然言語をバイト表現したものを指す. 具体的な文字コードとしては, ASCII, JISコードやUnicodeなどがある.
自然言語処理において, このように自然言語を数値データに変換する処理をtokenize（トークナイズ）といい, これまでにBPE（Byte Pair Encoding）やSentence Pieceなど様々な手法が提案されてきた.
これらの手法で作成されるのが, 自然言語と数値が一対一で対応する辞書である.
今回紹介する論文の内容は, この辞書に着目したものになる.

# 辞書作成の流れ
ここでは, BPEのアルゴリズムをざっくりと紹介する.

1. 単語分割された文を入力
2. 単語を文字単位に分割しリスト化
3. bi-gramの頻度を各リストごとに計算
4. 最頻殿bi-gramに従って文字を結合

文字列を連続したn個の文字で分割することを一般的にはn-gramと表記し, n=2のときをbi-gramと言う. この分割対象を単語とするか, 文字とするかは場合によると思われる.
BPEは, このbi-gramの出現頻度に基づいて文字列を決定するため, 頻出であれば単語として扱われ, 頻度が低ければ文字として扱われるといった性質を持つ. 
辞書の問題点には, 

- 未知語
    - 辞書にない単語
- 低頻度語
    - 辞書には存在するが, 出現頻度が低い語

といったものが挙げられる.
未知語は辞書にない為, 機械が扱うことが出来ない. また, 低頻度語は出現頻度が低い為, 辞書に入れる意味が薄く辞書のサイズが無駄に多くなってしまう可能性が出てくる.
BPEは単語レベルと文字レベルのバランスをとったサブワードという概念に基づいた辞書作成を行うため, 上記の問題点をある程度解決できた手法である.

# 新規性・提案手法
### 構成要素
この論文では, 最適化における最適輸送（Optimal Transport）という手法を用いる.
新規性として, MUV（Marginal Utility Vocablarization）という経済学における限界効用（Marginal Utility）という概念を語彙選択の基準に応用したことが挙げられる.
限界効用とは, サービスなどを消費することで得られる満足度の増加分を指す.
MUVは, サービスの消費を語彙数の増加, 満足度をエントロピーの減少として考えて, これを最適化することで, 辞書の語彙を選択する.
MUVの式を以下に示す（原著論文より引用）.

```math
\mathcal{M}_{v(k+m)}=\frac{-\left(\mathcal{H}_{v(k+m)}-\mathcal{H}_{v(k)}\right)}{m}\\
\mathcal{H}_{v}=-\frac{1}{l_{v}} \sum_{i \in v} P(i) \log P(i)\\
\mathcal{H}_{v}:エントロピー\\
v(k):語彙サイズがkの時の辞書にある語彙\\
m:任意の定数\\
l(v):語彙の平均長\\
P(j):語彙の出現確率
```

最適輸送は, MUVを定式化する際に, 式を簡単にしていく過程で用いる. 最適輸送を用いることで, 本来は解くのが難しい問題を最適輸送で用いられるSinkhorn-Knoppアルゴリズムで最適化することが可能になる.
### 辞書作成モデル
辞書作成モデルとして, VOLT（VOcabulary Learning approach via optimal Transport）を提案する.
VOLTの簡単なアルゴリズムは, 

1. 学習データをサブワード化（既存手法を使用）
2. 複数の語彙サイズを用意
3. 最適輸送を用いたアルゴリズムに大河って語彙を選択
4. 辞書の完成

また, 論文内にあるアルゴリズムを以下に示す（原著論文より引用）.
![スクリーンショット 2021-12-06 002545.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2270853/aeb0973a-7b99-aefe-bcce-c926c6a16488.png)

# 提案手法と既存手法の差異
比較対象となるBPEをはじめ, 既存手法の問題点として

- 語彙数を人手によって決定する点
- 最適な語彙を出現頻度やエントロピーなど1つでのみ決定する点

が挙げられる.
提案手法は, これらの問題点に対して

- 語彙数は, 複数の候補の中から自動的に選択
- 最適な語彙は, 出現頻度とエントロピーの両方を考慮

を行った.

# 実験
BPE（既存手法）とVOLT（提案手法）を比較することで, 提案手法の有効性を示した.
ここでは, そのうちの一部を紹介する.
データセットには, WMT-14, TEDいう2種類の翻訳データセットを用いた.
評価指標にはBLEUを用いた.
WMT-14は英独翻訳データセットで, TEDは英語を複数言語に翻訳するデータセットになっている.
また, BLUEは機械が生成した文章が正解となる文章とどれだけ一致しているかによって計算される. 一致度にはn-gramを用いており, n=1,2,3,4とそれぞれ計算しその平均をとる.
ここでは, データセットと評価指標に関する詳しい解説は割愛する.
### 結果1
まず, 単純に上記のデータセットを用いて, 辞書作成, モデルの学習を行い, モデルの評価を行った結果を示す（原著論文より引用）.
![スクリーンショット 2021-12-06 121942.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2270853/be52ec58-675c-3b02-ba0e-b296d8d82f38.png)

黒太文字になっている箇所に着目すると, 英語からドイツ語, ドイツ語から英語のどちらに関しても, VOLTの方がほとんど精度が高い結果となった.
また, 語彙サイズに着目しても, VOLTの方が少ない語彙数で辞書が作成されていることがわかる.
### 結果2
次にBPEの辞書サイズをデータセットに合わせて変化させた結果を示す（原著論文より引用）.
![スクリーンショット 2021-12-06 122031.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2270853/1047aa5d-4373-4137-0fdf-e1620c48604c.png)

辞書のサイズは, データセットの大きさにある程度比例させると良いことがわかっており, データセットが小さいときは辞書サイズも小さく, データセットが大きいときは辞書サイズも大きくすると良い結果が出やすい.
BPEをデータセットの大きさに従って, 辞書サイズを変化させてVOLTと比較した結果である.このことからも, VOLTが最適な辞書サイズを選択することが出来ていることがわかる.
### 結果3
次は, 辞書作成にかかる時間コストの比較を行った実験結果である.
比較した対象は, 

- BPE-search
    - 複数の語彙サイズに従った辞書を作成, それぞれに対して学習・評価を実施
- MUV-search
    - 複数の語彙サイズに従った辞書を作成, MUVが最大となる辞書のみ学習・評価を実施
- VOLT
    - あらかじめサブワード分割された辞書と, 語彙サイズ候補を用いて, 輸送行列を求め, 作成された辞書で学習・評価

結果, VOLTが最も時間コストが小さかった.
以下に結果の表を示す（原著論文より引用）.
![スクリーンショット 2021-12-06 122134.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2270853/a40575a5-3db4-b062-64cd-6ce74524bb62.png)

### 結果4
最後に, モデルを変化させて, モデルによらず一貫した性能改善を確認した実験も行っている.
結果として, モデルの構造に寄らずVOLTが良い性能を示した.
いかに結果の表を示す（原著論文より引用）.
![スクリーンショット 2021-12-06 122235.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2270853/d2257aca-26ec-35f0-4cf7-5ce4a815e2dc.png)

# おわりに
今回は, ACL2021のbest paperを紹介した.
正直まだ, 完全に理解したわけでは無いため, また勉強していき随時更新していきたい.
また, ACL以外の国際会議などのbest paperもしっかり読んで, 紹介したい.

# 参考文献

- BPEについて
    - [https://www.slideshare.net/ssuserd79a5c1/2019bpe](https://www.slideshare.net/ssuserd79a5c1/2019bpe)
- BLEUについて
    - [4. 自動評価尺度 BLEU](https://www2.nict.go.jp/astrec-att/member/mutiyama/corpmt/4.pdf)
- VOLTについて
    - [ACL2021のBest PaperのVOLTを日本語文書分類で試してみた結果...！ - Retrieva TECH BLOG](https://tech.retrieva.jp/entry/2021/08/25/185920#VOLT%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
    - https://docs.google.com/presentation/d/e/2PACX-1vTAW6uxcVSYYJkK7-8GZ9UqViMaBTdGMV50Sz0dG5JLOeNS--81syxgXc-rcGJtGhMzxGuallJhPVsD/pub?start=false&loop=false&delayms=3000&slide=id.geed76ef35e_0_63
    - [著者らのブログ](https://jingjing-nlp.github.io/volt-blog/)
- 最適輸送について
    - [https://theory-and-me.hatenablog.com/entry/2021/05/09/181435](https://theory-and-me.hatenablog.com/entry/2021/05/09/181435)