Higu`s diary

新米データサイエンティストのブログ。技術についてゆるく書きます〜

RankNetとLambdaRankの解説

本記事はWantedly 21新卒 Advent Calendar 2021の22(???)日目の記事です!(今は2021年12月22日 午後220時です。)

最近、From RankNet to LambdaRank to LambdaMART: An Overview というサーベイ論文を読みました。本記事ではその論文をもとに、ランキング学習のアルゴリズムである、RankNet, LambdaRankの解説をしたいと思います。

なるべく数式を噛み砕いて説明しようと思いますが、久しぶりにちゃんと数式を追ったので、間違っている部分もあるかもしれないです...悪しからず...(数式はサーベイ論文から引用しています。)

ランキングモデル・ランキング学習とは?

ランキングモデルとは、アイテムの集合を、定義した重要度順にソートして返すモデルのことを指します。このモデルを機械学習を使って構築すること、そのスキームを、ランキング学習(Learnig To Rank, LTR)と呼びます。

ランキングモデルは入力に、何ついて情報を得たいか指定する”クエリ”とアイテムの特徴量を受け取り、重要度順にソートされたアイテム群や、アイテム群の重要度のスコアを出力します。LTRの文脈では各アイテムのことを文書(docment)と呼ぶことが多いです。

f:id:zerebom:20220101100305p:plain

引用: Learning to rank - Wikipedia

RankNetとは

RankNetはデータセット内のクエリが同じアイテムをランダムに2つ選び、そのペアの順序関係が正しくなるように学習を進める、Pairwiseランキング学習の手法の一つです。

RankNetのベースモデルは、アイテムの特徴ベクトルを入力に、重要度のスコアを出力します。

 s_i = f(x_i)

このベースモデルから得られる、二つのアイテムSi, Sj のスコア差をsigmoid関数に通すことで、アイテム Si > Sjとなる確率を求めます。

 P_{ij} = P(U_i > U_j) = \frac{1}{1+e^{-\sigma(s_i-s_j)}}

そして、この Si > Sjとなる確率と理想的な並びになるとき得られる真の確率に近づけるように学習をします。

真の確率との誤差はクロスエントロピーで計算します。

f:id:zerebom:20220101175813p:plain

理想の確率は以下の通りです。

f:id:zerebom:20220101082100p:plain

モデルパラメータwの更新に必要な損失Cの微分は以下のようになります。

 \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}  = \lambda_{ij}(\frac{\partial s_i}{\partial w_k} - \frac{\partial s_j}{\partial w_k})

数式メモ

  • wがi, jの合成関数なので、項が二つに別れる
  •  \frac{\partial C}{\partial s_i} = - \frac{\partial C}{\partial s_j} なので、不等号を入れ替えて項をまとめている

このλは、アイテムiがアイテムjから受ける勾配として捉えることができます。

f:id:zerebom:20220101082019p:plain

数式メモ

  •  S_i > S_j だと値は0に、 S_j > S_i だと -2σに近づく
  • 順序関係が誤っている場合は、負の方向にスコアが更新される

LambdaRankとは

LambdaRankは以下のようなRankNetの課題を解決するために改良したランキングモデルです。

  • RankNetが行うのは、あくまでペア同士の順序関係の最適化なので、アイテムの位置によって損失への重みを変えることができない
    • 一般的にランキングは上位アイテムの並び順に強い重みをつけたほうが良い
    • nDCGやMRRなどランキングの評価指標も上位アイテムの並び順に強い重みをつけている
  • 1回のモデルの更新のために、全アイテムの組み合わせのスコア差が必要で、計算量が多い
    • 例えばiの勾配を得るには、i以外全てのアイテムとのスコア差を算出する必要がある。

上記の問題を解決するために、LambdaRankは勾配として利用するλを以下のように定義します。

f:id:zerebom:20220101081901p:plain

この |\Delta nDCG| はi, jを入れ替えた時のnDCGの差分で、またnDCGに限らず、任意のランキングの評価指標に置き換えて学習することもできます。

なぜ置き換えが成立するのかというと、アイテムを入れ替えた時のランキングの評価指標の差分もRankNetの  \sigma(\frac {1}{2}(1-S_{ij}) - \frac{1}{1+e^{\sigma(s_i-s_j)}}) の項と同様に、スコアの出力が真の確率から遠いほど、大きな負の値をとるという性質を持っているからと、解釈しています。

この置き換えを行うことで、モデルを1回更新するのに、必要な計算量が減り、また任意の評価関数を可能になります。つまりRankNetの課題を解決することができます。

おわりに

久しぶりに数式をちゃんと追って論文を読みました。めちゃくちゃ時間かかるけど、さっと読んでもすぐ忘れてしまうので、たまにはじっくり読むの良いなと思いました💪 サーベイ論文で紹介されていたLambdaMARTについても、いつかちゃんと読み込んでブログに足していきたいです...!(一応読んだけど、人に説明できるほど理解できなかったorz)

余談ですが、Wantedly 21新卒 Advent Calendar 2021 を無事走破できました!🎉 他の記事も良ければ読んでみてください!

zerebom.hatenablog.com www.wantedly.com zerebom.hatenablog.com zerebom.hatenablog.com

参考文献

サーベイ論文 www.microsoft.com

サーベイ論文の解説 qiita.com

ランキング学習の概要 jp.kamulau.com

RankNetの実装 www.szdrblog.info

RankNetの実装 qiita.com

RankNetの解説 ryo59.github.io

LambdaNetの解説 jp.kamulau.com

LambdaMartの解説 jp.kamulau.com

google-site-verification: google1c6f931fc8723fac.html