久しぶりにGloVeを触ったので、ソースコードや数式も含めて紹介したいと思います。

tl;dr

GloVeはword embeddingsの手法の一つで、共起回数を観測値としたweighted matrix factorizationをAdaGradを用いて最適化させています。

GloVe

GloVeはWord2Vecのように、単語を密で低次元のベクトルを用いて表現するためのモデルの一種で(a.k.a word embedding, word representation)元論文はGloVe: Global Vectors for Word Representationです。ソースコードはこちらです。

目的関数

以下の関数を最小化させるようにパラメータの学習を行います。

\begin{align} J = \sum_{i,j=1}^{V} f(X _{ij}) (w_i \top \tilde w_j + b_i + \tilde b_j -\log X_{ij})^2 \nonumber \end{align}

Notation:

  • $V$: 語彙数。総単語数ではない。
  • $X_{ij}$: 単語iと単語jの共起回数。共起は文脈窓を用いて測ります。
  • $w$, $\tilde w$: モデルパラメータ。行列。語彙数×次元数。$w_i$とした時に、単語iにおけるベクトルになります。
  • $b$, $\tilde b$: バイアスパラメータ。語彙数の長さをもつベクトル。$b_i$とした時に、単語iにおけるバイアス値(スカラ)になります。

係数$f(x)$は以下で与えられます:

\begin{eqnarray} f(x) = \begin{cases} (x/x_{\rm max})^{\alpha} & ( \rm if ~ x \lt x _{max} ) \\ 1 & ( \rm otherwise ) \end{cases} \nonumber \end{eqnarray}

$x_{\rm max}$, $\alpha$はどちらもハイパーパラメータです。与えましょう。

この関数は出現回数が$x_{\rm max}$以下の単語(低頻度語)がパラメータの更新に対しての影響度を少なくするためのものです。

この目的関数はいわゆるweighted matrix factorizationの形です。matrix factorization系の論文は(少し前の)推薦システムの論文を拝見した方が理解が深まるかもしれません。これとか、これとか、これでしょうか。

この目的関数が意味するところ(特に$w_i \top \tilde w_j -\log X_{ij}$の部分)は「単語同士が共起すればするほど、それらの単語ベクトルの内積は大きくなる(=似た要素を持つようになる)」ということです。この話はWord2Vecと同様、分布仮説(似た単語は似た/近い文脈に出現する傾向にある)に基づいています。

あとは$\frac{ \partial J }{ \partial w }$, $\frac{ \partial J }{ \partial \tilde w }$, $\frac{ \partial J }{ \partial b }$, $\frac{ \partial J }{ \partial \tilde w }$の偏微分を求めて、勾配降下でパラメータを更新して行きます。論文ではAdaGradを用いているようです。

AdaGrad

SGDの場合、$\theta$をモデルパラメータ、学習率$\alpha$、$t$時点での勾配を$g_t$とした時、$t+1$におけるモデルパラメータの更新式は:

\begin{align} \theta_{t+1} \leftarrow \theta_t - \alpha g_t \nonumber \end{align}

ただ、実際には学習率はepochごとにどんどん減少させていくのがどうもセオリーらしいです。シンプルには0.99…をかけていくとか。 そこをうまく自動的に減衰させて行こうというのがAdaGradです。(Wikiにほとんど書いてある)

\begin{align} \theta_{t+1} \leftarrow \theta_t - \frac{ \alpha }{ \sqrt {1+\sum_i^t \theta_i} } g_t \nonumber \end{align}

分母の1を足しているのは過去の勾配の二乗和の値が小さくなりすぎて学習率が大きくなりパラメータが発散してしまうのを防ぐためです。glove.c#L82

HogWild!

さらにGloVeは高速化のため、glove.c#L314に書いてある通り、HogWild!を利用しています。Lock-free(複数のスレッド/プロセスが共有メモリへのR/WをMutex無しで行うこと)にモデルパラメータを更新していきます。基本的にスパースで、衝突による上書きが収束率にとってそこまで影響がないケース(そもそも衝突することが少ない)で使われるようです。

GloVeでは、全ての単語x単語ペアについてnum_threadsで分割した上で、各々のthreadで学習しているようです。glove.c#L315-L323

参考までにmatrix factorizationの並列化実装は他にもFPSGDDSGDがあります。衝突しないように分割/割り当てを行いましょうというシンプルなものです。

共起回数

論文中では、$X_{ij}$を単に利用していますが、実際には単語間の距離も考慮した式を利用しています。cooccur.c#L361

