お久しぶりでございます。

技術評論者さまのWEB+DB PRESS Vol.59で少しだけ執筆させていただきました。

[実践]大規模データ分析というテーマで特集を組ませていただき、

1章 データマイニング入門
2章 テキストマイニング
3章 クラスタリング
4章 ログデータマイニング
5章 リンクマイニング

という章立てで僕は「テキストマイニング」について書かせていただきました。

テキストマイニングということで、とても幅の広い話なので、どのようにまとめるかに苦難しました。専門家の方には物足りないかもしれませんが、紙面にも限りがあるため、今回はテキストマイニングの概要とhadoopを使った効率的な頻度分析、共起分析についてまとめ、全体的に基本的な内容でまとめさせていただく運びとなりました。

キーワードを抽出し、特徴ベクトルさえできてしまえば、応用できる手法を掲載した書籍がたくさんあることもあり、今回はキーワード抽出のところに重きを置かせていただきました。hadoopを使ってmixiの日記から簡単にキーワードランキングを作成する方法や、共起分析をした結果なども掲載しました。

ぜひ、ご一読していただけたら幸いです!

仕事が少し落ち着いてきたのでそろそろblogを再開したいと思います!!


東工大の奥村先生監修、高村先生著の「言語処理のための機械学習入門」が発売されました。これは読まなければ!と思い、さっそく手に入れました。本書の感想は本当にシンプルな一言に尽きます。

「大学時代にこの本がほしかった。。。」

本書の目次の中見出しまでを以下に引用させていただきます。

1. 必要な数学的知識
1.1 準備と本書における約束事
1.2 最適化問題
1.3 確立
1.4 連続確率変数
1.5 パラメータ推定法
1.6 情報理論
1.7 この章のまとめ

2. 文書および単語の数学的表現
2.1 タイプ、トークン
2.2 nグラム
2.3 文書、文のベクトル
2.4 文書に対する前処理とデータスパースネス問題
2.5 単語ベクトル表現
2.6 文書や単語の確率分布による表現
2.7 この章のまとめ

3. クラスタリング
3.1 準備
3.2 凝集型クラスタリング
3.3 k-平均法
3.4 混合正規分布によるクラスタリング
3.5 EMアルゴリズム
3.6 クラスタリングにおける問題点や注意点
3.7 この章のまとめ

4. 分類
4.1 準備
4.2 ナイーブベイズ分類器
4.3 サポートベクターマシン
4.4 カーネル法
4.5 対数線形モデル
4.6 素性選択
4.7 この章のまとめ

5. 系列ラベリング
5.1 準備
5.2 隠れマルコフモデル
5.3 通常の分類器の逐次適用
5.4 条件付確立場
5.5 チャンキングへの適用の仕方
5.6 この章のまとめ

5. 系列ラベリング
5.1 準備
5.2 隠れマルコフモデル
5.3 通常の分類器の逐次適用
5.4 条件付確立場
5.5 チャンキングへの適用の仕方
5.6 この章のまとめ

6. 実験の仕方など
6.1 プログラムのデータの入手
6.2 分類問題の実験の仕方
6.3 評価指標
6.4 検定
6.5 この章のまとめ

数学的知識の解説が充実している

目次を見ただけで、納得していただけるのではないでしょうか。特に僕がよいと思ったのは1章の「必要な数学的知識」の充実振りです。僕も学生時代にはとても苦しんだのですが(今でも苦しみますが。。。)、時々、論文を読んでいて、「何がわからないかがわからない」ということがありました。
高村先生の先生としての経験の中から、機械学習を勉強するには、まずこれを知らないと理解ができないということをとてもよくまとめてくれているように思います。僕も学生時代にサポートベクターマシンを勉強しているときに苦しんだのですが、本書では以下のように解説されていて、当時にこれがあればなー!と思いました。

p.15

ラグランジュの乗数法をきっちり理解すれば、理解できる論文の数は激増するといってよいだろう。実際、確率分布のパラメータ推定でも(4.2節)、EMアルゴリズムでも(3.5節)、ナイーブベイズ分類器でも(4.2節)、サポートベクトルマシンでも(4.3節)、ラグランジュの乗数法が使われている。

素敵です。こういう情報があらかじめあるかないかで、論文を読むスピードはとても早くなると思います。学生のときはわけもわからず読み進め、わからないところがあっては、本で調べ、参考文献を読んで、を繰り返し、なんとなくわかってくることだと思うの\
ですが、本書を読めば、その時間がかなり短縮できるように思いました。

準備が素敵

3,4,5章の導入には「準備」と題して、これらの技法が実際どのように使われるのかが解説されています。本書の内容は一見、数学的で難しそうな感じもあるのですが、実世界とのリンクも考慮されていて、初学者にとっても理解しやすい構成となっています。

ビギナーな方にとってはとっつきにくいと感じられるかもしれない

本書は導入の時点で最適化問題や、ラグランジュの乗数法が解説されているため、ビギナーな方にとっては「なんか難しそう!」と感じて挫折感を味わってしまうかもしれません。しかし、これらは論文を読む上で、とっても大事な話が凝縮されているように見えます。そういった意味では、ものすごく親切な構成になっていると私は感じておりますので、ビギナーの方もあきらめずに読み進めることをお勧めします。

まとめ

