ランダムな予測値における ROC-AUC は0.5，では nDCG は?

先に結論

nDCG@all はどんな予測値やモデルであっても 1.0 に近づくので注意したほうが良さそうです．

疑問

機械学習モデルにおける予測値の評価にはさまざまな指標が用いられます．

RMSE
prec / recall / f1-score
negative log-likelihood

二値分類ではとくに ROC-AUC (Area Under the Receiver Operating Characteristic Curve)¹が用いられることが多いでしょう．

ランダムな予測値に対する ROC-AUC はその定義上からも 0.5 になることが知られています．これは非常に便利で，ROC-AUC の厳密な定義を知らない人でも「この予測結果はコイントスよりどれだけ優れているのか」がすぐに把握可能です． (ちなみに ROC-AUC については Quality Metrics in Recommender Systems: Do We Calculate Metrics Consistently? (RecSys 2021) に非常に興味深い話が複数掲載されているので，いつかまとめます．)

ところで，二値分類問題を「予測結果にもとづいて並び替えた時に，より真のラベルを持つものが先頭に来るように並んでいるか?」のようなランキング問題として捉えましょう．この場合は評価指標に nDCG (Normalized Discounted Cumulative Gain)²を用いることがしばしばあります(WWW2011³ や KDD2019⁴ など)．

(ここでは nDCG の定義は割愛します) さて，機械学習モデルを構築し予測値を得て nDCG で評価する時，「ランダムな予測値に対して nDCG はどのような値を取るのだろうか?」と疑問に思うのが自然でしょう．

実験

COLT の論文の数式を追うのは疲れるので，python のコードで再現しましょう．大まかな方針です．

N = 100, 200, ..., 100000 と変化させながら以下を繰り返す
- p を 0.1, 0.3, 0,5 で変化させながら以下を繰り返す
  - 以下を100回繰り返し，それぞれの nDCG の平均値を計算する
    - ランダムな値を N 個作り，予測値とする
    - N 個のうち，確率 p でランダムに 1 を，残りに 0 を振ってこれを正解ラベルとする
    - k = 1, 10, all で変化させ以下を繰り返す
      - nDCG@k(正解ラベル, 予測値, k) を評価する

from collections import defaultdict

import matplotlib.pyplot as plt
import numpy as np
from sklearn.metrics import ndcg_score
from tqdm import tqdm

# サンプルデータの生成
rng = np.random.default_rng(6162)

results = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: list())))

x_indices = []
top_ks = [1, 10, "all"]
probs = [0.1, 0.3, 0.5]
for n_samples in tqdm(range(1000, 100001, 1000), ascii=True):
    x_indices.append(n_samples)
    predicts = rng.random(n_samples)
    for p in probs:
        n_answers = int(n_samples * p)
        for _ in range(100):
            answers = np.zeros(n_samples, dtype=int)
            answers[:n_answers] = 1
            rng.shuffle(answers)
            for k in top_ks:
                _k = n_samples if k == "all" else k
                ndcg_at_k = ndcg_score([answers], [predicts], k=_k)
                results[p][k][n_samples].append(ndcg_at_k)

# show
for k in top_ks:
    labels = []
    values = []
    for p, h in results.items():
        _h = h[k]
        label = f"p={p}, ndcg@{k}"
        labels.append(label)
        vals = [np.average(_h[n]) for n in x_indices]
        values.append(vals)

    for value in values:
        plt.plot(x_indices, value)

    plt.legend(labels)
    plt.title(f"ndcg@{k}")

    plt.savefig(f"/tmp/hoge_{k}.png")
    plt.close()