Red Green Black and White

NOZAWA Kento

Noise Contrastive Estimation と Negative Sampling

単語の分散表現を学習するときに softmax を使ったモデリングをすると分母の計算が遅いので NCE や Negative sampling といった高速な手法が使われます。この2つは、式が似ており Notes on Noise Contrastive Estimation and Negative Sampling

This objective can be understood in several ways. First, it is equivalent to NCE when and is uniform.

と言っています。ここでの This objective は negative sampling を指します。微妙に違う別の解釈が個人的にあったので書きます。ちなみに上記の引用のあとに別の解釈もありますが、この記事はまた別です。

前準備

Continuous Skip-gram model [1]

単語 が与えられたとき、その周囲の単語 を予測するように単語ベクトルを学習するモデルです。予測は softmax を使って

とされます。ただし、 は学習する単語ベクトルです。これを使って負の対数尤度

を最小化するように単語ベクトルを学習します。ただし、 は学習する系列長で は単語 の文脈語を含んだ bag-of-words です。

Negative sampling [2]

Skip-gram の softmaxの計算が重いので、negative sampling loss を考えます。 Skip-gram の negative sampling loss は以下のように定義されます:

ただし、

  • : logistic sigmoid function
  • : 個の負例単語の bag-of-words で ノイズ分布 から i.i.d. にサンプルされます
    • この実装である word2vec では が正例のときは に含みません。
  • 第2項目はサンプル近似

Noise Contrastive Estimation (NCE) [3]

NCE 自体はいろんな分布の近似に使えるものですが、ここでは単語ベクトルの学習時に出てくる softmax の近似のために使います。 この辺りは [4] と [5] が最初の論文だと思います。

NCE では正規化項(今回は softmax の分母)をパラメータだと思って推定します。あとで対数をとって評価するので、まず対数をとって

これの第2項目を とした式を とします:

単語ベクトルに加えてこの も学習します。これを使って NCE を使った損失関数は以下のように定義されます:

2項目を 個の負例を使ったサンプリング近似を考えると、最終的には以下のような損失関数を最小化します:

本題

引用に戻ると

This objective can be understood in several ways. First, it is equivalent to NCE when and is uniform.

とありますが、 がひっかかります(それなら計算量が softmax と同じだし…)。ここにいたるために、NCE が経験的に としてもちゃんと学習してくれることを使っています。それをしないで考えてみます。

定義に従って代入すると、

なので のとき、negative sampling と等しくなります。このときノイズ分布 が uniform でなくても成立します。

その他

NCE や negative sampling のような softmax の近似方法は 深層学習による自然言語処理 で触れられています。

としても学習することを self-normalization とか言います。ちなみにこれだと安定しないらしく にしたりとか色々なヒューリスティックが提案されています。

間違えてたらおしえてください @twitter


References

  1. Tomas Mikolov, Greg Corrado, Kai Chen, and Jeffrey Dean. Efficient Estimation of Word Representations in Vector Space. In ICLR Workshop, 2013. 

  2. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed Representations of Words and Phrases and their Compositionality. In NeurIPS, 2013. 

  3. Michael U. Gutmann and Aapo Hyvärinen. Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics. JMLR, 2012. 

  4. Andriy Mnih and Koray Kavukcuoglu. Learning Word Embeddings Efficiently with Noise-contrastive Estimation. In NeurIPS, 2013. 

  5. Andriy Mnih and Yee Whye Teh. A Fast and Simple Algorithm for Training Neural Probabilistic Language Models. In ICML, 2012. 

Newer >>