Negative Samplingの復習 - 機械学習・自然言語処理の勉強メモ

はじめに

今更ですが、word2vecの高速化の計算手法である「Negative Sampling」について復習しました。
世は完全に「Transfomer」の趨勢ですが、勉強のために復習しました。

前に「階層的ソフトマックス」を説明している論文を読んでいて、これってどう実装すれば良いのかと思い、せっかくなので「Negative Sampling」も実装してみようと思ったのが、モチベーションです。

今回はnumpyを使用して、簡単な実装だけを行いました。
※簡単のため、正確ではない部分もあります。

後、word2vec、Negative Samplingの解説自体は既にたくさんの良記事があるので、詳しくは述べません。

全単語の出現確率の計算

ある単語が与えられた時、ターゲットとなる単語が出現する確率を求めます。

$\begin{aligned} p(y_{v}|y_{w})=\frac{\exp(y_{v},y_{w})}{\sum^V_{v=1}\exp(y_{v'},y_{w})} \end{aligned}$

$y_{v}$ などは隠れ層の出力であり、 $y_{v}\in\mathbb{R}^{\rm h}$ （ ${\rm h}$ は隠れ層の次元数）のベクトルとなります。
この辺についての詳細な背景は以下を読むことをお勧めします。

tkengo.github.io

では、簡単に行列を準備してみます。

import numpy as np

vocab_size = 100000
hidden_dim = 300
H = np.random.rand(vocab_size, hidden_dim)
H.shape  # (100000, 300)

今回、語彙数は100000、隠れ層の次元数は300としました。
行列Hは各単語の隠れ層の出力ベクトルからなる行列となります。

次に、ある単語が与えられた時、ターゲットとなる単語が出現する確率をソフトマックス関数を使って求めます。
先ほどの式を実装すると以下のようになります。

def softmax(x):
    e_x = np.exp(x - np.max(x))
    return e_x / e_x.sum()

source_idx = np.random.randint(vocab_size)
target_idx = np.random.randint(vocab_size)
p_target = softmax([np.dot(H[i], H[source_idx]) for i in range(vocab_size)])[target_idx]

最後の確率を求める計算では、語彙数分の内積計算を行っていることが分かります。
この繰り返し計算が非常にコストがかかるため、何とか高速化したいです。

Negative Sampling

全ての単語の内積計算をするのではなく、いくつかの負例を選択して損失計算を行います。
これは、NCE（Noise Contrastive Estimation）と言われる手法を発展させたものです。

Negative Samplingは、コーパス中の単語の頻度分布に基づいて行います。
では、コーパスの頻度分布を作ります。

n_corpus = 1000000
word_freq = np.random.randint(0, vocab_size, n_corpus)
# array([7847, 3041, 4726, ..., 9368, 6440, 6872])

word_dist = np.bincount(word_freq) / n_corpus
# array([1.3e-05, 1.0e-05, 5.0e-06, ..., 4.0e-06, 1.4e-05, 7.0e-06])

このコーパスは、先ほどの単語（各単語はインデックスに変換済）から構成されます。
※簡単のため、各単語の出現頻度は完全にランダムとしています。

各出現回数を総数で割ることで、単語の頻度分布が求められます。

この頻度分布に「0.75乗」をしたものを計算に利用します。
※「0.75乗」により、頻度分布の平滑化を行います。

word_dist = np.power(word_dist, 0.75) / np.sum(np.power(word_dist, 0.75))

この平滑化した頻度分布から、指定したサンプル数だけ負例を抽出します。

negative_samples = np.random.choice(range(vocab_size), size=5, p=word_dist, replace=False)
negative_samples  # array([8608, 4896, 5054, 3571,   37])

これにより、頻度分布を考慮したNegative Samplingが抽出できます。
これらを負例として損失関数に含めることで、負例の出現確率を低くするように学習が行われます。

最後に

一番大事なNegative Samplingですが、厳密にはNegative Samplingになっておりません。
実際は正例を除いてサンプリングする必要があるのですが、今回は省略しました。

とても簡単な実装でしたが、良い復習になりました。