今日は IIR (Introduction to Information Retrieval) 勉強会の10回目。

- Introduction to Information Retrieval
-- http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今までの復習資料(by naoyaさん)は以下です。
# いつもいつも良い感じの資料です。是非ご一読を！

http://bloghackers.net/~naoya/iir/ppt/

9章の今回「Relevance feedback and query expansion」は、
適合性フィードバック(関連フィードバック、関連性フィードバック)とクエリ拡張がテーマ。
# そのままですね。

いつもどおり、メモだけですが貼っておきます。

9.1 Relevance feedback and pseudo relevance feedback 

グローバルメソッド
全体のデータや、他の資源をもとに拡張や変形をおこなう

ローカルメソッド
クエリにマッチした文書を元に拡張や変形を行なう

適合性フィードバックの典型的なシナリオは以下のような感じ。

・ユーザから与えられたクエリを元に、システムが検索結果を返す。
・ユーザは検索結果が自分の意図と関連してるか、していないかをマークできる。
・システムはユーザのフィードバックに基づいて、文書のスコアを再計算する。
・再計算の結果、上位に来た文章のセットを再度提示する。

イメージサーチは適合性フィードバックを有効活用できる好例。

9.1.1 Rocchio algorithm
適合文書ベクトルの重心と不適合文書ベクトルの重心の差の
大きさでシステムの検索結果の質を評価しようとすると、
適合文書集合が全て分かっている必要があるので、
この手法は現実には利用できない。

ということでRocchio algorithmを使う場合が多い。

良くあるパラメタは、α=1、β=0.75、γは0.15

一般的に、適合フィードバックは不適合フィードバックよりも
より良い結果を得るのに役立つのが知られている。
不適合フィードバックについては、不適合のうち
提示した順序の中で一番上位のものを見ると良いでしょう。

9.1.2 Probabilistic relevance feedback
Naive Bayes統計モデルを使うのが良いかも。

文書xに単語tがあらわれる時をx_t = 1と表す。
x_t = 1となる確率を考えてみる。
P(x_t = 1)の時は、以下のような2通りである。

P(x_t = 1 | R = 1) = |VR_t| / |VR|
P(x_t = 1 | R = 0) = (df_t - |VR_t|) / (N - |VR|)

まぁ、詳しくは11章と13章に丸投げ。

9.1.3 When does relevance feedback work?

RF単体では、効果的ではないケースは以下の3つ

１、ミススペリング。ユーザがミスしたらどうしようもない。
例、マリオが乗っかるYoshiをYossiで検索してもね。

２、言語横断検索。違う言語で書かれている文書は、同じ単語が同じ表層で書いてあっても、
ベクトル空間で離れる。
例、chocolate、チョコレート

３、文書コレクション検索者の語彙のミスマッチ。
そもそも文書がヒットしない場合がある。
例、たとえばrelevanceを適合と訳すか、関連と訳すか

とはいえ、RFはユーザに気に入られるか分からない。

9.1.4 Relevance feedback on the web
RFはあんまりWeb検索で使われなかった。

RFは平均的なユーザに説明しづらい。
RFは再現率を高めるアプローチ。

ほとんどのユーザは、検索結果のTop10しか見ない。

いろいろシステム側にとって辛い条件が揃っている。

9.1.5 Evaluation of relevance feedback strategies 
適合フィードバックは、ユーザがフィードバックを行なう際に
使った文書は評価に使わないべきである。

そうすると2回目の評価セットに、適合する文書が含まれる数が減ってしまい、
良い評価結果がでないのは自明な感じがする。

そのため単純にはRFがある場合と無い場合の違いの評価は難しい。

その不具合に対処するには、最初から文書セットを2つに分けると良いかもしれない。

RFに関する評価の際には、ユーザに対して検索時間に関する調査をすれば良いかも。

9.2 Global methods for query reformulation

