「情報検索検索エンジンの実装と評価」Advent Calendar 14日目の記事です． adventar.org 本記事では，12章「有効性の評価」についてまとめます．

有効性の評価とは

まず，そもそも「有効性(effective)」とは何かですが，ここでは「検索結果の品質」のことを指します．検索エンジンがあったとき，そのシステムによる検索結果の品質をどう評価するか，というお話です．

なお，情報検索システムの評価に関する本としては，以下の和書があります．

https://www.amazon.co.jp/dp/4339024961

12.1 伝統的な有効性評価指標

まず，基本となる評価指標として， 適合率 再現率 P@k 検索結果の上位k件の適合率(P@k) 平均適合率 逆数順位 があります．これらの情報検索における伝統的な評価指標は，評価に際して以下のような仮定をおいています．

ユーザーの情報要求があり，それらが検索クエリで代表され，与えられたドキュメントコレクションのそれぞれのドキュメントは，その情報要求に対して関連，非関連のどちらかである．
ドキュメントdの関連性は，その情報要求とドキュメントdだけに依存する．ドキュメントコレクション中に存在する他のドキュメントに対する検索エンジンのランキングとは独立である．

シンプルですが，納得できる仮定だとは思います．このようなモデルの本で，以下のような伝統的な評価指標が定義出来ます．

再現率と再現率

再現率(recall) は，検索結果が，実際に関連のある文章のうちどの程度拾えているか，を示す割合です．検索結果の文章の集合を Res , 実際に関連がある文章の集合を Rel と書くと，以下の用に数式で書けます．

$recall = \frac{|Res \cap Rel |}{ |Rel|}$

ただし，再現率は，極端な話，すべての文章を検索結果として出してしまえば，100%になってしまいます．そのため，検索結果のうち，関連ある文章はどの程度か，を示す割合である 適合率(precision) が用いられます．数式で書くと以下のようになります．

$precision = \frac{|Res \cap Rel |}{ |Res| }$

検索結果の上位k件の適合率(P@k)

単純な適合率は，暗黙のうちに，ユーザーが検索結果を全件目を通す，という仮定をおいています．しかし，実際に私たちが検索エンジンを使うときを想像してみると，普通は検索結果の上位数件に目を通すだけだと思います．そのようなケースを考慮したのが 検索結果の上位k件の適合率(P@k) です．

平均適合率

P@k を求める時，kを幾つにするか，というのは悩ましい問題です． 平均適合率(Average Precision) は， P@k をある種のルールのもとで平均を取ることで，この問題を解決しようとしたものです．

$AP = \frac{1}{|Rel|} \sum^{|Res|}_{i=1}{ relevant(i) \cdot P@i }$

ここで， $relecant(i)$ は，上からi番目の検索結果が関連あるドキュメントなら1，関連のないドキュメントなら0を取ります．つまり，平均適合率は， k件目の検索結果が関連ある文章であるような P@k の和を取って，関連あるドキュメントの数で割った値になります．

平均適合率は，ある文章が含まれないという情報を，その文章対応する適合率が0であるという形で計算することで含んでいます．そのため，平均適合率は，暗黙的に再現率の情報を含んでいると考えることも出来ます．

逆数順位

今まで見てきた評価指標は，検索結果がどのような順番で並んでいるかを，そこまで気にして来ませんでした．しかし，私たちが検索エンジンを使う時，欲しい情報がどのぐらい早く結果として出てくるかは重要です．

逆数順位(reciprocal rank (RR)) は，関連する文章がどれだけ早く結果として表示されるかを評価する指標です．数式で書くと以下のようになります．

$RR = \frac{1}{ \min ( k | Res k \in Rel ) }$

ようは，関連する文章がk件目 に初めてでてきた時，逆数順位は 1/k です．ここで逆数順位は，ユーザーはお目当ての関連する文章を1件でも見つけたら，そこで満足して検索をやめることを仮定しています．

12.2 TREC

TREC（Text REtrieval Conference, テキスト検索会議）は，情報検索分野の発展の上で大きな役割を果たしてきたワークショップです． TRECで規定された評価の方法論は，情報検索システムの評価におけるデファクトスタンダードを提供していると言っても良いでしょう．本節では，そのTRECの評価の方法論について説明します．