今もぱらぱら読みながらこのレビューを書いているのですが、読むたびに、「あーこれ情報がなくて苦しんだんだよなー!」ってトピックがあって涙腺を緩ませながら読んでいます。最近は自然言語処理学での研究テーマは機械学習を用いた手法がトレンドとなっております。しかし、本書のように機械学習の勉強を始めるための解説書があまり無かったため、苦労する人が多かったのではないかと思います。本心で良い教科書だと思いました。本エントリーを読んで下さった皆さまもぜひご一読してみてください。


ほとんどネタ的な話なのですが,最近,OSSツールの多様化にともない,本当に便利になっているのですが,ツールの多様化とともに様々なプログラミング言語でプログラムを書かなかければならないことが増えてきました.Thriftなどを使えば,ある程度限られたプログラミング言語で作業できるので楽なのですが,どうしても特定の言語でツールのAPIを叩かなければならないことが多々あります.

autoconf

私は,普段はPerlやC++でプログラムを書くことが多いのですが,最近は上記の理由によりJAVAでプログラムを書く機会も増えてきています.それで,JAVAやC, C++などのプログラミングを行き来していると,いつもビルド環境を構築するのがとてもストレスになるんですね...

CやJAVAで開発する場合は,通常まずビルド環境を構築しなければなりません.C, C++であれば,Makefileを.JAVAであればantのためのbuild.xmlなどを書きます.で,これらの開発を行き来していると本当に,この環境を構築するだけで,ちょっとうんざりしてしまったりします.そこで,ご存知かと思いますが,Makefileをある程度自動で作ってくれる,便利なツールにautoconfがあります.

私もautoconfは使わせていただいており,とても作業が楽になるわけですが,だんだんとautoconfのconfを書くことするらもしんどくなってきます.

シンプルなautoconfの使い方

以下のエントリーで,id:mergentさんが,解説してくださっているように,だいぶ楽にできるようになったのですが,まだまだ手作業でやらなければならないことはたくさんあります.

autoreconfを使って簡単にビルド環境を作る

で,時間をかけてせっかくつくったにも関わらず,configuraとかがこけてしまうと「いやーん」という感じで,開発する意欲をものすごく下げます.これは,はっきり言って作業効率を下げます.やっぱりストレスフリーな開発環境を作りたいと思い,ネタ的なスケルトンを書いてみました.

なお,開発環境以外のストレスフリーな仕事術は以下の書籍が参考になります.

で,話を戻しますと,id:emergentさんのautoreconfの使い方は僕が知っている中で最もシンプルな方法です.概要を引用すると以下のようになります.

1. ソースコードを用意する
2. Makefile.amを用意する
3. configure.acを用意する
4. autoreconfを実行
5. あとは./configure && make && make install

シンプルですね.実際には開発にとりかかるには,ライブラリの部分と実行するプログラムとテストを切り分けたりとやや作業量は増えます.

autoconfを自動で実行するシェルスクリプト

そこで,僕はさくっとこのビルド環境のスケルトンを作るシェルスクリプトを書いて,それを使っています.使い方は簡単で引数に作りたいライブラリ名をあげるだけです.

./cpp_skelton.sh hoge

もしautoconfがないよ!って怒られたらインストールしてあげてください.

# autoconfのインストール

# ubuntuなど
sudo apt-get instal autoconf

# fedoraなど
sudo yum install autoconf

これで,hogeというライブラリ名のビルド環境が整います.スクリプトのソースを以下に示します.echoとかしまくっていておもしろかわいい,切ない内容となっていて笑えます.

使い方は簡単で,ソースをダウンロードして,実行権限を与えて実行するだけです.

wget http://gist.github.com/raw/412856/dda419e2c384410486572fd016a2d719f62b9d8d/cpp_skelton.sh

chmod +x cpp_skelton.sh

./cpp_skelton.sh hoge

実行すると以下のようなファイル構成となります.

cd hoge

tree hoge

hoge
├── AUTHORS
├── COPYING
├── ChangeLog
├── INSTALL
├── Makefile.am
├── Makefile.in
├── NEWS
├── README
├── aclocal.m4
├── autom4te.cache
│   ├── output.0
│   ├── output.1
│   ├── requests
│   ├── traces.0
│   └── traces.1
├── autoscan.log
├── config.guess
├── config.h.in
├── config.sub
├── configure
├── configure.in
├── configure.scan
├── depcomp
├── install-sh
├── ltmain.sh
├── missing
└── src
    ├── Makefile.am
    ├── Makefile.in
    ├── hoge.cpp
    ├── hoge_test.cpp
    ├── libhoge.cpp
    └── libhoge.hpp

プログラムはすべてsrcディレクトリに格納されています.プログラムの構成は以下のようになっています.

* libhoge.hpp libhoge.cpp : ライブラリの実装用のプログラム
* hoge.cpp : ライブラリ実行用のプログラム
* hoge_test.cpp : テスト用プログラム make checkで使われます.

ここまで整ったらもう,ビルドできる状態となっています.

./configure

make

make check

sudo make install # install はしない方がいいと思います!

sudo make uninstall

make clean

かなり,俺俺な構成となっていますが,ここまでできてしまえば好みの構成に変更するのは簡単です.スクリプトを変更した方が早いかもしれませんが...

なお,このスクリプトはfedora11とubuntu2.6で動作確認をしましたが,macなどでは動かないかもしれません.

ストレスフリーな開発環境を目指してこれからも精進したいと思います!

