Sources of evidence for vertical selection (SIGIR 2009)読んだメモ

Sources of evidence for vertical selection
SIGIR2009のbest paper．

この論文は何をしているのか

vertical selectionと言うと全くピンと来ない．上手いこと示す言葉を知らないので具体例を挙げる．例えばgoogleで「桜高軽音部」と検索すると3件目に「桜高軽音部」で動画を検索した結果へのリンクが張られる．また，「JAL」で検索した場合には5件目に「JAL」でニュースを検索した結果へのリンクが張られる．

このような「動画」「ニュース」「画像」などの区分をverticalと呼び，検索クエリに対してそれらへの検索を同時に行うべきか行わないべきか，どのverticalに対して行うべきか，を示したのがこの論文．

問題設定

検索エンジンに対するクエリに対し，いずれかのverticalに割り振るか，もしくはどのverticalにも割り振らない"no relecant vartical"かを選ぶ．
今回は18のvertical(autos, directory, finance, game, ...)を考える．

手法

大きく分けて3つの特徴量を用いる

Query String Features
Query-Log Features
Corpus Features

Query String Features

単体じゃ一番役たたなさそうなもの

Rule-based vertical triggers

ガチガチに作ったルールベースと正規表現でクエリを45のクラスに割り振る．

Geographic features

ルールベースで作った地理アノテーションツールを使ってクエリに地理情報かどうかの値を付与．

Query-Log Features

verticalごとのクエリログに対してunigramの言語モデルを作る．
$QL_q(V_i) = \frac{1}{Z}P(q|\theta_{V_i}^{qlog})$
$P(q|\theta_{V_i}^{qlog})$ は言語モデル， $Z=\sum_{V_i \in V} P(q|\theta_{V_i}^{qlog})$
verticalごとのクエリログは1年分，no relecant vartical用には一ヶ月分の普通の検索におけるクエリログを使う．言語モデルを作る際にはそれぞれのverticalごとに最貧20000語を使い，Witten-Bell smoothingを用いる．
Query-Log Featuresではout of vocabulary(OOV)termsをどう扱うかについて2パターン用意しておくらしい．OOVの扱いの話はsmoothingとどう違うのか全く判らない．

Corpus Features

Corpusとか書いてるけど"Corpus features are dericed from document rankings obtained by issuing the query to different collections"とか書いてあるしドキュメント集合を用いて得たfeaturesの話．

Corporaを作る

Corporaというよりもドキュメント集合を二種類作る．

Direct Sampling from Vertical

基になっているのはQuery-baesd samplingらしい．verticalごとのクエリログからunigramで上位1000個を取り出してqueryとし，verticalごとに検索して上位100件ずつを得てその和集合から25000ドキュメントをランダムサンプリング．vertical $V_i$ から得たこのドキュメント集合を $S_i^{vertical}$ と表記．

Sampling for Wikipedia

こっちはもっと大雑把．wikipediaから「カテゴリ」部分にvertical名を含んでいる記事を全て持ってくる．大雑把だが「テキストがリッチであること（videoやimageにおけるdirect samplingはテキストがpoor）」，「フォーマットが整っていること」，「整合性があること」などの利点がある．これをvertical $V_i$ から得たこのドキュメント集合を $S_i^{wiki}$ と表記．
これらCorporaを使って次の4つを計算する．

Retrieval Effectiveness Features

Clarityが提案した検索結果の良さを測る指標がある．これは検索クエリと，そのクエリでヒットした文書の上位（コレクション）で言語モデルを作り，それのKLダイバージェンスを比較するというもの（近ければ検索結果の有効性が高い）．
$Clarity_q(C) = \sum_{w in V} P(w|\theta_q)\log_2\frac{P(w|\theta_q)}{P(w|\theta_C)}$
VはコレクションCにおける単語， $P(w|\theta_q)$ 及び $P(w|\theta_C)$ はそれぞれクエリ及びコレクションから得られた言語モデル．また， $P(w|\theta_q) = \frac{1}{Z}\sum_{d \in R_{100}} P(w|\theta_d)P(q|\theta_d)$ で得る．Clarityは検索結果の上位ドキュメントがランダムサンプリングに近づくにつれどんどん下がっていく（検索結果の有効性が低くなる）．
これを流用する．クエリqに対する $V_i$ におけるClarityスコアは
$Clarity_q^{*}(V_i) = \frac{1}{Z^*}Clarity_q(S_i^*)$
$S_i^*$ は $S_i^{vertical}$ もしくは $S_i^{wiki}$ であり， $Z^*=\sum_{V_i \in V} Clarity_q(S_i^*)$ ．

ReDDE Features

今度はresouece selectionと呼ばれる問題で使われているReDDEを用いる．
$ReDDE^*_{q}(V_i) = |V_i|\sum_{d \in R_{100}}I(d \in S_i^*)P(q|\theta_d)P(d|S_i^*),\,P(d|S_i^*)=\frac{1}{|S_i^*|}$
しかしこの式がよく分からないのは[I(d \in S_i^*)]とかやると[S_i^{wiki}]があまりマッチしないんじゃなかろうか．と思ったが相対比較だから構わないのか．

Soft ReDDE Features

ReDDEはverticalに対するハードアサインなのでこれをソフトにしたものを考える．具体的には $\phi(d, V_i)$ でドキュメントの言語モデルとverticalの言語モデルにおける距離関数を考える．ここではBhattacharyya correlationを使って
$B(d, V_i) = \sum{w}\sqrt{P(w|\theta_d)P(w|\theta{V_i})}$
とし， $\phi(d, V_i)=\frac{B(d, V_i)}{\sum_{V_j in V}B(d, V_i)}$ として，
$Soft.ReDDE_q(V_i)=\sum_{d \in R_{100}}\phi(d, V_i) \times P(q|\theta_d)$
とする．

Categorical Features

階層的なカテゴリ構造を使ってうんちゃら．式に $I(y_i = depth_x(y_i))$ とか書いてあって意味がよくわからないのでスルー．

実験

Single Feature Runs

割り振るverticalを $\tilde{v}$ として閾値パラメータ $tau$ を考えて
$\tilde{v}=\left\{\begin{array}{ll}argmax_{V_i} score_q(V_i)& if\, \max_{V_i} \frac{1}{Z}score_q(V_i) > \tau \\ \emptyset & otherwise \end{array}\right.$
として割り振る．

Feature Combination Run

18 vetical + no relevant vertical = 19 one-vs-allなロジスティック回帰で学習のち予測
結果としてはsingleではprecが最低0.254(clarity.vertical)，最大0.368(Query-Log Features + OOV)．ロジスティック回帰では0.583とかなり高い．Clarityではverticalよりwikiが，ReDDEではwikiよりverticalの方が優れている．

言語モデルというものがどんなものでどんな時に使うのか全く知らなかったが，こういう使い方があるんだと勉強になった．resource selectionが何をどのように問題視してるかがピンと来なかったためにReDDEを使うあたりや結論のあたりがはっきり理解できなかったのが辛い．
queryに対して教師あり学習でverticalをハードアサインするのが一番いい，という結論ではあったのだけれど，ランキング学習の枠組みで解決するというのはどうだろうと思った．例えばgoogleなんかはクエリを複数のverticalに割り振ってそれの表示順が色々と変わっているように見える（「勝間和代」で検索すると少し下の方にリアルタイム検索へのリンクが張られていたりする）．なのでランキング学習で解いてランキングが一定以下なら検索しないとかするというのもありなんじゃないかなと思う（ランキング学習知らないので実現できるかどうか全く分からないけど）.

糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com