Negative Sampling 前編

AIって結局何なのかよく分からないので、とりあえず100日間勉強してみた Day83


経緯についてはこちらをご参照ください。

AIって結局何なのかよく分からないので、とりあえず100日間勉強してみた Day0



■本日の進捗

  • Negative Samplingを理解


■はじめに

今回も「ゼロから作るDeep Learning②　自然言語処理編（オライリー・ジャパン）」から学んでいきます。

今回は、コーパスが増えることによるソフトマックスの計算負荷増大を回避するためのNegative Samplingを学んでいきます。

■Negative Sampling

Negative Samplingとは、単語埋め込みモデルの学習における計算コストを削減するための手法で、これまで用いてきたソフトマックスでの確率変換で計算負荷が増大していた問題を解消します。

この手法での損失は、ターゲットとその正解となるコンテキストの組み合わせ（正例）と、それ以外のコンテキスとの間違った組み合わせ（負例）をいくつか（5～20個）選択し、これらの損失を同時に計算して足し合わせていった結果を最終的な損失とします。

出現回数を元にした確率分布によってサンプリングが行われますが、その際に出現回数の少ない稀な単語に対して、出現回数の多い単語の確率にかき消されないように0.75乗することが推奨されています。

$$ P'(w_i) = \frac{P(w_i)^{0.75}}{\displaystyle \sum_{j}^{n} P(w_j)^{0.75}} $$

また、ソフトマックスによる多値分類からシグモイド関数を用いた二値分類に落とし込みます。

これらの手法により、語彙全体を毎回計算する必要がなくなり、大幅な計算コスト削減が望めます。

■EmbeddingDot層

これまでのCBoWでは、Embedding層を通して埋め込み行列を取り出した後に、MatMul層で行列計算を行っていました。

$$ \mathrm{out} = \mathrm{\boldsymbol{W}}_{\mathrm{target}} \cdot \mathrm{\boldsymbol{h}} $$

●順伝播

埋め込み行列の取得と行列積を個別に行うため、余分な計算コストが必要になりますが、逆を言えばこれらを同時に行うことで計算コストを削減することができます。

$$ \mathrm{out} = \mathrm{sum}(\mathrm{\boldsymbol{W}}_{\mathrm{target}} \cdot \mathrm{\boldsymbol{h}}, \mathrm{axis}=1) $$

●逆伝播

先ほどの順伝播の式を埋め込み行列で偏微分をすれば、

$$ \frac{\partial \mathrm{out}}{\partial \mathrm{\boldsymbol{W}_{target}}} = \mathrm{\boldsymbol{h}} $$

ここで損失に対する埋め込み行列の勾配は、連鎖律を用いて、

$$ \frac{\partial \mathrm{Loss}}{\partial \mathrm{\boldsymbol{W}_{target}}} = \frac{\partial \mathrm{Loss}}{\partial \mathrm{out}} \cdot \frac{\partial \mathrm{out}}{\partial \mathrm{\boldsymbol{W}_{target}}} $$

ここで、doutを下記のように定義すれば、

$$ \mathrm{dout} = \frac{\partial \mathrm{Loss}}{\partial \mathrm{out}} $$

以上から、

$$ \frac{\partial \mathrm{out}}{\partial \mathrm{\boldsymbol{W}_{target}}} = \mathrm{dout} \cdot \mathrm{\boldsymbol{h}} $$

●実装

まずは単語埋め込み行列であるWを引数として受け取り、Embeddingクラスのインスタンスを作成します。cacheは逆伝播で利用するための順伝播で求めた入力ベクトル（h）とターゲットベクトル（target_W）を保持しておくためのものです。

class EmbeddingDot:
    def __init__(self, W):
        self.embed = Embedding(W)
        self.params = self.embed.params
        self.grads = self.embed.grads
        self.cache = None

順伝播では、Embeddingクラスのインスタンスであるembedのfoward関数を呼び出し、入力として得たidxに対応する埋め込み行列Wを取得します。

その後すぐさま行列積を計算し計算結果（out）に足し合わせていきます。

    def forward(self, h, idx):
        target_W = self.embed.forward(idx)
        out = np.sum(target_W * h, axis=1)

        self.cache = (h, target_W)
        return out

逆伝播では、出力に対する損失勾配（dout）を後のベクトル演算のためにreshapeしてから、ターゲットの単語埋め込み行列に対する損失（dtarget_W）を求めます。

実際には順伝播でもEmbeddingクラスを用いていたので、ここでもEmbeddingクラスのインスタンスであるembedのbackwardクラスに先ほどの勾配（dtarget_W）を渡して、埋め込み行列Wの該当箇所を更新するための勾配を計算します。

最後に入力ベクトル（h）に対する勾配（dh）を計算し、逆伝播の結果として入力層へ損失勾配を伝播します。

    def backward(self, dout):
        h, target_W = self.cache
        dout = dout.reshape(dout.shape[0], 1)

        dtarget_W = dout * h
        self.embed.backward(dtarget_W)
        dh = dout * target_W
        return dh



■UnigramSampler

サンプリングの基になる確率分布を求めるUnigramSamplerクラスを構築します。冒頭で提示した確率分布で負例を選べるようにしていきます。

$$ P'(w_i) = \frac{P(w_i)^{0.75}}{\displaystyle \sum_{j}^{n} P(w_j)^{0.75}} $$

まずは確率分布を格納するためのword_p配列などを初期化したら、コーパス内の出現回数をcollections.Counter()にカウントしていきます。

語彙（vocab_size）と同じサイズにしたword_p配列に出現回数を格納したら、これを用いて確率分布を決定します。

