Negative Samplingの配列の作り方

Kento Nozawa
15 July 2017

はじめに

word2vecのNegativeSamplingを読んでいたらAliasメソッド的な処理に感動したので記事にする。

NegativeSamplingでは単語頻度に\(3/4\)乗した以下の分布から単語をサンプルしまくる。

\[P_n(w) = \frac{freq(w)^{\frac{3}{4}}}{Z}\]

ただし\(Z=\sum_{w \in W} freq(w)^{\frac{3}{4}}\)。この分布からどうやって速くサンプルを得るかという話。

本題

すごく単純で、長さ1e8の配列を作り、右辺の割合だけ該当する単語のインデックスを詰めるだけ。 例えば、インデックス0の単語について \(P_n(w=0) = 0.1\)だったら0から1e7までの要素が0

Aliasメソッドよりメモリを使うことになるが、1回の整数の乱数生成で済む。またAliasメソッドのような大小比較も発生しない。

ちなみにこの操作の前に頻度の降順で単語はソートされているので配列のインデックスが小さいほど、頻度の大きい単語のインデックスを要素にもつことになる。

その他

(alias or light) LDAでやるとしたら配列のサイズは小さくすれば使えそうな気がしました。Cython化も容易そうです。