9.2.1 Vocabulary tools for query reformulation 
どのような仕組みによるかは手法により様々ですが、
検索システムが、検索語を推薦することで、ユーザが
文書集合に含まれる、検索に使う上で良い語を見つけられるのは便利。

9.2.2 Query expansion 
クエリ拡張の単純な方法はシソーラスの使用。
同義語や類義語を利用し、それらの語に、オリジナルの語よりも
低い重みを割り振り、クエリを構築するのは基本的な手法。

YahooやGoogleでも、クエリをユーザが対話的に拡張できる。
PubMedは自動的にクエリを拡張する。

クエリの拡張を自動的に行なうか、対話的に行なうかは、
目的や用途によって違うし、ユーザ層によっても買えるべき。

クエリ拡張には、人手で構築したシソーラス、
自動構築した共起ベースの統計的に自動構築したシソーラス。
クエリのログ、などを使うことが考えられる。

ユーザの入力は未だに必要なもの。

9.2.3 Automatic thesaurus generation 
単純には、語の共起を使う。
共起頻度を見つかる語の大半について計算しておくのがシンプル。
より頑健な手法としては、文法構造（関係、依存構造）を使うと良い。

語と語の類似度は、単語-文書ベクトル間の内積を計算することで算出できる。

18章ではLSIについて言及するよ。

いろいろあったけど、まー、クエリ拡張の方がユーザが理解しやすいと思うけど、
疑似RFの方が効果があるような気がするなーということを主張してる。

たつをさんのトーク。

シンプソン係数を10万語に対して算出したいとき
10万×10万回の計算をするのは無茶。
ある語に対するWeb検索のスニペットから、計算する語の候補を得て、
それらに関する計算だけを行なうとリーズナブル。

とはいえ、こういうやり方より言語構造を使って抽出するのが、一番楽。

語と語の間の関連性が何かも、言語構造から探すと良い。
でも関係性は一般的に爆発するので、対処が必要。

検索ログをみんなが使えないからWikipediaを使うのが良いのでは。

スパムメールの判定を例にNB分類器の話を。

いやー、すっかりブログの書き方を忘れまくってます。
画像の縮小用のスクリプトがどこにいったのか分からなかったのは凹みました。
今、いろいろ思い出しながら書いているところです。まいったなぁ。

ところで、東京都現代美術館で、スタジオ・ジブリ レイアウト展を開催しているみたいです。



- スタジオ・ジブリ レイアウト展

chumbyの件もほとんど片付いたし、ということで、イベント参加の自粛も解除。
今日は、有楽町のインテル株式会社で開催された、ブロガーミーティングに行ってきました。

感想から言うと、イベント自体とても楽しかったです。
個人的には、今回のようCPUに特化したマニアックな話でも楽しめます。
また次回のミーティングが開催されるのをwktkして待ってます。

イベントでは、プロセッサーの誕生から最近のCentreno Atomプロセッサに至る
インテルプロセッサの歴史を技術部長の土岐英秋さんがプレゼンしてくださいました。

土岐さんは、8/2,8/3に開催される、Intel Akibaというイベントでも会えるそうです。
探し出して、自分の思い出のCPUに関するエピソードを聞き出してみてはどうでしょう。

インテルプロセッサーの歴史

Pentiumはi486より遅い！？

Pentiumは電気を食いまくるCPUだった

バックサイドバスって聞いたことある？

1997年と言えばスロット1

2003年には、インテルcentrinoモバイルテクノロジーが発表。

2005年4月にようやく、デュアルコア時代

2006年7月に、インテルCore2 Duo

2006年11月についにQuad Dore

2007年11月に45nmプロセス化

その後は

割と気になっていた、iPhoneの料金プランですが、
こんな感じだよー的なプレスリリースが出ていました。

- iPhone 3G向けサービスの詳細について
-- http://www.softbankmobile.co.jp/ja/news/press/2008/20080623_02/index.html

