検索の評価指標その2

自然言語処理 機械学習・深層学習

検索の評価指標

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

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

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

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

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

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

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

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

つまり、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の場合は、ユーザが満足する確率に反映されています。これらは、仮定が今評価したい状況と合っていれば、前回紹介したものよりもより検索性能を「正確」に測定できます。しかし、検索では評価用の正解を用意することが非常に困難です。既存の検索システムでは、適合文書をラベリングできない場合もあります。次回は、そのようなケースに対するアプローチを紹介します。