検索の評価指標

こんにちは。レトリバの飯田(@meshidenn)です。カスタマーサクセス部研究チームのリーダーをしており、マネジメントや論文調査、受託のPOCを行なっています。

前回は、検索エンジンの評価について入門的な内容をご紹介しました。今回は、その続きとして、少し発展的な評価指標についてご紹介します。なお、以下の内容は酒井先生の書籍に記載されておりますので、詳細が気になる方は、こちらも読んでみてください。

検索の評価指標
複数の適合度に対応したランク付き検索評価指標
- nDCG(normalized Discounted Cumulative Gain)
- ERR(Expected Reciprocal Rank)
終わりに

複数の適合度に対応したランク付き検索評価指標

前回紹介した、ランク付き検索評価指標の $MAP$ や $MRR$ は、適合しているかしていないかの２値しか扱えませんでした。しかし、検索された文書には「部分的にあっている」ということもありえます。このような状況を扱うのが、これから紹介する指標になります。

まず、前回のおさらいですが、ウェブ検索には、以下の３つのモデルがあると言われています。

情報収集型：一つ以上のウェブページに書かれていると思われる情報を取得したいという意図
誘導型：特定のサイトを訪れたいという意図
取引型：ウェブを仲介したアクションを実行したいという意図（例えば居酒屋を予約するなど)

そして、前回紹介した、 $AP$ と $RR$ で使用された仮定は以下でした。

検索結果をみていく時、ユーザは通常上から順番に１件ずつみていく(線形縦断)。
その時、あるクエリにおけるユーザの利得は、P(適合率)である。
さらに、あるクエリに対する適合文書のうち、どの文書にどのくらいのユーザが満足するのかを考える。情報収集型であれば、複数の文書を閲覧したいので、それぞれ等分と考える。一方誘導型は、トップの文書１つが見つかれば満足すると考える。

つまり、2の利得と3のどの文書にどのくらいのユーザが満足するのかが変化します。今回紹介する指標は、利得と満足するユーザについて、複数の適合度に対応させて修正を加えています。

nDCG(normalized Discounted Cumulative Gain)

これは、情報収集型の指標です。 $nDCG$ は、名前の通り減損累積利得(Discounted Cumulative Gain。以下 $DCG$ )を正規化したものです。

まず、 $DCG$ を定義します。r位の適合文書を見つけた時の利得を $g(r)$ とします。そして、減損利得を $dg(r) = g(r)/ \log_b(r+1)$ とします。つまり、減損率を $\log_b (r+1)$ とします。この時、上位n件までを検索結果として表示するとして、 $DCG@n$ は、以下のように定義されます。

$\begin{aligned} DCG@n=\sum_{r=1}^n dg(r) \end{aligned}$

$DCG$ では $AP$ から利得を変更していることがわかります。利得を $g(r)$ と明示的に定義した上で、検索のための指標ですので、下位に表示されるほど利得が下がるとして、減損率をいれています。

さて、次に正規化ですが、 $DCG$ の最高値は適合文書を利得順に降順に並べた時です。故に、この時の $DCG$ で検索時の $DCG$ を割ることで、スコアが[0, 1]を取るように調整できます。（つまり、正規化できます)。理想時の減損利得を $dg^{\ast}(r)$ とおき、理想時の $DCG$ を $DCG^{\ast}@n$ とおくと、 $DCG^{\ast}@n=\sum_{r=1}^n dg^{\ast}(r)$ です。よって、 $nDCG$ は以下で定義されます。

$\begin{aligned} nDCG@n=DCG@n/DCG^{\ast}@n \end{aligned}$

以下、例を見てみましょう。例えば、あるクエリに対して、4つの適合文書があるとします。そのうち２つは適合度が高く利得が4であるとします。残りの２つは、適合度が低く利得が1であるとします。今、システム1は、1位に利得4の文書を、4位に利得1の文書を出力したとします。残りは非適合文書で利得0とします。システム2は1位に利得1の文書を、3位に利得4の文書を出力したとします。システム2も、残りは非適合文書で利得0とします。直感的には、システム1の方が優れている気がします。これが $nDCG$ に反映されているか確かめます。その他のパラメータですが、表示件数 $n=4$ 、減損率の $\log$ の底 $b=2$ とします。この時、