料金イメージを見てみると、こんな感じらしい。

今日は IIR (Introduction to Information Retrieval) 勉強会の9回目。

- Introduction to Information Retrieval
-- http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今までの復習資料(by naoyaさん)は以下です。
# 良い資料です。是非ご一読を！

http://bloghackers.net/~naoya/iir/ppt/

今回の、8章のテーマは「Evaluation in information retrieval」です。

検索エンジンの出力結果を評価する際の手法や指標に関するお話です。
7章が、検索結果として出力する結果のスコア算出法に関してだったので、
次はそれだろうなぁ、と思います。

----
7章の復習


- 基本はcos類似度
- cos類似度の計算量を削減する工夫が必要
-- 内積計算の積算を加算に
--- クエリもベクトルとして扱える
---- 0,1で次元を構成して単位ベクトルにする？
----- クエリくらいなら内積を計算せず、スコアを足すだけで良い。
-- ソートにはヒープを使おう
--- ヒープに格納しておけばTopKを、より低いコストで取得できる
-- 計算対象の文書を事前に削減する
--- 人間に重要そうな記事を残す
---- 全ての文書より遥かに少ない数まで絞る
----- 転置indexを使う
------ クエリの単語群からidfの高いものだけ残す
------- 紐づく文書も大量に削除できる
----- 残ったidfの高いクエリを、全て同時に含む文書だけ取得する
------ posting listの中から、最もらしいr個を求める手法
------ tfの閾値を決めて、足切りする
-- 足切りし過ぎに気をつける
-- 計算のIterateを減らす
--- posting listをtf順に、クエリをidf順にソートしておく
---- tf順のリストを閾値で切る
----- tfの値の変動が高い間だけ取得する
---- 重要なクエリから処理する
----- これ重要
---- 欲しい量が集まったらおしまい
- Tired index
-- tfの閾値ごとにindexを分けておいてFall Backするとか
- Query term proximity
-- クエリの単語の、文書中での距離が近いとスコアが高い、とか
- 構文解析
-- 単純なところだと、ABCというクエリを、ABC, AB, BC, 
- スコアリング
-- スコアはさまざまある。どうやって統合するか。
--- 手動でも良い
--- でも機会学習でやった方が良いだろう
- ベクトル空間法と今まで勉強してきたindexの間には使えるものと、使えない物があるよ。

----

8.1 情報検索システムの効果の評価

必要なものは
- 文書コレクション
- テスト用のクエリなど
- 評価方法
-- 関連しているか、していないか

これらを使うような手法を、gold standardとかground truthと呼ぶ。
クエリとユーザの要求が完全に一致しなかったり、
ユーザの要求に最適なように結果をしぼりこめなかったりする。
# python -> プログラミング言語、動物

inside data(学習データ)とoutside data(評価用データ)を分けよう。
交差検定とか。

学習データでチューニングして、学習データで評価したら
良い結果になるのはあたりまえ。

8.2 標準的なテストコレクションの紹介

- Crabfield
-- 小さいコレクションなので、適合性い関する評価がきちんと行なわれている
- TREC
-- indormation needに対して、文書コレクションから、抽出する手法を作成する
- GOV2
-- 巨大
- NTICIR
-- アジアの言語横断のテストコレクション
- CLEF
-- ヨーロッパの言語横断のテストコレクション
- REUTERS
-- ロイター
- 20 Newsgroups
-- テキスト分類のテストコレクション

8.3 ランク付けされていない検索セットの評価

適合率の定義 : 検索結果中の実際に適合している文書
再現率の定義 : 検索結果中の適合した文書数が、文書コレクション中の適合する文書を被覆する割合

判定の種類の呼び方。

検索結果は、適合率も重要になる場合もあるし、
適合率が重要になる場合もある。

一般には適合率を重視すると良いだろう。

適合率と再現率はトレードオフ。バランスが大切。

