この記事は何？
機械学習の応用例としてランキング予測があります．
ランキング予測の例としてウェブページランキングがあります．GoogleやYahoo!のような検索エンジンでは，ユーザーが入力したクエリに対して適合度の高い順にウェブページをランキングし，ランキング結果を提示します．
ランキング予測結果の評価指標として，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と呼びます）は次式で定義されます．
ここで，はランキング中の
番目の要素の適合度（レイティング）を表します．
は評価に用いる要素数を表します．検索エンジン等では
とすることが多いようです，ユーザーは上から10件までウェブページをポチポチするということでしょうか．
2つ目のDCGはC. Burgesら（2005）によって提案されました．彼らのDCG（この記事ではDCG2と呼びます）は次式で定義されます．
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を使いづらいですよね…このようなケースではどのように扱うのでしょうか…