$DCG^{\ast}@4 = 4/\log_2(1+1) + 4/\log_2(2+1) + 1/\log_2(3+1) + 1/\log_2(4+1)=7.454$

です。システム1の $DCG$ は、

$DCG_{s1} @4 = 4/\log_2(1+1) + 1/\log_2(4+1) = 4.431$

です。システム2の $DCG$ は、

$DCG_{s2}@4=1/\log_2(1+1) + 4/\log_2(3+1)=3$

です。よって、システム1の $nDCG$ は、

$nDCG_{s1}@4=4.431/7.454=0.594$

システム2の $nDCG$ は、

$nDCG_{s2}@4=3/7.454=0.402$

となり、システム1の方が優れていることが反映されています。

最後に $nDCG$ が、なぜ情報収集型なのか、利得 $AP$ からどう変化したのかを見ていきます。まず、なぜ情報収集型なのかという点ですが、 $AP$ は適合文書に一様に満足するユーザが広がっていました。ということは、検索でされていない文書にも満足するユーザが割り当てられています。逆にいうと、検索で表示されればされるほど、スコアが向上する指標と言えます。nDCGも、検索で表示されればされるほどスコアが向上する指標です。そのため情報収集型と言えます。次に利得についてですが、これは明らかで、APは適合率を使用していましたが、nDCGでは減損累積利得を使用しています。

ERR(Expected Reciprocal Rank)

こちらは、誘導型の指標です。 $ERR$ (Expected Reciprocal Rank)という名前の通り、 $RR$ の拡張になっています。ユーザの利得は、 $RR$ から変えず $1/r$ とします。 $RR$ は適合文書に出会った時点でユーザが満足し検索から離脱しますが、 $ERR$ では適合度が高いほどユーザが満足し検索から離脱する確率が高いとします。（これをカスケードモデルと言います。）

今、r位の適合文書を見つけた時の利得を $g(r)$ とします。また、全適合文書のうち最大の利得を $g_{\max}$ 、非適合文書の利得を $0$ とします。そして、ユーザがr位の文書だけを見たときに、その文書に満足して離脱する確率を $p(r)=\frac{2^{g(r)}-1}{2^{g_{\max}}}$ とします。このようにすると、ユーザが上から文書を確認しr位の文書で満足して離脱する確率は

$Pr_{ERR}(r)=p(r) \prod_{k=1}^{r-1}(1-p(k))$

となります。以上を用いて、 $ERR$ は以下のように定義されます。( $N$ は、全検索対象文書です)

$\begin{aligned} ERR=\sum_{r=1}^{N}Pr_{ERR}\frac{1}{r} \end{aligned}$

以上から、 $ERR$ が $RR$ の拡張で誘導型であることもわかります。

なお、 $ERR$ は検索結果が理想的な場合にも、指標が1以下になり得ます。 $ERR$ の範囲を[0, 1]にする(正規化する)ためには、 $nDCG$ と同様に理想的な場合の $ERR$ で割れば良いです。正規化した $ERR$ を $nERR$ と呼び、理想的な場合の $ERR=ERR^{\ast}$ と書くと $nERR=ERR/ERR^{\ast}$ となります。

終わりに

今回は、複数の適合度に対応したランク付き検索評価指標として、 $nDCG$ と $ERR$ を紹介しました。どちらの指標も前回と同様にユーザの利得と満足するユーザの割合という点でモデリングされていると見なせます。適合度を複数段階にしたことへの対応は、 $nDCG$ の場合は利得を変化させ、 $ERR$ の場合は、ユーザが満足する確率に反映されています。これらは、仮定が今評価したい状況と合っていれば、前回紹介したものよりもより検索性能を「正確」に測定できます。しかし、検索では評価用の正解を用意することが非常に困難です。既存の検索システムでは、適合文書をラベリングできない場合もあります。次回は、そのようなケースに対するアプローチを紹介します。