1. 主催者によるトピック集合とドキュメントの配布

TRECは，まず主催者がトピック集合を作成し，ドキュメントのコレクションと合わせて参加者に配布します．ドキュメントコレクションは，新聞や雑誌の記事といった，専門家によって書かれたドキュメントからなります．また，トピックには，Web検索のクエリなどではよく見られるような，誤字脱字やスペルミスなどはほぼ含まれません

2. 参加者によるトピックからのクエリの生成

参加者はトピックからクエリを生成します．この際，一般的には，クエリはトピックから自動生成する必要があります．

3. 参加者による実行結果の提出

参加者は，各トピックに対するクエリをコレクション上で実行し，上位k件のランク付けされたリストを主催者に提出します．このリストはrunと呼ばれます．kは $k = 1000$ が用いられることが多いようです．

4. 主催者による評価用のドキュメント集合（プール）の作成

主催者は，参加者から受け取ったrunから，それぞれ上位k件を取り出し，その和集合を評価用のドキュメント集合（プール）とします． kとしては多くの場合 $k=100$ が用いられます．そして，このプールに対し，トピックに対して関連しているか，関連していないかの二値のラベルが人手で付与されます．これらの判断結果はqrelと呼ばれます．qrelを用い，適合率や再現率，平均適合率などといった各システムの有効性指標が計算されます．

トピック，ドキュメントコレクションとqrelは，，他の実験でも再利用できるテストコレクションとして提供されます．

12.3 統計指標を用いた評価

本節は，検索エンジンを学ぶ人のための統計学再入門，といった趣きの節です．統計学の教科書に載っているような内容が多く，また分量的にかなり多いため，本記事では割愛します．

とはいえ，実際に検索エンジンを評価するシチュエーションを想定して統計学の道具立てが説明されており，誤解・誤用しやすいポイントも説明されているため，一読の価値はあります．本節の冒頭部分には，情報検索分野において統計学の不適切な使用が少なくなく，自分のこの文章がその状況を変える一助になるように，との著者の願いが書かれています．

12.4 判断処理数の最小化

パターン認識や機械学習でいうところのアノテーションの工数を削減する話です．情報検索の場合，クエリに対して，文章が関連しているな否かという評価が与えられるため，すべての文章に評価を与えようとすると，判断処理数はクエリ数と文章数の掛け算で増えていきます．そのようなすべての文章に評価を与える徹底的な評価(exhaustive adjudication)は，昨今のデータ量では到底不可能です．判断処理数を削減するため，関連がありそうなドキュメントを抽出し，それらに対してのみ判断を与えることや，評価対象をランダムにサンプリングし，そこから全体の有効性指標を統計的に推定するサンプル抽出法などが行われます．

判断するドキュメントの選択

TRECで用いられているプーリング法は，各システムの上位k位までのドキュメントを集めてプールを作り，そのプールに対してのみ評価を行うことで，判断するドキュメント数を削減していました．本項では，その他判断するドキュメントの選択に関わる話題について紹介します．

相互検索と判断
- 相互検索と判断(Interactive Search and Judging(ISJ))は，熟練した検索者が検索エンジンを用い，可能な限り関連するドキュメントを検索し，ラベル付けすることで評価を行います． ISJによってより短い時間で作成されたqrelによる評価結果が，TRECの公式結果とほぼ同等であるとの報告もあるようです．
前方移動プーリング
- 前方移動プーリング(Move-to-Front Pooling(MFP))は，性能のよいシステムによって上位にランク付けされたドキュメントについて，優先的に関連性の評価を行います．
浅いプーリング
- プーリングの深さk，すなわち各システムの上位から取ってくる結果の件数kを変えるのは．判断の工数を調整する簡単な方法です．
トピック数の増減
- コレクションのトピック数nを増減するのも，判断の工数を調整する簡単な方法です．判断の工数を固定したとき，トピック数やプールの深さをどう決めるかは，ISJやMTFなどの手法でも検討が必要になります．
プーリング戦略の評価
- 二つの異なるシステムランキングは，伝統的にはケンドールの順位相関件数τを使って比較されてきました．順位相関件数τは，もし二つのランキングが同一なら $\tau = 1$ を取り，反対のランキングであれば $\tau = -1$ になります．

サンプル抽出法