なおなお,autoconfには細かい環境変数などがたくさんあって,ちゃんと使うにはある程度勉強しなければなりません.私は以下の書籍を読んで勉強しましたが,よくまとまっていておすすめです.Makefileの仕様についても記述されているので,初心者の方にも\
お勧めでございます.

読んでくださった方で,おすすめなストレスフリーな開発環境がございましたらご教授願いますー!


お久しぶりです,木村です.

最近どうもやることが多くてエントリーを書けずにいました...これからはまたちょっとずつ書いていこうと思います.というかメモですね.

正規表現ライブラリRe2

つい先日Googleにより,正規表現ライブラリがリリースされたのは有名な話ですね.

Re2とは

米Googleは3月11日、正規表現ライブラリ「RE2」を発表した。動作が高速で「スレッドフレンドリー」な点が特徴。従来のバックトラック型正規表現ライブラリの代替として開発を進めていく。

http://sourceforge.jp/magazine/10/03/15/0331223より引用

だそうです.

僕もしばしば言語処理のプログラムを書くときは正規表現を使うので,これは良さそう!ってことでRe2を物色してみました.

Re2を使ってみた

使い方はPerlの正規表現っぽく使えて簡単です,後方参照とかもできます.

詳しくはヘッダーファイルを読んでいただくとして,ヘッダーファイルからパクってきた簡単な後方参照のサンプルを載せておきます.Re2がインストールされている環境で行ってください.

以下のサンプルコードをRe2test.cppという名前で保存します.


このコードを以下のようにコンパイルします

g++ -Wall -I/usr/local/include Re2test.cpp -lre2 -lpthread

超簡単ですね.他にも色々機能がありますのでぜひヘッダーファイルをご参照ください.

Re2のスピード

そこで,ベンチマークをとってみようかなあと思ったのですが,以下のエントリでid:tkuroさんがすでにベンチをとっておられました.結論「RE2はええ」だそうです.

Re2のメモリチェック

使い方もわかったので,そろそろvalgrindをかけたくなるというのが男の性.
そこで,先ほどのサンプルプログラムにvalgrindをかけて実行してみました.

valgrind ./a.out

ををを・・・?
めちゃくちゃメッセージがでてきましたね.

メッセージの要約

==13496== Conditional jump or move depends on uninitialised value(s)
==13496== at 0x8069B9A: re2::Prog::Optimize() (sparse_array.h:296)
==13496== by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496== by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496== by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496== by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496== by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)
==13496==
==13496== Use of uninitialised value of size 4
==13496== at 0x8069D9B: re2::Prog::Optimize() (sparse_array.h:296)
==13496== by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496== by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496== by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496== by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496== by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)

==13496== ERROR SUMMARY: 866 errors from 41 contexts (suppressed: 16 from 1)
==13496== malloc/free: in use at exit: 0 bytes in 0 blocks.
==13496== malloc/free: 265 allocs, 265 frees, 40,326 bytes allocated.
==13496== For counts of detected errors, rerun with: -v
==13496== Use --track-origins=yes to see where uninitialised values come from
==13496== All heap blocks were freed -- no leaks are possible.

以下の32bit環境?64bit環境でチェックしましたが,両方ともエラーが出ました.
* fedora core 11 32bit
* fedora core 11 64bit
* g++ (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2)

エラーメッセージを追ってみるとどうやら,複数の個所でイニシャライズされていない領域を使用しているように見えました.深追いするとちょっと時間がかかりそうなので今回は深追いはやめました.どうやらエラーの中のひとつはdfa.ccの中にあるAddToQueue()という,おそらくジョブをキューに追加する関数の中で起こっているようですが,明確なことは言えないので調査が済んだらまたエントリーを書きたいと思います.

Re2にパッケージングされているテストを実行しても同じようにエラーが出たので,おそらくどこかに不具合があるのだと思いますが...もし僕のケアレスミスでしたらごめんなさい.

もうちょとRe2のソースをよく読んでみたいと思いますー.


プログラム保存用

#include 
#include 

using namespace re2;

int main(void) {

  int i = 0;
  std::string s = "";
  
  if(RE2::FullMatch("hello", "h.*o")) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s, &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby", "(.*)", &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby:1234", "\\w+:\\d+", &s)) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s)) std::cout << "PASS" << std::endl;
  
  return 0;
}


寒くなってきましたね.秋です.ブログを更新する時間がなかなか確保できませんな今日この頃です.

はじめに

今日は機械学習におけるソフトの「再利用」と「再実装」についておもしろい記事を見つけたので引用しながら考察したいと思います.このトピックに関しては機械学習だけに限らず,すべてのソフトにおいていえると思います.ソフトの「再利用」と「再実装」
に関しては,私は学生時代から結構議論になっていましたし,そして現在ビジネスシーンでもこれについては議論になります.特にビジネスでは工数という概念があるためなるべくなら「再実装」はしたくないという前提がありますよね.

本日引用する記事は以下の記事です.

Re-implement or reuse?
Posted by Cheng Soon Ong on October 14, 2009

このブログはmloss.org(machine learning open source software)という機械学習に関する手法の実装を登録・検索できるサイト上の有
識者による機械学習に関するコラムに掲載されていた記事です.ここのサイトは実装の検索だけでもかなり有用なのですが,何気にブログもおもしろい!ということを渋谷の中心で叫びたいと常々思っていました.

