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

#ランキング学習

February 3, 2023

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

MARTは、スコアについての損失の勾配を予測する決定木の学習をくりかえす。 $i$回目に訓練した決定木を$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でも使われていた。