のんびり読書日記

日々の記録をつらつらと

Bayesian Setsを試してみた

Programming

この前YAPC Asia 2009に参加してきたのですが、そこで「はてなブックマークのシステムについて」の発表の中で、「はてブの関連エントリはBayesian Setsを使って計算されている」という話を聞いてBayesian Setsに俄然興味が湧いてきました。Bayesian Setsは以前論文だけ少し読んで、あまりよく分からないまま放置していたのですが、せっかくなのでPerlで作って試してみました。

Bayesian Setsについて詳しくは、以下のリンク先の資料をご参照下さい。

実際に作成したコードは以下の通りです。上記のMatlabのコードを参考にさせていただいています。

#!/usr/bin/perl
#
# Bayesian Sets
#
# Usage:
#  % bayesian_sets.pl input.tsv query1 query2 ..
#
# Reference
# - Paper: http://www.gatsby.ucl.ac.uk/~heller/bsets.pdf
# - Matlab code: http://chasen.org/~daiti-m/dist/bsets/
#

use strict;
use warnings;

use constant {
    MAX_OUTPUT => 20,
};

sub read_vectors {
    my $fh = shift;
    my %vectors;
    while (my $line = <$fh>) {
        chomp $line;
        my @arr = split /\t/, $line;
        my $doc_id = shift @arr;
        my %vector = @arr;
        map { $vector{$_} = 1 } keys %vector;
        $vectors{$doc_id} = \%vector;
    }
    return \%vectors;
}

sub get_parameters {
    my ($vectors, $c) = @_;
    my $average_vector = _average_vector($vectors);
    my (%alpha, %beta);
    while (my ($key, $val) = each %{ $average_vector }) {
        $alpha{$key} = $c * $val;
        $beta{$key}  = $c * (1 - $val);
    }
    return (\%alpha, \%beta);
}

sub calc_similarities {
    my ($vectors, $queries, $alpha, $beta) = @_;
    my %query_vector;
    my $num_query;
    foreach my $query (@{ $queries }) {
        if (!exists $vectors->{$query}) {
            warn "[WARN] '$query' doesn't exist in input documents. Skip it\n";
            next;
        }
        while (my ($key, $val) = each %{ $vectors->{$query} }) {
            $query_vector{$key} += $val;
        }
        $num_query++;
    }
    return if !%query_vector;
    my $length_qvec = scalar(keys %query_vector);
    my %weight_vector;
    foreach my $key (keys %{ $alpha }) {
        my $val = $query_vector{$key} || 0;
        $weight_vector{$key} =
            log(1 + $val / $alpha->{$key})
            - log(1 + ($num_query - $val) / $beta->{$key});
    }
    my %score;
    while (my ($doc_id, $vector) = each %{ $vectors }) {
        $score{$doc_id} = _inner_product(\%weight_vector, $vector);
    }
    return \%score;
}

sub _average_vector {
    my $vectors = shift;
    my %average_vector;
    my $num_vector = 0;
    while (my ($doc_id, $vector) = each %{ $vectors }) {
        while (my ($key, $val) = each %{ $vector }) {
            $average_vector{$key} += $val;
        }
        $num_vector++;
    }
    map { $average_vector{$_} /= $num_vector } keys %average_vector;
    return \%average_vector;
}

sub _inner_product {
    my ($v1, $v2) = @_;
    return 0 if !$v1 || !$v2;
    my @keys = scalar(keys %{ $v1 }) < scalar(keys %{ $v2 }) ?
        keys %{ $v1 } : keys %{ $v2 };
    my $prod = 0;
    foreach my $key (@keys) {
        $prod += $v1->{$key} * $v2->{$key} if $v1->{$key} && $v2->{$key};
    }
    return $prod;
}

