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グラムの一部のみを扱うことで、効率がよくなる。
