論文メモ: Distributed Representations of Words and Phrases and their Compositionality

前回の投稿で紹介したGloVeの論文を読もうと思ったのですが、先発のword2vecの論文をまだ読んでなかったので、先にそっちを読んだメモです。

なお、gensimのword2vecの実装を使った例を以前投稿してます。

ohke.hateblo.jp

Distributed Representations of Words and Phrases and their Compositionality

word2vecを提案したThomas Mikolovの論文はいくつかありますが、肝となるSkip-gramやNegative Samplingの説明が一番詳細そうだったので、今回はDistributed Representations of Words and Phrases and their Compositionality (arXiv) を読みます。

@article{DBLP:journals/corr/MikolovSCCD13,
  author    = {Tomas Mikolov and
               Ilya Sutskever and
               Kai Chen and
               Greg Corrado and
               Jeffrey Dean},
  title     = {Distributed Representations of Words and Phrases and their Compositionality},
  journal   = {CoRR},
  volume    = {abs/1310.4546},
  year      = {2013},
  url       = {http://arxiv.org/abs/1310.4546},
  archivePrefix = {arXiv},
  eprint    = {1310.4546},
  timestamp = {Mon, 13 Aug 2018 16:47:09 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/MikolovSCCD13},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Abstract

単語の分散表現の精度と学習速度の両方を改善するNegative samplingについて提案します。

1 Introduction

大量のテキストから高速に単語ベクトルを得られるSkip-gramを、Efficient estimation of word representations in vector space (arXiv) で提案しました。

Skip-gramでは、単語の周辺単語を予測するというタスクのもと、ニューラルネットワーク (NN) を学習させることで単語ベクトルを獲得します (Figure 1抜粋) 。

巨大な行列積をなくすことで、100,000,000,000単語の文書からでも、1日で単語ベクトル計算できます

f:id:ohke:20181027103154p:plain

本稿ではSkip-gramモデルを拡張します。

頻出単語をサブサンプリングすることで、2〜10倍の高速化し、また、低頻度の単語のベクトル表現の精度を改善
階層ソフトマックスに代わって、Noise Constrastive Estimationの簡易版を使うことで、高速化、および、頻出単語のベクトル表現の精度を改善

2 The Skip-gram Model

Skip-gramモデルは、文または文書内の周辺の単語を予測することで、単語ベクトルを得ます。

文内で $w_1,w_2,...,w_T$ の順番で単語が現れるとき、Skip-gramは以下の式 (対数確率の項) を最大化するベクトルを学習で見つけようとします。

$p(w_{t+j}|w_{t})$ は $w_{t}$ の周辺t-c番目からt+c番目内に単語が現れる確率を表します
cを大きくすることで、計算時間と引き換えに精度は高くなる

$\frac{1}{T}\sum_{t=1}^{T}\sum_{-c \leq j \leq c, j \neq 0} log p(w_{t+j}|w_{t})$

$p(w_{t+j}|w_{t})$ は以下のソフトマックスによって計算しています。

とはそれぞれ単語の入力・出力のベクトル表現 (W次元)
- NNの隠れ層のノードと出力層のノードに相当します
- 入力ベクトル $v_{w}$ が今回必要な単語ベクトル
- 出力ベクトル $v_{w}^{\prime}$ は、周辺単語の出現確率
Wはボキャブラリ数 (=単語の種類数) で、100,000〜10,000,000くらい

$p(w_{O}|w_{I}) = \frac{exp(v_{w_{O}}^{\prime T} v_{w_{I}})}{\sum_{w=1}^{W}exp(v_{w}^{\prime T}v_{w_{I}})}$

2.1 Hierarchical Softmax

現実的な計算量にするため、全結合ソフトマックス (入力層のノードが全ての出力層のノードに結びつく) の近似である階層ソフトマックスを使います。

全結合ソフトマックスでは、上の式の分母の計算量が大きすぎるためです

階層ソフトマックスでは、二分木で表現され、出力層 (W個) はその葉に対応します。これにより、Wではなく $log_{2}(W)$ ノードの計算のみで済みます。

加えて、2分ハフマン木によって頻出単語には短いコードを割り当てて近似することで、さらに学習を高速化しました。

2.2 Negative Sampling

階層ソフトマックスに代わって、Noise Constrastive Estimation (NCE, ソフトマックスを近似する手法) を単純化したNegative sampling (NEG) を定義します。

$P_{n}(w)$ の雑音分布からk個サンプリングして、そのサンプルのみで計算することでさらに粗く近似します。

$log \sigma(v_{w_{O}}^{\prime T}v_{w_{I}})+\sum_{i=1}^{k}\E_{w_{i} \sim P_{n}(w)} [log \sigma(-v_{w_{I}}^{\prime T}v_{w_{I}})$ ]

kのサイズは、小さなデータセットであれば5〜20、大きなデータセットであれば更に小さく2〜5で、実用上十分です。元々ボキャブラリ全て (100,000〜10,000,000) だった計算が、5〜20程度に収まるので、計算量は大幅に削減できます。

雑音分布 $P_{n}(w)$ はユニグラム分布 (単語の出現頻度分布) を3/4乗で正規化したものが、ユニグラム分布そのものや一様分布と比較して良かった

2.3 Subsampling of Frequent Words

頻出単語 ("in", "the", "a"など) は低頻度の単語と比較すると大きな情報量を持っていないので、頻出単語の学習頻度を以下式で下げます。

$f(w_{i})$ が単語の出現回数
tは閾値で $10^{-5}$ が良さそう

$P(w_{i})=1-\sqrt{\frac{t}{f(w_{i})}}$

3 Empirical Results

階層ソフトマックス (HS) 、NCS、NEG (kは5と15) で比較実験を行います。

2パターンの類推タスクの精度を比較
- 意味的な類推タスク
  - ex.1 "Germany":"Berlin" :: "France" : ? (正解は"Paris")
- 統語論的な類推タスク
  - ex.2 "quick":"quickly" :: "slow" : ? (正解は"slowly")
- いずれもベクトル加算で計算し、コサイン距離で最も近い単語で予測する

結果 (Table 1抜粋) を見ると、精度はNEGが最も良く、kを少なくしたりサブサンプリングを行うことで学習速度が向上することが確認できます。

kが大きいほど精度が良くなるが、学習に時間はかかるというトレードオフが伺える
NEG-5の場合、サブサンプリングによって精度が改善されているのが面白い

f:id:ohke:20181027170209p:plain

4 Learning Phrases

複数の単語からなるフレーズに拡張して、3と同じタスクを行った。
(3と類似のため、省略)

5 Additive Compositionality

Skip-gramで得られた単語ベクトルは単純な線形構造なので、ベクトル演算だけで意味の類推が可能となります (Table 5抜粋) 。

f:id:ohke:20181027215832p:plain

それぞれの単語ベクトルは周辺単語が現れる確率 (対数和) を最大にするように学習されているので、単語ベクトル同士の和はAND検索のように2つの単語と一緒に現れた単語のベクトルに近くなります。"Volga River"は、"Russian"や"river"といった単語と一緒に現れるので、"Russian"と"river"の和は"Volga River"の単語ベクトルと類似するようになるのです。

6 Comparison to Published Word Representations

下表 (Table 6抜粋) のとおり既存の他の手法と比較しても、妥当な単語ベクトルがリーズナブルに獲得できることがわかります。データが巨大化しても計算量が爆発しないことが、本手法のポイントです。

f:id:ohke:20181027215226p:plain

7 Conclusion

Skip-gramモデルのアーキテクチャの改善によって、もっと大量のデータでも効率的に学習できるようになりました。

頻出単語のサブサンプリングによって、学習の高速化と、低頻度の単語の単語ベクトルの精度向上
Negative samplingは、頻出単語の単語ベクトルの精度向上に寄与

適用にあたって考えないといけないのはモデルアーキテクチャとハイパパラメータ。

モデルアーキテクチャは、階層ソフトマックスとNegative samplingのどちらかを選ぶ必要がある
ハイパパラメータで重要なのは、ベクトル長、サブサンプリングの割合、ウィンドウサイズ

Skip-gramで得られた単語ベクトル同士を単純に足し算するだけでも面白い表現が得られ、Skip-gramが柔軟であることが伺えます。

け日記