tl;dr

せっかくなのでWord2Vecも書こうと思いました。

Word2Vec

今回も数式とソースコードを交えて書き留めていきたいと思います。

元論文はDistributed Representations of Words and Phrases and their Compositionalityです。

Word2Vecは総称のようなもので、具体的には以下の2つのコンポーネントの組み合わせです:

Model

  • Continuous Bag of Words (CBOW)
  • Skip-Gram

Optimizer (Approximater?)

  • Hierarchical Softmax
  • Negative Sampling

今回はSkip-GramについてHierarchical SoftmaxとNegative Samplingを紹介していきたいと思います。

Skip-Gram

Skip-Gramは以下の目的関数を最大化するようにパラメータの学習を行います:

\begin{align} E=\frac{1}{T} \sum_{i}^{T} \sum_{i-c \leq j \leq i+c} \log P(w_j|w_i) \nonumber \end{align}

長さ$T$のコーパスについて各単語$w_i$に対して前後$c$に隣接する単語$w_j$が出現する条件付き確率$p(w_j|w_i)$で構成されています。また、$p(w_j|w_i)$は以下で定義されています。

\begin{align} P(w_j|w_i) = \frac{\exp (v_i \top v’_j)}{\displaystyle \sum^K_k \exp (v’_k \top v_i)} \nonumber \end{align}

コーパスの大きさにもよりますが、基本的には分母の計算量が膨大なため(語彙数に比例する)、Hierarchical SoftmaxとNegative Samplingで近似的な目的関数を定義することで計算時間の効率化が主な内容です。

Hierarchical Softmax

Hierarchical Softmaxは葉が単語で出現回数を元に構成されたハフマン木を構築します。

hierarchical_softmax

NODE(ノード)がベクトルを持っており、該当する単語のパス上に存在するノードを参照しながら単語ベクトルの更新を行います。

Hierarchical Softmaxにおける$P(w_j|w_i)$は論文に倣って記述すると以下の通りです:

\begin{align} P(w_j|w_i)=\prod_{l=1}^{L(w_j)-1} \sigma{([\![n(w_j, l+1)=ch(n(w_j, l))]\!] \cdot {v’}_{n(w_j, l)}^\top v_{w_i})} \nonumber \end{align}

$\sigma(x)$はシグモイド関数を表します。説明のため、この数式を少し書き換えてみます。

\begin{align} P(w_j|w_i) = \prod_{l=1}^{L(w_j)-1} \frac {\exp \{(1-c_l) \cdot v_l \top v_i\} }{1 + \exp (v_l \top v_i) } \nonumber \end{align}

\begin{eqnarray} \log P(w_j|w_i) &=& \sum_{l=1}^{L(w_j)-1} \log \frac {\exp \{(1-c_l) \cdot v_l \top v_i\} }{1 + \exp (v_l \top v_i) } \nonumber \\
&=& \sum_{l=1}^{L(w_j)-1} [ (1-c_l) \cdot v_l \top v_i - \log \{1 + \exp (v_l\top v_i) \} ] \nonumber \end{eqnarray}

Notation

  • $L(w_j)-1$: ハフマン木におけるルートから単語$w_j$の直前までのパス。
  • $c_l$: パスlの地点におけるのコード。0, または1。
  • $v_l$: 単語パスlの地点におけるノードのベクトル。
  • $v_i$: 単語$w_i$のベクトル。

ちなみに

if $c_l=1$: \begin{eqnarray} P(w_j|w_i) &=& \prod_{l=1}^{L(w_j)-1} \frac {1}{1 + \exp (v_l \top v_i) } \nonumber \\
&=& 1 - \sigma (v_l \top v_i) \nonumber \end{eqnarray}

if $c_l=0$: \begin{eqnarray} P(w_j|w_i) &=& \prod_{l=1}^{L(w_j)-1} \frac {\exp \{v_l \top v_i\}}{1 + \exp (v_l \top v_i) } \nonumber \\
&=& \sigma (v_l \top v_i) \nonumber \end{eqnarray}

2分木上のどちらのパスを辿ったかの確率の掛け合わせで目的関数を表現していることがわかります。

パラメータは$v_l$、および$v_i$で勾配法を用いて更新されます。したがって$v_l$、$v_i$における偏微分$\frac{\partial \log P(w_i|w_j)}{\partial v_i}$、$\frac{\partial \log P(w_i|w_j)}{\partial v_l}$は:

