【順位を予想する🐎】ランク学習#1

目的

業務で間接的に知ったのがきっかけで、分類や回帰とは少し枠組みの異なるランク学習（ランキング学習、Learning to rank）について、従来の問題設定と何が異なるのかを調査し、応用可能性を検討することを目的とする。また、ライブラリに基づく簡単な実装を行い、アルゴリズムの性能を実装の観点から知ることも併せて目的とする。

ランク学習とは

ランク学習とは、「結果の順序」に興味がある機械学習のフレームワークである。
通常の分類や回帰問題であれば、それぞれのラベルに対する予測値があって、それらが実際の正解値とどの程度ずれているか（＝誤差）が目的変数になっていて、学習時にはその誤差が小さくなるようにパラメータを学習する。
それに対してランク学習は、結果の順序が合っていれば値が小さくなるような目的変数が設定される点である。結果の数値が正解と大きく異なっていても、予測値間での順序が正解値の順序と一致していれば、目的変数は小さくなるという点において、従来の学習と異なる。
また、分類や回帰問題とは異なり、学習データが「クエリ=検索キーワード」と「クエリに対する検索結果リスト」のような形式で与えられる。検索エンジンをイメージした時、クエリに対する結果が何らかの順番で並んでいることが多いことから想像はつきやすい。

ランク学習の応用先として、検索エンジンのシステムや、公営ギャンブル（競馬、競艇、競輪など）の順位予想などがあるようで、それらの記事も多く散見された。
https://www.szdrblog.info/entry/2018/12/03/004600
https://blog.tstylestudio.com/2022/02/19/xgbrankerを使って競馬aiのランク学習をやってみた/

アルゴリズム（フレームワーク）

この章では、ランク学習で使用されるアルゴリズムについて紹介する。ランク学習で一般的に利用されるのは、"XGBoost"や"LightGBM"などに代表される「勾配ブースティング決定木」アルゴリズム (GBDT=Gradient Decent, Boosting, and Decetion Tree)である。名前の通り、勾配降下法＋ブースティング＋決定木のそれぞれのアルゴリズムを組み合わせた手法のことを指す。以下に、それぞれの手法の概要を示す。執筆に際し、以下のサイトを参照させていただいた。下記の二つは、個人的にとてもわかりやすい。
なお、この記事では主に勾配ブースティング決定木のみの紹介にとどめ、"XGBoost"や"LightGBM"の詳細およそれぞれの特徴の説明は割愛する。今回実装して動作を確認した"LightGBM"と、このGBDTの関係は、以下のようになっている。
(図は、下記リンク先から参照)
https://qiita.com/Uking/items/d7bb7da33d2bbe3eeb71

以下にGBDTで使用され得る要素アルゴリズムをそれぞれ簡単に紹介する。下図は、GBDTのアルゴリズムのフローのポンチ絵である。
(図は、下記リンク先から参照)
https://qiita.com/triwave33/items/aad60f25485a4595b5c8#勾配ブースティングにおける漸化式

決定木 (Decision Tree)

決定木は、データが属するクラスを特定するための分岐を用意するフレームワークである。解く問題によって分類木や回帰木などがあるが、基本的にやりたいことは同じである。生やす木は、エントロピーや情報ゲインと呼ばれる指標を用いて決定される。
https://qiita.com/takurofukuta/private/1d206e674b6dbaddc5dc

勾配降下法 (Gradient Decent)

下記に示すように、損失関数のパラメータの勾配を計算して、それを元にパラメータ（重み）を更新していく方法である。これは比較的一般的な問題で、様々なアルゴリズムで使用されている。ただし、このGBDTでは重みベクトルの最適化が目的ではなく、決定木の出力から得られる損失関数の値を小さくすることが目的なので、関数で偏微分する。下の式のように、各データサンプルごとの勾配$g$は、損失関数$L$を予測値(モデル)で偏微分することで表される。

$$g_i = -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}|_{f(x)=f_{m-1}(x)}$$