加重調和平均をみてみよう。式8.5。
F-measure。
頻繁に業界標準なF値は、F_B=1 = 2*P*R / (P + R)。式8.6。

調和平均の妥当性は図8.1を見ると分かる

8.4 ランク付けされた検索結果の評価

interpolater precisionを使う。
再現率を一定以上に固定された状態での、適合率。
たとえば、検索結果の評価では、一定の再現率を満たすように
検索結果を出力して、その検索結果の適合率を測定する。

現実にも、検索結果の1ページ目がそこそこの結果なら、
欲しい結果が1ページ目になくても、検索を続けるだろう。

評価時には、あまり細かいinterpolater precisionを使わず
0.1刻みで11点で測定するのが良いだろう

Precision at k : k個とった時の適合率。文書セットのサイズは確定してなくても良い。
R-precision : 上位R件の時点の適合率。文書セットのサイズが分かっている必要がある。

Break even point : 適合率と再現率が等しくなる点

DCG : 検索検索の出力結果のランキングが、指標の値でソートされた場合に近いのかを判断する
nDCG : さまざまな検索課題に対するDCGの平均

8.5 関連度の付与

検索結果と人の判断の一致度は興味深い。
Kappa値を良く使う。

k = (P(A) - P(E)) / (1 - P(E))
P(A) = (true positive + true negative) / document size
P(E) = P(positive)^2 + P(negative)^2
P(positive) = (false negative + true negative) / 2 * (document size)
P(negative) = (true positive + false positive) / 2 * (document size
)

例えば、2人のアノテータの一致度を計る。
2人の判断がばらついてたら値が低くなる。
よって、タスクの難しさなども測定できるよ。

8.6 より広い評価

8.6.1
システム的な指標

- indexingの早さ
- 検索可能になるまでの早さ
- クエリ言語のコスト
- 文書コレクションの大きさ

8.6.2 

ユーザビリティ的なことはほっとく。

8.6.3 既にデプロイされたシステムの改良

ユーザからのクリックによるフィードバック。
1から10%くらいの割合で、クリックログを得るための検索結果にとばす。

A/Bテストは、説明しやすい評価指標としてよく使われる。

8.7 スニペット

スニペットにはクエリに依存するものと、依存しないものがある。
前者のような静的なスニペットは、metatagなどから作る。
NLPを使って、オリジナルの文書から内容を良く表す文書を抜き出す。
高度に、文書の要約や校正などもすることはできるけど、研究じゃなければやらない。

keyword-in-context (KWIC) snippetsというものがある。
検索キーワードの左右のコンテキストを示す。
その際に、ユーザのための工夫を、NLPなども交えておこなう。

スニペットの生成は高速じゃないといけない。
大半の文章と、巨大な文章の主題や主要な話題を高速にキャッシュするには、現実問題、10000文字くらいの間にあるのではないか。

おしまい

先日「自分で考え、自分でやる」という、なんとも曖昧だけど、
ちょっぴり感じるところがあるフレーズを見かけました。

このフレーズを僕にしっくりくるように派生させた、
「4つの心がけたいフレーズ」をブログでさらしてみます。

それは、以下の4つです。

- 自分で多くのアイディアを考える
- 自分で速くアイディアを実現する
- はじめは軽い気持ちでやってみる
- 実現したものを自分で広く伝える

たくさん考え、速く実現し、最初は軽くまとめ、自分で宣伝。
我乍ら、どんな分野で生きていても適用できそうな曖昧さがたまりません。

アイディア実現の速度を早めることと、とまりがちなブログを続けることが、
自分にとっては重要だと感じました。ということでブログ再開。

今回挙げた例に限らず、何か曖昧だけど心に残るフレーズを見たら、
一歩立ち止まって、詳細、具体例、反例などを考えると、良さそうです。
# 某社の「君は何かを成し遂げる人かもしれない」とか心に残ります。良い意味で。