\begin{align} \frac {X_{ij}}{ \sum_k^{X _{ij}} d_k( i, j ) } \nonumber \end{align}

$d_k( i, j )$はk回目の共起における単語iと単語jの距離を表しています。例えば”You must not eat this cake”の文における$d(“eat”, “cake”)$は2といった感じです。

これにより先ほどの分布仮説のくだりにおいて「近ければ近いほど」という尺度が新たに追加されているようです。

学習部分

glove.c#L108-L161

for (a = 0; a < lines_per_thread[id]; a++) {
      fread(&cr, sizeof(CREC), 1, fin);
      if (feof(fin)) break;
      if (cr.word1 < 1 || cr.word2 < 1) { continue; }
      
      /* Get location of words in W & gradsq */
      l1 = (cr.word1 - 1LL) * (vector_size + 1); // cr word indices start at 1
      l2 = ((cr.word2 - 1LL) + vocab_size) * (vector_size + 1); // shift by vocab_size to get separate vectors for context words
      
      /* Calculate cost, save diff for gradients */
      diff = 0;
      for (b = 0; b < vector_size; b++) diff += W[b + l1] * W[b + l2]; // dot product of word and context word vector
      diff += W[vector_size + l1] + W[vector_size + l2] - log(cr.val); // add separate bias for each word
      fdiff = (cr.val > x_max) ? diff : pow(cr.val / x_max, alpha) * diff; // multiply weighting function (f) with diff

      // Check for NaN and inf() in the diffs.
      if (isnan(diff) || isnan(fdiff) || isinf(diff) || isinf(fdiff)) {
          fprintf(stderr,"Caught NaN in diff for kdiff for thread. Skipping update");
          continue;
      }

      cost[id] += 0.5 * fdiff * diff; // weighted squared error
      
      /* Adaptive gradient updates */
      fdiff *= eta; // for ease in calculating gradient
      real W_updates1_sum = 0;
      real W_updates2_sum = 0;
      for (b = 0; b < vector_size; b++) {
          // learning rate times gradient for word vectors
          temp1 = fdiff * W[b + l2];
          temp2 = fdiff * W[b + l1];
          // adaptive updates
          W_updates1[b] = temp1 / sqrt(gradsq[b + l1]);
          W_updates2[b] = temp2 / sqrt(gradsq[b + l2]);
          W_updates1_sum += W_updates1[b];
          W_updates2_sum += W_updates2[b];
          gradsq[b + l1] += temp1 * temp1;
          gradsq[b + l2] += temp2 * temp2;
      }
      if (!isnan(W_updates1_sum) && !isinf(W_updates1_sum) && !isnan(W_updates2_sum) && !isinf(W_updates2_sum)) {
          for (b = 0; b < vector_size; b++) {
              W[b + l1] -= W_updates1[b];
              W[b + l2] -= W_updates2[b];
          }
      }

      // updates for bias terms
      W[vector_size + l1] -= check_nan(fdiff / sqrt(gradsq[vector_size + l1]));
      W[vector_size + l2] -= check_nan(fdiff / sqrt(gradsq[vector_size + l2]));
      fdiff *= fdiff;
      gradsq[vector_size + l1] += fdiff;
      gradsq[vector_size + l2] += fdiff;
      
  }

Wが全てのパラメータを1つの長い1次元配列に格納しています。glove.c#L66-L84:

vector_size++; // Temporarily increment to allocate space for bias
for (b = 0; b < vector_size; b++) { // vector_size=単語ベクトルの次元とバイアスパラメータ  
  for (a = 0; a < 2 * vocab_size; a++) { // 2 * vocab_sizeで語彙数×次元の行列を2つ生成したことになる
    W[a * vector_size + b] = (rand() / (real)RAND_MAX - 0.5) / vector_size;
  }
}
vector_size--;

ちなみにWord2Vecでもこのような実装になってます。多次元配列による参照コストを減らそうといった理由なのでしょうか。

Tips

AdaGradの論文と比べてみてアルゴリズムが異なっていそうな部分:

  • gradsqという変数は過去の勾配をストレージしておくための変数なのですが、バイアスパラメータの部分でWを更新した後にgradsqに加算しています。
  • fdiff *= eta;とありますが、学習率をかけた後でgradsqに加算しています。

単語ベクトル

先述した通り、GloVeは単語ベクトルとして$w$と$\tilde w$が存在するのですが、実際には$w + \tilde w$の値で出力されます。

まとめ

さらに理解を深めたい/ハイパーパラメータの調節についてはWord2Vecも含め、この論文を参考にするといいかもしれません。