Coda

論文メモ Ranking Relevance In Yahoo Search

December 7, 2019

概要

Yahooの検索エンジンを解説するKDD16の論文である。 論文におけるランキングの課題は、クエリと文書の語彙がことなること、ほとんどのクエリは滅多に入力されないこと、クエリの意味の解釈が難しいことである。 これらの課題に対する手法として、ランキングのモデル、特徴のつくりかた、クエリを文書によせる翻訳モデルを解説する。

アーキテクチャ

数十億の文書を検索するために、シャード化されたインデックスサーバで文書は管理される。 エンジンがクエリを受けとると、はじめに計算量の少ないランキング関数を実行する。 次に、求めたスコアの高い文書に対して後述するLogisticRankを適用する。 論文で解説される特徴はLogicticRankで使われる。 LogisticRankのスコアが高い文書は、一つのノードに集られ、集められた文書の特徴の平均、分散、トピックなどの傾向をもとに並びかれられた出力される。

ランキングのモデル

LogisticRankは、GDBTをベースにしたランキングのモデルである。 順序関係のあるラベルを文書にあたえ、疑似的な残差をラベルごとに異なる値でスケールすることで、 クエリと文書の適合度合いを出力できるようにモデルを学習する。 論文におけるラベルの種類は、”Perfect”, “Excellent”, “Good”, “Positive”, “Fair”, “Bad”, “Negative”の7つで、はじめの4つを\(+1\), 残りを\(-1\)として、目的関数に\(L(y, F)\)をつかう。 $$ L(y, F) = \log (1+\exp((-yF)), y \in \{1, -1\} $$ 疑似的な残差pseudo_response\((x)\)はラベルの種類によってスケールされる。 $$ \begin{align} -g_m(\rm{x}_i) &= - \big[\frac{\partial L(y_i,F(\rm{x}_i))}{\partial F(\rm{x}_i)}\big]_{F(\rm{x})=F_{m-1}(\rm{x})} \\
&= y_i/(1+\exp(y_iF_{m-1}(\rm{x}_i)) \end{align} $$ $$ \text{pseudo_response}(x) = -g_m(\rm{x}_i) \times \text{scale}(\mathcal{label}) $$ 各スケールは、 \(\mathcal{scale}(Perfect)=3\), \(\mathcal{scale}(Excellent)=2\), \(\mathcal{scale}(Good/Fair/Bad)=1\)である。

特徴

LogisticRankにあたえる特徴は、ユーザの行動ログからつくられる。 そのうS.Jiangらによるグラフベースの手法で生成される。 この手法は、はじめにクリック回数を辺の重みとするクエリと文書の2部グラフをつくる。その後、文書とクエリを単語埋め込みベクトルに変換するモデルを学習する。ベクトルの次元は、両者の総数を次元になる。

S.Jiangらのような単語の出現頻度を利用する手法のほか、DSSMとよばれる深層学習による手法もつかわれる。 DSSMは、ランキングのための順伝播ネットワークで、クリックスルーログからクエリと文書の関連度を学習する。 モデルからえられるクエリとURLの埋め込みベクトルの内積をLogisticRankの特徴につかう。

クエリの翻訳

クエリを文書によせるために、クエリを文書の表題に翻訳するモデルをもちいる。 ただし、翻訳されたクエリだけでは検索結果が悪いため、もとのクエリもエンジンに入力される。


論文はこちらからダウンロードできます。