word2vecのソースを読んでみた

単語の意味をベクトルで表現する手法であるword2vec。検索するといろんな方の解説が見つかります。その解説とソースコードを見比べながら、自分なりに勉強してみました。

今回はword2vecのC#実装であるWord2Vec.Netのソースで勉強しました。ロジックは元々のC言語による実装とほとんど同じなので、このソースで勉強しても問題ありません。また、この方がVisualStudioのデバッガが使えるので追いやすいです。

word2vecには学習アルゴリズムとして「C-BOW」と「Skip-gram」の２種類の手法が紹介されていますが、今回は「Skip-gram」について勉強しました。計算量を抑えるやり方としては「階層的ソフトマックス」と「Negative Sampling」の２種類がword2vecのプログラム中に実装されていますが、今回は「Negative Sampling」を勉強しましたので、そちらの処理をメモします。

間違った記述もあるかもしれませんが、その点はご容赦を。

なお、word2vecの勉強にあたって、一番参考にしたのがこちらの記事です。

けんごのお屋敷「Word2Vec のニューラルネットワーク学習過程を理解する」
http://tkengo.github.io/blog/2016/05/09/understand-how-to-learn-word2vec/

１．単語の意味のベクトル表現

ソースコードの解析をする前に、簡単にword2vecのおさらいをします。

単語の意味をベクトルで表現するというのがword2vecの特徴ですが、これはつまり
　東京 = {0.8, -0.01, 0.45, 0.23, ..... ,0.34, -0.56}
　夜景 = {0.76, 0.71, -0.92, -0.86, ...., 0.45, 0.22}
というように、それぞれの単語の意味をいくつかの数字の組み合わせで表す、ということです。デフォルトでは200個の数字の組み（＝200次元）で表すように動作します。

単語の意味をこのように表現すると、各単語の意味の類似性（＝関連性）をベクトルの内積を計算することで得られるようになります。

１．１ ベクトルの内積

ベクトルの内積の持つ性質については、以下のページに説明があります。
http://www.not-enough.org/abe/manual/cg-math-ad06/vector2.html

このページに紹介されている通り、ベクトルの内積は、その２つのベクトルがどれだけ同じ向きを向いているかどうかを表す数値になります。

ですので、関連性のある単語同士の内積の値が同じ方向を向いていることを示す値になり、関連性の無い単語の同士の内積の値が違う方向を向いていることを示す値になるように、機械学習により各単語のベクトル値を修正していけば良いわけです。

２．どのような単語を関連性があるとみなすか。

word2vecでは「ある単語の周辺の単語は、関連性のある単語」とみなして学習していきます。つまり、
　「今日　の　晩御飯　に　白米　と　お味噌汁　と　焼き魚　を　食べ　ました」
という文章があったときに（単語で分かち書きしています）、これらの単語はそれぞれ関連性のある単語として扱います。

word2vecでは、ある単語の周囲何単語までを関連性のある単語としてみなすか、というものをパラメータで指定することができます。デフォルトでは5単語となっているようですね。このパラメータは、ソースコード中では "window" という変数に代入されます。

２．１ 関連する単語が出現する確率

ある単語の周辺に、関連する単語が出てくる確率（例えば「晩御飯」という単語の周辺に「白米」という単語が出てくる確率）は、以下のようにソフトマックス関数であらわすことができます。

p(w_o|w_i) = \frac{\exp({v_{w_o}}^T・v_{w_i})}{\sum_{w_v\in V} \exp({v_{w_v}}^T・v_{w_i})}　    (式1)

注目する単語が$w_i$、周辺の単語が$w_o$です。$w_i$の意味を表すベクトルが$v_{w_i}$、$w_o$のベクトルが$v_{w_o}$です。今回の例の場合、$w_i$が「晩御飯」、$w_o$が「白米」ということになります。

$exp(x)$というのは$e^x$のことです。また、${v_{w_o}}^T・v_{w_i}$は、2つのベクトル$v_{w_o}$と$v_{w_i}$の内積を表しています。$V$は、文書データ中のボキャブラリーを示します。ここでいう「ボキャブラリー」というのは、word2vecに読み込ませた文書データ中に登場する重複を除外した単語の数です。例えば、「晩御飯」とか「白米」とかいう単語は文書データ中の至る所に出現する場合がありますが、何回出現したとしてもボキャブラリー数としてはそれぞれ１です。データベースでいうところの select distinctで取得される値と思ってもらえれば良いと思います。

なお、ソフトマックス関数については、こちらのページに分かりやすく書かれています。
http://mathtrain.jp/softmax

