抄訳 Learning to Rank with Nonsmooth Cost Functions (2006)

January 23, 2023

情報検索の指標は、モデルの返す文書の順序を評価する。指標の関数自体を損失関数にできれば、重みの更新を指標に最適化できる。ところが、文書の順序を評価する指標は、重みによる微分が未定義や0になりえるので、損失関数には使えない。 LambdaRankは損失関数に直接は使えない関数を学習に応用するアルゴリズムである。 RankNetをLambdaRankで学習することで、学習時間を短縮し、NDCGを向上できた。

RankNetは、2つの文書からクエリに適合する方を選べるように学習する。損失関数$C_T$に交差エントロピーを使う場合、文書$i, j$を入力したときのスコアの差$s_i - s_j$をシグモイド関数にあたえ、その値を文書$i$が$j$よりも適合する確率とみなす。学習データの集合を$\mathcal{P}$, モデルの重みを$w_k\in\mathcal{R}$とするとき、$w_k$で$C_T$を偏微分すると

$$ \begin{align} C_T&\equiv\sum_{\{i,j\}\in P}C(s_i,s_j)\\ \frac{\partial C_T}{\partial w_k}&=\sum_{\{i,j\}\in P}\frac{\partial C(s_i, s_j)}{\partial s_i}\frac{\partial s_i}{\partial w_k} + \frac{\partial C(s_i, s_j)}{\partial s_j}\frac{\partial s_j}{\partial w_k}\\ \end{align} $$

もっとも、式が成立するには$C(s_i, s_j)$が$s_i$と$s_j$でつねに偏微分できなければならない。そこで、クエリ$i$を与えたときにモデルが出力する$n_i$個のスコアを$s$とラベルを$l$として $$ \frac{\partial C}{\partial s_j} = -\lambda_j(s_1, l_1,\dots, s_{n_i}, l_{n_i}) $$ が存在する必要十分条件を求める。

ポアンカレの補題より、$S\in \mathcal{R}^n$が星型の開集合であるとき、$S$上の閉形式は完全である。同時に完全形式は閉形式であるから、星型の開集合上の微分形式が完全形式であり、かつそのときに限り、閉形式になる。 $\mathcal{R}^{n}$上の1-形式の基底を$dx^j$として$\boldsymbol{\lambda}$を $$ \boldsymbol{\lambda} \equiv \sum_j \lambda_j dx^j $$ と定義する。このとき1-形式$\boldsymbol{\lambda}$は閉であるから $$ \frac{\partial \lambda_k}{\partial x^j} - \frac{\partial\lambda_j}{\partial x_k} = 0\ \ (\forall k < j \le n_i) $$ である。以上から $$ \frac{\partial\lambda_j}{\partial s_k} = \frac{\partial \lambda_k}{\partial s_j}\ \ \forall j,k \in \{1,\dots , n_i\} $$ が成りたつような$C$であればよい。

RankNetの高速化をはかる実験では、複数の損失2つの文書を入れ換えてえられるNDCGの利得とRankNetの損失関数の積が、損失関数に使われている。このとき $$ \lambda = N\left(\frac{1}{1+e^{s_i-s_j}}\right)(2^{l_i}-2^{l_j})\left(\frac{1}{\log(1+i)}-\frac{1}{\log(1+j)}\right) $$ である。

論文のリンク