ランク学習(Learning to Rank)で順位を予測する（実装で学ぶ機械学習シリーズ）

2024年1月18日 12:57

こんにちは。株式会社Rosso、AI部です。競馬の着順順位、検索エンジンの検索順位、選挙の投票数順位など私達の身の回りには、順位、ランキングが関わる多くの事象が存在しています。今回は、順位、ランキングを機械学習で扱うランク学習をご紹介します。また、xgboostに付属しているランク学習のコードを例にして、ランク学習の簡単な実装を行ってみます。最後に通常の機械学習とランク学習の違いについて、簡単に検証を行っていきます。

ランク学習とは

ランク学習(Learning to Rank)とは、競馬の着順予測、検索エンジンの検索ランキングなどの順序そのものを目的変数とした場合に用いられる機械学習の手法のことです。
通常の機械学習と違う点としては、通常の機械学習は、予測値と実現値の誤差に着目する（基数的アプローチ）のに対し、ランク学習では、予測結果の順序と実現結果の順序が合っている（序数的アプローチ）かどうかに着目する点が挙げられます。

ランク学習の特徴

上記のように、ランク学習は予測結果の順序と予測結果の順序に着目するため、損失関数は順序を最小化する指標が使用されます。また、評価指標も予測値と実現値の誤差よりも予測値と実現値の順序の整合性を評価する指標を使用します。損失関数や評価指標で使われる指標は下記の３つの種類があります。

ポイントワイズ（pointwise)
ペアワイズ(pairwise)
リストワイズ(listwise)

ポイントワイズ(pointwise)

従来の機械学習モデルで使われる方法です。この方法では、順位の値をそのまま推定し、予測値と実現値の誤差を評価します。具体的な手法としては、MSEやMAEがこの方法に当てはまります。また、ポイントワイズを指標で用いられる際は、順序を考慮せず、あくまで、個々の予測値と実現値から損失を定義します。

ペアワイズ（pairwise)

ペアワイズとは、データから2つの予測値(ペア)をそれぞれ抽出し、その2つの予測値の順序が、実現値の順序と一致しているかどうかを全てのペアに対して計算することによって、損失を定義する方法です。この手法には、スピアマンの順位相関係数やケンドールの順位相関係数などが当てはまります。また、ペアワイズで損失関数を定義したランク学習モデルも多数存在します。(例: RankNet、Rank SVM、LambdaRankなど)
例えば、RankNetでは、Xj>xiとなるとき（Xjがxiより順位が高い）ときの確率をPijと定義しクロスエントロピーによる損失関数を下記のように定義しています。

ペアワイズの問題点としては、各ペア同士の順序の一致しか考慮していないため、順位ごとの価値が無視されるという点が挙げられます。例えば、競馬の着順予測では、予測結果の正答が上位ならばその価値が高くなり、下位の予測結果は価値が低いとされます。一等の馬を正確に予測することと最下位の馬を正確に予測することでは、前者の方が明らかに価値が高いですが、ペアワイズの手法ではこれらの価値を同等に扱ってしまいます。

リストワイズ(listwise)

リストワイズ(listwise)とは、順序全体の整合性に着目することで、損失を評価する方法です。この手法では、順位ごとの価値も評価に含めることができる利点があります。
例えば、リストワイズの指標であるnDCG(normalized Discounted Cumulative Gain)では、予測結果の順序に基づいたDCG(normalized Discounted Cumulative Gain)を真の順序に基づいたDCG(normalized Discounted Cumulative Gain)で割った値として定義されます。
DCG(normalized Discounted Cumulative Gain)は、予測結果などのスコアを順位に対数を取って重みづけし、総和を計算したものです。
スコアをr、順位をiとすると、DCGとnDCGは以下の式で表されます。

リストワイズを使用したランク学習手法としては、ListNetやAdaRankなどが挙げられます。

注意点

リストワイズ、ペアワイズを用いたアプローチでは、あくまで順序の予測の精度を高めることだけにフォーカスをしているので、リストワイズ、ペアワイズを用いたランク学習手法では、MAE,MSEといった指標で予測値と実現値の誤差を計算しても大きな誤差が計算されてしまいます。
リストワイズ、ペアワイズを損失関数に用いているランク学習手法では、評価指標もあくまで、リストワイズ、ペアワイズに基づく指標を使用する必要があります。

ランク学習をお手軽に試す

実は、xgboostでは、xgboostをランク学習に適用したモデルが使用可能です。
さらに、demoもきちんと用意されており、mq2008というランキング学習用のデータセットを使って、ランキング学習のサンプル例が示されています。
https://github.com/dmlc/xgboost/tree/master/demo/rank
この中では、通常のxgboostモデルと同様、trainデータ、validationデータ,testデータをDMatrix型に変換し、パラメータのobjectiveに'rank:ndcg'を使用することで、ndcgの指標を用いたランク学習を行っています。
なお、XGBoostでは、パラメータのobjectiveに'rank:ndcg'に指定したとき、pairwise的なアプローチをとるLambdaMARTモデルをベースとしたランク学習を行うことができます。
https://xgboost.readthedocs.io/en/latest/tutorials/learning_to_rank.html

train_dmatrix = DMatrix(x_train, y_train)
valid_dmatrix = DMatrix(x_valid, y_valid)
test_dmatrix = DMatrix(x_test)

train_dmatrix.set_group(group_train)
valid_dmatrix.set_group(group_valid)

params = {'objective': 'rank:ndcg', 'eta': 0.1, 'gamma': 1.0,
          'min_child_weight': 0.1, 'max_depth': 6}
