IIR7章まとめ

6章でVSMについて述べたが、それを実際に適用しようとすると、かなりの計算コストがかかる。

そこで7章では、VSMの計算コストを出来るだけ小さくすることを考える。

クエリベクトルの非正規化

6章では、コサイン類似度を求める際、ドキュメントベクトルとクエリベクトルを正規化して計算していた。

ここでクエリベクトルの例として、

(0, 1, 0, 0, 1, 1, 0, 0, 1, 0)

というものを考えると、これを正規化して

(0, 0.5, 0, 0, 0.5, 0.5, 0, 0, 0.5, 0)

を計算に使用していた。

この正規化は必要か?

よく考えてみると、目的はランキングであるため、相対的な大きさの違いが分かればよい。

よって、クエリベクトルは正規化せずに用いてよい。

正規化をしなければ、コサイン類似度を求める際の内積足し算で求めることができ、計算コストが小さくなる。

例として、クエリベクトルを上記のものとし、ドキュメントベクトルを

(A, B, C, D, E, F, G, H, I, J)

とすると、

(0, 1, 0, 0, 1, 1, 0, 0, 1, 0)・(A, B, C, D, E, F, G, H, I, J) = B + E + F + I

というように、足し算のみで計算できる。

※ ドキュメントベクトルは正規化が必ず必要である。

トップK件の取得

6章では、ランキングのトップK件を以下のように取得していた。

  1. 全ドキュメントのコサイン類似度を求める。
  2. それらを降順にソート
  3. 上位K件を取得

実際に必要なのは上位K件なのに、全ドキュメントのコサイン類似度を計算するのは計算コストがかかりすぎではないか?

そこで、全ドキュメントを計算するのではなく、まずスコアの高そうなドキュメントのみに絞ってから計算を行う。

高"そう"というところがポイントで、正確性を犠牲にして高速化しよう、といった感じ。

では、どうやってスコアの高そうなドキュメントを見付けるのか。

インデックスを絞る

2つのアプローチを考える。

  • idfの高いクエリタームのみを考える。

idfの低いタームは多くのドキュメントに出てくる上にあまり有用ではないので、それらを排除することで計算コストが小さくなる。

  • 複数のクエリタームを含んでいるドキュメントのみを考える。
チャンピオンリスト

postings中のドキュメントから、候補を絞る。

得られたドキュメントセットをチャンピオンリストという。

静的スコア

ユーザが得たいドキュメントは、関係性の深いもの、そして信頼のおけるものである。

これまでは関係性の深さにのみ焦点を当てていたが、ここでは信頼性により候補を絞ることを考える。

信頼性の高いドキュメントの例

  • Wikipedia
  • 新聞記事
  • 沢山引用されているドキュメント
  • 沢山ブックマークされているドキュメント
  • ページランクの高いもの

ちなみに見て分かるように、信頼性はクエリとは独立したものである。

インパクトによるソート

以下の2つのアイデアがある。

  • postingsをtfの降順にソートしておき、何らかの基準で上位K件を取得する。
  • クエリをidfの降順にソートしておき、高いものから順にソートする。
クラスタ削減

ますドキュメントをクラスタリングし、あるクエリに対して、それと最も近いクラスタのみを対象とする。

情報検索システムについて

以下、実際に情報検索システムを実装する時に必要な要素を挙げる。

段階的インデックス

tfの値によりpostingsを分ける。

クエリの近さ

クエリタームが近くに現れるほどスコアを高くしたい。