昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ

ときどき、たまたま自分がそのとき考えていたことについてそれを補強するような材料が偶然たくさん集まってくる、なんてことがあります。そんな出来事があったので、ちょっとブログを書いてみようかなと。 以前に HBFav を作ったときこんなことを書きました。 Mark Zuckerberg は、いずれみんな、ニュースは友人知人経由で知ることになるだろうと言っていました。自分もそうなるだろうと思います。 4年ぐらいが経ちましたが、その思いは以前よりも増して確信めいたものになってきています。 ところで先日、Twitter の iOS アプリに「ニュース」という機能が追加されました。人によっては出てないそうなのでまだテスト中か、もしくは既に削除されているのかもしれないですが。 この機能についての自分の感想は以下のようなものでした。 もうすこし補足します*1。 Facebook や Twitter のような

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章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_11.ppt 11章は、は "Probabilistic information retrieval" すなわち確率的検索モデルです。 IIR 10章までにあつかった検索モデル IRシステムをどのような概念を用いて実現するかが「検索モデル」であり、IIR ではここまで以下の2つのモデルを扱いしました。 ブーリアンモデル ベクトル空間モデル ブーリアンモデルは比較的単純な検索モデルで、ブール代数を基礎とした論理式によりクエリを組み立て、検索するモデルです。基本的にスコアリングは行いません。 ベクトル空間モデルは、クエリや文書を索引語の重みベクトルで表現して、クエリベクトルと文書ベ

明日は一ヶ月ぶりの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章の復習資料を以下にアップロードしました。 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章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_09.ppt 9章は、検索結果の適合性を改善するするための二つのアプローチ、Relevance Feedback (RF) とクエリ拡張についての話です。 検索結果のドキュメントに対してユーザーから追加の入力 (Relevant か Non-relevant か) を受け取るのが RF です。受け取ったフィードバックは、ベクトル空間でベクトルの重心を使ってクエリベクトルを最適化することに利用できます。最適化のアルゴリズムとして Rocchio アルゴリズムを利用します。ただし、特に Web 検索などにおいては、ユーザーは明示的なフィードバックを好みません。そこで、ユーザーからの入

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 の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

Introduction to Information Retrieval の4章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_04.ppt 4章はインデックス構築に関するアルゴリズムなどがテーマです。 前半では単一マシン上で二次記憶装置を使ったインデックス構築手法として、入力を適当なサイズのブロックに分けて最後にマージする Blocked sort-based indexing (BSBI) と、BSBI を改良して入力をストリームで扱うようにした Single-pass in-memory indexing (SPIMI) が紹介されています。 次に、例えばウェブ検索のような、単一のマシンでは扱いきれない巨大なインデックスを扱う戦略として、並列計算クラスタで分散インデックスを構築する Google の Ma

Introduction to Information Retrieval 2章後半と3章前半の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_02_2.ppt http://bloghackers.net/~naoya/iir/ppt/iir_03_1.ppt 今回は 2 章の後半 postings list のマージの効率的な実装方法 フレーズインデックスと positional インデックスによるフレーズ検索の実現方法 3 章前半 辞書検索のためのデータ構造 ワイルドカードクエリの実現方法 という内容です。次回はスペルミス補正 (もしかして機能) についてになります。次回の輪読会は少し間が空いて 4/12 予定ですので復習資料のアップロードも 4 月になるかと思います。 過去の章のアーカイブは同 URL のデ

id:naoya:20080205:1202208135 から引き続き、Introduction to Information Retrieval 2章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_02_1.ppt 今回は 2 章の前半、インデックス作成前のドキュメントの前処理に関する話題が中心です。2章は長かったので、区切りの良いところまでとなっています。次回の輪読会は 3/8 予定です。また次回の開催日後に、先週末の復習分である 2章残りと 3章前半についての資料を公開したいと思います。 過去の章のアーカイブは同 URL のディレクトリ (http://bloghackers.net/~naoya/iir/ppt/) から一覧できます。

Introduction to Information Retrieval の 輪講 に参加しています。自分はこの輪講で復習係を担当させてもらっています。毎回輪講の頭に、前回分の内容をサマリしてプレゼンテーションする係です。 これから輪講の度、作成した資料を公開していきたいと思います。第一回目の資料を以下に置いておきます。 http://bloghackers.net/~naoya/iir/ppt/iir_01.ppt (ppt, 274K) 第一回目は、書籍の第一章 "Boolean Retrieval" の復習です。大規模データを検索する検索システムにおいて、転置インデックスはどのように作成されるか、またブーリアン検索 (「渋谷 and ラーメン」という検索クエリの類) はどう処理されるかといったことの導入部です。 先週末の第二回目は、転置インデックス作成時の前処理部分(トークナイズ、