« September 2009 | Main | November 2009 »

2009.10.25

全文検索エンジン Miniseをリリース + WEB+DBで全文検索の特集記事

全文検索エンジンの Minise: MIni Search Engineをリリースしました.

このエンジンは全文検索の基本的な機能をサポートしたもので,索引手法は逐次検索(索引無),N-gram,転置ファイル,接尾辞配列をサポートしており,そこそこ最適化を行ってます.Wikipedia日本語版を実験で使ったもので20万文書で構築時間が500秒前後,検索時間が一クエリあたり数msとなっています.

BSDライセンスで公開しています.

割りきって,機能を絞ってシンプルな構成にしていますので改造したりしやすいようになっています。まだ、ドキュメントはないですが、C++ APIとして利用しやすいようにもなっていますので、研究用途などで新しい索引やランキングとかでの利用も想定しています(実際に研究用で使ってます).

---

今回の全文検索ライブラリを開発する機会になったのが,私が担当した今月号のWEB+DB Pressでの特集記事です.

・ WEB+DB Press Vol.53 特集記事「[速習]サーチエンジン」

この特集記事では,検索エンジンのついての話題全般を解説しています.

第1章ではサーチエンジン全般の話題について述べています。
- 検索エンジンの機能,性能,評価
- クローラ, インデクサ, サーチャの役割
- 全文検索の手法について
-- 逐次検索
-- 転置ファイル
-- N-gram (q-gram)
-- 接尾辞配列
-- 新しい索引,半転置ファイル,圧縮全文索引
- 検索エンジンの技術的困難性の境界
-- 日本語の単語区切り

第2章では実際に全文検索エンジンを一から作ってみます.これが今回公開したMiniseです.
- 各索引の構築
- 文書からタームの抽出.その効率的な格納方法
- 検索処理
- ランキング

また,後半では転置ファイル/N-gram索引の効率的な格納方法について扱います
- VarByte
- Rice符号
- Simple9/Simple16
- PFOR / New PFOR
- 整数列の格納サイズの下限, Rank/Select辞書

第三章ではその他の高度な話題を広く浅く扱いました
- 検索結果の評価 再現率・精度・ROC曲線
- ランキング手法
- ランキングの特徴情報
-- tf, idf
-- BM25
-- PageRank, Topical PageRank
-- 言語モデルによる単語の重要度
- ランキングの機械学習による学習(Learning to Rank)
- 大規模なデータの扱い方
- キャッシュ
- リアルタイム検索
- クエリログの利用
- 画像自体の情報を利用した画像検索 (SIFT)

最後に情報検索についての教科書や研究学会を紹介しています.

一般向けの雑誌で専門的な内容はどこまで書いていいのかわかりませんでしたが,
自由に書かせてもらいました。

もし、興味があるところが少しでもありましたら上の公開したソースコードと合わせて
読んでいただけたら幸いです。

---
今回、コマンドラインの入力オプション解析に同僚tanakh氏によるcmdlineを利用しています.
cmdline.hをインクルードするだけでつかえて、使い勝手がよいので
C++でいつもオプション解析が面倒だが、getoptはややこしいし、gflagsほど大きなものは
必要ないと思っている人は使ってみてください。ドキュメントはまだないですが、
cmdline内のtest.cppまたはminise内のminiseBuild.cpp miniseSearch.cpp
を見てもらえれば大体使い方がわかるかと思います。

| | Comments (1130) | TrackBack (0)

2009.10.08

天気予報から機械学習、金融工学まで

もう随分経ちますが,先日CompView秋の学校というのに行き,2泊3日みっちり機会学習を勉強してきました.講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです.

その話を説明するために,まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう.

解きたい問題は,毎日,次の日の天気が晴れか雨かを予想する問題です.t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう.t日目にy(t+1)を予想するわけです.

さて、自分は天気の専門家ではないので,自分で予報せずに,専門家に頼ることにしてみます.M人の天気予報士がいて,それぞれが独自に次の日の天気を予想しています.i人目の天気予報士のt日目の予報をp(i,t)∈{0,1}とします.

これらの天気予報士の予報を組み合わせて,次の日の予報をしてみます.

まず,全予報士に重み(信頼度)を設定します.m(i,t)がi番目の予報士に対するt日目の信頼度とします.初期値は1,つまりm(i,1)=1 for all iです.

