行列分解ライブラリredsvdで潜在的意味インデキシングを試してみたの巻

久しぶりに自然言語処理的な話です。

redsvd は行列分解を解くためのC++ライブラリであり、特異値分解（SVD)、主成分分析(PCA)、固有値分解などをサポートしています　（中略）　例えば、行と列がそれぞれ10万、非零の要素が100万からなる行列に対する上位20位までの特異値分解を1秒未満で行うことができます．

１秒未満って、す、す、すごくねぇだべか？

というわけで早速導入してみますた。

インストール

redsvdは内部の行列演算などにeigen3を使っているとのことなので、まずはこいつをセットアップ。あ、そうそうCMAKEも必要だよ。

ちなみに自分の環境でmake checkしたらエラーが少し出てたけど、気にせずそのまま突っ込んでみました。

続いてredsvdをインストール。
マニュアルサイト見ながらやれば問題ないかと思われますので、ここらへんの詳細は省略します。

下ごしらえ

さて、さっそく！
と言いたいところですが、いろいろと下ごしらえが必要です。

今回は解析対象データとして、某検索サイトの検索ログを数万件分を持って来て、この検索クエリーを関連語で適当に拡張させたものを使います。

検索クエリーを関連語に拡張させるのは、拙作のLingua::JA::Expandというperlモジュールでもできるし、YahooAPIの「関連検索ワード」を使ってもいいかもね。まぁ、データは適当に用意した、という前提ですすめましょう。

ちなみにこの時点では以下のような

「検索クエリ key value key value key value .....」

というようなフォーマットだと仮定します。
要するに検索クエリに対して関連語が bag of words として並んでいるようなフォーマットです。

実例↓
feature_vector.txt

B-1グランプリ順位グランプリ 57.5651697754102 順位 55.2949308955951 厚木 49.9866441630489 B-1グランプリ 39.3727412201767 祭典 34.3234789476085 中間 32.5569044283475 横手 32.4415825522972 -1 29.5295559151325 投票 24.6079632626104 富士
宮 24.1869095999417 津山 23.9561674837952 八戸 21.9336671532829 久留米 20.8208354120631 発表 19.8165814990785 八戸せんべい汁 19.6863706100883 ご当地グルメ 19.6863706100883 りう 19.0337310644589 行田 16.6138645318661 開催 15.4453195644505
横手やきそば 14.7647779575663 B級グルメ 14.7647779575663 箸 13.5186705477277 グルメ 12.8579683394308 太田 12.2752941145721 日本一 12.1918731374094 初日 11.6451320212923 最終 11.3429842290652 ゴールド 10.5028675612984 優勝 10.3416080924982 三浦海岸 10.185320100199
　・
　・
　・

この例だと「B-1グランプリ順位」という検索クエリに対して、それ以降で「グランプリ => 57.5651...」や「順位 => 55.294...」のように素性が並んでいます。
なお数値部分はTFIDFなどの重み付けされたスコアを使ってます。

さて、早速redsvdをぶん回してみたいのですが、このままだと食べてくれません。

疎行列の場合にはlibsvdでつかわれている表現方法と同じように各行毎に、0では無い列番号とその値をコロン区切りで書く方法で行列を表します．

むぅ。面倒ですがこんな感じのスクリプトで加工。

use strict;
use warnings;

my $word_idx;
my @labels;

while (<>) {
    chomp $_;
    my @f       = split "\t", $_;
    my $label   = shift @f;
    my %wordset = @f;

    push @labels, $label;

    my @item;
    while ( my ( $key, $value ) = each %wordset ) {
        my $idx = _idx($key);
        push @item, $idx. ':' . $value;
    }
    print join(" ", @item);
    print "\n";
}

# ラベル（検索キーワード）は別ファイルでとっておく
open(OUT, "+>", "labels.txt");
for(@labels){
    print OUT  $_,"\n";
}
close(OUT);


sub _idx {
    my $key = shift;
    $word_idx->{$key} || do {
        $word_idx->{$key} = int( keys %$word_idx ) + 1;
    };
}

走らせてみます。えい。

perl filter.pl feature_vector.txt > svd_in.txt

そうするとこんな感じ。

