情報検索ことはじめ〜教科書編〜 - シリコンの谷のゾンビ
2011-01-18追記 教科書編その2 にて2011年版のIR教科書を紹介しています 情報検索(IR)の勉強を本格的に始めて8ヶ月．大体どんな分野があって，どんなことを勉強すればいいのかわかってきた（と思う）．この気持ちを忘れないうちにメモしておこう．以下，若輩があーだこーだ言ってるだけなので，間違いや他に情報があれば，ぜひコメントをお願いします． # ここで述べている情報検索とは，コンピュータサイエンスの一分野としての情報検索です．図書館情報学の側面は一切扱っていません，あしからず． というわけでまず教科書編． 本腰を入れて勉強する場合，基礎づくりのためには教科書選びがいちばん重要だと思っている．自分の知っている限り，情報検索における教科書の選択肢はそれほど広くはない．以下に紹介する本は，情報検索を学ぶ上で「買い」の本．これらを読めば，最新の論文を読めるだけの土台はできるし，専門家と議
Introduction to Information Retrieval #12 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 12章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_12.ppt 12章は、は "Language models for information retrieval" ということで、確率的言語モデルを情報検索に適用する話でした。 確率的言語モデル 確率的言語モデルとは、自然言語を数学的に扱うモデルに単語列、文字列が起こる確率を与えたものです。例えば "frog said that toad likes dog" という単語列 s があったとして、それぞれの単語の生起確率が与えられているとします。 frog said that toad likes that dog M1 0.01 0.03 0.04 0.01 0.02 0.04
Introduction to Information Retrieval #11 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 11章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_11.ppt 11章は、は "Probabilistic information retrieval" すなわち確率的検索モデルです。 IIR 10章までにあつかった検索モデル IRシステムをどのような概念を用いて実現するかが「検索モデル」であり、IIR ではここまで以下の2つのモデルを扱いしました。 ブーリアンモデル ベクトル空間モデル ブーリアンモデルは比較的単純な検索モデルで、ブール代数を基礎とした論理式によりクエリを組み立て、検索するモデルです。基本的にスコアリングは行いません。 ベクトル空間モデルは、クエリや文書を索引語の重みベクトルで表現して、クエリベクトルと文書ベ
Array::Gap - naoyaのはてなダイアリー
明日は一ヶ月ぶりのIIR輪読会 です。主催のたつをさんから「教科書の話題から何か適当に実装せよ」という課題が出ていたので、5章 のインデックスの圧縮の所で見た Variable byte codes (以下 VB code) を使った圧縮の実装を作ってみました。 整列済みの整数を圧縮する手法 ここでの圧縮のポイントは二つ。 昇順に並べられた整数を、整数そのままの数で扱うのではなく、一つ前の要素との差で扱う。差で扱うと 21,314,156 → 21,314,157 という数は "1" というより小さい数で表現することができる。(整列済みなので、差が分かれば逆の操作で復元が可能) 32 ビット int の整数を固定長 32 ビットで表現するのではなく可変長バイトで表現する。(これが VB code) VB code なら小さな数字は 32ビット = 4バイトよりも小さなビット数で表現できる
Introduction to Information Retrieval #10 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 10章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_10.ppt 10章は、は "XML retrieval" です。XML が題材になっては居ますが、実際には XML がどうこうというよりも、構造化されたドキュメント (structured document) に対して IR システムを拡張しようとすると、どのような困難があるか、それをどのように解決すべきか、拡張された IR システムはどう評価されるべきか、という話が主だったところです。 対象が structured な物である場合「その構造の中のどの部分を検索結果として返却すれば良いか」など、自明でない点が出てきます。XML retrieval であれば、XML docum
Introduction to Information Retrieval #9 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 9章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_09.ppt 9章は、検索結果の適合性を改善するするための二つのアプローチ、Relevance Feedback (RF) とクエリ拡張についての話です。 検索結果のドキュメントに対してユーザーから追加の入力 (Relevant か Non-relevant か) を受け取るのが RF です。受け取ったフィードバックは、ベクトル空間でベクトルの重心を使ってクエリベクトルを最適化することに利用できます。最適化のアルゴリズムとして Rocchio アルゴリズムを利用します。ただし、特に Web 検索などにおいては、ユーザーは明示的なフィードバックを好みません。そこで、ユーザーからの入
Introduction to Information Retrieval #8 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 8章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_08.ppt 8章は、検索結果の適合性を定量的に評価する指標の解説が主です。適合性判断のための最も基本的な指標である Precision と Recall、その二値のトレードオフを加重調和平均値で表現する F measure がまず最初に紹介されています。ランク付けされた検索結果に関してはこれらの指標をもう少し拡張する必要があります。そのために Precision - Recall 曲線を分析する方法や、検索結果指標を一つの統計量で表現する MAP (Mean Average Precision) などが紹介されています。また、Web 検索のような先頭数十件の検索結果が重要な場合
Introduction to Information Retrieval #7 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 7章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_07.ppt 7章の前半は、6章に引き続きスコアリングの話題です。Vector space model での内積計算を真面目にやろうとすると計算量が膨大になるため、いくつかのヒューリスティクスを導入して計算量を削減します。cos 類似性算出のアルゴリズムの見直し、idf や tf あるいは静的なドキュメントの何かしらのスコア (例えば PageRank のようなもの) を使って計算対象のドキュメントを足切りする、Impact ordering により cos 類似計算のループ回数を削減する、などの手法が紹介されています。 後半では、7章までに紹介されてきた各種コンポーネントを統合
Introduction to Information Retrieval #5 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval の5章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_05.ppt 5章はインデックス圧縮がテーマです。辞書の圧縮と postings files の圧縮に対するそれぞれのアプローチについての解説が主です。転置インデックスの振る舞いに特化した圧縮手法などが紹介されていて、とても面白い章でした。数値表現をビット単位で最適化する γ coding などは目から鱗です。 次回の輪読会は 6/8 予定です。次章の内容は、検索結果のスコアリングについて。tf-idf や Vector space model についての話が中心になります。 過去の章のアーカイブは同 URL のディレクトリ (http://bloghackers.net/~naoya
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