２．２ この方法では計算量が膨大になります

ここから、ベクトルの値の更新式を求めて学習を進めることはできるのですが（更新式についてはこちらのページを参照ください）、先ほど示した式1の計算量が非常に膨大になります。通常、ボキャブラリーの数が数万～数百万語になるため、分母の計算に非常に時間がかかるのが理由です。なので、なんらかの工夫をしないととても実用には耐えられません。

そこで、せっかくモデル化したのですが、このソフトマックス関数を使った方法はやめます。

２．３ 高速化の手法「Negative Sampling」

ここでword2vecでは、より高速に学習させる手法として2つの手法を用意しています。
　・Negative Sampling
　・階層的ソフトマックス
ここではNegative Samplingを説明します。

これは、window変数の範囲内にある単語については関連性の確率を高く、それ以外からランダムに選ばれた単語については確率を低くするように学習していく手法です。

着目する単語を$w_{i}$、選ばれた単語を$w_{o}$とし、$w_{o}$が$w_{i}$の関連する単語である確率を$p(w_o|w_i)$と表すと、$w_{o}$が関連しない単語である確率は、確率の定義から$1-p(w_o|w_i)$となりますよね。

ここで、$p(w_o|w_i)$の数式をシグモイド関数（ロジスティック関数とも呼ばれます）とします。0～1までの間でなだらかな曲線を描く関数で、確率の表現に使えるものです。

関連する単語である確率　：　p(w_o|w_i) = \sigma({v_{w_o}}^T・v_{w_i}) =  \frac{1}{1+exp(-{v_{w_o}}^T・v_{w_i})}

関連しない単語である確率 　：　1-p(w_o|w_i)

この２つの式から、以下のような関数を考えます。

E = -\log p(w_o|w_i)\prod_{w_v\in V_{neg}}(1-p(w_v|w_i))　（式２）

$V_{neg}$は、関連性の無い単語の集合です。つまり、変数windowで指定された範囲の外にある単語から選ばれた単語です。

この式ですが、いわゆるロジスティック回帰による最尤推定法です。通常この手の問題は、尤度関数を最大にするようにパラメータの値を求めていくのですが、自然対数を取る数式になっているので、この関数の値を最小にする単語ベクトルの値を求めていきます。

ここから、単語ベクトルの更新式（いわゆる損失関数）を微分して求めることになるのですが、それについては最初に紹介したこちらのページを参照してください。

なお、単語数のデフォルトでは5です。学習させる文書データの量が十分大きければ、2～5個程度の関連性のない単語を選ぶだけで十分な結果が得られるそうです。

３．ソースコード

それではword2vecのソースコードを読んだ結果、要点と思われる箇所をメモしていきます。

３．１ 単語データの構造

word2vecが訓練用の文書データ（日本語の場合、分かち書きされている必要があります）から単語を1つずつ読み込んでいくのですが、その単語データを以下の構造体で保持します。1単語につきこの構造体を1つ持ちます。

VocubWord.cs

internal struct VocubWord : IComparable<VocubWord>
{
    public long Cn { get; set; }        // 文書データ中でその単語が出てきた回数
    public string Word { get; set; }    // その単語の言葉（例えば「晩御飯」）
    public char[] Code { get; set; }    // 階層的ソフトマックスで使うハフマン木構造を表す値
    public int CodeLen { get; set; }    // Code[]. Point[]の終端インデックス番号
    public int[] Point { get; set; }    // ハフマン木の分岐点のインデックス番号

    public int CompareTo(VocubWord other)
    {
        return (int)(this.Cn - other.Cn);
    }
}

ご覧の通り5つの要素を持ちますが、Negative Samplingでは"Cn"と"Word"だけを知っていれば良いです。他の3つの要素はNegative Samplingでは使いません。

読み込んだ単語1つにつき上記の構造体に収めていくわけですが、読み込んだ単語は数万～数百万にもなります。word2vecでは、これらを下図のように管理しています。

読み込んだ単語の文字コードを利用して、以下に示すハッシュ関数で数値化します。

Word2Vec.cs

private uint GetWordHash(string word)
{
    int a;
    ulong hash = 0;
    for (a = 0; a < word.Length; a++) hash = hash*257 + word[a];
    hash = hash%VocabHashSize;
    return (uint) hash;
}

各単語をこの関数で数値化した値を保持するのが _vocabHash[] 配列です。そしてこのハッシュ値をインデックス番号として _vocab[] 配列から VocubWord 構造体を取り出せるように、VocabWord構造体を _vocab[] 配列に格納していきます。

