petitviolet_blog

@petitviolet blog

Information Retrieval-6章

IIR第6章

第6章 Ranked Retrieval

第1章で取り扱ったboolean検索の問題点を解決するために,
Ranked retrieval:ランキング検索を考える.

  • boolean検索の問題点
  1. 検索queryを書くのが難しい.
  2. 検索結果が多すぎるor少なすぎる

(andは減らしすぎ,orは増やしすぎる)

と言ったところ.

  • でも、文書内にtermがあるかどうかだけを調べたい時には役立つ.

ranked retreval

ランキング検索の利点とは,

  1. queryを満たす文書を返すだけでなく,"より"満たすものを返す.
  2. boolean検索と違って、自由な文章を質問文にすることが出来る.
  3. 検索結果は上位しか見ない => 検索結果の量は問題ではない

しかしどうやってランキングするのか.

  • スコアリング手法について.

文書と質問文のマッチ具合に0〜1の間で点数をつける.
前提として知っておくべき2つのこと.
1.jacard係数

jacard(A,B)はAとBの共起する度合いを示す.
語が文書内に何回現れるかを示すだけであり,
例えば長い文書と短い文書では出現頻度が同じでも回数が違う,
といったことを考慮していないため、そのまま使うことは出来ない.

2.bag of words

文章を単語の集合として扱うこと
語の出現位置を考慮しなければならないが,bag of wordsモデルではそれが考慮されていない.

  • Mary is taller than John.
  • John is taller than Mary.

これらでは登場する単語は全く同じだが,単語の出現位置によって
意味が反対になっているため,bag of wordsで考えるとよろしくない.
これらを踏まえた上で,tf-idf法について考える.

term frequency(tf)

tfとは文字通りに,

  • それぞれの単語の文書内における出現頻度(出現回数)

を表す.

  • tf_{t,d}:文書dにおける語tの出現回数

しかし文書と単語の関連度はtfに比例するわけではない.
ある語が10回出てくる文書と1回出てくる文書で10倍違うことはない.
従ってtfの値自体は正確でなくてよく,
比較出来れば問題無いため大小関係を保存できるlogを取って使う.

Google検索で用いられているPageRankの計算でも
正確な値を求めるのではなく,値の大小関係だけ判ればいい為
値が収束するまで計算をしないというのと同じ.

Document Frequency(df)

文書頻度というもので,

  • 文書集合においてある単語を含む文書がどれだけあるか

を示す値.

  • df_t:文書集合内における語tの文書頻度

Inverse Document Frequency(idf)

df_t値をどうやって使うか.

  • 頻出語

dfの定義から,高いdf_t値を持つ単語は多くの文書に登場することになり,
 文書と単語の関連性を考える時にあまりいい情報とならない.

    • もちろん,登場しないよりは関連性が強い.
  • 珍しい語

 df_t値を逆にしたidf_t値が高ければ珍しい単語であると考えられ,
 高いidf_t値を持つ単語が登場する文書はその語との関連性が強い.

  • idf_tの求め方は

idf_t = log_{10}(N/df_t)
ただし,Nは文書数

これらから,

df_t:単語の持つ情報量の少なさ
idf_t:単語の持つ情報量の多さ

と考えられる.
ちなみに,tf-idfの値の求め方には色々ありますよ.

ベクトル空間モデル

各単語を軸とする空間を考えると,各文書はその空間における点やベクトルとなる.
クエリも同様にベクトルで表現して,各文書との類似度を求める.

  • コサイン類似度

クエリと各文書のなす角度によって類似度の大小関係を求める.
そのために長さを正規化する必要があり,それにはL2ノルムを用いる.

  • L2ノルム:各次元の値を2乗したものの和

各文書ベクトルをそれぞれのL2ノルムで割ることで長さを正規化出来る.
=> コサインを求められる!

まとめ

tf-idfを用いて文書とクエリをベクトルで表現して,
それらの長さを正規化.
そしてそれらがなす角を求めてクエリとより類似度の高い文書を
上位から適当に返せばランキング検索となる!!

こんな感じで.