検索の評価指標 その３

機械学習・深層学習

検索の評価指標

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

前回は、検索結果にグレードをつけられる場合の検索エンジンの評価についてご紹介しました。今回は、未評価データがある場合等の修正方法についてご紹介します。なお、以下の内容は酒井先生の書籍やこちらの論文に記載されておりますので、詳細が気になる方は、こちらも読んでみてください。

未評価データの問題点

検索は通常、検索対象が非常に大きいため、あるクエリと関連あるドキュメント(正例)を全て判定することが不可能です。そのため、既存の検索エンジンを使用するなどして評価データを作成します。よって、新しい検索のランキングアルゴリズムを考えた時、評価していないデータが上位にくる可能性があり、それはクエリに関連する文書である可能性があります。そのため、未評価データを負例として扱うと、新しいシステムに不利になってしまいます。

未評価データを考慮しない方法

indAP

もっとも簡単な発想は、未評価データを評価しなければ、不利になることはないということです。つまり、未評価データは評価から取り除けば良いのです。未評価データを評価から取り除く場合の APを indAPと呼びます（ APについては、第一回を参照してください)。 今、適合文書がR件あるうち、評価済みの文書だけを上から数えた時の順位を r'とします。また、第r位の文書が適合しているか否かを表すフラグ変数を I(r')とし、第r'位までの適合文書の合計を C(r')=\sum_{k=1}^{r'} I(k)とし、適合文書数を Rとします。この時 indAPは以下の通りです。

\begin{aligned} indAP=\frac{1}{R}\sum_{r'=1}^k I(r')\frac{C(r')}{r'} \end{aligned}

期待値による方法

infAP

infAPは、期待値を使用して未評価データを補完する方法です。今、検索結果リストの上位r件から、文書を１件サンプルして、適合しているかどうか判定することを考えます。APは、r位が適合している時に増える値なので、r位は適合しているとします。この時、適合文書がサンプルされる期待値 E(r)は、r位がサンプルされる確率と、r位より上位の文書中で評価済みのデータのうち適合している文書がサンプルされる確率の和になります。式で表すと以下です。( C(r)はr位までの適合文書数、 \bar{C}(r)はr位までの非適合文書数です。)

\begin{aligned} E(r) &=\frac{1}{r} + \frac{r-1}{r} E(above_r)　\\ & =\frac{1}{r} + \frac{r-1}{r} \frac{C(r-1)}{C(r-1)+\bar{C}(r-1)} \end{aligned}

なお、 C(r-1)+\bar{C}(r-1)は、 r-1より小さくなりやすいです。

これは、未評価データを期待値 E(above_r)で補完している形になっています。なお、r-1番目が適合文書とは限らないので、再帰的に計算されません。

これを用いて、infAPは以下の式で表します。

\begin{aligned} infAP=\frac{1}{R}\sum_{r=1}^k I(r)E(r) \end{aligned}

例

完全に評価できている場合、あるクエリに対して、適合文書 R^ * = 5で、検索結果7件のうち、1,2,3,6位に適合文書がある状況を考えます。しかし実際には、コストの問題で、評価したデータ中に適合文書が R=3件となり、評価した適合文書が1,3位に現れているとします。また、2,5,6,7は未評価文書だったとします。この時、真の AP=AP^ *, 未評価データを負例とした場合の AP, indAP, infAPはそれぞれ以下の値になります。

\begin{aligned} AP^* &= (1/1+2/2+3/3+4/6)/5 = 0.733 \\ AP &= (1/1+2/3)/3 = 0.556 \\ indAP &= (1/1+2/(3-1))/3 = 0.667 \\ infAP &= (1+(1/3+2/3*1))/3 = 0.667 \\ \end{aligned}

APからの変更点は、例えば、 indAPでは、第3位までに適合文書が2件あり未評価文書が1件あるので、 2/(3-1)と変わっています。 また、上記の結果から、 indAPや infAPが、 APより、 AP^ *に近いことがわかります。

層別サンプリングを考える方法

xinfAP

infAPに層別サンプリングの考えを入れたのが、xinfAPです。(以下、原論文から変更しています。仮定の間違いなどあるかもしれませんが、式は同じになります。)

今、評価がいくつかの層 Sで行われており、その評価は、層ごとに N_sあるデータのうち、一様にサンプルした n_s個を評価しており、適合文書が r_s個あるとします。例えば、複数の検索ランキングで検索した結果に対して、その上位 N_s件から一様にサンプルした n_s件について適合性判定を行うなどです。また、実際には N_s中に適合文書が R_sあり、全適合文書数は R_Qとします。 APの Rの部分が、 R_Qです。

まず、 R_Qを推定します。 R_Qは素直に、 R_Q = \sum_s R_s, \hat{R}_s = r_s/n_s \cdot N_sとします。

次に、 E(r)を考えます。 infAPと同様に考えます。上位からr番目の適合文書の場合を考えるので、

\begin{aligned} E(r)=\frac{1}{r} + \frac{r-1}{r} E(above_r) \end{aligned}

です。また、 E(above_r)は各層ごとに考えるため、

\begin{aligned} E(above_r) = \sum_s \frac{N^{k-1}_s}{k-1} \cdot \frac{r_s^{k-1}}{n_s^{k-q}} \end{aligned}

です。ここで、 N_s^ {k-1}はk-1番目までに出ている層 s由来の文書数、 n_s^ {k-1}はその中で評価した文書数、 r_s^ {k-1}はその中の適合文書数です。よって、 Rの推定と、 E(above_r)の推定を層別に行なっているのが、 infAPからの変化です。

xinfnDCG

nDCGは、以下のように分解できるため、検索結果の DCG_rと、理想的な結果 DCG_Iの期待値をそれぞれ算出します。

\begin{aligned} nDCG = \frac{DCG_r}{DCG_I} \ where \ DCG_r=\sum_{i=1}^{Z} g_i/\lg(i+1) \end{aligned}

なお、 Zは検索された文書数、 g_iは利得、 \lg()は対数関数です。

DCGIの期待値

今、すべての g_iの値の集合を g \in Gとします。層 sに対して、利得 gを持つ文書の数を r_s(g)、評価した全文書を n_s、層の全文書数を N_Sとします。 DCG_Iは、各利得の文書数が分かれば、それを降順に並べた場合の DCGを計算すれば算出できます。よって、全体の各利得の文書数を R(g)とし、層ごとの各利得の文書数を R_s(g)とすると、推定値は \hat{R} _ s(g) = \frac{r _ s(g)}{n _ s} \cdot N _ s, \hat{R}(g) = \sum _ s \hat{R} _ s(g)となります。

よって、この \hat{R}_s(g)を使って、gが大きい順に利得を \sum _ s \hat{R} _ s(g) g として、上位から順に減損されれば、 DCG_Iを算出できます。

DCGrの期待値

試行回数１回で全体の利得を考えたいとします。この時、 Zの中からi番目の文書が選ばれ、その利得が g_iだとします。すると、検索された文書全体の利得は、 x_i = Z \cdot \frac{g_i}{ln(i+1)}と推定できます。よって、層別で考えたときに、 E[DCG_r]は以下のようにかけます

\begin{aligned} E[DCG_r] = \sum_s \frac{Z_s}{Z} \cdot E[x_i \| document \ at \ rank\ i \in s] \end{aligned}

そして、

\begin{aligned} E[x_i \| document \ at \ rank\ i \in s]　= \frac{1}{n_s} \sum_{j \in sampled_s \ in \ retrieved \ document} x_j \end{aligned}

となります。これは、１サンプル毎に、全体の利得を予測し、その平均を計算しています。

以上から、 DCG_rと DCG_Iが計算できたため、 xinfnDCGが計算できます。

終わりに

今回は、全てのデータを評価していない場合の指標を紹介しました。単純な方法として、評価していない文書を考慮しない方法を紹介しました。また、期待値を考え計算する方法も紹介しました。今回で、検索指標に関する記事は終了します。さらに興味がある方は、酒井先生の書籍などを参照してください。