今日は 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プロセス化

その後は

今日は 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文字くらいの間にあるのではないか。

おしまい

昨日の夜から、ブログ合宿 08春 (秋元の春) に来ています。
早いものでブログ合宿も4回目ですね。

インテル・ブロガーミーティングに参加させて頂きました。

参加者のほとんどの方が顔見知り、または、どこかで見たことがある、
または、面識が無いけど僕は顔を存じてる、という人ばかりでした。
今月はブログディナーに行かなくても良いかも、と思うような顔ぶれでした。

内容は、インテルの製品に関するプレゼンテーションと、
軽食を頂きながらのグループディスカッションでした。

実は、ミーティングの主旨は参加していても分からなかったです。

ある程度の事前説明的資料は配布されていましたが、
会場には、インテルの新しい製品を搭載したマシンは試作機しかないし、
試作機には電源を入れられなかったのです。

なかなか、電源を入れられる動作可能な端末を用意するのは難しいと思います。

でも、もしも、会場に電源を入れて自由に扱えるデバイスが無いと知っていたら、来なかったブロガーも居たのではないかと思います。
ブロガーが何に期待して、やってくるのかを考えて、
無い物は無い！と事前に伝えて頂けると、すれ違いは少ないと思いました。

ただ、よくよく考えてみると、誰が来るのか分からない状態で、
インテル側としては何か思い切ったことができないし、様子見だったのかもしれません。
インテルのブロガーに対する気遣いは異常なまでに手厚かったし、
なにが起こるのかなぁと、ちょっと怖さを感じたりもしました。

最終的には、今回のミーティングだけに絞って考えると、
新しい製品の紹介をブログ界経由でしたい、のかなと思いました。

個人的には面白かったので紹介してみます。

Intel Centrino Atom プロセッサー・テクノロジーの紹介

グループディスカッション

年度末ということで飲み会でした。

今年度もお疲れさまでした。

id:nipotanとid:nagayamaを送る会は、昼12時締め切られました。

詳しくは以下。

- [O] 【締め切りは3/21昼12時】nipotan nite & id:nagayama送別会開催のお知らせ
-- http://overlasting.dyndns.org/2008-03-18-1.html

YAPC::Asia 2008 の公式サイトがリニューアルしたのと同時に、
スポンサーとスピーカーが公開になりました。今年もかっこ良いデザインです！

- YAPC::Asia 2008 - May 15-16th in Tokyo, JAPAN
-- http://conferences.yapcasia.org/ya2008/



今年も多くのスポンサーに支えられ、さらに多くのスピーカーが参戦してくれます。
志の高いみなさんが、すごい勢いでイベントに足を運んでくれでしょうし、
きっと最高のイベントになるのでは。わくわくしてます。

チケットの販売開始はもうすぐみたいですから、うっかり忘れないようにしてくださいね。

チケットを購入してくださる方は、「チケットがうっかり不要になったら、頑張って他の人に譲るぜ！」という気持ちで購入して頂けると、「残念なことにチケットを買えなかった人」が、たくさん救われるような気がして嬉しいです。

ボランティアスタッフも、まだ若干名ですが募集していると思います。
僕はYAPCで多少人生が変わったので、変わろうとしている方にボランティアで貢献することをおすすめします。

YAPC::Asiaまで、あと2ヶ月を切りました。
5/15、 16付近はスケジュールをバッチリ開けておいてくださいね。 m(_ _)m

言語処理学会の全国大会の3日目に行ってきました。
午前は固有表現抽出のセッション中心。

- NLP2008 program
-- http://nlp2008.anlp.jp/program.html#C2

D4-5 単語正規化による固有表現の同義性判定手法 高橋いづみ, 浅野久子, 松尾義博, 菊井玄一郎 (NTT)

D4-6 カーネル法を用いた意味的類似度の定義とブートストラップの一般化 小町守 (NAIST), 工藤拓 (Google), 新保仁, 松本裕治 (NAIST)

B4-7 言語パターンを用いた検索クエリによる単語間の上位・同位関係の抽出 荻原由紀恵, 山下達雄, 前澤敏之 (ヤフー)

A4-8 Nグラム検索エンジン -Google日本語7グラムを使って- 関根聡 (NYU)

C5-1 綴り誤りに対してロバストなローマ字語のマイニング手法 永田亮, 掛川淳一 (兵教大), 杉本洋美, 籔田由己子 (教育測定研究所)

C5-3 トラブルを見つける De Saeger Stijn (NICT), 鳥澤健太郎 (JAIST)

C5-4 経験マイニング：Webテキストからの個人の経験の抽出と分類乾健太郎, 原一夫 (NAIST)

C5-5 "商品カテゴリ"および"取扱店舗"の統計情報を用いた商品タイトルに含まれるフレーズの重要度判定 前澤敏之, 山下達雄, 荻原由紀恵 (ヤフー)