Why reuse and Why re-impelment

さて,上記の記事で「再実装または再利用?」というタイトルで以下のように,それぞれのメリットを論じています.

Why reuse
    ■ Standard software engineering practice 
    ■ antipattern (reinvent the wheel) 
    ■ Better than "hacked up" own version
    ■ Save time by outsourcing maintenance

Why re-implement
    ■ Existing solution is not good enough
    ■ Educational purposes
    ■ Not aware of other solution
    ■ Existing interface changes too often

Re-implement or reuse? より引用 詳しくは参照先のエントリーを参照されたし.

和訳

  • なぜ再利用するか
    • 一般的なソフトウェア工学の慣習のため
    • アンチパターン(車輪の再発明)
    • 自分で作るよりも優れているため
    • メンテナンスの時間がとられない
  • なぜ再実装するのか
    • 既存のソリューションは十分ではない
    • 教育的な目的
    • すでに存在するソリューションの存在に気づいていない

考察

当たり前といってしまえば当たり前のことのなかもしれないですが,今後の自分のためにもこのトピックに関して自分なりの考えをまとめておきます.
ある問題を解決するときには,考えなしにすぐに再実装するのではなく,再実装するにせよ再利用するにせよ,必ず既存の実装について調査をしなくてはならないと思っています.例えば,既存の実装では,マシンスペックをどれぐらい要求するのか(特にメモリ使用量など),処理時間はどれぐらいかかるのか,APIは適切に実装されているかなどを調べなくてはならないと考えています.この調査をしっかりしていなければ,再実装した際に評価する指標も無いし,もしかしたら劣ったものを実装してしまう可能性もあるため
です.再利用できるかを検討する際は,「自分が求める要求」と「既存の実装に足りないこと」を照らし合わせ,再実装したほうが早いか,既存の実装を修正し再利用したほうが早いかを検討します.

ちょっと中途半端ですが今後もこの話題に関しては機会があったらまとめたいと思います.この手の話題は結構ソフトウェア工学系の分野では語り尽くされているのかもしれないので,その手の本を読んだときにまた再考したいと思います.

もし,読んでくださった皆様にも意見がございましたら,お気軽にコメントくださいませ.


thriftとかhadoopなど,何やらいろいろと手を出してしまい,ここのところブログの更新が滞ってしまっていますが,今日は前から書きたかったトピックについて自分へのメモの意味も含めて記しておきたいと思います.

はじめに

最近,といっても結構前からなのですが,海外のブログなどで「機械学習の勉強を始めるガイドライン」についてのエントリーがいくつか見られ,かつ,議論も少し盛り上がっています.僕は機械学習が好きなだけで,専門というにはほど遠いのですが,僕も一利
用者としてはこのトピックに関してはとても興味があります.

機械学習というと,色々な数学的な知識が必要であったり,統計学や人工知能の知識も必要になったりしまったりと,専門的に学ぶ機会が無かった人にとっては興味が湧いてもなかなか始めるには尻込みしてしまうことかと思います.今日紹介するエントリーは,
そんな方々にヒントになるような内容になっていると思います.基本的なことを体系的に説明しているのでとても質が高いです.

紹介するエントリー : Guide to Getting Started in Machin Learning

要約になりますが,上記のエントリーでは機械学習の勉強を始める流れを以下のように説明しています.

