対数共起頻度のSVD

対数共起頻度を用いた四項類推：word2vecとPMI との比較
https://doi.org/10.11517/pjsai.JSAI2020.0_4Rin177

という報告を読んだ。四項類推は、queen-woman+man ≒ kingみたいなタイプの類推問題。word2vecは、この手の問題によく答えられるということになっている。

四項類推の精度については、通常、最も類似度の高い単語を1〜数個取ってきて、妥当性を確認するという方法が取られ、類似度の値そのものは見てないことが多いけど、ちょっと類似度の値を見てみる。
Pretrained Embeddings
https://wikipedia2vec.github.io/wikipedia2vec/pretrained/

で公開されているword2vecで学習したenwiki_20180420_300dに含まれるデータでは、kingとqueenのコサイン類似度は、元々、0.63ある。kingもqueenも、最上級の支配者を表すという点では、共通していて同じような文脈で出現することが多いと考えられるので、それ自体は問題ない。しかし、king-man+womanとqueenのコサイン類似度は、0.65になるが、単にkingとqueenが、最初から類似度の高い単語であることが効いてるだけのように思える。類似度が上がってるように見えるのも多分偶然の産物で、queen-woman+manとkingのコサイン類似度は、0.60になって、むしろ小さくなる。

しかし、四項類推について全く意味のある情報を含んでいないとも言えない。(king,queen),(man,woman),(father,mother),(god,goddess),(boy,girl),(boys,girls),(son,daughter),(prince,princess),(waiter,waitress)という9組について、差のベクトルの平均を取って、(actor,actress)の差ベクトルとのコサイン類似度を計算すると、0.82という高い値になる。個別の差ベクトルとのコサイン類似度は、0.43〜0.69までバラバラであるが、平均化することで類似度が上がるので、"性差"を表現するベクトルが存在している可能性もある。

actorとactressのコサイン類似度は、元々、0.78ほどあり高いのだけど、actor-"性差"ベクトルとactressのコサイン類似度は、0.92とかなので、0.4~0.7くらいの胡散臭い数値を、うろうろしてるのとは違うようにも思える。個別のペアに関しては、性差以外の部分でも、用法の差があるのかもしれない(例えば、日本語で、"ボーイ"を給仕的な意味に使うことがあり、英語圏でも、この用例は存在するっぽいが、girlで、これに相当する使い方は、多分しないっぽいとか、そういった感じのこと)が、平均化することで、こうした微細な違いが消失するのかもしれない。

gloveの場合も、githubレポジトリのREADMEにリンクがあるglove.42B.300dで実験すると、同じようなことが起きる。例えば、上と同様にして"性差"ベクトルを計算して、actor-"性差"ベクトルとactressのコサイン類似度を見ると、0.89程度になっている。he-"性差"ベクトルとsheのコサイン類似度は、0.93以上ある。
stanfordnlp/GloVe
https://github.com/stanfordnlp/GloVe

gloveに同梱されてるdemo.shでは、小さなコーパスtext8をダウンロードして学習するようになっているけど、text8で学習したベクトルを使うと、同じことをやっても成績は悪いので、大きなコーパスを使うことは重要かもしれない。text8は、Wikipediaを元に作成したコーパスから100MBを抜粋したデータで、約1700万tokensを含む。glove.42B.300dは、420億トークンからなるコーパスで学習しているらしい。Wikipedia+αから作成したコーパス(60億トークン)で学習したglove.6B.300dでも、学習精度は、glove.42B.300dと大差ないように思える。

これらのコーパスは、通常の本などと比べて桁違いに大きく、例えば、King James版英訳聖書は、延べ80万tokens弱(unique wordsは約5400単語)らしい。
単語の分散表現を使った教師なし単語翻訳
https://m-a-o.hatenablog.com/entry/2019/04/01/221230
の末尾で、King James版英訳聖書で学習した分散表現がイマイチっぽいと書いたけど、本1〜2冊程度で学習できる分散表現は、(少なくとも、現在のアルゴリズムでは)やはりカスなんじゃないかと思う

で、冒頭の報告は、対数共起頻度の(trunated) SVDを使っても、四項類推問題で、それなりの成績を収めるということらしい。多くの点で、以下の2015年の論文を参照している。
Improving Distributional Similarity with Lessons Learned from Word Embeddings
https://www.aclweb.org/anthology/Q15-1016/

論文には、(LSAとかで古くから行われてたような)old-styleの"count-based"な手法でも、prediction-basedな手法(≒neuralなんとか)に近い性能を実現することができる的なことが書いてある。対数共起頻度も、count-based modelではあるけど、以下の論文では実験されてないので、それをやったのが冒頭の報告ということ。