ここで$x_i$は$i$番目のデータであり、f(x)はそのデータを決定木モデルに通した時の出力、$y$はデータに対するラベル、$m$はiterationのindexである。

ブースティング (Boosting)

ブースティングとは、各ラウンド(iteration)ごとの決定木の出力が、次の決定木の損失関数に足される構造のことを差す。ある決定木が出力する予測値は正解値との誤差を含むが、それらが次のiterationの決定木の損失関数に入って、だんだん損失関数の値を小さくするような働きをするイメージである。
あるiterationにおける決定木が3つの場合、$i$番目のデータの予測値$\^y_i$は、

$$\^y_i = f_1(x_i)+f_2(x_i)+f_3(x_i)$$

で表される。ここで予測値$\^y_i$は、それぞれの決定木の最終出力の葉ごとの出力の和で表される。
損失関数は、各データ->全データの予測値の和をとって、

$$\begin{align*} L(\phi)^t &= \Sigma_i l(\^y_i^{t}, y_i^t) + \Sigma_k \Omega(f_k)\\ &= \Sigma_i l(\^y_i^{t-1}+f_t{x_i}, y_i^t) + \Sigma_k \Omega(f_k)\\ where \Omega(f) &= \gamma T + \frac{1}{2}\lambda||\omega||^2\\ \end{align*}$$

で表される。この損失関数の右辺第二項は正則化項である。
他方で、右辺第一項は損失関数の「勾配を計算する」部分で、以下に示すメトリックを基に微分可能な凸関数を定義する。（実際に利用するのはこの関数の一次微分および二次微分なので、明示的に$l$の値が明記されている文献が少ない。。）

損失関数

ランク学習に用いる損失関数は、主に3つある。
https://note.com/rosso_blog/n/n56b6dd55d6c4

Pointwise

分類や回帰問題と同様で、並び替えの順序の結果（順位）をそのまま値だと思って、その予測値と実現値との差を利用する方法である。今回欲しいのは順位なので、PointwiseだとTrue Positiveであっても損失関数の値が小さくならないことが起こり得る。

Pairwise

これはランク学習ならではで、二つの予測値の順序が二つの正解値の順序と一致していれば値が下がるようなメトリックが用意される。ChatGPTに聞くと、例えば以下のようなメトリックになるとのこと。

$$L_{pairwise} = \Sigma_{(i,j)\in P} log(1+exp(-|\^y_i-\^y_j|))$$

ここで$P$はクエリ内でラベルの順位が異なるデータペアの集合である。

Listwise

Pairwiseのように二つの順序ではなく、クエリ全体の順序の整合性を評価値とする方法である。

$$\begin{align*} L_{listwise} &= \Sigma_{i\in Q} P_i^{true}log{P_i}^{pred}\\ P_i^{pred} &= \frac{exp{(\^y_i)}}{\Sigma_{k\in Q} exp{(\^y_k)}}\\ \end{align*}$$

ここで$Q$はクエリ内の全てのデータの集合, $E$はエントロピーである。

実装するにはどうしたらいいか

LightGBMを利用

筆者は、LightGBMのGithubからレポジトリ (https://github.com/microsoft/LightGBM/tree/master/examples/lambdarank)
をクローンすることで環境を構築した。
まずはpip (or conda)でlightgbmをインストールし、その後gitをクローンした。おそらく順番はどちらでも大丈夫。

conda install -c conda-forge lightgbm
git clone --recursive https://github.com/microsoft/LightGBM.git

学習および推論は、以下で実行した。計算時間はすぐ終わる。
とりあえず動作することは確認したので、分析や応用の仕方は今後の課題とする。

cd LightGBM/expamples/lambdarank
lightgbm config=train.conf
lightgbm config=test.conf

これからどう応用していくか？

公営ギャンブルのようなものの予測に使ってみようか、というのもこの記事を書き始めたきっかけなので、それらへの利用可能性を検討したい。一般にランク学習に利用されるのは、Pairwiseのような手法だが、おそらく順序だけ合っていればいいか、というとそうではない場合ではないもある（経験上。。）