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

はじめに

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

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

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


    今日会社で多次元のデータを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機能もあるようですし、ちょくちょく目を向けたいと思います。おもしろい論文があったら紹介したいですね。