対数共起頻度をSVDするだけというのは、理屈上は簡単なので自分でも試してみることにした。上にも書いた通り、コーパスサイズが小さいとゴミになる可能性があるので、報告と同じく、英語Wikipedia全文を利用することにする(少なくとも、word2vecやgloveは、これで、そこそこの性能が出てるらしいし)。報告では、メモリの都合が〜と言い訳しつつ、なんか回りくどいことをしているが、メモリを潤沢に利用できる環境を用意して直接計算した。

Wikipediaの前処理には、fasttextのレポジトリに含まれるwikifil.plを使用して、以下のように、コーパスを作成した。

wget https://raw.githubusercontent.com/facebookresearch/fastText/master/wikifil.pl
curl -L -O http://dumps.wikimedia.org/enwiki/latest/enwiki-latest-pages-articles.xml.bz2
bzcat enwiki-latest-pages-articles.xml.bz2 | perl wikifil.pl > enwiki_all.txt

次に、共起頻度の計算には、gloveで使われているcooccurを流用。デフォルトの設定では、distance-weightingという距離による重み付けが入ってたりするけど、オプションで切ることができる。
GloVe
https://github.com/stanfordnlp/GloVe

gloveのレポジトリに含まれてるdemo.shを改変して、以下のようなシェルスクリプトを使用した。メモリの設定は64GBとかにしてるので、環境に合わせて変更しないとメモリを使い切るかもしれない。shuffleとgloveは、やらなくてもいいけど、ついで。

#!/bin/bash
set -e

make

CORPUS=enwiki_all.txt
VOCAB_FILE=vocab.txt
COOCCURRENCE_FILE=cooccurrence.bin
COOCCURRENCE_SHUF_FILE=cooccurrence.shuf.bin
BUILDDIR=build
SAVE_FILE=glove.raw.300d
VERBOSE=2
MEMORY=64.0
VOCAB_MIN_COUNT=100
VECTOR_SIZE=300
MAX_ITER=15
WINDOW_SIZE=10
BINARY=2
NUM_THREADS=24
X_MAX=10

echo "$ $BUILDDIR/vocab_count -min-count $VOCAB_MIN_COUNT -verbose $VERBOSE < $CORPUS > $VOCAB_FILE"
$BUILDDIR/vocab_count -min-count $VOCAB_MIN_COUNT -verbose $VERBOSE < $CORPUS > $VOCAB_FILE
echo "$ $BUILDDIR/cooccur -memory $MEMORY -vocab-file $VOCAB_FILE -verbose $VERBOSE -window-size $WINDOW_SIZE -symmetric 1 -distance-weighting 0 < $CORPUS > $COOCCURRENCE_FILE"
$BUILDDIR/cooccur -memory $MEMORY -vocab-file $VOCAB_FILE -verbose $VERBOSE -window-size $WINDOW_SIZE -symmetric 1 -distance-weighting 0 < $CORPUS > $COOCCURRENCE_FILE
echo "$ $BUILDDIR/shuffle -memory $MEMORY -verbose $VERBOSE < $COOCCURRENCE_FILE > $COOCCURRENCE_SHUF_FILE"
$BUILDDIR/shuffle -memory $MEMORY -verbose $VERBOSE < $COOCCURRENCE_FILE > $COOCCURRENCE_SHUF_FILE
echo "$ $BUILDDIR/glove -save-file $SAVE_FILE -threads $NUM_THREADS -input-file $COOCCURRENCE_SHUF_FILE -x-max $X_MAX -iter $MAX_ITER -vector-size $VECTOR_SIZE -binary $BINARY -vocab-file $VOCAB_FILE -verbose $VERBOSE"
$BUILDDIR/glove -save-file $SAVE_FILE -threads $NUM_THREADS -input-file $COOCCURRENCE_SHUF_FILE -x-max $X_MAX -iter $MAX_ITER -vector-size $VECTOR_SIZE -binary $BINARY -vocab-file $VOCAB_FILE -verbose $VERBOSE

無事計算を終えると、cooccurrence.binに共起頻度が入っている。(symmetricオプションを有効にしたため)対角成分が、2倍になってたりするけど、どうせ対数を取るので、大きな問題はないと考えて、そのままにしてある

私がやったところ、共起頻度行列の次元は40万弱で、非ゼロ要素の数は、17.8億弱になった。非ゼロ要素の半分近くが1なので、対数を取ると0になるけど、それでも、疎行列を作るだけで10GB以上のメモリが要る(cooccurrence.binのサイズは28GB強)。疎行列のSVDには、RedSVDを使った(RedSVDの実装が正しいのかチェックしてないけど信じることにする)。使用した実装が、Eigenに依存してたので、Eigenも必要。
Eigen
http://eigen.tuxfamily.org/index.php?title=Main_Page