1:4.81836340644913 2:7.03558865049202 3:7.83207818255356 4:4.36772932997306 5:7.02204442538426 6:3.65583160006774 7:2.32278780031156 8:7.41858090274813 9:2.94124408826992 10:1.77431255562433 11:5.86254376704114 12:4.52082903755434 13:5.92492802330774 14:7.1665260079395 15:2.44876760317213 16:3.70365474023736 17:3.70365474023736 18:6.51841955280386 19:5.417100902538 20:6.00759392903787 21:5.63127578386945 22:6.57701371706991 23:4.81836340644913 24:3.70365474023736 25:6.1247673944224 26:7.67562600573802 27:10.1468338111679 28:7.41858090274813 29:4.66279929882473 30:1.84769510155836
　・
　・
　・

ラベル（検索クエリー）がなくなって、素性のキー部分が１から始まる数値に置き換わりました。

これでredsvdのスパース行列のフォーマットになりました。

ようやく本番

さて、redsvdの登場です！

今回試してみるデータですが、24万クエリくらい。
列数は28万ぐらいのスパースマトリックス。

こいつを特異値分解により200次元に圧縮してみます。

[miki@godzilla work]$ redsvd -i svd_in.txt -o svd_out -r 200 -f sparse
compute SVD
read matrix from svd_in.txt ... 12.0844 sec.
rows: 281280
cols: 243421
rank: 200
compute ... 148.231 sec.
write svd_out.U
write svd_out.S
write svd_out.V
50.6651 sec.
finished.
[miki@godzilla work]$

終わりました。
データの読み込みに12秒、計算に148秒、その後の行列を分解したデータの書き出しに50秒かかったよ、という意味のようです。

え、これってめちゃくちゃ速くない？

さて、結果としてsvd_out.U、svd_out.S、svd_out.Vという３つのファイルが生成されました。

なお、octave等でsvdを使って次元縮退させる際は特異値分解の後に、S（固有値を降順にならべた配列）の累積寄与率(?)を自分で計算して、再度 U x sqrt(S) などすることで結果のマトリックスを得るという手順でしたが、redsvdはこの時点でそこまでやってくれています。

つまりsvd_out.Uがそのものズバリ、ということのようです。（たぶん）

なので、上のperl スクリプトで「とっておいた」ラベルのファイル（もとの検索クエリ文字列が順番に書かれたもの）とくっつければ、「200次元に圧縮された行列」のできあがりです。（たぶん）

検証してみる

上で「たぶん」と書いたのは、本当にこれで合ってるのか、結果の行列睨んでいてもわからないからです。

なんとかして検証しなければ、ということで簡単な「潜在的意味インデキシング風」なスクリプトを用意します。（以前も紹介したネタですが）

ここまでの処理で出来上がった「検索クエリーのSVD行列」をすべてメモリにのっけて、適当な文字列を入力として受け取ったら、メモリ上の全レコード分と総当たりに距離を測定して、近いものから１０件を表示するスクリプトです。

総当たりなのですごく遅いですが、検証にはなるでしょう。

use strict; 
use warnings;
use Data::Dumper;

# データ復元
my $featured_vector;
open( VEC, "query_svd_matrix.txt" );
while (<VEC>) {
    chomp $_;
    my @f = split( "\t", $_ );
    my $key = shift @f;
    $featured_vector->{$key} = \@f;
}       
close(VEC);
    
# 標準入力からのデータ取得
print "INPUT NAME : ";
my $query = <>;
chomp $query;
my $query_vec = $featured_vector->{$query};
    
# 近傍検索
my @sorted
    = sort { $a->{dist} <=> $b->{dist} }
    map {
    my $name = $_; 
    my $vec  = $featured_vector->{$name};
    my $dist = distance( $query_vec, $vec );
    {   name => $name,
        dist => $dist
    }
    }
    keys %$featured_vector; 
        
# 上位10件を表示
for ( 1 .. 10 ) {
    print Dumper shift @sorted;
}   

# ユークリッド距離を計算する関数
sub distance {
    my $vector_1 = shift;
    my $vector_2 = shift;

    my @vec1 = @$vector_1;
    my @vec2 = @$vector_2;

    my $sum;
    for my $i ( 0 .. $#vec1 ) {
        my $d = ( $vec1[$i] - $vec2[$i] )**2;
        $sum += $d;
    }
    my $distance = sqrt($sum);
    return $distance;
}

さっそく走らせてみます。
まずはラーメン。

