07: 検索モデル その1－ベクトル空間モデル－
検索モデル
- 検索ランキングに対する数学的基礎を提供するもの
- 検索モデルの発展は検索効果の向上に寄与する
- 適合性の背景となる理論
適合性
- 適合文書とは，クエリをサーチエンジンに投げたときにユーザが探している情報を含む文書のこと
- 適合性の判断には多くの要因が必要で複雑
- タスク，文脈，新規性，書き方のスタイル
- 人によって判定結果は一致しない
- 適合しているかどうかの情報要求は人それぞれ異なっているため
- 検索モデルによる適合性算出のモデル化によう問題の単純化を図る
- 話題適合性(topical relevance)？ or ユーザ適合性(user relevance)？
- 二値？ or 多値？
ブーリアン検索
- 初期の検索モデル
- クエリに対して2種類の検索結果を返す
- true(照合した) or false(照合しなかった)
- クエリはブール演算子(and, or, not)で指定
- クエリは検索結果を確認しながら修正
利点
欠点
- 検索効果はブール演算子を用いたユーザのクエリ経験に依存
- 単純なクエリでは検索できない
- 複雑なクエリを考えることは難しい
ベクトル空間モデル
- 文書とクエリを，単語の重みのベクトルで表現
- 文書集合は，単語の重みの行列で表現
- 単語の文書内出現頻度を用いた転置行列
- クエリと文書の類似度(コサイン類似度など)で文書をランク付け
Cosine(文書D(i), クエリQ) = ∑{d(ij)･q(j)} / sqrt(∑{d(ij)^2} ･ ∑{q(ij)^2})
- 文書内の単語出現順序を考慮しない(bag of wordsモデル)
John is quicker than MaryをMary is quicker than Johnと同一にしてしまう- 位置が索引付けに埋め込まれれば区別可能
tf - idf
tf
- 語彙の出現頻度
- 文書dにおける語彙tの出現回数をtf(t,d)とする
- クエリと文書の照合にtfを重みとして利用したい
- 出現頻度に対数をとって重みとする方法
w(t,d)= tf > 0 ? 1 + log₁₀(tf) : 0
- d適合性は，単純に語彙の出現頻度に比例するわけではない
- クエリに対する文書のスコアは
∑w(t,d)
idf
- 語彙の文書頻度
df(t)は語彙tを含む文書の数- 逆文書頻度は
idf(t) = log₁₀(N/df(t))
- 多くの文書に含まれている語彙はスコア低め
- ごく少数の珍しめの語彙なら高め
tf-idf
w(t,d) = tf(t,d) ･ idf(t,d)
(1+log₁₀tf(t,d)) ･ log₁₀(N/df(t))
- 文書内出現頻度、文書集合内の単語の珍しさにより重みが増加
- 転置行列の重みに使用
クエリのベクトル表現
|V|次元(V=語彙サイズ)のベクトル空間- 単語数がベクトル空間の軸（次元数）
- 文書はこの空間内のベクトル（あるいは一点）
- 高次元：Webサーチエンジンの場合には，1,000万次元
- 非常に疎なベクトル：ほとんどの要素は0
ベクトル空間モデルにおける類似度
- クエリと文書の2点間の距離で類似度を測りたい
- ユークリッド距離
- 文書の長さが異なるベクトルに対して大きくなるのでダメ
- 文書ベクトルとクエリベクトルのなす角度
- ユークリッド距離が離れていても類似しているかを判定できる
角度からコサイン類似度へ
- コサイン類似度は，[0°, 180°]の間で単調に減少する
Cosine(文書D(i), クエリQ) = ∑{d(ij)･q(j)} / sqrt(∑{d(ij)^2} ･ ∑{q(ij)^2})- 文書ベクトルとクエリベクトルがなす角の余弦
- 単語や文書ベクトルは普通、文書長で正規化された単位ベクトル
ベクトル空間モデル利点
- ランニングのための処理がシンプル
- 類似度や単語の重み付け尺度は利用可能
ベクトル空間モデル欠点
- 単語同士の出現が独立を仮定してる
- 効果的なランキング戦略の予測（学習）が難しい
確率を利用したランキング
- Robertsonさん (1977)
「サーチエンジンが，データに基づき推定された適合性の確率が低くなる」順番に文書をランクづけすれば，ユーザにとっての検索効果は最良となるだろう