言語処理学会の全国大会の2日目に行ってきました。
とりあえずは、午前の要約セッションだけ。

- NLP2008 program
-- http://nlp2008.anlp.jp/program.html#C2

C3-5 要約文の選定による用例利用型要約の可読性向上 牧野恵, 山本和英 (長岡技科大)

C3-5 要約文の選定による用例利用型要約の可読性向上 牧野恵, 山本和英 (長岡技科大)

C3-6 HTML文書からのリスティング広告の自動生成 幾島克洋, 藤田篤, 佐藤理史 (名大), 横川睦, 岩本宜式, 片岡亮 (リクルート)

C3-7 １３文字で何が伝えられるか：ウェブニュースボックス見出しの分析 佐藤理史 (名大)

言語処理学会の全国大会に行ってきました。
午前は用事があったので午後からです。

- NLP2008 program
-- http://nlp2008.anlp.jp/program.html#C2

あらためまして、こんにちは。id:overlast(としのり)です。

このたび悪ノリで、nipotan niteと言うイベントを開催します。
id:nagayama送別会も同時に開催いたします。

nipotan niteとは

開催期日

開催目的

イベントの詳細

にぽLT

id:nagayamaの壮行会も同時開催

申し込み方法

最近ブログから遠ざかっていたので、リハビリも兼ねて、ブロガー勉強会に出てみました。

- 3月17日（月）ブロガー勉強会のご紹介 - Agile Media Network
-- http://agilemedia.jp/blog/2008/03/317.html

ブロガー勉強会

サムネイルの活用

会社公認ブログの作り方

Blogger Matrix by Blogger

サラリーマンブロガー

恵比寿在住または歩いて来られるエンジニアでブログを書いていて、
ソースコードを公開している人なら入る資格があるらしい恵比寿会の
2回目に集まりがありました。

akkyさんが新宿から歩いて参加いました。ww。

会には遅れて参加しましたが、割とすんなりとけ込めて、
楽しい時間を過ごしました。

会の途中で、「nipotan Nite」という、ただただ、にぽたんを囲む会が
企画され、これからの進行次第では良いイベントになる模様。
なんか 3/25 日らしい。えらい急ですな。

恵比寿会の次の幹事は僕らしい。
で、次の開催日は4月20日以降らしい。それまでは忘れよう。

帰り、amachangと店から一番近い横断歩道を渡ったところで
持ち物の中にデジカメが無いことに気づきました。
もし路上にデジカメを落としたら音で気がつきます。
そこで、確実にデジカメを使っていた出たばかりの店に戻ったところ、
「デジカメは無かった」と言われました。
その前に入った店にも行きましたが、当然ながらありません。

うーん、これは「参加者」「同じ店にいた客」「店員」の誰かが、
カメラを持って行っちゃったパターン。あああ。残念すぎる。
ちゃんとカメラを確認しないで店を出てしまった自分の責任。
ということで、近いうちに秋葉原で中古カメラでも買ってきます。

全体として、楽しいイベントでした。

ブロガー勉強会の第4回目に、都合が合えば参加したいと思いました。
楽しそうなイベントです。

- 3月17日（月）ブロガー勉強会のご紹介 - ブログラボ （Bloglabs.jp)
-- http://bloglabs.jp/2008/03/317.html

「FON NIGHT 2008」というイベントが開催されるようです。

イベントに参加すると、今、FONルーターをもっているのに、
さらにもう1つ貰うことにしまうのでしょうかwww。

- FON NIGHT 2008
-- http://www.fon.ne.jp/fonnight/

今日は、IIR輪読会でした。
[2008-02-16-2] の #03 に引き続き、#03です。
終わったのは、第3.3節から第4章の概説まで。つづきは次回。

今日の会場は渋谷のはてなの会議室でした。



今回も冒頭はnaoyaさんの復習プレゼン。分かりやす。

- naoya さんによるIntroduction to Information Retrievaの輪読の資料
-- http://bloghackers.net/~naoya/iir/ppt/

3章の担当は、僕でした。軽く忘れていてグダグダになりがちでした。
内容は、スペルコレクション（単語のつづり誤り訂正）のお話。

- n-gram に基づく単語Indexの活用
- 動的計画法による編集距離の算出

- [を] Dynamic Programming による類似文字列マッチの実装例
-- http://chalow.net/2007-01-22-4.html

八王子の『鳥良』でお疲れ会でした。
2007年度も終わりということで、年度の締めです。





ちょっと高めのコースにしたので、料理が沢山出てきます。
そのうえ、店員が2時間きっかりで追い出そうとするので、
テーブルの上は終始混沌としていました。



鍋の締めのおじやと、デザートを同時に持ってこられたときは、
本当に酷いお店だなと思いました。
味を楽しむ前に、口に詰め込まなければいけないのはツライです。

一次会のあとは、AGOSTで軽く飲み直して帰りました。





おつかれさまでした。
また、来年もよろしくおねがいします。