情報検索の評価指標とバイアスについて

はじめに

こんにちは。ミスミグループ本社Gateway推進本部のはたはたです。
私たちは日々、当社ECサイトの検索システムの改良を行っています。改良の際に重要なのが、検索システムの評価指標です。既存のアルゴリズムAと新しく導入を考えているアルゴリズムB、どちらが優れているかを的確に評価することが必要不可欠になります。この記事では、一般的な評価指標のご紹介と、ECサイトの検索システムにおける評価の難しさについてをご紹介をしたいと思います。

検索システムの概要

評価指標の前に、情報検索がどのようなタスクかについてご説明します。
情報検索は、入力として検索ワード（この分野ではクエリと呼びます。以下本記事でもクエリと記述）を受け取り、クエリに適合していると考えられるアイテムを順位付きで出力するタスクです。
そのクエリに対してアイテムが適合しているかのラベル（正解）があれば、出力結果のアイテムがどれだけ良いかを評価することが可能になります。
アイテムではなくクエリとアイテムの組み合わせに対してラベルが定義されることに注意してください。　例えばアイテムとして果物を考えると、「赤い果物」というクエリに対してはリンゴは適合しているアイテムですが、「やわらかい果物」というクエリに対してはそこまで適合していません。
このように「赤い果物とリンゴ」に対して適合のラベルが付与されており、「リンゴ」に対してラベルが付与されているわけではありません。

アイテム \ クエリ	赤い果物	やわらかい果物
りんご	○	×
みかん	×	○

主な評価指標

• Recall
• Precision
• MRR
• nDCG

Recall（再現率）

Recallと、後述するPrecisionは、情報検索のみならず幅広い分野で使用される評価指標です。
Recallは、正解のラベルが付与されたもののうち、システムが正解と判定したものの割合を計算したものです。言い換えると「正解をどれだけシステムが拾えたか」の指標になります。

$${Recall = \frac{システムが正解と判定できた正解の数}{正解の数}}$$

情報検索においては、システムの予測したアイテムの上位k件までに対して計算を行うRecall@kを使用します（例：Recall@1000）。

precision(精度)

precisionは、正解と判定したアイテムのうち、正しく正解を予測したアイテムの割合です。言い換えれば、「システムの予測の中にはどれだけ正解があるか」の指標です。

$${Precision = \frac{システムが正解と判定できた正解の数}{システムが正解と判定した数}}$$

Recall同様、情報検索ではPrecision@10などで予測した上位のアイテムに対して評価を行います。

MRR(Mean Reciprocal Rank：平均逆順位)

MRRと、後述するnDCGでは順位についてより厳格に評価を行います。例えば、同じPrecision@10=0.1、つまり上位10件の予測のうち正解が1件あった状況でも、それが1位なのか10位なのかで好ましさは異なります。
MRRでは1位から予測アイテムを見た際に、初めて出せた正解の順位に焦点を当てます。この順位の逆数を取ることで好ましさを表します。1位が始めての正解の際は$1/1 = 1$の好ましさ、10位に初めて正解があったときには$1/10 = 0.1$の好ましさとなり、前者の方がより好ましいランキングとなります。このような数値をテスト対象の各クエリで算出し、平均を取った数値がMRRです。

$$MRR = \frac{1}{|Q|} \sum_{k=1}^{|Q|} \frac{1}{rank_k}$$

nDCG(normalized Documented Cumulative Gain)

これまではあるクエリに対して、アイテムを正解/不正解の二値で見ていましたが、nDCGではゲインという好ましさを数値化したものをラベルとして使用します。正解であれば何を上位に上げても良いわけではなく、より適合度の高いものを、高いものから順に提示できるほど好ましいという考え方の指標がnDCGです。
まず、高順位に高適合度があることを評価する手段として、減損累積利得(DCG)の考え方があります

$$DCG@k = \sum_{i=1}^{k}\frac{rel_i}{log_2(i + 1)}$$

$$= \frac{rel_1}{log_2(2)(=1)} + \frac{rel_2}{log_2(3)} + \frac{rel_3}{log_2(4)}・・・+ \frac{rel_k}{log_2(k+1)}$$

ここで、$rel_i$は順位$i$位のアイテムの適合度です。

ただ適合度を足すのではなく、順位が下がるに従い分母を大きくすることで適合度を減衰させています。
次に、この式のスケールの問題について、正規化で対応します。どういうことかというと、適合度の設定を1 ~ 100にしているタスクと0 ~ 1で設定しているタスクがDCGの値を比較しづらいです。そこで、理想的な検索システムの出力である、適合度の高い順にランキングを行った際のDCG（ideal DCG = IDCG）を考え、IDCGを用いて正規化を行ったnDCG

$$nDCG@k = \frac{DCG@k}{IDCG@k}$$

を指標として用いることで、適合度の設定に依らず一般的に用いることができます。

バイアス

紹介したこれらの指標を用いてアルゴリズムAとBを比較したいのですが、実はまだ考慮すべきことが残っています。私たちは適合度のラベルの計算に過去の実績データを用いて、クエリQに対して商品Xのクリック率を算出し、それをQとXの適合度としています。

例えば、過去一年で「赤い果物」や「やわらかい果物」と検索された回数と、提示したアイテムがクリックされた回数を集計することで、そこから計算されるクリック率（CTR, Click Through Rate）を適合度とすることができます。

アイテム \ クエリ	赤い果物（検索数=200）	やわらかい果物（検索数=100）
りんご	クリック数=100 → CTR=0.5	クリック数=0 → CTR=0
みかん	クリック数=10 → CTR=0.05	クリック数=80 → CTR=0.8

しかし、この過去の実績による適合度では以下のような問題があります。

• これまで提示してこなかった商品や新商品の適合度が0になる
• 一般的に上位に提示されている商品はクリックされやすい一方、ページの下の方や次のページに表示されている商品はクリックされづらいため、過去の表示順位にも依存する

更には、過去の実績データを使用した評価（オフライン評価）と、試しにお客様にアルゴリズムAとBの結果でどちらがクリック率が高くなるかを検証するABテスト（オンライン評価）は必ずしも相関しないことがわかっています。

例えば、低頭ボルトというKWでは、オフライン検証段階ではアルゴリズムAでのCTRが94.08%、アルゴリズムBでは94.21%と、少し良くなる試算でしたが、オンライン検証を行ったところAは変わらず90%台の一方、アルゴリズムBは77.33%とかなり悪化してしまいました。
このような乖離は、過去の実績と検証時期で選好の傾向が異なることや、オフライン評価時には評価できなかったアイテムのポテンシャルの差などの要因が考えられます。

このような難しさを踏まえつつ、私たちはアルゴリズムやデータ、評価結果を正しく解釈し、素早いモデル改善に取り組んでいます。

おわりに

この記事では、一般的な評価指標のご紹介と、ECサイトの検索システムにおける評価の難しさについてをご紹介致しました。情報検索分野のほんの一部分ではありましたが、私たちの業務に興味を持っていただけたら幸いです。