抄訳 From RankNet to LambdaRank to LambdaMART: An Overview(2010)

February 3, 2023

LambdaMARTは、勾配ブースティング決定木(MART)の訓練に、RankNetとLambdaRankを応用するランキング学習である。 RankNetとLambdaRankを以前抄訳で解説した(RankNet, LambdaRank)。 RankNetは、名前にNetがついているが、ネットワークアーキテクチャではなく学習方法の技術である。モデルが入力されたベクトルを実数に写像することができれば、モデルはニューラルネットワークでなくてもよい。 RankNetの学習は、モデルの出力する実数をスコアとみなし、あるクエリに該当する2つの事例のうち、より該当する方に高いスコアを与えられるようにモデルを訓練する。各訓練データはランキングの異なる2つの特徴とランキングの高い方を示すラベルであり、2つのスコアの差をシグモイドに与えたときの出力を、一方のサンプルが他方よりもランキングが高い確率とみなす。そして、交差エントロピーが最小になるようにモデルを訓練する。 LambdaRankは、損失の計算を省き、スコアと損失の勾配で重みを更新することで、RankNetの学習を高速化する。 LambdaMARTは、RankNetに勾配ブースティング決定木を使い、残差の計算にLambdaRankを応用したランキング学習のモデルである。

MARTは、スコアについての損失の勾配を予測する決定木の学習をくりかえす。 $N$回目に訓練した決定木を$f_i(x)$, その重みを$\alpha_i$とするとMARTを関数 $$ F_N(x) = \sum^N_{i=1}\alpha_if_i(x) $$ であらわせる。損失関数を$C$, 学習データの数を$m$、$i$番目の特徴を$x_i$とおけば、$N+1$番目の決定木は、$x_i, i=1,\dots m$における微分係数$\frac{\partial C}{\partial F_N}$を学習する。損失とスコアの微小変化の関係 $$ \delta C\approx\frac{\partial C(F_N)}{\partial F_N}\partial F $$ より、学習率を$\eta$として$\delta F=-\eta \frac{\partial\mathcal{C}}{\partial F_N}$であれば、$\delta C<0$であり、決定木を追加して損失を減らすことを期待できる。