[miki@godzilla work]$ perl test.pl
INPUT NAME : ラーメン
$VAR1 = {
'name' => 'ラーメン',
'dist' => 0
};
$VAR1 = {
'name' => 'ぼぶラーメン紀行',
'dist' => '0.0177238305396999'
};
$VAR1 = {
'name' => 'とん太ラーメン',
'dist' => '0.0211681702090663'
};
$VAR1 = {
'name' => 'ラーメン醤油亭',
'dist' => '0.0218072035346121'
};
$VAR1 = {
'name' => 'らーめん',
'dist' => '0.0235849467881528'
};
$VAR1 = {
'name' => '百福ラーメン',
'dist' => '0.0261412958171549'
};
$VAR1 = {
'name' => 'ラーメン虎ジ',
'dist' => '0.0265464345063513'
};
$VAR1 = {
'name' => 'ラーメン二郎',
'dist' => '0.0292685444803803'
};
$VAR1 = {
'name' => 'ラーメン彩味',
'dist' => '0.0299031733934711'
};
$VAR1 = {
'name' => 'げんこつラーメン',
'dist' => '0.0302795406669256'
};
[miki@godzilla work]$

おお！見事にラーメン関連のクエリが並びました。200次元に圧縮してもちゃんと意味が残ってたんですね！

おつぎは今話題のコレ。

INPUT NAME : 尖閣諸島
$VAR1 = {
'name' => '尖閣諸島',
'dist' => 0
};
$VAR1 = {
'name' => '日中尖閣諸島問題',
'dist' => '0.0146660394449217'
};
$VAR1 = {
'name' => '尖閣諸島領海',
'dist' => '0.0250298066312946'
};
$VAR1 = {
'name' => '尖閣諸島中国人',
'dist' => '0.025504166345913'
};
$VAR1 = {
'name' => '中国尖閣諸島',
'dist' => '0.030786449957733'
};
$VAR1 = {
'name' => '尖閣諸島中国なんかに',
'dist' => '0.030786449957733'
};
$VAR1 = {
'name' => '尖閣諸島中国のこうどうは?',
'dist' => '0.0325268407472967'
};
$VAR1 = {
'name' => '台湾中国尖閣',
'dist' => '0.0345627984399412'
};
$VAR1 = {
'name' => '尖閣諸島アメリカ',
'dist' => '0.0360544180926554'
};
$VAR1 = {
'name' => '中国尖閣',
'dist' => '0.0400427653890188'
};

ふむ。。。不穏な空気を感じますね。。。

最後にオマケでもう１発。

INPUT NAME : 焼肉
$VAR1 = {
'name' => '焼肉',
'dist' => 0
};
$VAR1 = {
'name' => '焼肉キング',
'dist' => '0.0354135623031629'
};
$VAR1 = {
'name' => '焼肉の仁',
'dist' => '0.0355411440586822'
};
$VAR1 = {
'name' => '焼肉店',
'dist' => '0.0363344784467866'
};
$VAR1 = {
'name' => 'ホルモン市場じゅうじゅう',
'dist' => '0.0388911970759451'
};
$VAR1 = {
'name' => '焼肉幸四日市',
'dist' => '0.0394660728474471'
};
$VAR1 = {
'name' => '焼肉チェーン',
'dist' => '0.0395717680550162'
};
$VAR1 = {
'name' => '焼肉チェーン安',
'dist' => '0.0395717680550162'
};
$VAR1 = {
'name' => 'プルコギ',
'dist' => '0.0398892503564557'
};
$VAR1 = {
'name' => '焼肉明洞',
'dist' => '0.0399250527864397'
};

ホルモンとかプルコギとか、直接「焼肉」というコトバではないものがしっかり意味的に「近い」と評価してくれてるあたり、いいですね。

検証してみる　その２

その２としてbayonでクラスタリングしたみたよ、って内容を書こうと思ったんですが、眠くなって来たので、省略。

ポイントというか、気になったことだけ書いておきます。

元のデータをbayonで「-l 1.5」という条件でクラスタリングしたら25000くらいのクラスタになったんですが、redsvdで次元圧縮したデータをくわせたら13000程度のクラスタにしか分割されませんでした。

つまり、SVD（特異値分解）による潜在的意味インデキシングだと、単にサイズをちいさくするだけでなく、ノイズもカットしてることになるので、その影響で細かいクラスタには分かれなくなったんだと思います。

「ノイズをカットする = 大事なところだけにする = 特徴がよりはっきりする = あんまり細かくは分けられない」

といったところでしょうか。

当方シロウトにつき、識者の意見求ム。

まとめ

redsvdはえー。

岡野原さんすげー。

おわり。

インストール

下ごしらえ

ようやく本番

検証してみる

検証してみる その２

まとめ

検証してみる　その２