2

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

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

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

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

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

ソースコードへのリンクを貼ります。 distance.cのソース

3 件の回答 3

4

質問者さんのご指摘の通り、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 以上のメモリを割り当てられることがプログラム実行の前提条件となります。

1
  • ありがとうございます。 現在のマシンスペックだとデータがメモリ空間にさえ格納されていればこれだけ高速に計算できるのですね。
    – NLP Lover
    Commented 2014年12月19日 4:34
4

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

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

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

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

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

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

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

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

2
  • なるほど。分散表現で効率よくしていたのですね。 それではプログラムコード内ではどのような工夫が具体的に施されていたのでしょうか?
    – NLP Lover
    Commented 2014年12月18日 12:23
  • word2vecの速さではなく提示のソース部分の速さが謎だったのですね、失礼しました。比較対象がないと主観や環境によってしまいそうですので、同様の操作で遅いと感じるコードや計算(200次元20万ならこれぐらいかかるはずという目安)、あなたの実行環境の情報もあると説明を得られやすいと思います。
    – fliedonion
    Commented 2014年12月18日 12:40
4

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

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

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

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

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

#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]);
}
1
  • 実験までしていただきありがとうございます。 納得いきました。
    – NLP Lover
    Commented 2014年12月19日 4:32

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。