はじめに
ランキング学習のサーベイ論文 "From RankNet to LambdaRank to
LambdaMART: An Overview (2010)" を読んで概要をまとめました。ちょっと古いですが、LambdaRankは検索分野で現在も実際に使われているという話を聞いているので、興味を持って読んでみました。
元論文: From RankNet to LambdaRank to
LambdaMART: An Overview
$$
\newcommand{\curly}[1]{{\left \{ #1 \right \} }}
\newcommand{\vecx}{{\bf x}}
\newcommand{\vecxi}{{\vecx_i}}
\newcommand{\vecxj}{{\vecx_j}}
\newcommand{\real}{{\mathbb{R}}}
\newcommand{\Pij}{{P_{ij}}}
\newcommand{\barp}{\bar{P}}
\newcommand{\realPij}{{\barp_{ij}}}
\newcommand{\oij}{{o_{ij}}}
\newcommand{\par}[1]{{\left ( #1 \right ) }}
\newcommand{\abs}[1]{{\left | #1 \right | }}
\newcommand{\sigmalr}{{ \sum_{(i,j) \leftrightarrow I} }}
\newcommand{\sigmaij}{{ \sum_{(i,j) \in I} }}
\newcommand{\sigmaji}{{ \sum_{(j,i) \in I} }}
\newcommand{\sigmai}{{ \sum_i }}
\newcommand{\w}{{ \bf w }}
\newcommand{\fw}{{ f_\w }}
\newcommand{\pfrac}[2]{{ \frac{\partial#1}{\partial#2} }}
$$
問題設定
ランキング学習とは、データ同士の相対的な順序関係を学ぶためのアルゴリズムです。
身近な実用例でいうと、web検索・ショッピングサイトの検索の検索結果などがこの手のアルゴリズムを使用しています。
式で書くと、データ $\vecx \in \real$ に対して $\fw(\vecx) : \real^n \rightarrow \real$
を定義し、その大きさの順序を出力するアルゴリズムです。
ランキング学習のアルゴリズムは、優れた順番を生成してくれるパラメータ $\w$ を得ることが目的となります。
RankNet(2005)
データ $\vecxi$ とデータ $\vecxj$ の順序を比べる時、$\oij=f(\vecxi)-f(\vecxj)$ が $0$ より大きいならば前者がより順位が高い確率が高いということになります。
RankNetでは、その確率が $\oij$ にのみ依っていると仮定し次のようにモデルします。
$$\Pij = sigmoid(\oij) = \frac{1}{1+\exp(-\oij)}$$
真の確率を $\realPij$ とし、$\Pij$に関するクロスエントロピーロスを計算すると、
$$
\begin{align}
C_{ij}&=-\realPij\log{\Pij}-(1-\realPij)\log(1-\Pij)\newline
&=-\realPij \log \par{\frac{1}{1+\exp{(-\oij)}}} - (1-\realPij) \par{\frac{\exp{(-\oij)}}{1+\exp{(-\oij)}}}\newline
&=-\realPij \log \par{\frac{\exp{(\oij)}}{1+\exp{(\oij)}}} - (1-\realPij) \par{\frac{1}{1+\exp{(\oij)}}}\newline
&=\realPij(\log(1+\exp{(\oij)})-\oij) + (1-\realPij) \par{1+\exp{(\oij)}}\newline
&=-\oij \realPij + \log(1+\exp{(\oij)})
\end{align}
$$
となります。ただし、真の確率は
$$
{\realPij=
\begin{cases}
1 & \vecxi \text{の方が順位が高い} \newline
0 & \vecxj \text{の方が順位が高い} \newline
1/2 & \text{順位が同じ}
\end{cases}
}
$$
とします。これを代入すると、
$$
{C_{ij}=
\begin{cases}
\log(1+\exp{(-\oij)}) & \vecxi \text{の方が順位が高い} \newline
\log(1+\exp{(\oij)}) & \vecxj \text{の方が順位が高い} \newline
\log(\exp{(\frac{1}{2}\oij)}+\exp{(-\frac{1}{2}\oij)}) & \text{順位が同じ}
\end{cases}
}
$$
と表せます。
データが $I=\curly{(i,j) | \vecxi \text{と} \vecxj \text{を比べると} \vecxi \text{の方が順位が高い}}$ の形で与えられている場合、最小化したい損失は $C=\sigmaij C_{ij}$ となります。
この$C$についてパラメータ $\w$ の微分を求められれば、gradient descent(勾配降下法)を利用して、$C$を最小化できることがわかります。それを計算すると
$$
\begin{align}
\pfrac{C}{\w}&=\sigmaij \pfrac{C_{ij}}{\w}
=\sigmaij \pfrac{C_{ij}}{\oij} \par{\pfrac{\fw(\vecxi)}{\w}-\pfrac{\fw(\vecxj)}{\w}}
\end{align}
$$
となります。 ($\pfrac{C_{ij}}{\oij}$ は、$C_{ij}$ の定義から容易に計算できますが、式の完結さのためににこのまま置いておきます。)
これを馬鹿正直に計算すれば、$(i,j) \in I$ の数に比例した回数だけ $\pfrac{\fw(\vecxi)}{\w}$ を計算することになります。この計算は、モデルにニューラルネットワークを使用する場合、back propagationなどのコストのかかる計算です。そこで、この式を次のように書き直します。
$$
\begin{align}
&\sigmaij \pfrac{C_{ij}}{\oij} \par{\pfrac{\fw(\vecxi)}{\w}-\pfrac{\fw(\vecxj)}{\w}}\newline
=&\sigmai \lambda_i \pfrac{\fw(\vecxi)}{\w}
\end{align}
$$
$\sum$が $(i,j)$ に関する和から$i$に関する和になっていることに注目してください。ここで、$\lambda_i$は
$$
\lambda_i=\sum_{j:(i,j)\in I} \pfrac{C_{ij}}{\oij} -\sum_{j:(j,i)\in I} \pfrac{C_{ji}}{o_{ji}}
$$
です。この形式にすることによって、モデルの微分の計算はデータ数分で済むことが明らかになりました。
RankNetの拡張、LambdaRank(2006)
RankNetはモデルが出力した確率と真の確率のクロスエントロピーを最小化することで、ランキングを正確にするアルゴリズムでした。しかし、場合によってはクロスエントロピー以外の指標を最小化したいケースがあります。
例えば、web検索の検索結果などにおいて、１番目と３番目の記事の順番が逆になってしまっているのと、７番目と９番目の記事が逆になってしまっているのは、どちらが重大な間違いでしょうか。人間視点から見れば明らかに前者の方がより大きな間違いだと言えます。
このように、例えば上位N位までの正確性を重視したい場合は、クロスエントロピー以外の損失関数をデザインすることができ、一般的に次のように書けます。
$$
L(\curly{f(\vecx_1),f(\vecx_2),...,f(\vecx_m)},\curly{l_1,l_2,...,l_m})
$$
$f(\vecx_i)$ がモデルの出力で、$l_i$が実際の順位です。
ここで問題になるのは、順位が関係する損失関数は一般的には連続値を取らないのでLambdaRankのような微分を用いた最適化ができないということです。
そこで、LambdaRankはRankNetを拡張して最適化を行います。元のLambdaRankは次の微分を使用して最適化していました。
$$
\pfrac{C}{\w}=\sigmaij \pfrac{C_{ij}}{\oij} \par{\pfrac{\fw(\vecxi)}{\w}-\pfrac{\fw(\vecxj)}{\w}}
$$
それを、次のように改変します。
$$
\pfrac{C'}{\w}=\sigmaij \pfrac{C_{ij}}{\oij} \abs{\Delta_{ij}} \par{\pfrac{\fw(\vecxi)}{\w}-\pfrac{\fw(\vecxj)}{\w}}
$$
ここで、$\Delta_{ij}$ は、 $f(\vecxi)$ と $f(\vecxj)$ の値を逆にした場合の損失の差、
$$
L(\curly{...,f(\vecx_i),...,f(\vecx_j),...},\curly{l_1,...,l_m}) - L(\curly{...,f(\vecx_j),...,f(\vecx_i),...},\curly{l_1,...,l_m})
$$
です。
これを満たす損失関数 $C'$ が存在するとは限りませんが、これを微分としてgradient descent(勾配降下法)を行うと、$L$を小さくできることが知られています。直感的には、間違えると大きな損失をうむ $(i,j)$ のペアに関する勾配を増やしている、と見ることができると思います。
LambdaMART
LambdaRankは勾配の計算方法を与えるものなので、微分可能なモデルならどのモデルにも適用することができます。LambdaRankをGradient Boostingに適用したものを、LambdaMARTというようです。
$f(\vecxi)$ に関する損失の勾配は、次のように計算できます。
$$
\begin{align}
\pfrac{C'}{f(\vecxi)}&=\sigmaij \pfrac{C_{ij}}{o_{ji}}\abs{\Delta_{ij}} - \sigmaji \pfrac{C_{ij}}{o_{ji}}\abs{\Delta_{ij}} \newline
&= \par{\sigmaij-\sigmaji} \pfrac{C_{ij}}{o_{ji}}\abs{\Delta_{ij}} \newline
&= \par{\sigmaij-\sigmaji} \frac{-\abs{\Delta_{ij}}}{1+\exp(f(\vecxi)-f(\vecxj))}
\end{align}
$$
これを用いて、Gradient Boostingを行うことができます。
このLambdaMARTは、2010年のYahoo! Learning To Rank Challengeで優勝しています。
おわりに
以上です。何か間違い等コメントご指摘あったらよろしくお願いします。