2034


word2vecに付属しているベクトル空間で単語同士が似ているかを計算させるdistance.cというプログラムはとても動作が軽快です。

1単語を表すベクトルは200次元

単語のエントリー数は20万語

この条件でも上位40位の単語候補が1秒未満で出力されます。プログラムコード内にどのような工夫が施されているのでしょうか？ぱっと見たところ、全単語に対して探索を行っているように思えるのですが、その工夫がよくわかりません。

また、入力するベクトルの次元数は任意で、どの場合でもすぐに答えがヒットします。

ソースコードへのリンクを貼ります。
[distance.cのソース](https://gist.github.com/anonymous/051324db98614eaed22f)


CC BY-SA 3.0
2014-12-18T07:09:36.133
2001
2015-01-07T03:08:31.103
2015-01-07T03:08:31.103
2155
2155
question
c word2vec 自然言語処理
word2vecのdistanceはなぜ高速に動作するのか？


「なぜ速いのか」と言われると、「研究の成果です」とも回答できてしまいます。

「どういった工夫がされているのか」といった質問の方が良さそうです。

以下のページがわかりやすく説明されていると思いました。

<http://business.nikkeibp.co.jp/article/bigdata/20141110/273649/>

リンク先がみれる場合はそちらを参照してください。

以下は将来リンク先が見れなくなった場合に備えて速度に関する部分を要約してみました。

人工ニューラルネットワークの研究で提唱された「分散表現」という考え方を使い、「同じ文脈の中にある単語はお互いに近い意味を持っている」という前提のもとに人工ニューラルネットワークに学習させるようです。
この前提により構造の単純化と探索量の縮小とを実現しつつ、ベクトル表現する上で分散表現を利用することで精度の向上も実証されているそうです。

こういった工夫により高速化を実現しているようです。 速いのは魅力的ですね。私も興味を持ちました。


CC BY-SA 3.0
2014-12-18T08:25:45.007
2015
2014-12-18T08:25:45.007
728
2001
answer


たしかに全探索を行っているように見えますね。

手元のマシン(MacBook Pro, core i5 2.6GHz)で、200次元ベクトルの類似度を20万個計算して上位を求めるコードを試してみました。

[code]

    $ gcc -std=c99 hoge.c && time ./a.out
    real    0m0.549s
    user    0m0.495s
    sys     0m0.044s
    
[/code]

……というわけで、「最近のマシンだとベタに書いても余裕」ということではないでしょうか。

ベンチマークコードは以下です。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    const long long N = 40;                  // number of closest words that will be shown
    
    const long long DICT_SIZE = 200000;
    
    const long long DIMENSION = 200;
    
    float *gen_random_vector() {
        float *vec = malloc(DIMENSION * sizeof(float));
        for(int i = 0; i < DIMENSION; i++)
            vec[i] = (float)rand() / RAND_MAX;
        return vec;
    }
    
    float dist(float *v1, float* v2) {
        float d = 0;
        for(int i = 0; i < DIMENSION; i++)
            d += v1[i] * v2[i];
        return d;
    }
    
    int main(int argc, char **argv) {
        float *query = gen_random_vector();
        float **words = malloc(sizeof(float*) * DICT_SIZE);
        float bestd[N];
        int a = 0;
    
        for(int i = 0; i < DICT_SIZE; i++)
            words[i] = gen_random_vector();
        for(int i = 0; i < N; i++)
            bestd[i] = -1;
    
        for(int i = 0; i < DICT_SIZE; i++) {
            float d = dist(query, words[i]);
            for(int a = 0; a < N; a++) {
                if(d > bestd[a]) {
                    for(int b = N - 1; b > a; b--) {
                        bestd[b] = bestd[b - 1];
                    }
                    bestd[a] = d;
                    break;
                }
            }
        }
        for(int i = 0; i < N; i++)
            printf("%f\n", bestd[i]);
    }
    
[/code]


CC BY-SA 3.0
2014-12-18T10:40:18.447
2030
2014-12-18T11:22:25.307
2014-12-18T11:22:25.307
3479
3479
2001
answer


質問者さんのご指摘の通り、distance.cは総当たりで探索を行っています。ではなぜ高速に結果を返せるのか？

まず、distance.cのプログラムの大まかな処理の流れを説明すると次の通りになります：

  1. 全ての単語ベクトルをファイルから読み出し、その長さを計算しておく。  
読み出したベクトルの情報は一本の巨大なfloat配列としてメモリ上に格納しておく。

  2. ユーザー入力を受け付ける（ _"Enter word or sentence"_ と出力されるのはこのタイミングです）

  3. 入力された単語/文のベクトルを1.のfloat配列を元に求め、そのベクトル長を計算する。

  4. 最後に、1.と3.の情報を元に総当たりで入力語とのコサイン距離を求めてゆき、その上位N件を取り出す※

※ なお、上位N件の選択アルゴリズムは単純な挿入ソートです。

この処理の流れから明らかなように、 _ユーザが入力を行う段階で、既に全ての単語/ベクトルはメモリに読み出し済み + ベクトルの長さ計算済み_
となっています。また、1.の時点で既に全ての必要な情報をメモリに格納し終わっているので、以後の処理でファイル読み込みは一切発生していません。

要するに、distance.cが高速に結果を返却できるのは、このように（メモリを潤沢に利用して）最初に可能な限り事前処理を行っているからです。逆に言えば、リソースに乏しい環境ではこの戦略は使えないことになり、実際に質問者さんの例で言えば、最低でも、20万語
x 200次元 x float(4bytes) = 152MB 以上のメモリを割り当てられることがプログラム実行の前提条件となります。


CC BY-SA 3.0
2014-12-18T11:08:51.053
2034
2014-12-18T11:59:56.897
2014-12-18T11:59:56.897
2001
answer