\begin{align} \frac{\partial \log P(w_j|w_i)}{\partial v_i} = \sum_{l=1}^{L(w_j)-1} v_l \left[1 - c_l - \frac {\exp \{(1-c_l) \cdot v_l \top v_i\} }{1 + \exp (v_l \top v_i)} \right] \nonumber \end{align}

\begin{align} \frac{\partial \log P(w_j|w_i)}{\partial v_l} = v_i \left[1 - c_l - \frac {\exp \{(1-c_l) \cdot v_l \top v_i\} }{1 + \exp (v_l \top v_i)} \right] \nonumber \end{align}

Negative Sampling

Negative SamplingはNoise Contrastive Estimationの拡張です。共起しなかった単語から負例としてサンプリングを行い、そのベクトルを用いて学習を行います。

\begin{align} P(w_j|w_i) = \sigma(u_j \top v_i) \prod_{k=1}^{K} \sigma(-u_k \top v_i) \nonumber \end{align}

\begin{align} \log P(w_j|w_i) = \log \sigma(u_j \top v_i) + \sum_{k=1}^{K} \log \sigma(-u_k \top v_i) \nonumber \end{align}

Notation

  • $v_j$: 単語$w_j$のベクトル。
  • $K$: サンプル数。
  • $u_i$, $u_k$: 単語$u_i$、およびサンプルされた単語におけるコンテクストベクトル。Negative Samplingで学習を行う際は単語ベクトルとは別に同じサイズのベクトルを用意しています。このベクトルもパラメータとして扱い、サンプリングされた単語やターゲットから見て共起している単語はこちらのベクトルを利用して学習を行います。

パラメータは$u_j$, $u_k$, $v_i$でHierarchical Softmaxと同様に勾配法を用いて学習を行います。したがって$u_j$, $u_k$, $v_i$における偏微分$\frac{\partial \log P(w_j|w_i)}{\partial u_j}$, $\frac{\partial \log P(w_j|w_i)}{\partial u_k}$, $\frac{\partial \log P(w_j|w_i)}{\partial v_i}$は:

\begin{align} \frac{\partial \log P(w_j|w_i)}{\partial u_j} = 1 - \sigma(u_j \top v_i) \cdot v_i \nonumber \end{align}

\begin{align} \frac{\partial \log P(w_j|w_i)}{\partial u_k} = - \sigma(u_k \top v_i) \cdot v_i \nonumber \end{align}

\begin{align} \frac{\partial \log P(w_j|w_i)}{\partial v_i} = 1 - \sigma(u_j \top v_i) \cdot u_j - \sum_{k=1}^{K} \log \sigma(-u_k \top v_i) \cdot u_k \nonumber \end{align}

Others

Subsampling

出現頻度の極端に高い単語はそのほかの単語に比べると情報量が少ないので、学習には利用しないようにしています。そのためにSubsamplingと呼ばれるテクニックが紹介されています。論文中に記述されているSubsamplingの式は以下の通りです。

\begin{align} p(w_i)=\sqrt \frac{t}{f(w_i)} \nonumber \end{align}

$f(w_i)$は$w_i$の学習コーパス内における出現回数を表します。$p(w_i)$は学習に利用するかどうかの確率として扱います。ただ、実装を見てみると若干式の差異が見られます:

// The subsampling randomly discards frequent words while keeping the ranking same
if (sample > 0) {
  real ran = (sqrt(vocab[word].cn / (sample * train_words)) + 1) * (sample * train_words) / vocab[word].cn;
  next_random = next_random * (unsigned long long)25214903917 + 11;
  if (ran < (next_random & 0xFFFF) / (real)65536) continue;
}

これを数式で表すと:

\begin{align} p(w_i)=\left(\sqrt \frac{g(w_i)}{t} + 1\right) \cdot \frac{t}{g(w_i)} \nonumber \end{align}

$t$ is a chosen threshold, typically around $10^{-5}$.

$g(w_i)$は$w_i$の出現頻度をコーパス内の総単語数で割った値です。$p(w_i)$は先と同様に単語$w_i$が学習に含まれるかどうかの確率です。言い換えると、$g(w_i)$の値が大きい、つまり$w_i$の出現頻度が多い場合(andtheのような単語が含まれる可能性が高いです)、$p(w_i)$は小さい値をとるため無視されやすくなるというわけです。

つまり、式は違えど上記の$P(w_i)$らは同じことを意味しています。ご参考程度に、グラフの形状は以下の通りです:

subsample

まとめ

GloVeも合わせて実装しました → wego