Introduction to Information Retrieval #12 の復習資料

Introduction to Information Retrieval 輪読会 12章の復習資料を以下にアップロードしました。

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 0.005
M2 0.002 0.03 0.04 0.0001 0.04 0.04 0.01

すると

  • P(s|M1) = 0.01 x 0.03 x 0.04 x 0.01 x 0.02 x 0.04 x 0.005 = 0.48 x 10^-12
  • P(s|M2) = 0.002 x 0.03 x 0.04 x 0.0001 x 0.04 x 0.04 x 0.01 = 0.384 x 10^-15

とそれぞれの確率分布から P(s|M) を求めることができます。このように単語の生起確率をベースに自然言語を捉えるのが確率的言語モデルである、と理解しています。

12章 Language models for IR

11章までに扱った検索モデルはブーリアンモデル、ベクトル空間モデル、確率モデルでした。これらの検索モデルは、検索クエリから情報ニーズを予測し、適合文書をマッチさせるという考え方で構築されています。一方、確率的言語モデル(以下言語モデル)を用いた検索では、文書 d から言語モデル Md を推定し、その言語モデルがクエリを生成する確率 P(q|Md) をベースにランキングを行います。

他方、情報検索とは条件付き確率 P(d|q) を最大化する問題と見ることができます。クエリ q に対して P(d|q) が最も大きくなる d を求める問題です。この P(d|q) はベイズ定理により

  • P(d|q) = P(q|d) x P(d) / P(q)

となります。このとき P(q) は全てのドキュメントに一定なので無視、P(d) はクエリに関わらない文書の適合性ということなりますが、これもここでは定数として無視できます。結局、argmax P(d|q) は argmax P(q|d) を求めることに帰着します。argmax P(q|d) はつまり、「文書 d がどういう q で検索されやすいか」です。この P(q|d) を軸に情報検索を考えるモデルは「クエリ最尤モデル」と呼ばれます。

ここで言語モデルを用いると P(q|d) → P(q|Md) とみなすことができます。結局、各文書毎に言語モデル Md を推定することにより、先に "frog said ..." で文字列の生起確率を求めたのと同様の方法でそれぞれの文書の P(q|Md) の値が決まりますから、これを比較することでスコアリングが可能となります。

言語モデルの推定

言語モデルを推定するには、まずどの種類の言語モデルを前提にするかを考えます。代表的な言語モデルには

などがあります。IIR では、IRシステムでは(音声認識などに比較して) 文脈構造をそこまで考慮する必要がなくNグラムモデルで十分として、Nグラムモデルを採用しています。また、ここまでに見てきたように bag of words でも効果的ということで unigram で考えます。

言語モデルの推定アルゴリズムにも幾つかの手法がありますが、ここでは学習データの生成確率を最大化する最尤原理 (maximum likelihood principle) に基づいた最尤推定法 (maximum likelihood method = MLE) を用います。

unigram を仮定し MLE を用いると、文書中に出現する単語の相対頻度により言語モデルが推定されることがわかります。ただし相対頻度をそのまま使うと、学習データに出現しない単語がモデル全体の確率を 0 にしてしまうという「ゼロ頻度問題」が問題になります。そこで確率分布をスムージングするわけですが、このスムージングにはこれまでに様々な手法が提案されてきたそうです。IIR では 11 章でも見た加算スムージング(ラプラス法)に加え、線形補間法やベイジアンスムージングなどが紹介されています。12章では、線形補間法が用いられます。

unigram を仮定し MLE で言語モデルを推定、線形補間法でスムージングすることにより P(d|q) を求める数式が得られます。(スライド24枚目) この数式に実際の文書群を当てはめることで P(d|q) に基づいたスコアリングが可能になります。(スライド25枚目)

本章を読み進めるにあたっては 言語と計算 (4) 確率的言語モデル が参考になりました。自分には少々敷居の高い内容でしたが、IIR 12章と併読することで理解が深まりました。

言語と計算 (4) 確率的言語モデル

言語と計算 (4) 確率的言語モデル

また、以下の URL の記事も参考にしました。

次回輪講ほか

今日の輪読会、第13章は少し内容が変わって "Text classification and Naive Bayes" でした。続く 14 章は Vector space classification、15 章が SVM ということでしばらくは機械学習によるテキスト分類がテーマになります。だんだんと理論の解説が主となり、実践とのギャップが開いてきた感があります。適当な実装を作って検証するなりしていきたいところです。

次回の輪読会は 10/18 (土) 予定。次回輪読会後、いつも通り復習資料をアップします。

過去の章の復習資料 ppt は同 URL のディレクトリ (http://bloghackers.net/~naoya/iir/ppt/) から一覧可能です。

Introduction to Information Retrieval

Introduction to Information Retrieval