The Elements of Statistical Learning Data Mining, Inference, and Prediction.を読む

  • なんとこの本は[[PDF|http://www-stat.stanford.edu/~tibs/ElemStatLearn/]]が公開されていますので参照してください.
  • この本は有名な教科書なのですが,これのチャプター1のIntroductionを読んで概要をつかむと良いと言っています.
  • Introductionには統計学習がどのような分野で応用されているかなどがまとめられています.
  • 医療分野や,マーケティング,画像処理,e-mailのスパムフィルタリングなど

Rで試す

  • The Elements of Statistical Learning Data MiningのIntroductionを読んだら,をダウンロードしましょう.
  • GoogleやFacebookではRがどのように活用されているかを記したエントリーのリンクがありおもしろかったです.How Google and Facebook are using R

Googleの場合

The typical workflow that Bo thus described for using R was: 
(i) pulling data with some external tool,
(ii) loading it into R,
(iii) performing analysis and modeling within R,
(iv) implementing a resulting model in Python or C++ for a production environment.

上記を意訳で要約すると,GoogleのBoさんはRを以下のように使っているようです.

  • 何らかの抽出ツールでデータを取得する
  • Rに読み込ませる
  • Rを使って解析したりモデルを作ったりする
  • 結果のモデルをPythonやC++で実装する

といった感じで,つまりプロトタイプの段階でRを使って実験するようですね

データを使う

Rで何かしらので機械学習の手法を使うには,データが必要となります.学習やテスト(分類)に使うデータをよくデータセットというのですが,これを集めるのは容易ではありません.以前にここのサイトでも紹介したデータセット集(Classicicationにおけるデータセット)をこのエントリーでも紹介しています.

UCI Machine Learning Repository: Data Sets

ここのデータセットを使ってRで遊んでみると良いでしょう.エントリーでは,先ほど示したThe Elements of Statistical Learning Data Miningを読み進めてRで実装してみると良いと言っています.

個人的には直感的に学ぶにはWekaもいいと思っています.wekaについては後述します.

Bishop本を読む

他にも機械学習の教科書は山ほどあるのですが,以下の本がおすすめだと言っています.

この本はかなり評判がいいですよね.実は僕は図書館で必要な箇所を読んだことしかないのですが,よくまとまっていた記憶があります.これは和訳が販売されていて,これもかなり評判がいいですね.結構色々なところで読書会とかもされているようですね.僕
も買わなくちゃ.Bishop先生が書いた本ということで,一部ではBishop本と呼ばれているようです.

授業の動画ライブラリを見る

昨今は本当に便利な時代になって,スタンフォード大学の機械学習の授業を見ることができます.

Course Machine Learning

以下が授業で使っているハンドアウトになります.

CS229 Machine Learning Course Materials

実は,これは僕もジムで筋トレしながらこつこつと見ていたのですが,とてもおもしろいです.でも,音声が英語ということもあって,英語力も要求されるため,機械学習に関して全く知識が無いと聞き取りが大変かもしれないので,英語が得意ではない方は一通
り勉強し終わってから復習の意味で見ると良いかもしれません.

以上が上記のエントリーに記述されていた,機械学習の初学者のためのガイドラインとなります.

で,自分はどう思うか

で,自分もまだまだ初学者の一員ではあるのですが,自分なりに機械学習を勉強する事始めとして良いのではないかと思っていることをまとめておきます.もちろん,これは賛否両論あると思いますし,人によって効率の良い学習方法は違うと思いますので,これ
は一アイデアとして読んでいただけたらと思います.

まずは,興味を持った手法を徹底的に学び尽くす

私は機械学習の全体の知識をいきなりつけようとすると挫折してしまう可能性が高いと思っています.特に昨今のアルゴリズムはとても複雑なモデルを使うようになっており,理解に時間がかかるものが多くあります.そこで,私としては(当時の私は)自分がやりたいことが達成できそうなアルゴリズムを1つに絞って勉強するというスタンスをとりました.そして,そのアルゴリズムは初学者であれば単純なものが良いと思います.例えば,機械学習の分野(明確には機械学習の分野とは言えませんが)で単純なアルゴリズムで,威力があるものでは,Naive Bayesや,decision tree,KNNなどがあります.これらのアルゴリズムはデータマイニングや,パターン認識などですぐに使うことができます.人によっては式だけ眺めてうなっているよりも,作りながら悩んだ方が理解が早いことがあります.動かしながらだと直感的に理解できるんですね.もちろん,人それぞれ学習の仕方があると思うので万人には通用するとは思っていません.

そして,一つのアルゴリズムを徹底的に学ぶといっても,実は全然一つでは収まらなくなります.例えばNaive Bayesを使ってみよう!と思ってNaive Bayesの論文などを読むと,その論文の中には細かい引用がたくさんされています.そして,その引用先の論文で言っている手法を理解していないと,その論文で言っていることがわからなかったりします.結局一つの論文を読むのに,10以上の論文を読むことになったりします.だから,簡単なアルゴリズムでもちゃんと理解しようするにはとても苦労するんですね.だけど,学ぶことがたくさんあるからそういうことをしているうちにだんだん幅広い知識がついてくる,と経験上思いました.

オープンソースのライブラリから学ぶ

僕がこれらの勉強を始めた当時は,実はあまりオープンソースのライブラリの情報がそこまで出回っていませんでした.しかし,今は本当に多くの,かつ質のいいオープンソースの機械学習のライブラリがあります.教科書を見ていてよくわからない!という方は人の実装を見ながら仕組みを理解するといいと思います.数式がものすごく難しく説明されていても,ソースを見ると意外に実装は簡単だったりするものもあります,自分の力だけで実装するのもいいし,人の実装を参照しながら自分の実装をするのも良いと思います.

一例ではありますが,最近では以下のようなものがあります.(全部細かくは調査していません)

nltk

  • http://code.google.com/p/nltk/
  • Python
  • 自然言語処理のライブラリなのですが,機械学習のアルゴリズムも多く実装されています.
  • Pythonということもあって,処理は遅いですがコードは読みやすいのでプロトタイプとしてはおすすめです.
  • クラスタリング・分類関係だと以下のような手法が実装されています
    • decision tree
    • maximam entropy
    • naibe bayes
    • kmeans

weka

  • http://www.cs.waikato.ac.nz/ml/weka/
  • JAVA
  • このサイトでもちょっと紹介したwekaですが,これはJAVAで実装されたData miningツールで多くの機械学習の手法が実装されています.
  • 有名な手法はだいたい実装されています.スピードもそこそこ出るのでちょっと遊んだり実装を見るにはおすすめ.

Mahout

  • http://lucene.apache.org/mahout/
  • JAVA
  • Hadoop上で動く機械学習ライブラリです.これは初学のためにはお勧めできませんが,Hadoop上で動くということもあり,実用上使えると思って現在調査中です.

まとめ

今回は素人の素人による素人のための機械学習事始めということでエントリーを書かせていただきました.実は僕は勉強の仕方は「何が一番いい」っていうのは無いと思っています.でも,勉強するために手助けになるための情報は存在すると思っています.それを一度まとめておきたいなと思って,書かせていただきました.もし,こんな情報があるよ!とか,こうやると効率がいいよ!というアイデアがある方がいらっしゃいましたらご教授いただけたらと思います.


10/14 追記
shima_shimaさんより参考になるご意見をいただいたので追記しておきます。以下shima_shimaさんのコメントを整理して引用させていただきます。

  • Bishop本のレベル表

http://ibisforest.org/index.php?PRML/course

  • その他参考になる本
    • 強化学習なども解説されているが古い部分もある
    • カーネル
    • マルコフ連鎖
    • 入門で優しい内容
    • Bishopレベル表の入門レベルの内容
    • Bishopレベル表の入門レベルの内容
  • #% 2009-10-13T02:16:16+09:00|shima_shima|PRML本翻訳の仕掛け人です.とりあげていただいてどうもです. EoSL本は,Bishop本より高度だと私は思っています.加算型モデルを重視しています.ちょっと,内容的には我田引水があると思います. Bishop本は,ややカーネルが多く,全体をベイズの観点で見ているという特徴があります.Bishopさんの筆力により,読みやすい本だと思い翻訳を思い立ちました. いろいろなレベルの内容が混ざってますので,レベル表を作りました http://ibisforest.org/index.php?PRML/course あと,著名な本は Tom Mitchell の Machine Learning です.強化学習とかもちょっと載ってますが,やや古くなってきました. カーネル系にご関心があれば,赤穂「カーネル多変量解析」岩波 とか,MCMCとかなら伊庭 他「計算統計II — マルコフ連鎖
    モンテカルロ法とその周辺」岩波 とかかと. より入門的な内容としては,ブログの内容を拝見していると,おそらく簡単すぎるかと思いますが,荒木「フリーソフトで作る音声認識」森北の第1部 が一番やさしいと思います. その次だと,麻生 他「パターン認識と学習の統計学」岩波とか,元田 他「データマイニングの基礎」オーム社あたりかと思います.この辺が,Bishop本のコース表の入門レベルとお考え下さい. 線形代数と確率は多少いりますが,l^2空間とか,複素数とか,可則集合とかまで踏み込む必要はないので,高校数学 + Bishop本の1章+付録で事足ります. 機械学習にご関心をもっていただいて嬉しいです.以上,よろしければ,ご参考になさって下さい.
  • #% 2009-10-13T11:08:37+09:00|shunya|shima_shimaさん: 貴重なコメントありがとうございます!感激です. レベル表を拝見させていただきました.素晴らしいです! こういう指標があると学習するときは助かりますね.また,すべてではないですが各項目に解説ページが貼られているがとても便利だと思います.ご存知かとは思いますが,英語のwikipediaの機械学習のページが結構網羅的に書かれていて,普段はそこを参照したりしているのですが,shima_shimaさんのページもレパートリーに追加したいと思います. http://en.wikipedia.org/wiki/Machine_learning_algorithms レベル表を拝見していて思ったのですが,初学の場合はリストの「基礎」項目だけ読んでみて雑感をつかむのも良いかもしれませんね.項目を見ていて改めて良い本だと思いました.買っちゃいます. ご紹介をいただいた本では,麻生 他「パターン認識と学習の統計学」岩波は当時SVMの勉強をしていたときに読みました.当時はあまりこの手の本が無かったので重宝していた気がします. – 赤穂「カーネル多変量解析」岩波 – 伊庭 他「計算統計II — マルコフ連鎖モンテカルロ法とその周辺」岩波 – 荒木「フリーソフトで作る音声認識」森北の第1部 – 元田 他「データマイニングの基礎」オーム社 これらの本で,岩波のものは前から気になっていたのですが目を通せずにいました.Bisiop本の入門編といった感覚で読んでおきたいと思います.というのも,実は今回書いたエントリーの内容は入門としては難しいと感じておりました.しかし,入門の入門,つまりshima_shimaさんが紹介してくださったような本の情報が少ないように感じていて,そこらへんの情報を勉強がてら少しずつ整理していきたいと思います.
  • #% 2009-10-14T11:53:41+09:00|anonymous|PDFのリンクのURLにtypoがありました
  • #% 2009-10-14T11:57:44+09:00|m11m|荒木先生の本ですが、タイトルは軽いですけど中身は教科書です。学部の講義で使われていました。
  • #% 2009-10-14T14:13:28+09:00|shunya|anoymousさん: 修正しましたー。ご指摘ありがとうございます。
  • #% 2009-10-14T14:15:15+09:00|shunya|m11mさん: 情報提供ありがとうございます!amazonで目次を読んでみたのですが、基礎事項が整理されているよう良さそうですね。参考に読んでみますー。


ここまでの流れの整理をします。Thriftの調査の続きです。前回のエントリー(Thriftのスピードが改善しました)では、Thriftのperlクライアントが遅いのはNagleアルゴリズムが原因ではないかという仮説をたて、そしてNagleアルゴリズムをオフにした状態で速度が向上したことを書きました。

それに対し、tokuhiromさんにより投稿されたエントリー(ThriftはThrift::BufferedTransport をつかいわすれると 147 倍遅くなってつかいものにならない)では、send(2)のバッファリングをしていないことが原因で、Thriftが吐き出すデフォルトのperlクライアントのスケルトンでは使われていない
Thrift::BufferedTransport を使うことによってsend(2)がバッファリングされて、高速になることを示してくれました。加えてkazuhookuさんのご指摘によりread(2)もバッファリングしてないため遅いとのこと。僕の環境でもThrif::BuffredTransporを使うことによって高速化することを確認しました。

そして、「Thriftのスピードが改善しました」のエントリーに対して、はてぶコメントでkazuhookuさんに以下のコメントをいただきました。kazuhookuさん、ありがとうございます!

282QPSってむちゃくちゃ遅いと思う。てか、サーバサイドのロジックがここまで単純なら、多重化してベンチとるべき / これだとパケット流れまくるのでせめて MSG_MORE とか使うべき

http://b.hatena.ne.jp/entry/blog.broomie.net/index.cgi?id=38 より引用

MSG_MOREについて

ご指摘をいただくまで知らなかった&調べてみてわかったのですが、確かにTCP_NODELAYにするのであれば、MSG_MOREを使ったほうが良いみたいですね。冗長で恐縮なのですが、メモの意味も含めて整理すると、TCP_NODELAYというのはmanで以下のように解説されて
います。

% man tcp

ソケットオプション
  TCP ソケットのオプションは、オプションレベル引数に IPPROTO_TCP を指定した setsockopt(2) で設定でき、 getsockopt(2)で取得できる。さらに、ほとんどの IPPROTO_IP ソケットオプションも TCP ソケットに対して有効である。詳細は ip(7)を見よ。

TCP_NODELAY
  設定すると Nagle アルゴリズムを無効にする。すなわち、データ量が少ない場合でも各セグメントは可能な限り早く送信される。設定されていないと、送信する分だけ溜まるまでデータはバッファされ、小さなパケットを頻繁に送らずにすみ、ネットワークを有効に利用できる。このオプションは TCP_CORK により上書きされる。しかしながら、 TCP_CORKが設定されている場合であっても、このオプションを設定すると、送信待ちの出力を明示的に掃き出す (flush) ことになる。

以前のエントリーと繰り返しになってしまいますが、上記の引用のようにTCP_NODELAYを有効にすると 「データ量が少ない場合でも各セグメントは可能な限り早く送信される」 わけですね。そうすると、今回の実験のケースのような場合、細か
いパケットが通常よりも大量に送信されてしまう可能性があります。そこで、それを防ぐためにせめてMSG_MOREを使ったほうが良いという指摘をうけたのだと思います。MSG_MOREが何なのかというman sendで以下のように解説されています。

% man send

MSG_MORE (Linux 2.4.4 以降)
  呼び出し元にさらに送るデータがあることを示す。このフラグは TCP ソケットとともに使用され、TCP_CORKソケットオプションと同じ効果が得られる (tcp(7) を参照)。TCP_CORK との違いは、このフラグを使うと呼び出し単位でこの機能を有効にできる点であ
る。Linux  2.6 以降では、このフラグは UDP ソケットでもサポートされており、このフラグ付きで送信された全てのデータを一つのデータグラムにまとめて送信することを、カーネルに知らせる。まとめられたデータグラムは、このフラグを指定せずにこのシス
テムコールが実行された際に初めて送信される (udp(7) に記載されているソケットオプション UDP_CORK も参照)。

これだけではわからないので、TCP_CORKも引用しておきます。

% man tcp

TCP_CORK
  セットされると、partial フレームを送信しない。このオプションが解除されると、キューイングされたpartialフレームが送られる。これはsendfile(2)を呼ぶ前にヘッダを前置したり、スループットを最適化したい場合に便利である。現在の実装では、TCP_CORKで出力を抑えることができる時間の上限は200ミリ秒である。この上限に達すると、キューイングされたデータは自動的に送信される。Linux 2.5.71 以降においてのみ、このオプションをTCP_NODELAYと同時に用いることができる。移植性の必要なプログラムでは
このオプションを用いるべきではない。

この解説の通り、部分的な小さいフレームは送信せずにキューイングしたかたまりを送ってくれるようになります。そして、このフラグはTCP_NODELAYと同時に用いることができます。上記で引用したTCP_NODELAYの解説によるとTCP_CORKによってTCP_DELAYは上書きされてしまい、TCP_MSGが優先されるようですね。しかし、送信待ちの出力を明示的にflushするとなっているが、これがどう振る舞いに影響するのかはもっと詳しく調査してみないと定かではないのでここでは述べないことにします。

MSG_MOREをThrift::Socketで使ってみようと思って、perlライブラリに入ってるSocketを見てみたのですが、まだMSG_MOREは対応していないみたいでした。おそらくDanga::Socketなどを使えばできそうかもしれませんが、Thrift::Socketを大々的に書きかえる作業は今はやりたくないので今回はあ
きらめました。

で結局どうしたらいいのか

ここまでの考察で、確信はできないけれどもTCP_NODELAYやMSG_MOREを使うことは場合によっては危うい感じもします。であれば、少しでもリスクになりうるTCP_NODELAYフラグは使わないほうがよいと僕は結論を出しました。というのもtokuhiromさんによって示された、Thrift::BufferedTransportを使ってreadをバッファリングする方法で十分に高速化できることを確認できたためです。


多重化してベンチをとる

「282QPSってむちゃくちゃ遅いと思う。てか、サーバサイドのロジックがここまで単純なら、多重化してベンチとるべき」とのご指摘をうけ、「うう、確かにそうだなあ。。」と思い、server(c++) + client(perl + Thrift::BufferedTransport)の構成でクライア
ントを多重化してベンチをとってみることにしました。

server側をマルチスレッドにする

今回もプログラムは以前のエントリー(Thriftが便利すぎる)で紹介した「足し算・引き算」サーバを使います。この構成ではサーバ側はC++で
実装しています。そしてTSimpleServer.hというシングルスレッドのサーバを使っているため、このままの状態でクライアントを多重化してsendしてもシングルスレッドで処理されてしまいます。TSimpleServerで当方の環境で多重化したクライアントで使用したら
サーバがアボートしました。

そこで、今回はマルチスレッドのサーバを作成することにします。したがってTSimpleServerではなく、TThreadPoolServerを用います。そのほかにもサーバ用ライブラリはいくつかありますが時間の関係もあり全ては未調査なので、このエントリーでは他のライブ
ラリに関しては割愛させていただきます。以下に今回のベンチで使用したTThreadPoolServerを使ったサーバの実装を示します。

#include "TinyCalc.h"
#include 
#include 
#include 
#include 
#include 
#include 

using namespace apache::thrift;
using namespace apache::thrift::protocol;
using namespace apache::thrift::server;
using namespace apache::thrift::transport;
using namespace apache::thrift::concurrency;


using boost::shared_ptr;

class TinyCalcHandler : virtual public TinyCalcIf {
public:
  TinyCalcHandler() {
    // Your initialization goes here                                                                                                                                                
  }

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

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

int main(int argc, char **argv) {
  int port = 9090;
  int workerNum = 50;
  shared_ptr handler(new TinyCalcHandler());
  shared_ptr processor(new TinyCalcProcessor(handler));
  shared_ptr serverTransport(new TServerSocket(port));
  shared_ptr transportFactory(new TBufferedTransportFactory());
  shared_ptr protocolFactory(new TBinaryProtocolFactory());
  shared_ptr threadManager = ThreadManager::newSimpleThreadManager(workerNum);
  shared_ptr threadFactory =
    shared_ptr(new PosixThreadFactory());
  threadManager->threadFactory(threadFactory);
  threadManager->start();
  TThreadPoolServer server(processor, serverTransport, transportFactory,
                           protocolFactory, threadManager);
  server.serve();

  return 0;
}

TSimpleServerとの大きな違いはスレッドのマネージャとしてThreadManagerを使うことです。上記の例のように使い方は簡単です。ThreadManager::newSimpleThreadManager(workerNum)この関数では、ThreadManagerを生成するときにworkerの数を指定します。今回は50にしましたが環境に合わせて引数を与えてください。

今回ベンチに使用したソースをUPしておきましたので、ご興味がある方は参照してみてください。コンパイルの仕方などは同封されているREADMEに記載しておきました。

TinyCalc.tar.gz

ベンチ方法

今回のベンチテストではサーバー1台、クライアント8台の構成で行いました。サーバ、クライアントすべて以下のスペックです。

cpu: AMD Opteron 2.4GHz * 4core
memory: 4GB

サーバについて

サーバのプログラムは上記のTinyCalc_server.cppを用い、ThreadManagerの引数に与えるworkerの数は50で行いました。

クライアントについて

クライアントはperlクライアントを用い、実装を以下に示します(TinyCalc.tar.gzに入っています)。localhostの部分は環境にあわせて修正してください。

1クライアントに5プロセスずつ同時に走らせ、クライアントサーバはすべてで8台あるので合計40プロセスが同時に1台のThriftサーバに問い合わせます。

#!/usr/bin/env perl

use strict;
use warnings;
use FindBin;
use lib "$FindBin::Bin/gen-perl/";

use lib './gen-perl';
use Thrift;
use Thrift::BinaryProtocol;
use Thrift::BufferedTransport;
use Thrift::Socket;
use TinyCalc;

use constant TEST_NUM => 100000;

my $transport = Thrift::Socket->new('localhost', 9090);
my $client = TinyCalcClient->new( Thrift::BinaryProtocol->new(Thrift::BufferedTransport->new($transport)) );
$transport->open();

for(my $i = 0; $i < TEST_NUM; $i++){
    my $arg1 = int(rand(10000));
    my $arg2 = int(rand(10000));
    my $sum = $client->sum($arg1, $arg2);
    my $subst = $client->subtract($arg1, $arg2);
    print "$sum\t$subst\n";
}
$transport->close();

結果

上記の構成で5回計測したところ平均28649QPSとなりました。処理は簡単であるためサーバ側のCPUはまだまだ余裕だったので,クライアントが増えればまだあげられると思います。でも、そろそろネットワークがボトルネックになるような気もしました。

考察

僕が想定しているThriftのユースケースでは、主に分類器やクラスタリングなどに使おうと思っています。分類器などの場合は、分類器自体の計算量が高いのでボトルネックは分類器となる可能性が高いと思います。今回Thriftで簡単な処理をさせて約3万QPSが出ることが確認できたので、分類器などを使う場合、Thriftは十分なスピードかな、と思いました。分類器でThriftを使う場合は転送させるデータ量も意識しないといけないので、圧縮して送ったりしないといけないかな、とか考えたりしています。

まだThriftのチェックできていないライブラリも多くあるので、今後もよさそうな情報があったらエントリーを書きたいと思います。情報提供していただいた皆様ありがとうございましたー。当方、ネットワークの知識はあまりないのでとても勉強になりました。
多謝多謝。


今日帰宅したら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を使ってこの手のプログラムを書いたら紹介したいと思います
    ー。