$\newcommand{\argmin}{\mathop{\rm arg~min}\limits}$ Learning-to-Rankについて学ぶついでにGBTについて再確認したので備忘録。
基本的にreferenceのPDFを追っているだけなので表記が怪しい場合はそちらを参照する。

Gradient Boosting Tree (GBT)

入力をN個のd次元ベクトルxと実数yとして $(\textbf{x}_i, y_i) (i=1 \dots N, \textbf{x}_i \in \mathrm{R}^d, y_i \in \mathrm{R})$

とし、GBTの出力を $f(\textbf{x})$ , 特にm番目の木までの出力を $f_{m}(\textbf{x})$ 、Loss function Lを $L(f(\mathbf{x}), y)$ と書く。 GBTのm回目のラウンドは以下のように表される:

各データ $\mathbf{x}_i$ に対し、 $r = -\left|\frac{\partial L(f(\mathbf{x}), y_i)}{\partial f(\mathbf{x})}\right|_{f(\mathbf{x}) = f_{m-1}(\mathbf{x}_i)}$ を計算する
$r$ をlabelとしてdecision treeをfitする
出来上がった木のそれぞれのleafについて出力値 $\gamma = \argmin_{\gamma}\sum L(y_i, f_{m-1}(\mathbf{x}_i) + \gamma)$ を求める
$f_{m}(\mathbf{x}_i) \leftarrow f_{m_1}(\mathbf{x}_i) + \alpha\gamma$ , $\gamma$ は属するleafに対応するもの、 $\alpha$ はlearning rate

γを求めるにはNewton法を使えばよいが、解析的に求まる場合もある(Loss functionを $0.5 * (y_i - f(\mathbf{x}_i))^2$ とした場合など)

RankNet

(半)順序集合 $\{x_i\}, x_i \in \mathrm{R}^d$ に対して $x_i \succ x_j \rightarrow f(x_i) \geq f(x_j)$ となるようなスコア関数 $f$ を学習したい。

$s_i := f(x_i)$ とし、 $P_{ij}$ を $P_{ij} := Pr(x_i \succ x_j) = \frac{1}{1 + e^{-\sigma(s_i - s_j)}}$ と定義し、 $i$ , $j$ のペアに対してラベル $S_{ij} = \{1, -1, 0\}$ をそれぞれ正しい順序、逆、どちらでもない場合のラベルとすると cross-entropy lossを $C_{ij} = \frac{1}{2}(1 - S_{ij})\sigma(s_i - s_j) + \log(1 + \exp(-\sigma(s_i - s_j))$ と書ける。

これは $\frac{\partial C_{ij}}{\partial s_{i}} = -\frac{\partial C_{ij}}{\partial s_j} = \sigma(\frac{1}{2}(1 - S_{ij}) - \frac{1}{1 + \exp(\sigma(s_i - s_j))})$ という性質を持ち、fのパラメタwの更新は $w \leftarrow w - \alpha\frac{\partial C_{ij}}{\partial w} = w - \alpha\left(\frac{\partial C_{ij}}{\partial s_i}\frac{\partial s_i}{\partial w} + \frac{\partial C_{ij}}{\partial s_j}\frac{\partial s_j}{\partial w}\right)$ とできる。

ただし、これだと全てのペアについて $C_{ij}$ を評価しなければならず効率が悪い。そこで $\lambda_{ij} := \frac{\partial C_{ij}}{\partial s_i}$ とおくと、 $\frac{\partial C_{ij}}{\partial w} = \lambda_{ij}\left(\frac{\partial s_{i}}{\partial w} - \frac{\partial s_j}{\partial w}\right)$ とかけて、すべてのペアに対するlossの和
$\sum_{i,j}\lambda_{ij}\left(\frac{\partial s_{i}}{\partial w} - \frac{\partial s_j}{\partial w}\right) = \sum_i\frac{\partial s_i}{\partial w}$ と書き直せる。ここで $\lambda_{i} = \sum_{j:x_i \succ x_j}\lambda_{ij} - \sum_{j:x_j \succ x_i}\lambda_{ij}$ であり、右辺第一項はi,jが正しい順に並んでいる場合は足して、そうでない場合は引くという計算になっている。

ここは若干わかりにくいのだが、例えば $\{(1,2), (1,3), (2,3)\}$ というデータを考え(tupleの1つ目の方が順位が高いとする)、 $\sum_{i,j}\lambda_{ij}\left(\frac{\partial s_{i}}{\partial w} - \frac{\partial s_j}{\partial w}\right)$ を書き下すと $\lambda_{12}\frac{\partial s_1}{\partial w} - \lambda_{12}\frac{\partial s_2}{\partial w} + \lambda_{13}\frac{\partial s_1}{\partial w} - \lambda_{13}\frac{\partial s_3}{\partial w} + \lambda_{23}\frac{\partial s_2}{\partial w} - \lambda_{23}\frac{\partial s_3}{\partial w}$ であり、まとめて
$(\lambda_{12} + \lambda_{13})\frac{\partial s_1}{\partial w} + (- \lambda_{12} + \lambda_{23})\frac{\partial s_2}{\partial w} + (-\lambda_{13}-\lambda_{23})\frac{\partial s_3}{\partial w}$ とかけることから、それぞれの係数をまとめて $\lambda_i$ としていると考えると解りやすい。これで $\frac{\partial C}{\partial w} = \sum_{i,j}\frac{\partial C_{ij}}{\partial w}$ が計算でき、パラメタの更新ができる。

LambdaRank

RankNetは転倒数を最小化していると考えられる。しかしそれが常に良いとは限らず、実際にはtopNに重みを付けた最小化がしたい、というケースが考えられる。 NDCGやERRはそういったmetricsで、LambdaRankはこれらの指標を最大化する方法の1つ。RankNetではLoss functionを定義しそれを基に $\frac{\partial C_{ij}}{\partial s_i}$ を計算したが、
LambdaRankは直接 $\frac{\partial C_{ij}}{\partial s_i} := \frac{-\sigma}{1 + \exp(\sigma(s_i - s_j))}|\Delta_{ij}|$ と構成する方法で、経験的にうまくいくということが知られている。
ここで、 $|\Delta_{ij}|$ は $x_i$ と $x_j$ を入れ替えた時のmetricsの差で、これを $\lambda_{ij}$ としてRankNetと同様の計算(ただし最大化)をすることでランキング学習をすることができる。

LambdaMART

LambdaRankにおけるscore function $\frac{\partial C_{ij}}{\partial s_i} := \frac{-\sigma}{1 + \exp(\sigma(s_i - s_j))}|\Delta_{ij}|$ の最大化にGBTを使ったものがLambdaMARTで、GBTのステップ1で $L$ を $C$ 、 $f(x)$ を $s_i (= f(x_i))$ と読み替えてやれば、あとは更新方向を逆にしてやればよい。