プールから一部分のサンプルを無作為に抽出し，有効性指標を推定することも可能です．平均適合率の推定値（推定平均適合率, inferred average precision, infAP）は，以下のようになります．

$AP = \frac{1}{|Rel|} \cdot \sum^{|Res|}_{i=1} relevant(i) \cdot E(P@i)$

E[P@i] の部分を推定することになります．

12.5 新しい有効性評価指標

12.1節で述べられていたとおり，古典的な有効性指標は極めてシンプルな検索行動のモデルを仮定しているため，より現実的な状況でシステムの有効性を評価する上ではあまり適切でない場合も多いです．そのようなより現実的な設定のための評価指標を紹介します．

段階的な関連度

平均適合率などでは，クエリと文章の関係は関係は関連か非関連のどちらかであると仮定しています．しかし，実際は関連と非関連の間にはグラデーションがあるはずです．

nDCG（normalized Discounted Cumulative Gain, 正規化された割引累積利得） は，段階的な関連度を考慮した指標です． nDCGの計算は以下の4ステップからなります

1. 利得ベクトルの構成 検索システムが出力したランク付けされた文章のリストに対し，それぞれの文章の関連度に対応する利得(gain)を割り当てて利得ベクトル(gain vector) Gを作ります．

$G = (5, 10, 0, 5, 1, ..)$

2. 累積利得ベクトルの計算 つぎに，累積利得ベクトル(cumulative gain vector) CGを計算します．CG[k]は， k-1までのGの和です．

$CG(k) = \sum^{k}_{i=1}{G(i)}$

3. 割引累積利得の計算 順番が後にくる文章の利得を減点するようにして割引累積利得(discounted cumulative gain, DCG)を計算します．DCGは以下の式で定義されます．(以下では対数を利得の割引関数として使っているが，他の関数を使う場合もあり）

[tex: DCG(k) = \sum^{k}{i=1}{ \frac{G(i)}{\log{2}{1+i}}}]

4. 割引累積利得の正規化 最後に，割引累積利得を，最も理想的な結果が得られた場合の割引累積利得DCG'で正規化します．

$ｎDCG(k) = \frac{DCG(k)}{DCG'(k)}$

不完全で偏った関連性評価

情報検索のテストコレクションには,関連性が評価されていない文章が含まれることが多いです．慣例的には，これら未評価の文章は関連性なしとして扱われてきました．一方で，未評価の文章を単純に関連性なしとして扱ってしまうと問題があるケースもあります．例えば，Web検索サービスのように，定期的にクローリングされた文章がテストコレクションに追加されるような場合，未評価であっても関連性のある文章が存在することは大いにありえます．

このような不完全で偏った状況でも，システムランキングの安定性において比較的良好なことが報告されている指標として ランク有効性指標(rank effectiveness measure(RankEff)) があります． RankEffは，以下の式で定義されます．

$RankEff(k) = \frac{1}{|Rel|} \sum^{|Res|}_{i=1} relevant(i) 1 - \frac{|Res(1..i) \cap Non| }{ |Non| }$

ここで， Non は評価済みの非関連文章の集合です．

検索結果の新規性と多様性

古典的な評価指標が考慮していない観点として，情報の新規性と多様性があります．

新規性がある検索結果とは，列挙されている文章にそれぞれお互いに重複しないような情報が記載されている場合です．夏目漱石と検索した場合，あるページには小説家としての漱石が記載されており，またあるページには英文学者としての漱石について記されている，といった具合いです．

多様性が問題になるのは，クエリは多義性を含むような場合です．例えば，ジャガーと検索された場合，猫科の動物としてのジャガーか，車か，フェンダー社製のギターか，ユーザーがどの情報を求めているのかわかりません．このような場合，ユーザーの母集団における興味を考慮しつつ，それぞれの内容が多様に含まれる結果を出すのが望ましいと考えられます．

新規性と多様性も考慮した評価指標として，α-nDCGというのがあります． α-nDCGでは，クエリは複数の意図・情報の塊（ナゲット）からなると考えます．そして，それぞれ文章について，幾つナゲットを含んでいるをカウントしたものを利得とし，nDCGを計算します．

mofumofu1729の計算機日記

プログラミングの勉強メモや日々の雑記など

「情報検索：検索エンジンの実装と評価」１2章有効性の評価