読者です 読者をやめる 読者になる 読者になる

人間だったら考えて

考えて考えて人間だったら考えて

予測ランキング評価指標:NDCGの2つの定義と特徴の比較

この記事は何?

機械学習の応用例としてランキング予測があります.
ランキング予測の例としてウェブページランキングがあります.GoogleYahoo!のような検索エンジンでは,ユーザーが入力したクエリに対して適合度の高い順にウェブページをランキングし,ランキング結果を提示します.

ランキング予測結果の評価指標として,Normalized Discounted Cumulative Gain (NDCG) が広く使われています.NDCGは0から1の値を取り,1に近いほど正しいランキング予測結果であることを表します.

実はNDCGには2つの定義があります.この記事ではNDCGの2つの定義を紹介し,それぞれの特徴を比較します.

NDCGの定義

NDCGはDiscounted Cumulative Gain (DCG) を正規化した値です.
具体的には,予測ランキングを用いて得られたDCGを,真の正しいランキングを用いて得られるDCGで割ることで正規化します.
NDCGには2つの定義がありますが,どちらも正規化する方法は同じです.異なる点はDCGの計算方法であるため,2つのDCGの定義を紹介します.

1つ目のDCGはK. Jarvelinら(2002)によって提案されました.彼らのDCG(この記事ではDCG1と呼びます)は次式で定義されます.

 \textrm{DCG1}=\textrm{rel}_1 + \sum_{i=2}^{k}\frac{\textrm{rel}_i}{\log_2 i}

ここで, \textrm{rel}_iはランキング中の i番目の要素の適合度(レイティング)を表します. kは評価に用いる要素数を表します.検索エンジン等では k=10とすることが多いようです,ユーザーは上から10件までウェブページをポチポチするということでしょうか.

2つ目のDCGはC. Burgesら(2005)によって提案されました.彼らのDCG(この記事ではDCG2と呼びます)は次式で定義されます.

 \textrm{DCG2}=\sum_{i=1}^{k}\frac{2^{\textrm{rel}_i} - 1}{\log_2 (i+1)}

DCG2では適合度を2のべき乗で扱う点がDCG1と異なります.

計算例

いくつかのランキング例を使って,2つのNDCGの結果を比べていきます.

予測ランキングが正しいランキングのとき

予測順位 1 2 3 4 5 6 7 8 9 10
適合度 5 3 3 3 3 3 0 0 0 0

このとき,2つのNDCGは

NDCG1 1.00
NDCG2 1.00

となります.正しいランキング予測結果のときはNDCGはどちらも1になります.

そこそこの適合度の要素に対する予測は成功したが,高い適合度の要素に対する予測は失敗したとき

予測順位 1 2 3 4 5 6 7 8 9 10
適合度 3 3 3 3 3 0 0 0 0 5

このとき,2つのNDCGは

NDCG1 0.88
NDCG2 0.63

となります.NDCG1の方が高い値となります.

高い適合度の要素に対する予測は成功したが,そこそこの適合度の要素に対する予測は失敗したとき

予測順位 1 2 3 4 5 6 7 8 9 10
適合度 5 0 0 0 0 3 3 3 3 3

このとき,2つのNDCGは

NDCG1 0.73
NDCG2 0.89

となります.NDCG2の方が高い値となります.

2つのNDCGの特徴の違い

上の計算例で見たように,同じ予測ランキングでもNDCG1とNDCG2とで結果が変わることが分かりました.
NDCG2は適合度を2のべき乗で扱っているため,適合度の高い要素を強く重み付けして評価することになります.そのため,適合度5の要素が上位に来る予測ランキングではNDCG2の方が高い値となった一方で,適合度5の要素の予測を失敗してしまった予測ランキングではNDCG2の方が低い値となったと考えられます.

そこそこの適合度でも良いからたくさんのヒットが欲しいケースではNDCG1を使って,どれか1つでも良いから高い適合度の要素を当てたいケースではNDCG2を使うのが良いと言えるでしょう.

ソースコード

実験に使ったソースコードを貼っておきます(jupyter notebookベタ貼り).

# coding: utf-8

# In[1]:

import numpy as np


# In[2]:

def ndcg(y_true, y_pred, k=None, powered=False):
    def dcg(scores, k=None, powered=False):
        if k is None:
            k = scores.shape[0]
        if not powered:
            ret = scores[0]
            for i in range(1, k):
                ret += scores[i] / np.log2(i + 1)
            return ret
        else:
            ret = 0
            for i in range(k):
                ret += (2 ** scores[i] - 1) / np.log2(i + 2)
            return ret
    
    ideal_sorted_scores = np.sort(y_true)[::-1]
    ideal_dcg_score = dcg(ideal_sorted_scores, k=k, powered=powered)
    
    pred_sorted_ind = np.argsort(y_pred)[::-1]
    pred_sorted_scores = y_true[pred_sorted_ind]
    dcg_score = dcg(pred_sorted_scores, k=k, powered=powered)
    
    return dcg_score / ideal_dcg_score

def ndcg1(y_true, y_pred, k=None):
    return ndcg(y_true, y_pred, k=k, powered=False)

def ndcg2(y_true, y_pred, k=None):
    return ndcg(y_true, y_pred, k=k, powered=True)


# In[3]:

y_true = np.array([5, 3, 3, 3, 3, 3, 0, 0, 0, 0])


# In[4]:

y_pred = np.array([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
print("ndcg1", ndcg1(y_true, y_pred))
print("ndcg2", ndcg2(y_true, y_pred))


# In[5]:

# 5, 0, 0, 0, 0, 3, 3, 3, 3, 3
y_pred = np.array([10, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print("ndcg1", ndcg1(y_true, y_pred))
print("ndcg2", ndcg2(y_true, y_pred))


# In[6]:

# 3, 3, 3, 3, 3, 0, 0, 0, 0, 5
y_pred = np.array([1, 10, 9, 8, 7, 6, 5, 4, 3, 2])
print("ndcg1", ndcg1(y_true, y_pred))
print("ndcg2", ndcg2(y_true, y_pred))

その他

適合度が10とか100みたいに大きな値のケースではNDCG2を使いづらいですよね…このようなケースではどのように扱うのでしょうか…

参考文献

  • Järvelin, Kalervo, et al. "Cumulated gain-based evaluation of IR techniques." ACM Transactions on Information Systems (TOIS) 20.4 (2002): 422-446.
  • Burges, Chris, et al. "Learning to rank using gradient descent." Proceedings of the 22nd International Conference on Machine Learning. ACM, 2005.