DSOC研究員の吉村です. 年末年始の連休で本をたくさん読むぞと意気込んだにも関わらず, 2.5冊しか読めなかった悔しさに苛まれております.
さて, 今回も前回に引き続き評価指標についてまとめていきます. 特に, ランキング学習の出力結果を評価する際に用いられる指標について見ていきましょう. マルチラベル分類の文脈における, ランキング学習の出力結果の評価指標の一部については, 前回の記事で紹介しておりますので, そちらも読んでいただけると嬉しいです.
ランキング学習の精度評価
ランキング学習とは, 対象物の順序を予測するように学習する問題です. マルチラベル分類の予測時に各ラベルの信頼度を計算するようなモデルを用いる場合には, その信頼度の大小によって順位付けができるため, マルチラベル分類とも関係の深い問題設定です. そのため, ランキング学習の評価指標がマルチラベル分類の予測結果の評価に使われることも度々あります.
今回は, ランキング学習の評価指標として下記の 7 個を紹介します.
- Discounted Cumulative Gain (DCG) [*1, *2]
- normalized Discounted Cumulative Gain (nDCG)
- Mean Reciprocal Rank (MRR)
- Kendall rank correlation coefficient, Kendall's
- Spearman's rank correlation coefficient, Spearman's
- Yandex's pFound [*3, *4]
- Expected Reciprocal Rank (ERR) [*5]
ただし, 今回はランキング学習の評価指標という意味の中に, なんらかのモデルの出力として得られるランキング結果の性能を評価するというかなり広義の意味を含めています. そのため, ここで紹介する各種指標は何が与えられているか (e.g. 真のラベル, 真のランキングなど) によって, 使えるものが異なることに注意してください. また, ランキングを扱うという点で Information Retrieval (IR) の色が強いため, 今回は並べ換える対象のことをドキュメントと呼ぶことにします. この部分は適宜, 並べ換えるアイテムとして読み替えてもらえるといいかと思います.
Discounted Cumulative Gain (DCG)
DCG とひとことで言っても, その定義は二つあることが知られています. 一つ目は, 下記の式で与えられます.
$$\text{DCG}_p=\sum_{i=1}^p\frac{\text{rel}_i}{\log_2(i+1)}$$
ただし, はあるドキュメントの順位を表し,
は
番目のドキュメントの関連度 (グレード) を表します. この一つ目の定義は, ランキングに現れるドキュメントの関連度を順位の対数で割り引いている (Discounted) ものであると言えます.
もう一つの定義は, 下記の式で与えられます.
$$\text{DCG}_p=\sum_{i=1}^p\frac{2^{\text{rel}_i}-1}{\log_2(i+1)}$$
こちらの式は, ドキュメントの関連度が指数的に影響するため, 関連度に対して少し敏感であることが見て取れます.
これら二つの定義は, 関連度が二値の時に一致します.
normalized Discounted Cumulative Gain (nDCG)
nDCG はその名の通り, DCG を正規化 (normalize) したものです. これにより, 出力の長さの違うクエリに対する評価結果などを同じ土俵で評価することができます. nDCG は次の式で与えられます.
$$\text{nDCG}_p=\frac{\text{DCG}_p}{\text{IDCG}_p}$$
ただし, は順位
での理想的な (Ideal) DCG を表しており, 関連度の大きい順に並べたドキュメントに対する
を表します.
Mean Reciprocal Rank (MRR)
MRR は, 複数のクエリとそれに対応するランキングが与えられているときに, そのランキングを与える検索アルゴリズムの性能を評価する指標です. まず, Reciprocal Rank (RR, 日本語で逆順位) とは, そのままの意味で, 順位の逆数のことを表します. つまり, RR の値は, 順位が 2 位であれば 1/2, 5 位であれば 1/5 ということになります. ここで, クエリ集合を とすると, MRR は次の式で書けます.
$$\text{MRR}=\frac{1}{|Q|}\sum_{q \in Q}\frac{1}{\text{Rank}_q}$$
ただし, は,
番目のクエリに対して得られるランキングのうち, 最初に出てくるクエリに関連するドキュメントの順位を表します. 例えば, 「果物」というクエリで検索した結果, 得られたランキングが 1 位: 名刺, 2 位: りんご, 3 位: バナナの場合には, 当然関連するのはりんごとバナナで, そのうち上位のりんごの順位は 2 位なので
となります.
Kendall rank correlation coefficient, Kendall's 
日本語では, ケンドールの順位相関係数と呼ばれます. この指標は, 二つのランキングがどの程度相関しているかを見るための指標です. Kendall's は, 比較する二つのランキングの長さ (含まれるドキュメントの数) が等しい必要があります. 事例
の真の順位と予測結果の順位をそれぞれ
,
とすると, Kendall's
は次式で表されます.
$$\tau = \frac{2(\sum_{s < t} \mathbb{I}[(y_s - y_t)(\hat{y}_s - \hat{y}_t) > 0] - \sum_{s < t} \mathbb{I}[(y_s - y_t)(\hat{y}_s - \hat{y}_t) < 0])}{N(N-1)}$$
ただし, ] は指示関数を表し, 引数の論理式が真であれば 1 を, 偽であれば 0 をとります. したがって,
] の部分は, 真の順位と予測結果の順位との間の順位関係が一致する件数を表し,
] の部分は, 順位関係が不一致する件数を表しています.
Spearman's rank correlation coefficient, Spearman's 
日本語では, スピアマンの順位相関係数と呼ばれます. この指標も Kendall's と同様に, 二つのランキングがどの程度相関しているかを見るための指標です. Spearman's
でも, 比較する二つのランキングの長さ (含まれるドキュメントの数) が等しい必要があります. 事例
の真の順位と予測結果の順位をそれぞれ
,
とすると, Spearman's
は次式で与えられます.
$$\rho=1 - \frac{6\sum_{i=1}^N(y_i - \hat{y}_i)^2}{N(N^2-1)}$$
は -1 から 1 の間をとる値で, 1に近いほど相関していることを表しています. 上記の式はそれぞれのランキングのなかに同順位がない, または, 非常に少ない場合を想定した指標です. 同順位の数が多い場合にはそれを考慮した spearman's
が別で提案されています.
Yandex's pFound
Yandex とは, ロシアの検索エンジンサイトを運営している企業です. pFound は, 答え (目当ての検索結果) が見つかる確率を表します. したがって, 検索結果を出力するランキングアルゴリズムに対して, この値が高ければ高いほどユーザのニーズに合った出力を返すことができているということになります. 式は下記のように定義されています.
$$\text{pFound}=\sum_{r=1}^n(1 - \text{pBreak})^{r-1}\cdot \text{pRel}_r \prod_{i=1}^{r-1}(1-\text{pRel}_i)$$
ただし, は順序をつけるドキュメントの総数を, pBreak は各位置において (目当ての検索結果を探すのを) 放棄する確率を, そして, pRel
は位置
番目のドキュメントがクエリに関連する確率を表します. また, pBreak は, 0.15 と設定され, pRel はクエリとドキュメントのペア (query, document) に対して予めつけておいたラベルごとに値を割り当てます. [A. Gulin et. al, 2009] では, 'vital', 'notrelevant', 'cantbejudged' の三つのラベルに対して, それぞれ 0.4, 0, 0 を割り当てているようです.
Expected Reciprocal Rank (ERR)
ERR は, それまでの評価指標で仮定されていたユーザ行動のモデル (position model) が, 実際のユーザの行動の傾向を反映していないことを問題視して提案されました. ERR を提案した [O. Chapelle et.al., 2009] では, 新たなユーザ行動のモデルとして cascade model を提案しています. 従来の position model ではユーザの行動は, 関連のあるドキュメントの順位のみに依存すると考えていたのに対して, cascade model では, 関連のあるドキュメントの順位だけではなく, そのドキュメントより順位が上の他のドキュメントにも依存してユーザの行動が決まると考えます. この cascade model を仮定して提案されたのが, 下記の ERR です.
$$\text{ERR}=\sum_{r=1}^n\frac{1}{r}\prod_{i=1}^{r-1}(1 - R_i)R_r$$
ここで, はドキュメント総数 (または, ランキングをつけたドキュメントの総数) を表し,
はランキングが
位のドキュメントの関連度に応じて決められる、ユーザがそのドキュメントに満足する確率を表します.
の決め方は様々あるのですが, [O. Chapelle et.al., 2009] では, 一つの決め方として,
を
番目のドキュメントのグレードとした時に
$$R_i=\mathcal{R}(g_i)=\frac{2^{g_i}-1}{2^{g_{\text{max}}}}$$
とすることを提案しています.
ERR は見てわかるように, Yandex's pFound と似たような評価指標であると位置付けられています.
まとめ
今回は, ランキング学習とランキングが出力となる場合の評価指標について見ていきました. 前回紹介した と MAP の 2 種類と合わせて, 9種類の関連する評価指標をこれまでに確認し, いくつか似通っている指標があるものの, その多くが少しずつ使う場面が異なることが伝わっていれば嬉しいです.
さて, 今回までで 5 回評価指標について見てきました. この直近 5 回の連載によって, 私もモデルの評価の際に気をつける点が少しずつわかってきました. その時々で, 適切かつ (測定したいものを測定できるという意味で) 正確な評価指標を使って行くように心がけようと思います. 次回からはまた別のテーマで書いていきますので, 引き続きお付き合いください.
▼この連載における機械学習のモデルの評価方法についての記事
【ML Tech RPT. 】第10回 機械学習のモデルの評価方法 (Evaluation Metrics) を学ぶ (1) - Sansan Builders Box
【ML Tech RPT. 】第11回 機械学習のモデルの評価方法 (Evaluation Metrics) を学ぶ (2) - Sansan Builders Box
【ML Tech RPT. 】第12回 機械学習のモデルの評価方法 (Evaluation Metrics) を学ぶ (3) - Sansan Builders Box
【ML Tech RPT. 】第13回 機械学習のモデルの評価方法 (Evaluation Metrics) を学ぶ (4) - Sansan Builders Box
*1:K. Järvelin, and J. Kekäläinen, "Cumulated gain-based evaluation of IR techniques," in TOIS, 2002.
*2:C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender, "Learning to rank using gradient descent," in ICML, 2005.
*3:A. Gulin, P. Karpovich, D. Raskovalov, and I. Segalovich, "Yandex at romip’2009: Optimization of ranking algorithms by machine learning methods," in ROMIP, 2009.
*4:I. Segalovich, "Machine learning in search quality at yandex," in SIGIR, 2010.
*5:O. Chapelle, D. Metzler, Y. Zhang, and P. Grinspan, "Expected Reciprocal Rank for Graded Relevance", in CIKM, 2009