例えば「晩御飯」という単語のハッシュ値を、上記の GetWordHash()メソッドで取得した結果が "25687" だとします。すると、_vocabHash[] 配列にこの番号が存在するかどうかを確認します。存在すれば、その単語の情報を持つVocabWord構造体が _vocab[] 配列中にあるはずです。_vocab[25687] とやって中のデータを参照すると、単語「晩御飯」の情報を持つVocabWord構造体を取り出すことができます。

３．２ 単語ベクトルの管理

単語のベクトルの管理をするのが _syn0[]配列です。下図のように各単語のベクトルを管理しています。

例えば「晩御飯」という単語のハッシュ値が "25687" で単語ベクトルの次元数が 200 だとすると、単語「晩御飯」のベクトルデータは、_syn0[25687 * 200 + 0]　～ _syn0[25687 * 200 + 199]までの範囲に格納されているわけです。

３．３ 関連しない単語のテーブル

Negative Samplingでは関連性のない単語をランダムに選び、そのベクトル値を無関係の方向に修正する処理を行います。その関連性の無い単語を、以下のメソッドで _table[] 配列に用意します。

Word2Vec.cs

private void InitUnigramTable()
{
    int a;
    double trainWordsPow = 0;
    double power = 0.75;
    _table = new int[TableSize];
    for (a = 0; a < _vocabSize; a++) trainWordsPow += Math.Pow(_vocab[a].Cn, power); // (1)
    int i = 0;
    var d1 = Math.Pow(_vocab[i].Cn, power)/trainWordsPow; // (2)
    for (a = 0; a < TableSize; a++)
    {
        _table[a] = i;
        if (a/(double) TableSize > d1)
        {
            i++;
            d1 += Math.Pow(_vocab[i].Cn, power)/trainWordsPow; // (3)
        }
        if (i >= _vocabSize) i = _vocabSize - 1;
    }
}

これは以下の数式の計算を行ってます。$U(w)$というのがその単語の文書データ中の出現回数です。実際のソースコードでは、VocabWord 構造体の Cn に相当します。

P(w) = \frac{U(w)^{3/4}}{\sum_{v=1}^{W}U(w_{v})^{3/4}}

分母の部分がプログラム中の(1)で計算され、この式全体の計算は(2)で実装されています。そして、配列の添字 a のテーブル全体の比率が、この(2)の計算値を上回ったら、d1の値に新たな単語の計算値を足しています（プログラム中の(3)）。そして、次の単語のハッシュ値が table[] 配列に入るわけです。

配列_vocab[]は単語の出現回数の降順でソートされています。つまり_vocab[].Cnの大きい順になっています。この条件でtable[]配列を上記のメソッドで初期化すると、以下の図のように単語のハッシュ値が格納されます。

関連性のない単語のランダムな選択なんて、_vocabHash[] 配列からランダムに選べばよいのでは？と思うのですが、こういう配列を用意することで、出現頻度の高い単語が、より選ばれやすくなります。

なお、3/4乗している理由は、実験の結果これが一番精度が高くなるかららしいです。こちらの本に書かれていました。
https://www.oreilly.co.jp/books/9784873116839/

３．４ 出現頻度の高すぎる単語は学習させない

実際の学習処理を行うメソッドである TrainModelThreadStart() に、下図に示すロジックがあります。

ロジック中の_sampleという変数は、コンストラクタでユーザーが指定する値です。ちょっと数式の意味が分かりませんが、Excelで実際に値を計算してみると見えてきます。

出現回数の多い単語の計算結果が低く、出現頻度の少ない単語の計算結果が高くなっています。これはつまり、あまりにも頻度の高い単語は学習の対象外にすることを目的としたロジックです。

日本語の場合、「など」「または」のような単語は文章中にたくさん出てきます。が、これらの単語は関連語の学習対象には含めたくありません。そのための措置だと思います。

ですがロジックを見てみると、すべての高頻度の単語を除外しているわけではないですね。ランダムに除外しています。これは、出現頻度の高い単語の中には、学習させたい単語もあるためだと思います。

３．５ 単語ベクトルの学習部分

先ほど説明した出現頻度の高すぎる単語を削除した単語データ（正確には単語のハッシュ値）が、配列「sen[]」に格納されます。この sen[] に格納されている単語のベクトル値を機械学習により修正していきます。

この配列 sen[] から、基準となる単語と、その周辺の単語の２つを指し示すポインタとなる変数が必要です。skip-gram法によるロジックでは、2つの変数「c」と「sentencePosition」がそれに当たります。

上記の変数 c は、for文のループカウンタ a から算出されており、1つずつインクリメントされながら学習対象の単語を拾い上げていきます。

