ランク学習と検索結果の精度評価指標

この記事はランク学習（Learning to Rank） Advent Calendar 2018 - Adventarの4本目の記事です。

この記事は何？

前回の記事で、LightGBMを用いたランク学習によるランキングモデルを作りました。
www.szdrblog.info

機械学習モデルを作ったら、次にやるべきことはそのモデルの予測精度を確認することです。
*1
この記事では、ランク学習の予測精度を測る指標として、Mean Reciprocal Rank (MRR)・Mean Average Precision (MAP)・Normalized DCG (NDCG) を紹介します。*2

…といっても、この辺りの予測精度の話は非常に有名なので、解説記事はたくさん出てきます。なのでこの記事では、これらの予測精度にまつわる問題点もちょっとだけ紹介しようと思います。

ラベルが0 or 1の2値のとき

データセットに含まれる各文書のラベルが0 or 1の2値を取る場合を考えます。

例えば、「検索キーワード」と「文書」の各組に対して、人が見て「この検索キーワードなら、この文書は検索結果に現れて良い」と判断したら○、ダメなら×とラベルを付与していくことが考えられます。

人手による処理は非常に大変なので、ユーザーの行動ログが得られる場合は、例えば「検索キーワード」と「文書」の各組に対して、ユーザーがその文書へのリンクをクリックしたら○、クリックしなかったら×とラベルを付与することもできます。

ラベルが0 or 1の2値のときは、Mean Reciprocal Rank (MRR)・Mean Average Precision (MAP) による評価を行うことができます。

Mean Reciprocal Rank (MRR)

まずReciprocal Rank (RR) を紹介します。
…と言っても非常に単純な評価指標で、「検索結果を上から見ていって最初に○(=1)の文書が現れた順位が $r$ のとき、 $\mathrm{RR}=\frac{1}{r}$ 」と定義します。

例えば以下のケースでは、検索結果の2位に最初の $y_{q,d}=1$ の文書が現れるため、 $\mathrm{RR}=\frac{1}{2}$ となります。
f:id:sz_dr:20181205233131p:plain:w400

Reciprocal Rankは最初に○(=1)の文書が現れた順位しか気にしないので、他の○の文書の順位はReciprocal Rankの値に影響しません。
なので、以下のような奇妙な評価を行うときがあります。

順位	1	2	3	4	5	6	7	8	9	10
ランキングモデルAで並べた際の文書のラベル	1	0	0	0	0	1	1	1	1	1
ランキングモデルBで並べた際の文書のラベル	1	1	1	1	1	0	0	0	0	0

ランキングモデルBはAよりも○(=1)の文書を検索結果上位に集めているので、直感的にはランキングモデルBはAよりも優れているはずです。
一方で、どちらのランキングモデルも1位に○(=1)の文書が現れているため、共にRR=1となってしまいます。

もちろん、検索サービスによってはReciprocal Rankによる評価が正しいケースもあるとは思いますが、本当にReciprocal Rankで評価して良いのかは検討した方が良いです。

さて、Mean Reciprocal Rank (MRR) ですが、これは単純に「検索キーワード」毎に求められるReciprocal Rankの値を平均した値となります。

Mean Average Precision (MAP)

「Precision@k」→「Average Precision」→「Mean Average Precision」の順に紹介していきます。

Precision@kは、「検索結果のk番目まで見たときのPrecision」として定義します。

例えば以下のケースでは、

検索結果の1番目まで見たとき、○(=1)の文書の数は0なので、Precision@1=0
検索結果の2番目まで見たとき、○(=1)の文書の数は1なので、Precision@2=1/2
検索結果の3番目まで見たとき、○(=1)の文書の数は1なので、Precision@3=1/3
検索結果の4番目まで見たとき、○(=1)の文書の数は2なので、Precision@4=1/2

となります。

f:id:sz_dr:20181206000434p:plain:w400

次にAverage Precisionですが、「○(=1)の文書が現れる各順位について、Precision@kの値の平均を取る」として定義します。

例えば先ほどのケースですが、○(=1)の文書は検索結果の2番目と4番目に現れます。
そこで、Average PrecisonはPrecision@2とPrecision@4の平均である $(1/2 + 1/2)/2 = 1/2$ となります。

最後にMean Average Precision (MAP) ですが、これは単純に「検索キーワード」毎に求められるAverage Precisionの値を平均した値となります。

Mean Average Precisionの問題点について触れておきます。
"Some Common Mistakes In IR Evaluation, And How They Can Be Avoided", N. Fuhr, 2017で、Mean Average Precisionは以下のユーザー行動を仮定していると言っています。*3

1. users stop only after a relevant document, and
2. the probability of stopping is the same for all relevant ranks.