sub main {
    my $path = shift @ARGV;
    my @queries = @ARGV;
    if (!$path || !@queries) {
        warn "Usage $0 file query1 query2 ..\n";
        exit 1;
    }
    
    open my $fh, $path or die "cannot open file: $path";
    my $vectors = read_vectors($fh);
    return if !$vectors;
    my ($alpha, $beta) = get_parameters($vectors, 2);  # c=2
    my $score = calc_similarities($vectors, \@queries, $alpha, $beta);
    my $count = 0;
    foreach my $doc_id (sort { $score->{$b} <=> $score->{$a} }
        keys %{ $score }) {
        last if ++$count > MAX_OUTPUT;
        printf "%s\t%.3f\n", $doc_id, $score->{$doc_id};
    }
}

main();

入力データには以下のようなタブ区切りのテキストファイルを用意します。データ例は以前の記事で作成した、Wikipediaの各キーワードをTFIDFで重み付けしたデータです。実際にはvalue部分はいらないのですが、以前の名残りでそのままのフォーマットにしています。

# document_id \t key1 \t val1 \t key2 \t val2 \t ...

龍淵郡  郡      2365    長淵    1857    半島    1555    淵      1460    龍      1313    朝鮮    1137    （/     1126    九      987     串      971     長山 788 リョンヨン      777     モングンポ      777     クミポ  777     朝鮮民主主義人民共和国  777     美浦    733     派      720     教会    714     救面 708 ざんかん        708     チャンサンゴッ  708     金浦    605     史上    595     松川    555     プロテスタント  529     分割    527     地      526 岬 513     里      506     建設    505     苔      500     年      496     南岸    490     当時    487     珪砂    483     黄海    481     再編    468 夢 460     ら      460     北朝鮮  444     宣教    404     1884    397     相      397     ソレ    382     甕      379     白島    360     徐      359 灘 344     教会堂  341     景勝    336     崙      334
神さまこんにちは        ピョンテ        2332    チュンジャ      2332    慶州    1381    映画    1270    人      929     旅      827     チョン・ムソン  777 キム・ボヨン       777     ハン・ミヌ      777     国際    756     ペ・チャンホ    708     脳性    689     ソンギ  639     ミヌ    639     彼      624 祭 615     詩人    614     3       574     妊婦    548     麻痺    539     回      481     念願    468     英      458     39      430     Hello   425 ロード     419     アン    414     家      413     モスクワ        409     電車    399     God     395     16      377     乗車    366     遠足    350 神さま     342     無賃    339     !）     332     さ      331     大人    329     小学生  309     ムービー        298     ベルリン        296     とき 295 実家    289     一      288     原題    286     途方    272     神様    264     韓国    263     公開    259
藤原雅長        年      5208    雅      1285    藤原    1271    近臣    1263    位      1138    従      1118    任      1110    長      957     元年    903 3  861     7       813     院      798     近衛    782     五位上民部権大輔        777     嘉      770     視      764     4       760     下      747 日 747     左      713     隆信    708     月      689     わら    638     叙      629     保      600     8       599     能      595     参議    572 守 556     蔵人    521     久安    515     五      507     少将    506     26      503     顕能    500     在任    460     2       451     ふじ    448 中将       448     19      445     処分    431     久      425     死去    424     任命    422     兼      416     教      406     後期    403     長男 401 この間  377     辞任    377

実際に動かしてみます。入力ドキュメント集合のファイルと、(複数の)クエリを指定します。クエリは入力ドキュメント集合中に含まれている document_id しか使用できません。

% ./bayesian_sets.pl input.tsv トヨタ自動車
トヨタ自動車    140.748
豊田英二        47.205
トヨタ・トヨエース      45.501
5チャンネル     42.303
ポルシェ        40.428
トヨタ・マークX 37.372
日産・マーチ    36.659
フォード・モーター      36.333
三菱自動車工業  33.872
マツダ  33.625
ホンダ・インサイト      32.407
トヨタ・タンドラ        32.004
トヨタ・クルーガー      29.959
ジオ (自動車)   29.293
シボレー・キャバリエ    29.142
トヨタF1        28.830
三菱・ディオン  27.994
いすゞ・エルフ  27.712
ヒュンダイ・ソナタ      27.452
富士重工業      27.111

