« 2005年10月 | メイン | 2005年12月 »

2005年11月01日

キーワード抽出: tf-idf の意味づけ

単語の重み付けの古典的な方法に tf-idf があります。文書中の各単語の tf-idf 値計算し、値でソートすると、その文書に特徴的な単語リストを得ることができます。

http://nais.to/~yto/clog/2005-10-12-1.html

tf-idf は、単なるヒューリスティックスだと考えられていましたが、最近言語モデルに基づく情報検索手法がさかんに研究されるようになり、tf*idf の解釈が明らかになってきました。言語モデルに基づく手法は、ヒューリスティックスばりばりの手法と同性能にもかかわらず、文書のランキングに理論的で合理的な説明を与えることができます。

情報検索は、クエリ q に対し、もっとも適合する文書 d_opt を求めるタスクです。つまり、q が与えられたとき、文書 d が出現する確率 p(d|q) の最大化問題と解釈できます。

d_opt = argmax P(d|q)

ベイズの定理より、以下のように変形できます。

d_opt = argmax P(q|d) * P(d)

P(q|d) は、クエリモデル、p(d) は文書モデルと呼ばれます。この形はとても興味深いです。

クエリモデルは文書 d が、どういうクエリ q で検索されやすいかを表現します。d に特徴的な単語とは、 d を検索するのに適切なクエリといってもかまわないので、p(q|d) は、キーワード抽出そのものです。

p(d) は、クエリにかかわらず文書そのものが持つ適合性です。たとえば、ページランクのようなクエリ非依存なスコアが p(d) に相当します。以下、単純に p(d) = 定数 だと仮定します。

各単語は独立に生起すると仮定すると、p(q|d) は、単純にクエリ中の一単語ごとの確率 p(w|d) の積になります。

p(q=(w1,w2,...,wn)|d) = p(w1|d) * p(w2|d) * ... * p(wn|d)

さて、p(w|d) は、以下のように、文書 d から単語が生成される確率 p(w|d) と、文書には関係なくランダムに単語が生成される確率 p(w) の線形結合として解釈してみます。

p(w|d) = lambda p(w|d) + (1 - lambda) p(w)

この確率が、クエリ w に対する 文書 d のスコアになります。あとは、このスコアが最大になる d を見つけるだけです。

d_opt = argmax { lambda p(w|d) + (1 - lambda) p(w) }
= argmax { 1 + ( lambda / (1-lambda) ) * p(w|d) / p(w) }
= argmax log { 1 + ( lambda / (1-lambda) ) * p(w|d) / p(w) }

実際の確率は、

p(w|d) = d中の単語wの頻度/d の単語数
p(w) = wの頻度/全単語数

になるので、それぞれ代入すると、

d_opt = argmax log { 1 + ( lambda / (1-lambda) ) *
                    (d中の単語wの頻度 * 全単語数) / (wの頻度 * dの単語数) }

となります。

d中の単語w の頻度 ~ tf (term frequency)
1/wの頻度 ~ idf (inverse document frequency)
1/dの単語数 = ドキュメントのサイズ

であるゆえ、自然と tf * idf の形がでてきていますし、おまけに単語数での正規化も行われています。

何をやっているかがはっきり分かる というのは気持ちがいいです。

投稿者 taku : 21:59 | コメント (17) | トラックバック