MARTを二値分類のために訓練する場合、$m$番目の決定木の$j$番目の葉の出力$\gamma_{jm}$を求める。学習データのラベルを$y_i\in\{\pm 1\}$, $P_+\equiv P(y=1|x)$, $P_-\equiv P(y=-1|x)$とする。ロジスティック回帰はオッズ比の対数のモデルであることより $$ F_N(x)=\frac{1}{2}\log\left(\frac{P_+}{P_-}\right) $$ または $$ \begin{align} P_+&=\frac{1}{1+e^{-2\sigma F_N(x)}}\\ P_-&=1-P_+=\frac{1}{1+e^{2\sigma F_N(x)}} \end{align} $$ である。損失関数$L(y,F_N)$が交差エントロピーであれば $$ L(y,F_N) =\log\left(1+e^{-2y\sigma F_N}\right) $$ である。$m$番目の決定木の$j$番目の葉にあるサンプルの集合を$R_{jm}$とすると$\gamma_{jm}$は、 $$ \gamma_{jm}=\underset{\gamma}{\operatorname{argmin}}\sum_{x_i\in R_{jm}}\log\left(1+e^{-2y_i\sigma(F_{m-1}(x_i)+\gamma)}\right)\equiv \underset{\gamma}{\operatorname{argmin}}g(\gamma) $$ MARTは、ニュートンラプソン法によって以下の更新式で反復的に$\gamma$の近似解を求める。 LambdaMARTは、この更新でLambdaRankを利用する。 $$ \gamma_{n+1}=\gamma_n - \frac{g'(\gamma_n)}{g''(\gamma_n)} $$

LamdaRankを導入するために、MARTから離れ、RankNetの話をする。 RankNetは、あるクエリに該当した2つのURL $U_i, U_j$があり、そのスコア$s_i, s_j$があれば、$U_i$が$U_j$よりも高いランキングである確率$P_{ij}$を $$ P_{ij}\equiv\frac{1}{1+e^{-\sigma(s_i-s_j)}} $$ とする。 RankNetの各学習データは、2つの特徴$U_i, U_j$とランキングのより高い方を示すラベルからなる。ラベルを$S_{i,j}\in\{0,\pm 1\}$とし、$i$のランキングが$j$より高ければ$1$, 低ければ$-1$, 同じであれば$0$とする。このとき、$\bar{P}_{ij}=\frac{1}{2}(1+S_{ij})$として交差エントロピーを損失$C$とすると $$ \begin{align} C&=-\bar{P}_{ij}\log P_{ij}-(1-\bar{P}_{ij})\log(1-P_{ij})\\ C&=\frac{1}{2}(1-S_{ij})\sigma(s_i-s_j) + \log\left(1+e^{-\sigma(s_i-s_j)}\right) \end{align} $$ である。この$C$の微小変化$\delta C$を負にするには、 $$ \delta C=\sum_k \frac{\partial C}{\partial w_k}\delta w_k=\sum_k \frac{\partial C}{\partial w_k}\left(-\eta \frac{\partial C}{\partial w_k}\right)=-\eta \sum_k\left(\frac{\partial C}{\partial w_k}\right)^2 < 0 $$ より$\delta w_k=-\eta\frac{\partial C}{\partial w_k}$であればよい。

ここで、モデルのあるパラメータを$w_k$とし、$C$を合成関数とみると $$ \begin{align} \frac{\partial C}{\partial w_k} &=\frac{\partial C}{\partial s_i}\frac{\partial s_i}{\partial w_k} + \frac{\partial C}{\partial s_j}\frac{\partial s_j}{\partial w_k}\\ &=\sigma \left(\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma(s_i-s_j)}} \right)\left(\frac{\partial s_i}{\partial w_k}-\frac{\partial s_j}{\partial w_k}\right)\\ &=\lambda_{ij}\left(\frac{\partial s_i}{\partial w_k}-\frac{\partial s_j}{\partial w_k}\right) \end{align} $$ となる。ただし $$ \lambda_{ij}\equiv\frac{\partial C(s_i-s_j)}{\partial s_i}=\sigma \left(\frac{1}{2}(1-S_{ij})-\frac{1}{1+e^{\sigma(s_i-s_j)}} \right) $$ と定義した。任意の$i,j$について$S_{ij}=1$となる学習データの集合$I$があれば $$ \lambda_i = \sum_{j:\{i,j\}\in I}\lambda_{ij} - \sum_{j:\{j,i\}\in I}\lambda_{ij} $$ とおくとき $$ \delta w_k=-\eta\sum_{\{i,j\}\in I}\left(\lambda_{ij}\frac{\partial s_i}{\partial w_k}-\lambda_{ij}\frac{\partial s_j}{\partial w_k}\right)\equiv -\eta \sum_i\lambda_i\frac{\partial s_i}{\partial w_k} $$ である。もともとのRankNetは各学習データを処理する度に重みを更新していたが、LambdaRankは$\lambda_i$によってURLごとに計算をまとめ、重みの更新頻度を減らし、計算を高速化する。 LamdaRankは、ほかにも、モデルの評価にNDCGを使う場合、$U_i$と$U_j$を入れ換えたときのNDCGの変化の大きさを$|\Delta_{\textrm{NDCG}}|$として $$ \lambda_{ij}=\frac{\partial C(s_i-s_j)}{\partial s_i}=\frac{-\sigma}{1+e^{\sigma(s_i-s_j)}}|\Delta_{\textrm{NDCG}}| $$ とすると評価が上がることを実験的に示した。

MARTに話をもどして、モデルのスコアについての$L(y, F_N)$の勾配は $$ \bar{y}_i=-\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)}=\frac{2y_i\sigma}{1+2^{2y_i\sigma F_{m-1}(x)}} $$ である。これが$\lambda_{ij}$に類似することから、LambdaMARTは$\bar{y}_i$の代わりに$\lambda_i$を利用する。

論文のリンク

雑記

LambdaMARTはAirbnbでも使われていた。