% ./bayesian_sets.pl input.tsv 原宿警察署
原宿警察署      203.638
滝野川警察署    80.618
牛込警察署      59.605
万世橋警察署    52.241
三田警察署 (東京都)     47.331
城東警察署 (東京都)     43.736
王子警察署      42.404
丸の内警察署    37.594
中野警察署 (東京都)     36.628
広島東警察署    32.846
田無警察署      31.444
豊田幹部交番    31.430
小金井警察署    31.352
尾鷲警察署      30.760
日下部警察署    30.656
山梨県警察      30.290
戸塚町  30.032
阿東幹部交番    29.785
神宮前 (渋谷区) 28.061
倶知安警察署    27.630

ちゃんと関連しているものが取得できていますね。本当は「apple banana」と「apple iPod」のように複数の意味を持つ言葉で、複数のクエリを入れた場合にそのクラスタ内の単語が出てくるのを確かめられるとよかったのですが。

今回使用した入力データのサイズは10万個のドキュメント(wikipediaのキーワード)ですが、実行には25秒ほどかかっています。今回のコードは入力データからのインデックスの作成と、クエリからの類似アイテムの検索の両方を同時に処理させているため動作が遅いですが、インデックスは初めに作成して保存しておけるようにしておけば、そこそこのスピードで検索できるようになると思います。

まだBayesian Setsの肝をあまり理解できていないのですが、

  • 与えられたクエリが含まれていると思われるクラスタをオンデマンドで求め、そのクラスタに含まれている他のアイテムを返す
  • クエリから求めた重みベクトルと入力ドキュメント集合から構成した行列の積(重みベクトルと全文書の内積)を求めるだけで計算できる

あたりがうれしいところなんでしょうか？一般的な転置インデックスを使用した類似コンテンツを求める方法でも同様のことはできそうな気がするのですが、「オンデマンドにクラスタを求める」というところでゴミが消されるんですかね。ちなみに単純に全文書とのcosine距離で類似したものを取ってきた場合だと、以下のような結果になります。大抵は良好な結果が得られますが、たまにクエリによってはゴミだらけになっちゃってますね。

% ./cos.pl input.tsv トヨタ自動車
トヨタ自動車    1.000
豊田英二        0.625
松井石根        0.610
島崎藤村        0.609
鉄道の歴史 (日本)       0.598
土佐電気鉄道    0.592
日産・マーチ    0.591
新関八洲太郎    0.588
近衛道嗣        0.588
岡村貢  0.587
高田保馬        0.587
8月7日  0.586
仙台東照宮      0.584
3月25日 0.584
飛鳥時代        0.583
三菱自動車工業  0.582
蒲郡競艇場      0.580
富士重工業      0.580
大林組  0.579
ホンダ・インサイト      0.576

% ./cos.pl input.tsv 原宿警察署
原宿警察署      1.000
阿東幹部交番    0.776
周南警察署      0.775
竹原警察署      0.773
高梁警察署      0.771
日下部警察署    0.769
大牟田警察署    0.764
三原警察署      0.758
音戸警察署      0.756
横須賀警察署    0.754
城東警察署 (東京都)     0.753
山口南警察署    0.752
松浦警察署      0.752
王子警察署      0.751
滝野川警察署    0.750
東近江警察署    0.750
つがる警察署    0.748
万世橋警察署    0.743
あわら警察署    0.743
丸亀警察署      0.743

あと、この前のpLSIの記事では結局そのまま放置になってるのですが、せっかくなので今度こそパッケージングしてAlgorithm::BayesianSetsを作ろうと思います。あまり使い道はなさそうですが、ざっくりどんなものか知るのには多少役に立ちそうですし、何より僕自身がCPAN Authorになってみたいので…^^;

追記：weight_vectorを求めるところが一部間違っていたため、コードと実行結果、実行時間を修正しました。ただ実行結果はポイント以外はほとんど違いはないと思います。