あなたの DCG (Discounted Cumulative Gain) 、間違ってませんか？ #機械学習

はじめに

コードレビューの際にランキング評価指標の DCG (Discounted Cumulative Gain) の実装ミスに出会いました。
これは実装時に参考にした記事に間違いがあったことが原因でした。
そこで試しに「DCG　実装」などで検索してみたところ、間違った実装例を記載している記事がそこそこ存在していることがわかりました。
評価指標をもとに改善を行っていくため、評価指標計算のミスは最終的な成果物の品質低下につながります。
今回はこのありがちで危険なミスについてまとめようと思います。

DCG とは

ランキングを評価するための指標のひとつです。
あるランキング (コンテンツのリスト) について、より上位のコンテンツで利得 (クリック etc.) が得られることをよしとする、といったものとなっています。

詳細な定義は以下のようなものとなっています。

DCG（減損累積利得、げんそんるいせきりとく、Discounted cumulative gain）は、ランキング品質の評価指標である。情報検索において、DCG はウェブ検索エンジンのアルゴリズムや情報検索に関連したアプリケーションの適合性に対する有用性を評価するために使用される。DCG は検索エンジンの検索結果に含まれる文書の適合性を段階的に評価することで、検索結果リストにおける文書の位置（順位）によって、その文書の有用性、すなわち利得を測定する。この利得は、結果リストの上位から下位に向かって累積され、下位の文書ごとに各結果までの利得が割り引かれる[1]。

DCG_p = \sum_{i=1}^p \frac{rel_i}{\log_2(i+1)} = rel_1 + \sum_{i=2}^p \frac{rel_i}{\log_2(i+1)}

cf. Wikipedia - DCG

よくあるミス

よくある実装ミスは以下のようなものとなっています。
実際に算出される DCG も記載しています。
ランキングの 1 番目をクリックした場合と 2 番目をクリックした場合で評価値が同じですが、これは違和感がありますよね。

import numpy as np


def calc_dcg(gains: list[float]):
    dcg = gains[0]
    for i in range(1, len(gains)):
        dcg += gains[i]/np.log2(i + 1)
    return dcg


# ランキングの 1 番目をクリックした場合の DCG を計算
gcg1 = calc_dcg([1.0, 0.0])
print(gcg1)
# -> 1.0
# ランキングの 2 番目をクリックした場合の DCG を計算
gcg2 = calc_dcg([0.0, 1.0])
print(gcg2)
# -> 1.0

正しい実装

正しい実装は以下のようなものとなっています。
間違った実装例で np.log2(i + 1) となっていた箇所が np.log2(i + 2) となっているのがポイントです。
こちらも実際に算出される DCG も記載しています。
こちらは「ランキングの 1 番目をクリックした場合の評価値」 > 「2 番目をクリックした場合の評価値」となっており、意図した通りの評価になっていそうですね。

import numpy as np


def calc_dcg(gains: list[float]):
    dcg = gains[0]
    for i in range(1, len(gains)):
        dcg += gains[i]/np.log2(i + 2)
    return dcg


# ランキングの 1 番目をクリックした場合の DCG を計算
gcg1 = calc_dcg([1.0, 0.0])
print(gcg1)
# -> 1.0
# ランキングの 2 番目をクリックした場合の DCG を計算
gcg2 = calc_dcg([0.0, 1.0])
print(gcg2)
# -> 0.6309297535714575

なぜこのミスが起こるのか

主に 2 つあるのかと思います。
まず 1 つは、数式が 1 オリジンなのに対して実装時のリストのインデックスが 0 オリジンである、というところではないでしょうか。
これは今回に限らずやりがちなミスなので気をつけたいですね。
もう 1 つはそもそも参照している定義式が間違っている、というのがあるかと思います。
記事いくつか眺めていたところ、以下のように DCG を定義している場合がありました。

DCG_p = rel_1 + \sum_{i=2}^p \frac{rel_i}{\log_2(i)}

この数式をもとにするとやはり上で紹介した間違った実装になります。

おわりに

ランキング評価指標としてよく使用される DCG について、ありがちな実装ミスを紹介しました。
評価指標の間違いは最終的な成果物の品質低下につながるので注意したいですね。