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

皆さんは、検索エンジンの評価をどのように行なっていますか？検索エンジンの評価は、実はユーザが求めていることによって変わってきます。今回は、ユーザが求めていること=ユーザモデルと検索評価指標の関係について、書いていきます。なお、以下の内容は酒井先生の書籍に記載されておりますので、詳細が気になる方は、こちらも読んでみてください。

集合検索指標

1クエリに対する評価

最も基本的な指標は、集合検索指標です。これは機械学習でよく用いられる、再現率 $R$ ・適合率 $P$ ・ $F_{\beta}$ スコアを使用します。以下、それぞれ式にします。まず、ある検索クエリ(検索要求)に対して、正解と見なされた文書集合(適合と判定されている文書)をA、検索システムがクエリに対して出力した文書集合をBとすると以下のようになります。

$\begin{aligned} R=\frac{|A \cap B|}{|A|} \\ P=\frac{|A \cap B|}{|B|} \\ F_{\beta} = \frac{(\beta^2+1)PR}{\beta^2 P+R} \end{aligned}$

特に $\beta=1$ のとき、 $F_{1}$ は $R$ と $P$ の調和平均になります。なお、 $F_{1}$ を変形すると、適合文書集合Aと検索された文書の集合Bの一致度を反映した指標になります。以下にその理由を説明します。なお、式のわかり易さのため $1-F_{1}$ がAとBの不一致度合いを表すことを示します。

$\begin{aligned} 1 - F_{1} &= 1 - \frac{2PR}{P+R}=1 - \frac{1}{\frac{0.5}{P}+\frac{0.5}{R}} = \frac{|B||A \cap B| + |A||A \cap B| - 2|A||B|}{|A \cap B||B| + |A \cap B||A|} \\ &= \frac{|A - B| + |B -A|}{|A| + |B|} \end{aligned}$

今、 $\frac{|A - B| + |B -A|}{|A| + |B|}$ は、AとBで一致していないものの割合なので、 $F_{1}$ は、適合文書集合Aと検索された文書の集合Bの一致度を反映した指標になります。

複数クエリに対する評価

複数のクエリに対する評価を行う場合は、平均を取ります。この平均の取り方には２種類あり、マクロ平均・マイクロ平均と呼ばれています。マクロ平均はクエリ毎の指標値で平均します。マイクロ平均は、全数で評価を行います。以下、式で表します。クエリが $i=1,...,n$ あり、今、評価指標をP(適合率)とします。また、各クエリの適合率を $P_i$ 、適合文書集合を $A_i$ 、システム出力文書集合を $B_i$ として、定式化すると以下の通りです。

$\begin{aligned} MacroP =\frac{1}{n}\sum_{i=1}^n P_i \\ MicroP=\frac{\sum_{i=1}^n|A_i\cap B_i|}{\sum_{i=1}^n|B_i|} \end{aligned}$

マクロ平均は、個々の検索要求を同等とみなしており、マイクロ平均はクエリ毎に文書数によって重み付けをしている(個々の文書を同等とみなす)と考えられます。

ランク付き検索指標

検索指標の評価も機械学習と同等の評価が使用できることをみましたが、この評価には欠点があります。それは、順位を評価できないため、適合文書がどの順位に出てきても、検索結果として出てきてしまえば同じ評価になるということです。例えば、検索結果をシステムのスコア上位10件までとした場合、目的の文書が1位に出ていても10位出ていても同じ評価結果になります。しかし、ユーザは通常、システムが適合していそうな順に文書を出力することを期待します。このような要求を満たす評価指標として、平均精度AP(Average Presicion)と逆数順位RR(Reciprocal Rank)があります。

平均精度は、第r位の文書が適合しているか否かを表すフラグ変数を $I(r)$ とし、第r位までの適合文書の合計を $C(r)=\sum_{k=1}^r I(k)$ とし、適合文書数を $R$ とすると以下のように書けます。

$\begin{aligned} AP =\frac{1}{R}\sum_{r=1}I(r)\frac{C(r)}{r} \end{aligned}$

例えば、適合文書が4つあるクエリに対して、システムが4位まで出力をし、1位と4位に適合文書が合った場合、 $AP=\frac{1}{4}(1/1+2/4)=3/8$ となります。なお、クエリ毎のAPを平均したものをMAP(Mean Average Precision)と言います。

逆数順位はより簡単に計算でき、検索結果中最上位の適合文書を $r_1$ とすると、以下の通りとなります

$\begin{aligned} RR=\frac{1}{r_1} \end{aligned}$

なお、検索結果に適合文書がない場合は $r_1=\infty$ とします。これによって $RR=0$ となります。クエリ毎にRRを平均したものをMRR(Mean Reciprocal Rank)と言います。

平均精度と逆数順位のユーザモデル

今回参考にしている書籍によるとウェブ検索には、以下の３つのモデルがあると言われています。

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

APは情報収集型の指標であり、RRは誘導型の指標と言われています。この意味を確認します。

まず、以下を仮定します。

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

このように考えると、どちらの手法もクエリに対して検索結果に表示された適合文書毎の適合率を足し合わせて、出現した文書に対する効用を満足したユーザ割合で重み足し合わせていることになります。

AP: 検索結果で出現した文書に対する効用を足し合わせ全ての適合文書数で割っている。これは各適合文書に満足するユーザが同数おり、検索結果で出現する文書の効用を満足するユーザで重みづけて足し合わせていることに相当する。よって、情報収集型であると言える。
RR: トップに出現した適合文書の適合率である。これは全てのユーザがトップに出現した文書に満足し、その時の効用のスコアをユーザが得ていることになる。よって、誘導型である。

終わりに

今回は、検索評価指標のうち、シンプルなものを紹介しました。しかし、これでもまだ問題があります。例えば、適合度の判定がスコアになっている場合はどうでしょう？人の評価スコアが高いものは、システムでもより上位に出して欲しいですし、それを正確に反映した評価指標を使った方が良いでしょう。次回は、このような指標とその仮定について紹介します。(なお、本稿では検索要求のことをわかりやすさのためクエリとしました)

Retrieva TECH BLOG

検索の評価指標