上図中の lastWord 変数、word 変数に入った各単語のハッシュ値から 3.2 章で説明したやり方で、各単語ベクトルの格納先の先頭の配列インデックス値を得ます。ソースコード中では、それぞれ変数 l1、l2に格納されます。

　l1 = lastWord * <単語ベクトルの次元数>
　l2 = word * <単語ベクトルの次元数>

Word2Vec.cs中の以下のソースコードがSkip-gram & Negative Samplingによる機械学習ロジックです。

Word2Vec.cs

// NEGATIVE SAMPLING
if (_negative > 0)
{
    for (d = 0; d < _negative + 1; d++)
    {
        if (d == 0)
        {
            // for文の1回目のループでは、sentencePositionで示された単語を学習対象に選ぶ。
            target = word; // word = sen[sentencePosition]。
            label = 1;
        }
        else
        {
            // for文の2回目のループでは、関連性のない単語をランダムに選ぶ
            nextRandom = nextRandom * 25214903917 + 11;
            target = _table[(nextRandom >> 16) % TableSize];

            if (target == 0)
                target = (long)(nextRandom % (ulong)(_vocabSize - 1) + 1);

            if (target == word)
                continue;

            label = 0;
        }

        // "l1"が基準となる単語
        // "l2"はd=0の時には、周辺の単語。d>0の時には、ランダムに選ばれた関連性の無い単語。
        // _layer1Sizeは単語ベクトルの次元数（デフォルト値 = 200）

        l2 = target * _layer1Size;
        f = 0;

        for (c = 0; c < _layer1Size; c++)
            // 2つの単語ベクトルの内積を計算。
            f += _syn0[c + l1] * _syn1Neg[c + l2];

        // 内積の値がMaxExpの絶対値より大きい場合、シグモイド関数の定義により、1 or 0で計算する。
        if (f > MaxExp)
            g = (label - 1) * _alpha;
        else if (f < MaxExp * -1)
            g = (label - 0) * _alpha;
        else
            // 内積の値がMaxExpの絶対値以内だった場合、シグモイド関数の計算結果を収めたテーブルから値を取り出し、計算する。
            g = (label - _expTable[(int)((f + MaxExp) * (ExpTableSize / MaxExp / 2))]) * _alpha;  // (A)

        for (c = 0; c < _layer1Size; c++)
            neu1e[c] += g * _syn1Neg[c + l2];    // (B)

        for (c = 0; c < _layer1Size; c++)
            _syn1Neg[c + l2] += g * _syn0[c + l1];  // (B)'
    }
}

// Learn weights input -> hidden ... (C)
for (c = 0; c < _layer1Size; c++)
    _syn0[c + l1] += neu1e[c];

ソース中のコメントにも書きましたが、forループによる繰り返し処理により、window幅内の関連性のある単語のピックアップと、3.3章で説明した配列から選ばれた関連性のない単語のピックアップが行われています。

変数 f に2つの単語ベクトルの内積が計算され、その値を元に、損失関数の値が計算されます（ソース中のコメント(A)）。損失関数の式は、最初に紹介したこちらのページに書かれている以下の式になります。

\sigma({v}^T・v_{w_i}) -t

$v$ は、window幅から選ばれた単語のベクトル、もしくはランダムに選ばれた無関係の単語のベクトルです。$t$ の値は、関連する単語のときには 1 、無関係の単語の時には 0 です。ソースコードを見ると、この $t$ に当たる変数が label であることが分かります。そして、この損失関数に -1 を掛けたものを足しているのが (B) (B)'の部分です。勾配降下法で出てくる「損失関数の値を減算していく処理」を、このように実装しています。

ソース中の(C)の部分は、こちらのページに説明されている隠れ層の更新処理です。このページに書かれている以下の数式を算出しているのが、ソース中の(B)の行です。

\sum_{v\in{w_{O}}\cup N_{Neg}}(\sigma({v_{v}}^T・v_{w_i}) -t)v_{v}

以上の処理を読み込んだ各単語に対して繰り返し実行していきます。

参考資料

けんごのお屋敷「Word2Vec のニューラルネットワーク学習過程を理解する」
http://tkengo.github.io/blog/2016/05/09/understand-how-to-learn-word2vec/

ディープラーニングチュートリアル 応用編：言葉の『意味』表現〜word2vec〜
https://adtech.cyberagent.io/pr/?p=1489

O'Reilly Japan 「word2vecによる自然言語処理」
https://www.oreilly.co.jp/books/9784873116839/

Distributed Representations of Words and Phrases and their Compositionality
http://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf