[WIP]From RankNet to LambdaRank to LambdaMART: An Overview

[zerebom]

2010年のサーベイ論文

https://www.microsoft.com/en-us/research/publication/from-ranknet-to-lambdarank-to-lambdamart-an-overview/

Abstract

実世界のランキング問題を解決するアルゴリズムとして成功しているRankNet、LambdaRank、LambdaMARTについて紹介したサーベイ論文。これらのアルゴリズムの詳細は複数の論文やレポートにわたるため、それをまとめた。

RankNet

• ランダムに2つのデータをサンプリングし、相対的な順序関係を学習する
  • ある2つのデータをX_i, X_jをランク関数に通して、スコアを得る
  • そのスコア差(O_ij)をシグモイドに代入することで、
    • X_i > X_jとなる確率を得る
  • その確率と真の確率の損失をクロスエントロピーを用いて算出する
• モデルの更新式は、損失を微分することで得られる
  • ただし、ナイーブにやるとi,jの組み合わせの数だけ計算する必要がある
  • iに関して、jの総和を求めることで、データ分の計算だけで済むようにしている
  • iを任意の他の値とswapし、その誤差の総和を求める

引用: http://wnzhang.net/teaching/cs420/slides/7-ranking-filtering.pdf

LambdaRank

• RankNetを拡張して最適化した計算方法
  • RankNetでは大小関係の誤差を損失にしていたがnDCGなど、順位が上位の差を優先的にスコアをつける関数に対応したい
• 連続値を取らない損失関数の最適化に対応している
• 勾配の計算方法なので、微分可能なモデルなら何にでも使える
• 以下雑多メモ
  • モデルを訓練するためにはコストそのものは必要なく、勾配だけあれば十分という点に着目した?
  • スコアでソートされた後のitemの勾配を計算することで、連続でない目的関数にも対応した
  • 経験的にnDCGを直接最適化することを示している

引用: http://wnzhang.net/teaching/cs420/slides/7-ranking-filtering.pdf

LambdaMART

• LambdaRankをGBDTに適応したもの

参考

• 上海交通大学の資料
• サーベイ論文まとめ
  • ランキング学習： RankNetからLambdaRank、そしてLambdaMARTへ - Qiita
  • RankNetを実装してランキング学習
• MART/勾配ブースティング
  • 勾配ブースティングの基礎と最新の動向 (MIRU2020 Tutorial)
  • 勾配ブースティング決定木ってなんぞや - Qiita