1つ目の仮定ですが、これはAverage Precisionが○(=1)の文書が現れる各順位のみで平均を取っていることに対応します。論文からは、1つ目の仮定についてはそこまで大きな問題では無さそうだと読み取れます。

While the first assumption might be approximately true in some applications (but how would users know when they have reached the last relevant document?)

問題は2つ目の仮定で、これはAverage Precisionが重みを付けず単純にPrecision@kの平均を取っていることに対応します。
一般的に、ユーザーは検索結果上位で目的の文書を発見したら、検索結果の下まで確認しにいく確率は小さくなります。にもかかわらず、Average Precisionは全てのPrecision@kを平等に扱って平均を取っています。

…じゃあ、どうしたらいいんだよという話ですが、論文中ではRank Biased Precision (RBP) を提案しています。*4

ラベルが多値のとき

データセットに含まれる各文書が「Perfect(4), Excellent(3), Good(2), Fair(1), Bad(0)」のように、多値を取る場合を考えます。

こちらも人手でラベルを振っても良いですし、ユーザーの行動ログを使ってラベルを振ることも考えられます（例えば、ユーザーの各文書に対する滞在時間からラベルを求めるなど）。

ラベルが多値のときは、まず出てくる評価指標としてNormalized Discounted Cumulative Gain (NDCG) があります。

Normalized Discounted Cumulative Gain (NDCG)

「Discounted Cumulative Gain (DCG)」→「Normalized Discounted Cumulative Gain (NDCG)」の順に紹介します。

高い値のラベルが検索結果上位に現れると嬉しいという気持ちから、DCG@kは以下のように形式的に定義されます。
$\mathrm{DCG}@k(\pi, l)=\sum_{j=1}^{k}G(l_{\pi^{-1}(j)})\eta(j)$

表記が入り組んでいてややこしいですが、 $\pi^{-1}(j)$ は検索結果 $j$ 番目の文書のIDを表し、 $l$ は各文書のIDに対するラベルのリストを表しています。

また、 $G(z)$ は「ラベル $z$ の文書の得点」を表し、 $2^z-1$ として計算されることが多いです。

Perfect(4)では $2^4-1=15$ 点
Excellent(3)では $2^3-1=7$ 点
Good(2)では $2^2-1=3$ 点
Fair(1)では $2^1-1=1$ 点
Bad(0)では $2^0-1=0$ 点

というように扱います。

$\eta(j)$ ですが、検索結果の下の方はあまり重要でないという気持ちから、 $G(z)$ で計算された得点に与えるペナルティを表しています。
一般的には順位 $j$ の文書について $\eta(j)=\frac{1}{\log(j+1)}$ と計算されることが多いです。

…数式で説明しても伝わりにくいと思うので、例を出して紹介します。

ランキングモデルのスコア順に文書を並べたとき、ラベルは $(2,4,0,1)$ となったとします。

f:id:sz_dr:20181206005822p:plain:w400

$G(z)$ と $\eta(j)$ を各文書で計算し、 $\mathrm{DCG}@4=12.9$ と求めることができました。

次にNormalized Discounted Cumulative Gain (NDCG) ですが、上で求めたDCGが0~1の間に収まるように正規化したスコアになります。
正規化ですが、文書を理想的に並べた際に得られるDCG（ideal DCG）で割ってあげます。

例えば上の例ですが、文書を理想的に並べたとき、ラベルは $(4,2,1,0)$ となります。
この元でDCGを計算すると、 $\mathrm{ideal\ DCG}=17.4$ が得られます。

さて、ランキングモデルのスコア順に並べた際には、 $\mathrm{DCG}=12.9$ でした。
なので、NDCGは $\frac{12.9}{17.4}=0.74$ と求められます。

さて、NDCGの厄介な点ですが、正直そこまでNDCGに課題は存在しないんじゃないかと思っています。
個人的に気になる点として、 $G(z)$ と $\eta(j)$ の任意性がありますが、上の定義で計算されることがほとんどです。
このあたりの話は、以前別の記事でも紹介しましたので、そちらをご覧ください。

www.szdrblog.info

まとめ

この記事では、検索結果の精度評価指標としてMRR・MAP・NDCGを紹介しました。
次の記事では、ランク学習が実際にどこで動いているのかなどの応用事例を紹介していきたいと思います。

参考

Learning to Rank for Information Retrieval, T. Y. Liu, 2011

*1:もちろん予測精度以外にも、ランキングモデルが出力する検索結果が意図通りになってるかを目で確認するとか、確認すべき事項はいくつもあると思います。

*2:ランク学習にこだわらず、検索結果一般の精度評価指標に使えます。

*3:元論文は"A new interpretation of average precision", S. E. Robertson, 2008です

*4:RBPもそれはそれでパラメータがあったりして扱いにくい評価指標ですが。