header-only version of RedSVD
https://github.com/ntessore/redsvd-h

実際のプログラムは、以下の通り。UとSを別々に出力してるけど、冒頭の報告では、UとSの平方根を掛けたもの(rootSVDと呼んでる)が一番成績がよいらしい。これは、後から計算する。U単体を、word vectorと見たものは、uSVDと呼んでいる。

#include <cmath>
#include <vector>
#include <iostream>
#include <Eigen/Sparse>
#include <RedSVD/RedSVD.h>

typedef struct cooccur_rec {
    int word1;
    int word2;
    double val;
} CREC;

int main(){
    std::vector< Eigen::Triplet<float> > triplets;
    FILE *fin = fopen("cooccurrence.bin","rb");
    fseek(fin , 0 , SEEK_END);
    size_t sz = (size_t)ftell( fin );
    triplets.reserve( sz / sizeof(CREC) );
    fseek(fin , 0 , SEEK_SET);
    int D = 0;
    while(!feof(fin)){
        CREC rec;
        fread(&rec, sizeof(CREC), 1, fin);
        if ( D < rec.word1 ) D = rec.word1;
        if ( D < rec.word2 ) D = rec.word2;
        if( rec.val > 1.0) {
            triplets.push_back( Eigen::Triplet<float>(rec.word1-1 , rec.word2-1 , logf((float)rec.val)) );
        }
    }
    fclose(fin);
    
    Eigen::SparseMatrix<float> M;
    M.resize(D,D);
    M.setFromTriplets(triplets.begin() , triplets.end());
    triplets.resize(0);
    triplets.shrink_to_fit();

    RedSVD::RedSVD<Eigen::SparseMatrix<float>> svd(M,300);
    auto U = svd.matrixU();
    auto S = svd.singularValues();
    std::cout << "S:" << std::endl << S << std::endl;
    std::cout << "U:" << std::endl << U << std::endl;
    return 0;
}

計算は、gloveより大分早かった(gloveは複数スレッド使って頑張ってるらしいのに数時間、rootSVDやuSVDは1スレッドで10分くらい)。後は、出力を適当に整形すれば、分散表現が得られる。で、四項類推とか以前に、そもそも、(king,queen),(man,woman),(father,mother),(god,goddess),(boy,girl),(boys,girls),(son,daughter),(prince,princess),(waiter,waitress)という9組で、単語のコサイン類似度がどうなってるのか見ると、以下のようになった。

名詞1	名詞2	rootSVD	uSVD	word2vec	glove.42B.300d	glove.text8
king	queen	0.69	0.40	0.63	0.76	0.52
man	woman	0.70	0.30	0.69	0.80	0.57
father	mother	0.89	0.69	0.81	0.82	0.65
god	goddess	0.64	0.45	0.61	0.47	0.42
boy	girl	0.85	0.48	0.77	0.83	0.53
boys	girls	0.84	0.65	0.86	0.86	0.54
son	daughter	0.86	0.67	0.84	0.82	0.64
prince	princess	0.79	0.64	0.68	0.66	0.50
waiter	waitress	0.85	0.65	0.72	0.78	0.11

word2vecは、上の方で触れたenwiki_20180420_300dを使った時の数値。glove.text8は、gloveに同梱されてるdemo.shの学習結果で、上に書いたようにコーパスが小さい。雰囲気としては、uSVDやglove.text8は、他よりコサイン類似度が小さい傾向にあるように見える。

rootSVDでは、king-man+womanとqueenのコサイン類似度は、0.64で下がる。king-male+femaleとqueenのコサイン類似度も、0.67で、元々のkingとqueenの類似度が効いてるだけのように見える。性差ベクトルを計算して、king-"性差"ベクトルとqueenのコサイン類似度は、0.75になり改善はする。

網羅的なテストはしてないけど、rootSVDが、四項類推課題に対して、そこそこの性能を持つという報告は正しそうに見える。ただ、それは、元々、類似度の高い単語を取ってるだけでないかという疑惑はある。報告を見る限り、skip-gramよりは多少精度が悪そうなのだけど、共起頻度のみを使う場合、共起単語の出現位置に関する情報(the kingとking theという単語列を区別できない)は完全に捨てられていて、入力の時点で、情報が少ないので、当然という気はする。SVDベースの方法で、このような情報を取り込むには、前方共起頻度と後方共起頻度を別にカウントするとか、もっと詳細には、窓幅4以下での共起と窓幅8以下での共起を分けるとか、複数のcontextを同時に使う方法が思いつくけど、実際有効かどうかは不明