IIR19章まとめ

勉強 IIR

19章は、Web検索の基本についてまとめている。

検索システムがなければ、欲しい情報を見付けることは当然難しい。

Webにおいて、検索は不可欠なものである。

広告

ご存知の通り、広告は検索結果の右側に現れる。

Web検索システムにおいて広告は非常に重要であり、例えばGoogleは、収入のほとんどが広告収入である。

では、広告はどのようにランキングされているのか。

まず、以下のことが基本である。

  • オークションの入札額でランキングが決まる
  • その広告がクリックされる度に金額を支払う

そしてオークションの方法として、セカンドプライスオークションが使われている。

セカンドプライスオークション

以下の例を見てみよう。

  • bid…入札額
  • CTR…クリックされている割合。適合性の尺度となる。
  • ad rank…bid×CTR
  • rank…オークションでのランキング
  • paid…支払額

支払額は、以下のようにして求める。

price = (自分よりランキングが1つ低い人のbid) × (自分よりランキングが1つ低い人のCTR) / (自分のCTR)

上表の例では、以下のように求まる。(実際はこれに1セント加えている)

  • Cのprice = 3.00 × 0.03/0.06 = 1.50
  • Bのprice = 1.00 × 0.08/0.03 = 2.67
  • Dのprice = 4.00 × 0.01/0.08 = 0.50

重複データ一括検出

Webには、似たような情報がいっぱいある。

例えば、検索結果が似たような情報ばかりだとユーザはいらいらするし、いくら情報ニーズと適合していても、似たような情報の後に出てくると価値がなくなる。

このような理由で、重複データはなくしたい。

では、どのように重複データを見付け、なくすことができるのか？

ここでは、文法上の類似度の高いものを重複と判断する。(意味的な類似度をコンピュータで求めるのは難しい)

2つのドキュメントをnグラムを適用し、その類似度をJaccard係数で求める。

以下に例を示す。

  • d1…“Jack London traveled to Oakland”
  • d2…“Jack London traveled to the city of Oakland”
  • d3…“Jack traveled from Oakland to London”

J(d1, d2) = 3/8 = 0.375

J(d1, d3) = 0

ドキュメントにおいて、nグラムを全て扱うとかなりコストがかかるが、それらをスケッチし、nグラムの一部のみを扱うことで、効率がよくなる。