class UnigramSampler:
    def __init__(self, corpus, power, sample_size):
        self.sample_size = sample_size
        self.vocab_size = None
        self.word_p = None

        counts = collections.Counter()
        for word_id in corpus:
            counts[word_id] += 1
        
        vocab_size = len(corpus)
        self.vocab_size = vocab_size

        self.word_p = np.zeros(vocab_size)
        for i in range(vocab_size):
            self.word_p[i] = counts[i]
        
        self.word_p = np.power(self.word_p, power)
        self.word_p /= np.sum(self.word_p)

続いて全体の確率分布に基づいて負例をサンプリングしていきます。

    def get_negative_sample(self, target):
        batch_size = target.shape[0]
        negative_sample = np.zeros((batch_size, self.sample_size), dtype=np.int32)

        for i in range(batch_size):
            target_idx = target[i]
            
            p = self.word_p.copy()
            p[target_idx] = 0
            total_p = 1 - self.word_p[target_idx]
            p /= total_p

            negative_sample[i, :] = np.random.choice(self.vocab_size, size=self.sample_size, replace=False, p=p)

        return negative_sample



■Sigmoid With Loss層

冒頭で述べた通り、Negative Samplingではソフトマックスではなくシグモイド関数を用います。ここではシグモイド関数と交差エントロピー誤差を組み合わせた層を構築していきます。

まずは変数を初期化します。self.yはシグモイド関数の出力を格納するためのもので、self.tは逆伝播用に正解ラベルを保持しておくためのものです。

class SigmoidWithLoss:
    def __init__(self):
        self.params, self.grads = [], []
        self.loss = None
        self.y = None
        self.t = None

順伝播は通常のシグモイド関数と同じですが、その結果を用いてそのまま交差エントロピー誤差を算出します。

    def forward(self, x, t):
        self.t = t
        self.y = 1 / (1 + np.exp(-x))

        self.loss = cross_entropy_error(np.c_[1 - self.y, self.y], self.t)

        return self.loss

逆伝播も同様です。

    def backward(self, dout=1):
        batch_size = self.t.shape[0]

        dx = (self.y - self.t) * dout / batch_size
        return dx



■Negative Samplingクラス

それではこれまで構築してきたクラスを用いて、Negative Samplingを行うためのクラスを実装していきます。

まずはUnigramSamplerでサンプリングをしたら、シグモイド関数と交差エントロピー誤差の層と、Embeddingと行列積を行う層を定義して、勾配を格納していきます。

class NegativeSamplingLoss:
    def __init__(self, W, corpus, power=0.75, sample_size=5):
        self.sample_size = sample_size
        self.sampler = UnigramSampler(corpus, power, sample_size)
        self.loss_layers = [SigmoidWithLoss() for _ in range(sample_size + 1)]
        self.embed_dot_layers = [EmbeddingDot(W) for _ in range(sample_size + 1)]

        self.params, self.grads = [], []
        for layer in self.embed_dot_layers:
            self.params += layer.params
            self.grads += layer.grads

foward関数ではUnigramSampler.get_negative_sampleにて負例でサンプリングしたら各層の順伝播を行います。

正例のスコアを入力ベクトル（h）と正例のターゲット（target）の行列積で算出し、正例を1でラベル付け（correct_label）したら、これらの値を用いて損失（loss）を算出します。

今度は入力ベクトル（h）と負例のターゲット（negative_target）の行列積と、負例を0でラベル付け（negative_label）したら、これらを用いて先ほど算出した正例の損失に負例の損失を加算して返り値とします。

    def forward(self, h, target):
        batch_size = target.shape[0]
        negative_sample = self.sampler.get_negative_sample(target)

        score = self.embed_dot_layers[0].forward(h, target)
        correct_label = np.ones(batch_size, dtype=np.int32)
        loss = self.loss_layers[0].forward(score, correct_label)

        negative_label = np.zeros(batch_size, dtype=np.int32)
        for i in range(self.sample_size):
            negative_target = negative_sample[:, i]
            score = self.embed_dot_layers[1 + i].forward(h, negative_target)
            loss += self.loss_layers[1 + i].forward(score, negative_label)
        
        return loss

backward関数では、シグモイド関数と交差エントロピー誤差の層と、Embeddingと行列積の層を順番に逆伝播の処理を行い、これらの勾配を入力ベクトル（h）に対する勾配dhに加算していきます。

    def backward(self, dout=1):
        dh = 0
        for l0, l1 in zip(self.loss_layers, self.embed_dot_layers):
            dscore = l0.backward(dout)
            dh += l1.backward(dscore)

        return dh



■おわりに

今回はNegative Samplingで用いる各クラスを実装しました。これらのクラスで、これまで用いてきたCBoWやSkipGram同様にコーパスを学習するように完成させていきたいと思います。

■参考文献

  1. Andreas C. Muller, Sarah Guido. Pythonではじめる機械学習. 中田 秀基 訳. オライリー・ジャパン. 2017. 392p.
  2. 斎藤 康毅. ゼロから作るDeep Learning Pythonで学ぶディープラーニングの理論と実装. オライリー・ジャパン. 2016. 320p.
  3. 斎藤 康毅. ゼロから作るDeep Learning② 自然言語処理編. オライリー・ジャパン. 2018. 432p.
  4. ChatGPT. 4o mini. OpenAI. 2024. https://chatgpt.com/
  5. API Reference. scikit-learn.org. https://scikit-learn.org/stable/api/index.html
  6. PyTorch documentation. pytorch.org. https://pytorch.org/docs/stable/index.html
  7. Keiron O’Shea, Ryan Nash. An Introduction to Convolutional Neural Networks. https://ar5iv.labs.arxiv.org/html/1511.08458
  8. API Reference. scipy.org. 2024. https://docs.scipy.org/doc/scipy/reference/index.html

hammertime

, ,
, , , ,

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です