『集合知プログラミング』のR実装

Sep 18, 2008

Rも相性がいいですね。

http://d.hatena.ne.jp/mrkn/20080725/collective_intelligence_in_gnu_r

R や SQL のように、データの集合に対して同じ演算を一括して実行するような記述ができる言語は、協調フィルタリングを簡潔に書ける。より正確には、繰り返し処理を書かないで済む。

とはいえ、『集合知プログラミング』で使われている Python の list comprehension もきれい。オブジェクト指向言語なら、”Collective Intelligence in Action” で示されているように、データそのものに演算を定義することによっても、読みやすいコードになる。

協調フィルタリングは同じ演算を均一に行うけど、他のデータマイニング手法、例えば k-means clustering などは、条件による処理の分岐が欠かせないし、繰り返し処理も書くことになるだろう。

Yahoo! Search BOSS

Sep 12, 2008

Web全体をインデックス化して独自のサーチエンジンを作るには、数百億円かかるらしい。Yahoo! が公開した BOSS (Build Your Own Search Service) の API を使うと、資金力のない企業にも、アイデア勝負で独自の検索エンジンが作れる。

Yahoo! Search BOSS は、Yahoo! が莫大な資金を投入して作成した検索インデックス、検索機能を API を通じて公開するもの。Yahoo! Search API との違いは、クエリの数に制限が無いこと、検索結果の表示方法に自由があること、など。

クエリの数に制限が無いといっても、bot による大量データ取得などの、Yahoo! が意図しない利用に対しては、規約上、Yahoo! は制限することができる。

こんなサービスを無料で提供して、Yahoo! は何で儲けるのかというと、もちろん広告。

<blockquote>
8. FEES AND PAYMENT

Yahoo! reserves the right, in its sole discretion, to charge fees and/or require the display of Yahoo!-supplied advertising on Your Offering, under additional terms and implementation requirements, for future use of or access to some or all of the Services or other APIs made available by Yahoo!. If Yahoo! decides to charge for the Services or require the display of Yahoo!-supplied advertising, such charges
and additional terms and conditions (including implementation requirements designed to protect Yahoo! advertising networks and exclusivity for sponsored search advertising) will be disclosed to You prior to the effective date when such fees or requirements would be imposed.

http://info.yahoo.com/legal/us/yahoo/search/bosstos/bosstos-2317.html

= 抄訳 =

Yahoo! は、自らの判断で利用規約または実装規約を追加することにより、課金を行うか、または、検索結果に広告を表示することを要求する権利を持つ。課金または広告表示の要求を行う際には、事前に規約を公開する。
</blockquote>

検索結果に Yahoo! が提供する広告を表示するか、広告を表示しない代わりに利用料を払うか、のどちらかの選択ができるようになるらしい。

<blockquote>
REVENUE SHARING

In the near future, we will launch a monetization platform enabling Yahoo! and partners to jointly participate in the economics of BOSS-powered search products. Either Yahoo! sponsored search integration, with certain implementation and exclusivity requirements, or potentially a payment model, will be required above a specified query threshold.

収益の分配

近い将来、Yahoo! とそのパートナーが BOSS を用いた検索製品により収益を上げるための仕組みを立ち上げる。ある決められたクエリ数を超える場合は、実装上の制約と Yahoo! の独占利用の制約を行う。あるいは、課金を行う可能性もある。
</blockquote>

広告収入は、Yahoo! と BOSS の利用者との間で分ける。全て自前で作れば得られた筈の広告収入が減ることを受け入れる代わりに、資金力無しでは実現が難しい検索性能が手に入る。

Hakia という会社では、文書中に現れる人、場所、ものなどの概念を捉えた上で、適切な結果を返すサービスを BOSS を使って構築した。検索クエリを BOSS で処理して、得られた結果のページを、自社で持っているウェブページの意味データと組み合わせてランキングする。自社のデータベースにないページであれば、新たにクロールする。どのみちクロールするのだが、BOSS を使うことによって、必要のないページ、重要度の低いページのクロールを避けることができる。

Yahoo! Search BOSS は、Yahoo の戦略的なサービスなのだろう。
<ul>
<li>Yahoo! の検索結果が露出する機会を増やすことによって Google を追う。</li>
<li>BOSS の利用によって成功しそうな会社を見つけたら、買収する、かも。</li>
</ul>


参考
<ul>
<li>http://developer.yahoo.com/search/boss/</li>
<li>http://www.technologyreview.com/Infotech/21342/</li>
</ul>

『集合知プログラミング』の Ruby 実装

Sep 12, 2008