次に,予想が外れた予報士の重みは下げることにします.つまりp(i,t+1)≠y(t+1)だった場合,m(i,t+1)=βm(i,t)とします.βは0<β<1で,どれくらい重みを減らすかの係数です.予報が当たった場合は重みはそのままとします.

最後に肝心の自分の予想をどう決めるかですが,これは重み付き多数決で決めます.晴れと予想した予報士の重みの合計と雨と予想した予報士の重みの合計を比較し,大きい方を採用します.

これが全アルゴリズムです.

さて、このアルゴリズムで,N日目までに自分が間違えた回数をwとします.また,ここまで,一番当たっている予報士i'が予想を間違えた回数をw'とおきましょう.このときwとw'がどういう関係になっているかを解析してみます.

まず,t回目の時点での全予報士の重みの合計をφ(t)とおきます.φ(t)=∑_i m(i,t)です.
次に,自分が間違えた時は重みが過半数な予報を採用しているはずなので
φ(t+1)<=(φ(t)/2) + (βφ(t)/2) = ((1+β)/2)φ(t)
が成り立ちます.
自分がw回間違えており,φ(t)=Mであることから,
φ(N)<=M((1+β)/2)^w (1)
が成り立ちます.
(x^yはxのy乗を意味します)
また,一番当たっている予報士の重みはw'回間違っているので,m(i',N)=β^{w'}です。
よって,
φ(N)=∑_i m(i,N)>=m(i',N)=β^{w'} (2)
が成り立ちます.(m(i,t)は全て正より)

さて,(1)と(2)を組み合わせると
β^{w'} <= M((1+β)/2)^w
がでてきます.これをwとw'について解くと
w <= (w' log(1/β) + logM) / (log(2/(1+β))
が求められます.例えばβ→1の時,大体w <= 2w' + logMとなるので,一番当たっている予報士の二倍以内で
予想できることがわかります.例えば,1万人ぐらい予報士がいれば一人ぐらいは殆ど当たっている人がいるでしょう.その場合でも,このアルゴリズムは誰がそれだけ当たるかをあらかじめ知らないながら、その人の二倍以内(logMの項はw,w'が大きくなれば無視できる)で予想できるということを意味しているので驚異的です.

さらに出力や予報に関して一切の仮定やモデルをおいていないことに注意しましょう.例えばこれまでよく当たっている人が次の日に当たるという仮定(いわゆるi.i.d.)は使っていません.悪意がある神様が重みが大きい方とは違う天気の方を出しまくっても上の定理は成り立ちます.
(自分も不思議に思ったが,もしそのようにした場合,全予報士の性能が悪くなっていくので一番当たっている予報士の正解率が悪くなっていくと思えばよい)

---

これが一番単純なアルゴリズムで,もっと一般的な問題に対するアルゴリズムが数多く提案されています.このようなアルゴリズムは基本的には,凸である損失関数と予想領域が凸集合である場合に,入力列を順に予想し損失関数の和を最小化するような問題としてみることができます.このような問題は統計的決定理論やゲーム理論,金融工学,情報理論(データ圧縮),機械学習など多くの分野で独立に提唱されてきたものであり,似た概念やアルゴリズムが提唱されています.それらの話が以下の本でまとまっています.

(一応ざっとは読んでみました.面白いですが,ポップな表紙とは裏腹に,読むには数学の知識がそこそこ必要です.分野毎に分かれているのでどこかの分野を知っていると読みやすいかも)

例えば,機械学習の文脈で言い直すと,決定するのはパラメータ関数(重みベクトルw)であり,凸であるような損失関数が毎回与えられた場合に,全損失関数の和を最小にするようなwをオンライン学習で求めている問題としてみることができます.また,情報理論(データ圧縮)の文脈で言い直すと,損失関数がlog-loss関数で,決定するのは次の文字の予測確率となり,全体の情報量を最小化する問題となります.金融工学では,決定するのはポートフォリオで損失関数は損失額そのものになります

このようなオンライン凸最適化は近年,様々な分野を包含し研究が進んでいます.例えば,パーセプトロン,最急降下法,multiplicative updateなどがRegularized Follow the Leader(RTFL)と呼ばれるアルゴリズムの特殊化としてみることができるようになっています[1].

[1] "The convex optimization approach to regret minimization." , E. Hazan

| | Comments (367) | TrackBack (0)

« September 2009 | Main | November 2009 »