今日帰宅したらACMから何やら届け物がきてて,中身をみたらなんとSIGIR 2009の論集でした.SIGIRというのは権威ある情報検索系の国際会議でとてもハイレベルな発表が集まります.僕は会員になっているのですが,ちゃんと論集を海外から送ってくれるなんて律儀ですなあ.

3962757362_ee1c575fdf

量が多いので全部目を通す自信も体力もないですが,ざーっと見た感じ興味ありそうなのを抜粋.

personalize系

  • 最近はやっぱpersonalize系がはやっているんですねえ.というか需要が高いのか.
  • Chen, Chun
    Personalized Tag Recommendation Using Graph-based Ranking on Multi-type Interrelated Objects  (Page 540)
    
    Chen, Homer
    Personalized Music Emotion Recognition  (Page 748)
    
    Chen, Liwei
    Predicting User Interests from Contextual Information  (Page 363)
    

    Clustering

  • Clusteringはジャンルを問わず興味があります
  • De Vries, Christopher M.
    K-tree: Large Scale Document Clustering  (Page 718)
    

    Social Network

  • SIGIRではソーシャルネットを使った手法はあまり見られなかったのですが,今回はいくつかあるようですね.
  • Gonçalves, Marcos
    Detecting Spammers and Content Promoters in Online Video Social Networks  (Page 620)
    

    Keyphrase Extraction

  • こうゆう知識抽出的な研究が大好き.軽く目を通しただけだからわからないけれども,Ranking SVMを使ってるみたい.
  • Hu, Yunhua
    A Ranking Approach to Keyphrase Extraction  (Page 756)
    

    日本人では藤井先生の発表が採択されたみたいです.すばらしい!

    Fujii, Atsushi
    Evaluating Effects of Machine Translation Accuracy on Cross-Lingual Patent Retrieval  (Page 674)
    

    少しずつ目を通していきたいと思います.面白いのがあったらいつか紹介しますー.


    9/29 追記
    本件に関して,一応の解決策を以下のエントリーにて記述しましたのでご参照ください.
    http://blog.broomie.net/index.cgi?id=38


    shunyaです.最近Crystal Keyのアルバムを聴いていてCrystal Keyが改めて良いと思いました.切なくて甘酸っぱいです.

    Thriftのパフォーマンスについて

    さて,前回のエントリー(Thriftが便利すぎる)では,僕が感じたThriftの便利さを熱弁する内容となっておりました.始めて使った感想としてはすごく便利!だったわけですが,実際に何かしらのサービスに導入するためにはThriftのパフォーマンスをチェックしなければなりません.

    で,今回は簡単なThriftのベンチをとってみることにしました.僕的に気になるのが,前回のエントリーでも書いたようにRESTととの違いです.つまりRESTではCGIを使ってHTTPで通信するので,比較的高速に処理できます.それに対して,Thriftでは独自に定義されたRPCで通信します.とても便利なのはいいのですが,この独自のプロトコルがどれほどのオーバーベッドがあって,スピードに影響を及ぼすのかはあらかじめ既知にしておかなければなりません.そこで,今回はRESTとThriftで前回のエントリーで作成した,「足し算,引き算」のプログラムのベンチをとってみることにしました.以下の図に概要を示します.

    1253879138-ThriftSpeedTest

    *Thriftのテスト方法

    図の左側がThriftの構成となります.サーバはC++で生成して,足し算,引き算のプログラムをそのC++のプログラムの中に書きました.クライアントはThriftで生成したperlライブラリを使いました.このプログラムの内容は前回のエントリーにも書いてあります
    が,要所部分だけ引用しておきます.

    今回使用したプログラムをアップしておきましたので,ご興味がある方は使ってみてください.
    TinyCalc.tar.gz
    コンパイルの仕方,テストプログラムについては同封したREADMEファイルに記述しました.

    thriftファイル

  • sumが足し算のインターフェース,subtractが引き算のインターフェース
  • #!/usr/bin/thrift
    
    service TinyCalc
    {
            double sum(1: double param1, 2: double param2)
            double subtract(1:double param1, 2:double param2)
    }
    

    サーバープログラムに書いた関数

    double sum(const double param1, const double param2) {
        return param1 + param2;
    }
    
    double subtract(const double param1, const double param2) {
        return param1 - param2;
    }
    

    サーバプログラムをコンパイル

    g++ -Wall -O2 -g TinyCalc_server.cpp TinyCalc.cpp -o TinyCal_server -lthrift -I/usr/local/include/thrift
    

    クライアントは上記のようにperlを使いました.以下の条件でテストをします.

  • テスト回数は1000回
  • 足し算(sub), 引き算(subtract)に与える引数は1から9の数字を用いた4桁の値をランダムに生成したものです
  • #!/usr/bin/env perl
    
    use strict;
    use warnings;
    use String::Random;
    use lib './gen-perl';
    use Thrift;
    use Thrift::BinaryProtocol;
    use Thrift::Socket;
    use TinyCalc;
    use constant TEST_NUM => 1000;
    
    my $transport = Thrift::Socket->new('localhost', 9090);
    my $client = TinyCalcClient->new( Thrift::BinaryProtocol->new($transport) );
    $transport->open();
    my $rnd = String::Random->new();
    for(my $i = 0; $i < TEST_NUM; $i++){
        my $arg1 = $rnd->randregex('[1-9]{4}');
        my $arg2 = $rnd->randregex('[1-9]{4}');
        my $sum = $client->sum($arg1, $arg2);
        my $subst = $client->subtract($arg1, $arg2);
        print "$sum\t$subst\n";
    }
    $transport->close();
    

    RESTのテスト方法

    RESTのテスト方法は先ほどの概要図の右側になります.RESTの場合は,サーバはfcgiをC++から呼んで実装しています.そのプログラムの中にThriftのサーバと同じようにsumとsubtractの関数を実装しています.
    そしてクライアントはperlスクリプトを書いてLWPを使ってサーバにPOSTで問い合わせるようにしました.テスト内容は一緒で,1000回,ランダムに生成された4桁の数字で足し算,引き算の計算の要求をします.このプログラムは明日アップしますので,少々お待ちください.といっても説明した通りの内容です.

    テスト結果

    これまで述べてきた内容でスピードテストをしました.で,テストの結果なのですが実は自信がありません.結論から言ってしまうとThriftがすごく遅いんですね.さすがにここまでは遅くならないだろー!ってぐらい遅い結果となってしまいました.だから,この結果には以下の可能性が潜んでいます.

  • テストプログラムに重大なミスがある
  • 実は僕が知らないだけでThriftにはチューニング用のパラメータがあって,それを使っていない
  • 単に僕のプログラムがバグがある
  • 上記の可能性がある上で今回出た結果をあまり信用せずに眺めていただけたら,と思います.では,計測した結果を以下の図にしめします.計測方法は単純にperlクライアントをtimeコマンドを使って時間を計測し,Thrift,RESTそれぞれ5回ずつ計測して平均を
    とりました.

    1253876512-ThriftSpeedTestResult

    なんと,RESTが9.89 secでThriftが81.41 secという結果になりました.実に約8倍もThriftが遅い計算となります.RESTのほうは約100QPSとなっていて妥当な値が出ています.それに対してThriftは約12QPSとちょっとありえない結果となてしまいました.

    もしかしたら,perlクライアントに問題があるのかな?と思ってpythonクライアントも書いてperlと同じような条件でテストしてみました.TinyCalc.tar.gzにも入れておいたのですが,一応ここにpythonのテストプログラムを示しておきます.

    #!/usr/bin/env python
    
    import thrift
    import thrift.transport.TSocket
    import thrift.protocol.TBinaryProtocol
    import TinyCalc.TinyCalc
    import random
    
    socket   = thrift.transport.TSocket.TSocket('localhost',9090)
    protocol = thrift.protocol.TBinaryProtocol.TBinaryProtocol(socket)
    client   = TinyCalc.TinyCalc.Client(protocol,protocol)
    
    socket.open()
    
    cnt = 0;
    while cnt < 1000:
        print client.sum(random.randint(10, 20),random.randint(10, 20));
        print client.subtract(random.randint(10, 20),random.randint(10, 20));
        cnt = cnt + 1
    
    socket.close()
    

    perlライブラリとはちょっとランダムな値の生成方法が違い,10から20の間の値をランダムに生成するといった実装になっています.そして,これの結果が5回計測して約80 secという結果になって,perlライブラリとほとんど同じになりました.

    まとめ

    やっぱりこの結果には自信がなくて公式のWhite Paperを読んだり,海外のサイトをチェックしてみたのですが,わからず.今回テストに使った環境を変えて別のサーバで実行してみたり,別のディストリビューションを使ってみたけど結果は同じになってしまいました.もしこの結果について何かわかる有識者の方がいらっしゃいましたらコメントかメールをいただけると幸いです.ちょっと気にな
    るのでこの件に関しては引き続き調査したいと思います.しょうもない内容を最後まで読んでいただき恐縮でございます.


    9/29 追記
    Thriftのperlクライアントをデフォルトのままで使うとパフォーマンスがあまりよくないようです.高速に使いたい場合は以下のエントリーを参照してください.

    http://blog.broomie.net/index.cgi?id=38


    ちょっと前に「thriftって便利らしいよー」って話を聞いていたのだけれども、なかなか手をつけられずにいたらはてなブックーマークで使われているらしいという噂を聞いたり、Thriftを使って俺俺Key-Value Storeを作ったのように、TXを使ったThriftの紹介などが出てきたりしたのでそろそろ自分でも試したいなあと思い、試しました。で、先に結論を言っておくとThrift、と
    ても気に入りました。とても簡単に処理用の専用サーバをたてることができて、かつ簡単にクライアントから処理要求が送れます。ボクは今まではRESTFulな感じでhttpでこのタスクをやっていたのですが、RESTFulな専用サーバをたてるのは結構開発コストがかか
    るんですよね。その点で、Thriftは開発コストはとても落ちると思うのでとても気に入っています。なんといって言語バインディングを自動で生成してくれるのは本当に開発コストが落ちますね。

    Thriftを使うモチベーション

    文書の自動分類とかを分類器にさせる場合、分類をリアルタイムに高速にやりたい場合があります。そんなときは分類器サーバはいくつかに分散されていることが望ましいし、ウェブアプリケーションから簡単に分類ができるようにしたいですね。そのために上記
    で述べたように、僕はRESTFulな環境をよく構築してhttp経由で処理していたりしていたんですね。適当ではあるのですが、以下にその概要図を示します。

    1253789684-REST

    この場合だとクライアントはperlスクリプトで書かれていて、http経由で分類の要求をするためにLWPなどを使います。これはこれで、高速だし使い勝手もなかなかよいのだけど、サーバーサイドのCGIプログラミングは結構チューニングが必要だったり、クライア
    ントプログラムは言語によって複数実装しなければならなかったりと、開発コストが結構かかります。

    そこで、Thriftを使うと以下の図のようになるんですね。

    1253789694-THRIFT

    何が楽になったかというと、サーバサイドも、クライアントサイドも基本的にはThriftがプログラムを生成してくれるんですね。特に通信部分を実装する際にRESTの場合だとCGIなどを自分で書かなくてはいけなかった部分を、ThriftではThriftで定義されたプロトコルを使うように自動的にプログラムを生成してくれるのがありがたいです。かつ、クライアントのバインディングも図に示したように多様に対応してくれるんですね。クライアントプログラムは対応している言語が多ければ多いほど利便性は上がると思いますし
    、これはたまらんです。バインディングのある、ないは喧嘩の種にもなっちゃいますしね!

    Thriftの簡単な使い方

    で、何がすごいって本当にすごく簡単にできちゃうんですね。例として以下にThriftを使った簡単な「足し算」と「引き算」のサーバを作る例をしめします。実は簡単な使い方は他のブログで懇切丁寧に説明されているので、わかりやすかった説明を引用させてい
    ただきながら説明します。間違えなどがあったらごめんなさい!

    Thrifのインストール

    • ThriftのインストールはUbuntuであれば以下のエントリーの内容に従えばできます。
    • http://d.hatena.ne.jp/conceal-rs/20081116/1226838725

    • fedoraでも試しましたが、基本的にはC++の開発環境が入っていれば問題なくコンパイルできました。
    • 自分の環境ではruby-devが入っていないと、怒られました。yum search ruby-devで簡単に探せます。

    インストールが完了したら、「足し算、引き算」プログラムの作り方を順に説明します。

    thriftファイルの作成

    • thriftファイルにはサーバーサイドのプログラムに定義される関数のインターフェースのようなものを書きます。これをもとにサーバのスケルトンをThriftが生成するようです。
    • 今回はパッケージ名をTinyCalcと名付けます
    • 定義する関数は2つだけ、sum(足し算), subtract(引き算)
    • TinyCalc.thriftと名付けます

    TinyCalc.thrift

    #!/usr/bin/thrift
    
    service TinyCalc
    {
            double sum(1: double param1, 2: double param2)
            double subtract(1:double param1, 2:double param2)
    }
    
    • 引数には引数番号を指定します。書式は例に示した通りです。
    • 今回使っている型はdoubleで指定しましたが、voidやstring, map, boolなども使えるようです。
      • なぜかintは定義されていないと怒られました。なぜ定義していないのかわかりません。

      10/25 追記

    • インターフェースで使えるデータ型は以下のものらしいです
    データ型
    インターフェース定義で利用できるデータ型は以下のとおりです。
        * 基本データ型
          bool, byte, i16, i32, i64, double, string
        * 構造体
        * コンテナ
          list, set, map
        * 例外
    

    http://cydn.cybozu.co.jp/2007/06/thrift.html より引用

  • intはixxになっているんですね。
  • スケルトンの生成

    • 上記のthriftファイルを元にスケルトンを生成します。
    thrift --gen rb --gen cpp --gen perl TinyCalc.thrift
    
    • 今回はperlとrubyのバインディングを生成するようにしました
    • サーバプログラムをc++で生成したいので–gen cppをしておきます

    サーバプログラムを作成する

    • スケルトンが生成されたらgen-cpp gen-perl gen-rbという3つのディレクトリが生成されていますね
    cd gen-cpp
    ls
    TinyCalc.cpp  TinyCalc.h  TinyCalc_constants.cpp  TinyCalc_constants.h  TinyCalc_server.skeleton.cpp  TinyCalc_types.cpp  TinyCalc_types.h
    
    • gen-cppには上記のようなスケルトンが生成されていると思います。
    • サーバプログラムを用意しましょう。
    cp TinyCalc_server.skeleton.cpp TinyCalc_server.cpp
    
    • TinyCalc_server.cppがサーバサイドのインターフェースのプログラムとなります。これを修正します。
    • 以下の部分を修正します。
     double sum(const double param1, const double param2) {
        // Your implementation goes here                                                                                                                                
        printf("sum\n");
      }
    
      double subtract(const double param1, const double param2) {
        // Your implementation goes here                                                                                                                                                
        printf("subtract\n");
      }
    
    
    • ちゃんとthriftファイルに書いたように、sumとsubtractのスケルトンが生成されていますね!
    • 修正は関数の中身を実装するだけです。
    double sum(const double param1, const double param2) {
        return param1 + param2;
      }
    
      double subtract(const double param1, const double param2) {
        return param1 - param2;
      }
    

    これでサーバプログラムが完成です。

    プログラムをコンパイルする

    • ちゃんとMakefileを書いたほうがいいのですが、今回はプログラムが小規模なので、さんと同じようにコマンドを直接打ってコンパイルしてしまいます。
    g++ -g TinyCalc_server.cpp TinyCalc.cpp -o TinyCal_server -lthrift -I/usr/local/include/thrift
    

    これでサーバのインターフェースが完成です。

    サーバを起動する

    • 作成したサーバを起動しましょう。単に実行するだけです。
    ./TinyCal_server
    

    クライアントプログラムを書く

    • 今回はperlとrubyのバインディングを生成するように指定しました。
    • perlのクライアントプログラムを書く例を示します。
    #!/usr/bin/perl
    
    use strict;
    use warnings;
    use lib './gen-perl';
    use Thrift;
    use Thrift::BinaryProtocol;
    use Thrift::Socket;
    use TinyCalc;
    
    # localhostの部分はサーバのipアドレスを入れれば他のクライアントサーバからでも呼べます
    my $transport = Thrift::Socket->new('localhost', 9090);
    my $tc = TinyCalcClient->new( Thrift::BinaryProtocol->new($transport) );
    
    $transport->open();
    
    my $rv = $tc->sum(1.0, 5.0);
    print "$rv\n";
    $rv = $tc->subtract(1.0, 5.0);
    print "$rv\n";
    
    $transport->close();
    

    実行結果

    perl test.pl
    6
    -4
    

    ちゃんと動いていますね!
    駆け足の説明となりましたが、このようにとても簡単にできるんですね。

    Thriftの実用的な使い方

    最初に説明したTxを使う例の紹介のように、言語処理などの重い処理にはとても有効だと思います。はてなブックマークでもブックマークの自動分類にThriftを使っているようです。そのほかにも形態素解析の専用のサーバを構築してクライアントサーバから呼んだり、クラスタリングなんかでも便利に使えますよね。

    ここでは日本語文書を分かち書きにする例を示したいと思います。超簡単です。

    準備

    • 分かち書きにするソフトは僕が作成したtinysegmenterxxを使います
    • これは工藤氏が作成した、Javascriptだけで書かれた日本語分かち書きソフトのC++で書いたものです。

    基本的な流れは上記で説明した、足し算引き算のものと一緒なので重要な部分だけ紹介します。

    thirftファイルの作成

    #!/usr/local/bin/thrift --gen cpp --gen perl --gen ruby
    
    service JpSegmenter
    {
      string segment(1:string input);
    }
    

    スケルトンの生成

    thrift --gen rb --gen cpp --gen perl JpSegmenter.thrift
    

    サーバプログラムの作成

    JpSegmenter_server.cpp

    // This autogenerated skeleton file illustrates how to build a server.                                                                                                              
    // You should copy it to another filename to avoid overwriting it.                                                              
    
    #include "JpSegmenter.h"
    #include 
    #include 
    #include 
    #include 
    
    /* TinySegmenterxxのヘッダーファイル */
    #include 
    
    using namespace apache::thrift;
    using namespace apache::thrift::protocol;
    using namespace apache::thrift::transport;
    using namespace apache::thrift::server;
    
    using boost::shared_ptr;
    
    class JpSegmenterHandler : virtual public JpSegmenterIf {
     public:
      JpSegmenterHandler() : sg(){
      }
    
    /* 日本語文を分かち書きする関数 */
      void segment(std::string& _return, const std::string& input) {
        tinysegmenterxx::Segmentes segs;
        sg.segment(input, segs);
        for(unsigned int i = 0; i < segs.size(); i++){
          std::cout << segs[i] << std::endl;
          _return.append(segs[i]);
          _return.append("\n");
        }
      }
    
    private:
      /* TinySegmenterxxのインスタンス */ 
      tinysegmenterxx::Segmenter sg; 
    
    };
    
    int main(int argc, char **argv) {
      int port = 9090;
      shared_ptr handler(new JpSegmenterHandler());
      shared_ptr processor(new JpSegmenterProcessor(handler));
      shared_ptr serverTransport(new TServerSocket(port));
      shared_ptr transportFactory(new TBufferedTransportFactory());
      shared_ptr protocolFactory(new TBinaryProtocolFactory());
    
      TSimpleServer server(processor, serverTransport, transportFactory, protocolFactory);
      server.serve();
      return 0;
    }
    

    スケルトンから修正したのは以下の三か所だけです

    • TinySegmenterxxのヘッダーファイルをインクルードする
      • 9/25 segment()の第一引数をconstにしたためプログラムを修正
    /* TinySegmenterxxのヘッダーファイル */
    #include 
    
    • インターフェースとなる関数を実装する
    • 日本語の文書を入力とし、分かち書きした結果を返す
    /* 日本語文を分かち書きする関数 */
      void segment(std::string& _return, const std::string& input) {
        tinysegmenterxx::Segmentes segs;
        sg.segment(input, segs);
        for(unsigned int i = 0; i < segs.size(); i++){
          std::cout << segs[i] << std::endl;
          _return.append(segs[i]);
          _return.append("\n");
        }
      }
    
    • ちょっとthriftの癖のある書き方になっていますが、わからないでもないです
    • _returnという引数はthriftが勝手につけます(stringを返り値にした場合はこうなります)
    • で、返り値は勝手にvoidにされるので、_returnの中に計算結果を格納すれば、バインディングにはちゃんと_returnの内容が返るようになっているようです

    TinySegmenterxxのインスタンス

    private:
      /* TinySegmenterxxのインスタンス */ 
      tinysegmenterxx::Segmenter sg; 
    
    

    プログラムのコンパイルと起動

    g++ -g JpSegmenter_server.cpp JpSegmenter.cpp -o JpSegmenter_server -lthrift -I/usr/local/include/thrift
    ./JpSegmenter_server
    

    クライアントプログラムの作成

    • ここでも例に従ってperlのクライアントライブラリの例を示します。
    #!/usr/bin/env perl
    use strict;
    use warnings;
    use lib './gen-perl';
    
    use Thrift;
    use Thrift::BinaryProtocol;
    use Thrift::Socket;
    
    use JpSegmenter;
    
    my $transport = Thrift::Socket->new('localhost', 9090);
    my $sg = JpSegmenterClient->new(Thrift::BinaryProtocol->new($transport));
    
    $transport->open();
    
    my $input = "東京特許許可局へ社会見学へ行ってきたよ.";
    my $result = $sg->segment($input);
    print "$result\n";
    
    $transport->close();
    
    

    このプログラムを実行すると以下のような結果が得られます。

    perl test.pl 
    東京
    特許
    許可
    局
    へ
    社会
    見学
    へ
    行っ
    て
    き
    た
    よ
    .
    

    ちゃんと分かち書きっぽくなっていますね!

    すごい駆け足な説明になってしまいましたが、Thriftの便利さが伝わったでしょうか。僕個人としては便利すぎてちょっと興奮しています。本当にいろんなプログラムで使いたいですね。今後もThriftを使ってこの手のプログラムを書いたら紹介したいと思います
    ー。


    今日会社で多次元のデータを2次元にクールでベストプラクティスな感じでプロットするにはどうしたらいいんだろうね、やっぱ多次元尺度構成法じゃない?的な会話をしていたのだけれども、2次元にデータを落とし込むと人間にもわかるデータになって本当におもしろいですよね。今日はその一例というか、いくつかの分類器の分類精度を2次元に
    プロットした結果を示した実験結果を解説したページを紹介します。おおーこうゆうのみたかったんだよなー!と個人的にはかなりエキサイティングな感じでした。

    要約というか意訳になってしまうのですが、ページに以下のように説明されています。(細かいところは訳してません)

    http://home.comcast.net/~tom.fawcett/public_html/ML-gallery/pages/index.html

    分類タスクの機械学習の研究では定量的な評価が重要です(精度とかACUとかね。)、で、これは分類器のアルゴリズムの振る舞いの「見える化(最近はやってますよね)」にも役立つ訳ですね。
    
    このページでは「機械学習の分類器ギャラリー」と題して、2次元における機械学習アルゴリズムの多数の実験結果を説明します。以下に示した列ではそれぞれ違ったパターン(またはパターンセット)を示しています。使用しているデータは2次元上にランダムに
    生成したポイントでX軸は0から4、Y軸は0から4の幅で、6561個のデータで構成されています。
    
    図の右側にはアルゴリズムの種類が書いてあります。アルゴリズムの名前のところはリンクになっていて、サンプルデータが50から1000の間での分類した結果を示してあります。
    
    このページで使用している図はgnuplotを使っていて、学習器はwekaを使っています。glue code(コーパスを作成したりするスクリプトのこと)はperlとpythonを使っています。
    

    データセット

    個人的に興味深かったものを紹介。

  • DISJUNCTIVE
  • 上記のページにDISJUNCTIVEというデータセットでの実験結果が示されています。とても分類が難しそうなデータですね!まさにSVMの出番って感じのデータセットですよね!

    1253333934-dataset

    Bayes

    bayesの各種分類器を使って分類した結果です。本当に名前通りの性格が分類結果に出ていますね、Naive! NBTreeというのはNaive Bayes + decision treeのアルゴリズムでの分類結果らしいのですが、これは比較的良さそうですね。重そうですけどね。

    1253333946-bayes

    大きい図はこちら

    SVM

    そこで、SVMですよ。カーネルトリックですよ。マージン最大化ですよ。って、あれあれあれ?あんまりよくなさそうですね。SVMRBF-100というのは、radial basis functionを使ったもので、これは結構良さそうなんですけど。SVMpoly-xというのは多項式カーネルを用いたものらしいのですが、全然だめですね!まったくうまくいってないですね!たぶん僕の個人的な予想なんです
    が、このデータのサンプル数が1000個ってうのが少なすぎる可能性があるか、うーん2次元データなのが問題なのかな。。。わからないけど、なんか特徴出ていますね。

    1253333959-svm

    大きい図はこちら

    decision tree

    なぜ、ここで決定木を例に出すの?と思われる方もいるかもしれませんが、それは僕が決定木が大好きだからです。決定木は一般的にはそんなに分類
    精度も良くないし、スピードも遅いともいわれていますが、なんといっても木を生成してくれるので人間にわかりやすいし、データマイニングに有用だから、僕は好きなのですね。なんといっても「なんでこうゆう分類結果になったの?」という非分類マニアな方
    にビジュアル的に説明できるのはとても便利。百聞は一見にしかずで、こうゆう理由で分類されたんですよ!と木を見せれば一言で説明がつく。情報利得がうんちゃらとかそういう話はしなくていいですけどね。ややこしくなるし。ちなみにSVMでの説明は地獄。

    1253333967-tree

    大きい図はこちら

    結構決定木もがんばっているではないですか!!特にRandom Forestは健闘していますね。これだけきれいに分離できるならば、やっぱりtreeも有用だなあと
    思う反面、おそらくこれはサンプルデータが少ないからだろうなあとも思う。このまま1000, 5000, 10000, 50000って続けていったらそれはそれで各分類器の特徴が如実に現れてくることだと思います。

    まとめる

    ユースケースにあわせて分類器を選択することはとても大事だと思います。

    • サンプル数の規模はどれぐらいか
    • 分類するクラスは何種類か
    • 分類に要求されるスピード
    • 学習に要求されるスピード(リアルタイムで更新してほしいならば、オンライン学習)
    • 分類結果を使う人は、専門家か、それとも非専門家か(上記で説明したように、分類結果の説明が大変)
    • メンテナンスできる人がどれほどいるか(あまりメンテナンスできる人がいない場合はnaive bayesなどの単純なアルゴリズムを選択した方が良い)

    などなど、仕事で分類器を使う場合は様々な分類器を検討しなければなりません。そのためにはそれぞれの分類器アルゴリズムの特徴を見極めていなければならないし、実験した経験も必要となります。どの分類器が一番いい!というのは無くて、それぞれいいと
    ころと悪いところがあります。このページは、そのような知識を手助けてしくれる大変有用なページだと思いました。

    エンジョイ ユア 分類ライフ
    今日から大型連休。


    勉強する時間があまりとれていないのでコネタが続いています。というよりも僕のブログのスタンスは基本的に有用なものメモするだけ、気軽にやる!って感じなのでこれで良いと思っています。時間ができたときに時々本気のエントリー!
    みたいな。あるのかな、そんなこと。

    前置きが長くなりましたが、今日は人工知能の教科書についてです。人工知能の授業でよく使われる教科書で最も有名なものの一つに「エージェントアプローチ人工知能」というものがあります。


    17800円とばか高いのですが、すごく網羅的に解説してあって僕は好きです。大学院時代の人工知能の授業はこの教科書でした。

    それで、たいしたことではないのですが、上記の教科書で解説しているアルゴリズムをpythonでひたすら実装しているプロジェクトがgoogle codeにあったので紹介しておきます。

    http://code.google.com/p/aima-python/
    上記のプログラムを熟読した訳ではないのですが、エージェントアプローチ人工知能を読むときにはすごく理解の手助けになるかと思います。

    またいつか人工知能全般も復習しないとならない時がくると思うで(だいぶ忘れている。。。)その時には利用してみようかと思います。


    身内の不幸などでどたばたしてしまい、ブログの更新ができていないのです。ということで、今日もどたばたなので小ネタで軽く更新しておきます。

    情報検索の教科書で有名なIntroduction to Information Retrieval(略してIIR)は、


    情報検索の基礎から、有名な機械学習のアルゴリズムまで幅広く解説されてあり、いろいろ忘れるたびにお世話になっています。どうお世話になっているかというと、これは結構有名な話なのですが、上記の本が実はPDFで公開されているんですね。すてき。

    http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html
    これは、本当によく使う手法がわかりやすく書かれているのでおすすめです。

    で、今回紹介したいのは、これまた機械学習の教科書として有名な本で、Introduction to Machine Learningという本があるんですね。

    まだ、すべては読破はしていないんですが、僕がいた研究室にもあって時々ちらちら読んでいたんです。これは、タイトルの通り機械学習の教科書なので、IIRのようにさくっと情報検索に使えるといったようには解説されていません。しかし、機械学習をちゃんと勉強するには網羅的に説明されているので、個人的はとても良い本だと思っています。

    で、実はこれも授業用のスライドがPDF形式とPPT形式で公開されているんですね!

    http://www.cmpe.boun.edu.tr/~ethem/i2ml/

    上記のリンクの先のページの一番下の方に、

    Lecture Slides: The following lecture slides (pdf and ppt) are made available for instructors using the book.
    
        * Chapter 1. Introduction (ppt)
        * Chapter 2. Supervised Learning (ppt)
        * Chapter 3. Bayesian Decision Theory (ppt)
        * Chapter 4. Parametric Methods (ppt)
        * Chapter 5. Multivariate Methods (ppt)
        * Chapter 6. Dimensionality Reduction (ppt)
        * Chapter 7. Clustering (ppt)
        * Chapter 8. Nonparametric Methods (ppt)
        * Chapter 9. Decision Trees (ppt)
        * Chapter 10. Linear Discrimination (ppt)
        * Chapter 11. Multilayer Perceptrons (ppt)
        * Chapter 12. Local Models (ppt)
        * Chapter 13. Hidden Markov Models (ppt)
        * Chapter 14. Assessing and Comparing Classification Algorithms (ppt)
        * Chapter 15. Combining Multiple Learners (ppt)
        * Chapter 16. Reinforcement Learning (ppt)
    

    というところがあるので、ちょろっとみてください。数式ばっかりで難しそうですね!でも、すでに理解されている方だったら忘れたときとかに参照するにはとても良いと思います。また、勉強会で説明しないといけない時とかに参考すると良いと思います。

    また、上記のページにはこの本を教科書として機械学習のレクチャーをしている、世界中の大学のページにもリンクされていて、そこにも各々のレクチャー用のスライドがあったりして、いろんな角度からみれておもしろいです。この際に私ももう一度この教科書
    を読み直してみようと思います。

    amazonでIntroduction Machine Learningを探していたら、なんと2010年にセカンドエディションが出るんですね!要チェックですね!
    http://www.amazon.co.jp/Introduction-Machine-Learning-Adaptive-Computation/dp/026201243X/ref=sr_1_1?ie=UTF8&s=english-books&qid=1252901537&sr=1-1


    ハイクオリティの最新の機械学習の論文って入手するのが大変ですよね。僕はよくACM系のちょっと前の論文をあさったりするのですが、やっぱり最新の機械学習ライフをエンジョイするには最新の論文が読みたいですよね。そんな、サイトがありました!ってこれってもしかして常識?

    Journal of Machine Learning Research

    これはすごい。最新の機械学習に関する論文が読めまくります。こんなポータルが欲しかったんです。RSS機能もあるようですし、ちょくちょく目を向けたいと思います。おもしろい論文があったら紹介したいですね。


    すごい、有名なアルゴリズムのサンプルプログラムがたくさんあります!

    http://www.yom-tov.info/Uploads/

    #  Parent Directory
    # Ada_Boost.m
    # Bottom_Up_Parsing.m# C4_5.m
    # DHSchapter2_fixed.mat
    # Grammatical_Inference.m
    # Marginalization.m
    # PPT.m
    # SVM.m
    # Sequential_Feature_Selection.m
    # calculate_region.m
    

    だけどmatlabわからない。。。
    いつか解読してみせる。


    突然なのですが、よく分類器などを実装して、その精度をチェックするためにコーパスが必要になることってよくありますよね。
    そこで、よく論文などで評価で使われているデータセットを使おうと考える訳ですが、そうゆう時に限ってデータセットの名前が出てこなかったりします。
    あと、いつも同じデータセットだとあんまり面白みもかけてきちゃったりして、よーし自分で作っちゃおうぞー!ってなってがんばってクローラーを書いたりして、ウェブコーパスを作ったりしようとするんですが、だいたい途中で飽きちゃったりするんですよね。

    さて、前置きが長くなりましたが、machine learningの評価で使われるデータセットがまとめてあるページを見つけたので紹介させていただきます。

    UCI Machine Learning Repository: Data Sets

    ぱぱーっと見た感じで、すごい色々な種類があってぜひ色々試してみたいですね。ダウンロードもできるみたいだし、さくっと使えそうです。
    今日は寝る時間なので試せないですが、今度時間があるときにいくつか実際に試したレポートを書きたいと思います!その日まで待っていてください。


    Algorithms of the Intelligent Webという情報検索の本がございまして、ずっと読みたいなあと思っていたら、本の内容のサンプルがありました。

    http://www.manning.com/marmanis/SampleChapter2.pdf

    これが、実はサンプルってレベルではなくて2章と3章がまるごとPDFで公開されているんですね。それで軽く読んでみたんですが、すごいわかりやすくて、普通に読み物としておもしろかったのでメモっておきます。

    上記のリンクは2章で「searching」という題で、つまり検索エンジンの話がまとめてあります。

    さらっと全部読んだんですけど、大雑把に感想を述べるとかなり基礎的な内容ですが、本当にわかりやすく解説してあるので、例えば、あまりこの分野に詳しくない人に説明する時や、自分でさらっと検索エンジンの要素を整理したい時とかには超便利だと思いま
    す。
    全体的な流れとしては

    • Luceneを使って検索エンジンの実装の仕方を説明
    • PageRankの説明
      • PageRankとindexのスコアリングの組あせ方の説明
    • Naive Bayesを使った分類の説明
    • Word document, PDFなどHTML以外の文書のスコアリング
    • Precision Recallなどの評価方法の話

    といった感じ。上記以外にもクエリ拡張や、クリックログの話など、検索エンジンで必要とする要素技術の話が幅広く、優しく説明してあります。なんで、これが初心者にいいかって、これらはLuceneに実装してあるんですね。だから、使いながら勉強できるので
    身に付きやすいと思うし、Luceneのコードの説明までしているのがすごい。僕はJavaは書かないのですが、コードに書いてあるコメントがわかりやすくてとてもよくわかりました。Luceneは実装が奇麗って話を聞いていたのですが、その再確認もなったなあ。図も
    豊富。情報検索とインデキシングのスコアリングに興味がある人はぜひ一読をお勧めします。