機械学習

LightGBMのランキング学習を理解する

ランキング学習について

ランキング学習は、情報検索や推薦アルゴリズムなど、予測値の絶対的な値より相対的な順位を予測したい場合に使用される学習方法です。

LightGBMによるランキング学習ではあるクエリに対するレコードの集合から、ペアを作成して、関連順序のラベルから教師あり学習を行います。

ペアを作成してラベルを付与するとは、あるクエリに対するレコードの集合が{d1, d2, d3}の時、d1 >d2, d1>d3など2つのレコード組み合わせに対して、関連順序の正しさに対してラベルを付与することを指します。

何を最適化しているのか?

LightGBMのランキング学習では、ペアの各レコードの予測値をsiとsjとして、これらの差分を予測値として損失を計算します。

σはパラメータです。真の関連順序がi>jの時を1, i<jの時を-1,同率の時を0として、定式化したものと、上記の予測値Pijをloglossの式に代入すると下記の損失関数を計算できます。

正解が1の時(Sij=1)のペアを考えると下記のように計算できます。

この損失関数を用いた最適化では、予測値の差分にしか着目していないので、ランキング上位下位どちらも同等の損失が計算されます(上位1,3位と上位100,103位の組み合わせの予測値の差分が等しい場合、同じ損失の値となる)。

しかし、推薦システムなどでは、掲載できる数に上限があるため、上位群の順番をより正確に予測したい場合があります。

そこで、上位が正解するとスコアが高くなる評価指標であるNDCGという評価指標を使って、上位に重み付けをしたのがLightGBMによるLambdaMARTとなります。

LambdaMARTの論文を参照すると、損失関数(上記のC)を1階微分した値をラムダと呼び、i,jの順番を入れ替えた場合のNDCGの変化の差分の絶対値を、ラムダに掛けて重み付けを行っているようです。

NDCGはsklearnで用意されています。0から100まで関連度が低い順から並べた時(100が一番関連度が高い)。先頭から2つずつ順番を入れ替える(0,1を入れ替える、1,2を入れ替える…)と、どの程度スコアが変化か計算すると下記のようになります。

関連度が高い対象、特に上位20程度まではスワップすると劇的にスコアが変わることがわかります。また、逆に上位20位以降はあまりスコアが変わらないので、LambdaMARTでは上位20位以降はあまり学習されないのではないか?という気がします。

実装とパラメータの意味

下記実装の一例(切り出し)となります。

ランク学習を行うためには、LightGBMのデータセットに変換するときにクエリの情報を与えて、パラメータをランク学習仕様にする必要があります。以下パラメータの意味です。

label_gainはDCGの分子(gain)を指定しています。デフォルトでは、2**i-1で関連度上位のDCGスコアが非常に大きくなってしまいます。(例えば、30個の関連度ランキングがある場合上位:(2^30-1)-(2^29-1), 下位:(1-0)と大きく違う)

そのため、gainは上記の例のように線形に増加させるように学習を行う方が良さそうに思えます。

lambdarank_truncation_levelは、ラムダの計算をいくつのサンプルまで使用するかを決めるパラメータのようです。LightGBMで最適化するには、損失関数の1階微分(ラムダ)と2階微分がレコード毎に必要になります。

同じクエリ内の全てのペアで関連度が上位の対象から計算されたラムダと、下位の対象のラムダの差分を計算する過程で、いくつまでのペアを使用するか指定するパラメータのようです。

基本的に全てのペアに対してラムダを計算した方が情報が多くて精度が上がると思うので、クエリ毎の最大レコード数で良いと思われます。

気になるところ

ラベルが同率の場合、ペアの計算は無視されるので、ラベルの個数がインバランスの場合、重複が多い対象の学習が上手くいかない気がします。

これは、例えば、ラベルが[3,2,2,2,2,1]のデータがあった時、ラベル2はラベル3と1からしかラムダが計算されないですが、3,1は他の全てのラベルからラムダが計算されるので、重複しているラベルに関しては学習があまり進まないように思います。

また、実装を確認すると同一順位の場合にも、DCGの分母の値が大きくなるので、同じ順位のラベルでもラムダの値が変わるように思います。([3, 3, 2, 1]のラベルの時、1つ目の3と2のペア、2つ目の3と2のペアで計算される値が違う?)

この場合、最適化したい上位のターゲットに同率のラベルが多いと上手く学習できるのかが疑問です。

そして、NDCGを損失に使っているため、下位順位の予測精度が必要である場合にLambdaMARTでは、あまり精度が出ないのではないかということは個人的に気になります。

簡単な実験

人工的なデータを作成して、回帰・ランク学習による精度の違いを確認します。レコード数は10M行、特徴量は10個で0以上1未満の一様分布から生成された乱数に、ターゲット=[1, 2, 3, 4]に応じて平均0.1~0.4,分散0.03の正規分布に従う乱数を加算した値とします。

また、1000レコード毎に連番でperiodという期間を割り振りランキング学習ではこれをクエリとします。学習データ:検証データ:テストデータを6:2:2で分割してテストデータでのみ評価を行います。

評価指標は、クエリ毎の予測値上位・下位20, 50, 100におけるターゲットの合計値とします。

期間毎にランキング学習、回帰の予測値をランク化して、ターゲットの合計値の差分を算出します。(ランキング学習から回帰を引く)

まずは、上位20, 50, 100の差分の累積値です。

縦軸の値が大きいほど、ランキング学習の方が高いターゲットの値を抽出できていること(上位を正確に予測できていること)になります。

乱数のseedで結果がかなり変わりますが、TOP20ではランキング学習の方が良く、TOP100になると回帰での予測の方が良いことがわかります。

これは、上述したようにNDCGが上位数十個を正しく予測するように重み付けされているからではないかと考えられます。

次に下位20, 50, 100を確認します。

こちらは回帰からランキング学習を引いた値を算出しています。(縦軸が大きいとランキング学習が優位、小さいと回帰が優位としています)

上位とは異なり、下位20においても回帰の方が優位となっており、LambdaMARTでは下位の予測順位の精度を向上させるのに適していないことがわかります。

ただ、下位においても、ラベルの順位を逆転させてモデルを構築して、日毎に上位・下位モデルのTOP20を取り出して組み合わせれば、単純な回帰よりも高い精度で予測ができるのではないかと思われます。

最後に

間違っていれば、教えてもらえるとありがたいです。

下記のページを参考にさせていただきました(感謝)

The inner workings of the lambdarank objective in LightGBM

「機械学習の論文をスクラッチから実装しよう!」LambdaMART の数式をコードに落とす

Numeraiでランク学習してみた