xgb_model = xgb.train(params, train_dmatrix, num_boost_round=4,
                      evals=[(valid_dmatrix, 'validation')])

また、上記のdemoを改良してpointwiseとpairwise手法の比較検証のコードを作成しました。注意点として、コードの実行の際には、必要なデータをダウンロードするため、xgboostのランク学習のdemo内のwgetdata.shを実行することが必要になります。
上記のコードで通常のxgboostでmq2008を学習させたときの、テストデータのmean_absolute_error、ndcgの各指標は以下の通りとなります。
ここで、k3_ndcg,k5_ndcg,k10_ndcgはそれぞれランキング上位３位、上位５位、１０位だけのデータをつかったときのnDCGを表しています。

mean_absolute_error 0.3400064352056042
k3_ndcg 0.6173196815056892
k5_ndcg 0.584790051318404
k10_ndcg 0.5228245040457891
k20_ndcg 0.46324198199775796
k30_ndcg 0.5157403025796785

一方、ランク学習のxgboostでmq2008を学習させたときの、テストデータのmean_absolute_error、ndcgの各指標は以下の通りとなります。

mean_absolute_error 0.9022516827265912
k3_ndcg 0.6173196815056892
k5_ndcg 0.5117558763970508
k10_ndcg 0.5786382879785582
k20_ndcg 0.5552646332918211
k30_ndcg 0.5086219888231489

両者のNdcgを比較すると、k3では両者で変わらず、k5、k30での値は通常の機械学習の方が高いが、k10,k20ではランク学習の方が高い値となっています。また、mean_absolute_errorは、ポイントワイズ的なアプローチである通常の機械学習の方が、ランク学習より低いといった結果となっています。

#!/usr/bin/python
from sklearn.datasets import load_svmlight_file
from sklearn.metrics import ndcg_score
import xgboost as xgb
from sklearn.metrics import mean_absolute_error
#  This script demonstrate how to do ranking with XGBRanker
x_train, y_train = load_svmlight_file("mq2008.train")
x_valid, y_valid = load_svmlight_file("mq2008.vali")
x_test, y_test = load_svmlight_file("mq2008.test")

group_train = []
with open("mq2008.train.group", "r") as f:
    data = f.readlines()
    for line in data:
        group_train.append(int(line.split("\n")[0]))

group_valid = []
with open("mq2008.vali.group", "r") as f:
    data = f.readlines()
    for line in data:
        group_valid.append(int(line.split("\n")[0]))

group_test = []
with open("mq2008.test.group", "r") as f:
    data = f.readlines()
    for line in data:
        group_test.append(int(line.split("\n")[0]))

#通常のxgboost(pointwise)での結果
train_data = xgb.DMatrix(x_train, label=y_train)
eval_data = xgb.DMatrix(x_test, label=y_test)
xgb_params = {
    "objective": "reg:squarederror",
    'eval_metric': "mae"
    }
evals = [(train_data, 'train'), (eval_data, 'eval')]
evals_result = {}
gbm = xgb.train(
    xgb_params,
    train_data,
    num_boost_round=100,
    early_stopping_rounds=10,
    evals=evals,
    evals_result=evals_result
    )
preds = gbm.predict(eval_data)
r2 = mean_absolute_error(y_test, preds)
print("normal xgboost point wise : mean_absolute_error rank",r2)
print("k3_ndcg",ndcg_score([y_test],[preds],k=3))
print("k5_ndcg",ndcg_score([y_test],[preds],k=5))
print("k10_ndcg",ndcg_score([y_test],[preds],k=10))
print("k20_ndcg",ndcg_score([y_test],[preds],k=20))
print("k30_ndcg",ndcg_score([y_test],[preds],k=30))
#ランク学習のxgboost(pairwise)での結果
params = {'objective': 'rank:pairwise', 'learning_rate': 0.1,
          'gamma': 1.0, 'min_child_weight': 0.1,
          'max_depth': 6, 'n_estimators': 40}
model = xgb.sklearn.XGBRanker(**params)
model.fit(x_train, y_train, group_train, verbose=True,
          eval_set=[(x_valid, y_valid)], eval_group=[group_valid])
pred = model.predict(x_test)
mae = mean_absolute_error(y_test, pred)
#pairwiseではpointwiseと比べて、maeはそこまで低くない
print("ranking xgboost pairwise : mean_absolute_error rank",mae)
print("k3_ndcg",ndcg_score([y_test],[pred],k=3))
print("k5_ndcg",ndcg_score([y_test],[pred],k=5))
print("k10_ndcg",ndcg_score([y_test],[pred],k=10))
print("k20_ndcg",ndcg_score([y_test],[pred],k=20))
print("k30_ndcg",ndcg_score([y_test],[pred],k=30))

まとめ

以上、ランク学習の紹介と通常の機械学習とランク学習の違いを簡単に検証してみました。予測ではなく、順序を対象とするランク学習では、ポイントワイズであるMAEの指標は通常の機械学習の結果より悪い結果になっていました。また、リストワイズであるNdcgでは、対象の順位によって、通常の機械学習の方が性能がいい場合と、ランク学習の方が性能がいい場合があるといった結果になりました。今回の結果を踏まえると、順序予測においては、検証で使用したランク学習モデルでは、常に通常の機械学習より性能がいいとは言えないものの、状況によっては、通常の機械学習よりいい場合もあるといった形でしょうか。この記事を読んで皆様のランク学習に関する知見が深まれば幸いです。

参考文献

https://www.szdrblog.info/entry/2018/12/04/010611
https://www.slideshare.net/sleepy_yoshi/dsirnlp1

＼株式会社Rossoでは、AI・データ分析に携われる人を募集してます／