本を読みながら、『集合知プログラミング』の Pythonコードを Ruby に移植している人がいた。

http://www.thoughtstoblog.com/articles/2008/09/10/programming-collective-intelligence

コードはこちら

http://github.com/whoisjake/collective_intelligence_rb/tree/master

ratproxy のインストール (cygwin)

Sep 11, 2008

Google が公開した、Webアプリの脆弱性検査ツール ratproxy をインストールした。

1. ratproxy をダウンロードする。ここでは、1.51 をダウンロードした。

2. make する。
<blockquote><pre>
$ make
cc ratproxy.c -o ratproxy -Wall -O3 -Wno-pointer-sign -D_GNU_SOURCE http.c mime.c ssl.c -lcrypto -lssl
cc1: error: unrecognized command line option “-Wno-pointer-sign”
cc1: error: unrecognized command line option “-Wno-pointer-sign”
cc1: error: unrecognized command line option “-Wno-pointer-sign”
cc1: error: unrecognized command line option “-Wno-pointer-sign”
make: * [ratproxy] Error 1
</pre></blockquote>

エラーが出たので、対処してみる。Makefile を編集して、CFLAGS から -Wno-pointer-sign を削除した。

そして再度 make。

<blockquote><pre>
$ make
cc ratproxy.c -o ratproxy -Wall -O3 -D_GNU_SOURCE http.c mime.c ssl.c -lcrypto -lssl
ratproxy.c:43:25: openssl/md5.h: No such file or directory
http.c:42:25: openssl/md5.h: No such file or directory
http.c: In function checksum_response': http.c:1329: error: MD5_CTX’ undeclared (first use in this function)
http.c:1329: error: (Each undeclared identifier is reported only once
http.c:1329: error: for each function it appears in.)
</pre></blockquote>

cygwin のインストーラで、openssl-devel をインストールした。再度 make。

<blockquote><pre>
$ make
cc ratproxy.c -o ratproxy -Wall -O3 -D_GNU_SOURCE http.c mime.c ssl.c -lcrypto -lssl

* WARNING: flare-dist/flare bianry is not operational.
* Please see flare-dist/README and update it for your OS.
</pre></blockquote>

README を読んで、Win用のバイナリを取得、配置した。再度 make。

<blockquote><pre>
$ make

* WARNING: flare-dist/flare bianry is not operational.
*** Please see flare-dist/README and update it for your OS.
</pre></blockquote>

flare-dist/flare を削除して、再度 make したら、ratproxy.exe ができた。

SQL による『集合知プログラミング』の実装

Sep 10, 2008

『集合知プログラミング』のコードを Oracle の SQL (+PL/SQL) で実装するという意欲的な試みをする人がいた。Oracle Data Mining の開発マネージャである Marcos M. Campos さん。

http://3.1415.jp/sites/default/files/blogger_importer/09/collective-intelligence-1-building-rss.html

『集合知プログラミング』より前は、ビジネス向け、データ解析者向けのデータマイニング本がほとんどであった。開発者向けのデータマイニング技術の本が出たことに感銘を受けて、Oracle の SQL でも実装してみることにした、とのこと。第一回目は、RSSフィードの取得処理まで。

Oracle が XML を扱えることは知っていたが、HTTP も使えるそうだ。

<pre class="prettyprint">
req := UTL_HTTP.BEGIN_REQUEST(url);
resp := UTL_HTTP.GET_RESPONSE(req);
IF (resp.status_code >=400 AND
resp.status_code <= 599)
THEN
res := null;
ELSE
res := httpuritype(url).getXML();
END IF;
</pre>

Oracle なら robust で scalable な集合知実装になる、という前提の元に書いているが、コストを考えずに RAC を使えば、そうなるのかもしれない。しかし、安いサーバを並べて並列処理をするなら、他の方法で実装するほうが、Oracle のライセンスが不要な分だけ、安い。

協調フィルタリングのように、同じ演算を何度も繰り返すような種類の集合知実装なら、SQL での実装も選択肢の一つになりえる。一台の DBサーバで処理速度が間に合う規模のデータと更新頻度に収まっていれば、問題ない。全データをアプリに fetch して、結果を RDB に書き込むよりも、RDB 内部で処理を完結させた方が速そう。

アプリに全データを一気に読み込んで計算すると、メモリが足りるかどうかを気にする必要がある。メモリのことを気にするのは嫌だといって、必要なデータを逐次 RDB から取得すると、javascript:void(0)遅くなる。全て RDB で実装すれば、巨大なデータであっても、中間テーブルに書き出すなどして、RDBMS が適切に処理してくれる。