【検索処理】検索の良し悪しをどのように測るか

今回は検索の良し悪しをどのように測るかという内容になります。

前回の記事までで、転置インデックス、日本語の切り方についてまとめました。これは検索したいデータをどのように引くかという話でした。

今回は、実際に作成した検索の質が良いのか悪いのか、そしてその良し悪しを客観的にどのように評価するのかといった話になります。

評価するために必要なもの

検索システムが完成したとして、実際に検索処理の質をみてみることにしましょう。

「達人プログラマー」という検索の結果が以下になったとしましょう。

検索文字列に対して、期待していたものは3位と4位に出てきました。

この結果はどう思うでしょうか？

本当はこれらのデータが1位2位に出てきて欲しいので

微妙だな。。。

と感じると思います。

では、この「微妙」という主観的で人間的な感覚を、客観的な指標、具体的な数字にどのように落とし込むかが今回の論点になります。

数字にしたい理由としては具体的に以下のようなものがあります。

1. 目視は量に耐えない（クエリ数 × 試す段階の数だけ繰り返す）
2. 基準がブレる（今日の「微妙」と来週の「微妙」の感覚が同じとは限らない）
3. 前の結果と比較できない

この中で、特に重いのが3つ目です。

1つ目と2つ目は、目の前にある結果をどう判断するかという話です。手間はかかりますが、時間をかければなんとかなる部分もあります。

ですが、3つ目は違います。

検索は一度作って終わりではありません。作り方を変えながら少しずつ良くしていくものです。そして作り替えるたびに「前より良くなったのか」を判断する必要があります。

ここで、速さと比べてみましょう。

速さであれば秒で比べられます。1.2秒かかっていた処理が0.3秒になった、それで終わりです。

ですが、順位の質には、そもそも比べるための物差しがありません。 前回の結果がどれくらい良かったのか、今回の結果はそれよりどれくらい良くなったのか。それをいうための共通の基準がないのです。

正解データ

客観的に評価するために正解データを作成します。

上記の例で、求めていたものが3位と4位にあったと言えたのは、先に正解の書籍があったからです。

正解データは、後に計算する指標の材料とすることができるのです。

そして、正解データとは何かですが、以下のようなものです。

クエリと、そのクエリで出て欲しい書籍の組

これをqrelsといいます。

これは人間の手で作るものになります。これを自動で作れるのであれば、それこそが検索エンジンになるからです。

順位を測る指標にはどんな種類があるか

正解データを準備できたので、それを使って何をするかを考えましょう。

指標とは

まず、指標とは何かを正確に定義しましょう。

「検索結果の並びと正解データを入れると、0.0〜1.0の数が1つ出てくる道具である」

これを、指標の定義とします。

そして、その道具には以下の3つがあります。

これから、これらの3つの指標についてどのような指標なのかを掘り下げていきます。

ちなみに、これから指標の算出に用いる正解データは、

「達人プログラマー」というクエリに対して

• 達人プログラマー : 熟達に向けたあなたの旅
• 達人プログラマー : 職人から名匠への道

としておきます。

Recall@10

Recall@10とは以下の計算で算出する指標です。

Recall@10 = 上位10件に入った正解の数 / 正解の総数

利用者が実際に目を通す件数によって@の後ろの数字が変わります。

Recall@10の場合は10件として算出するということになります。

冒頭の例で実際に算出してみましょう。

今回、「達人プログラマー」というクエリに対して

10件の検索結果の中に正解は全て入っていました。なので

Recall@10 = 2件（上位10件に入った正解の数） / 2件（正解の総数） = 1.0

となり、満点という結果になりました。

冒頭では、この検索結果に「微妙」という判断をしましたが、Recall@10では検索の質としての指標が満点という結果を出しました。

これは、Recall@10が

正解が検索結果に入っているかどうか

しか見ていないというところに起因します。

正解が1位であっても10位であっても結果が変わらないところがポイントとなります。

MRR

まず、RRについて説明します。RRの定義は以下になります。

RR = 1 / 正解が最初に出てきた順位

すなわち、正解が最初に出てきた順位の逆数のことになります。

RRの算出結果を表にまとめました。

注意しなければいけないのが、RRは最初の1件だけみるというところです。 これは、利用者が実際に検索をしている際に、探していた本が見つかった瞬間に検索を止めるという考え方が裏にあるからです。

また、1 / k の値の減り方ですが、1位と2位では倍の差がありますが、9位と10位ではほぼ差がありません。

RRは上位を極端に重く見る指標ということも頭に入れておきましょう。

RRを定義できました。そしてMRRのMですが、こちらは平均を意味する「Mean」のことです。RRの平均がMRRということになります。

では冒頭の例で計算してみましょう。

今回はクエリを1つしか用意していないので算出回数は1回なので MRR = RR になります。

正解の最上位は3位なので

MRR = 1 / 3 ≒ 0.333

になります。

この結果をRecall@10と比較してみましょう。

どちらの計算も正しい結果ですが、評価としては大きく変わります。

これは見ているものが違うということに起因した結果になります。冒頭の「微妙」という感覚に近いのはMRRだったということになります。

nDCG

最後にnDCGです。

まず、nDCGはRecall@10とMRRと前提が違うということを押さえましょう。

Recall@10とMRRは正解を「その本か、そうでないか」の2値を用いて算出するものでした。

対してnDCGは正解に段階をつけて算出するものになります。

段階のついた正解データ

例として、「Go言語の並行処理について知りたい」というクエリに対して正解データを以下のように設定します。

• 3点：Go言語による並行処理
• 2点：Go言語による分散サービス
• 1点：並行プログラミング入門（Rust・Cによる実装）
• 0点：Go言語によるWebアプリケーション開発

そして、この点のことを**適合度（relevance）**と呼びます。

算出方法ですが、まずDCGを定義します。

DCG = Σ rel_i / log2(i + 1)

log2(i + 1) で割っているのは、下の順位ほど割引く調整になります。MRRの1 / kと同じ発想ですが、こちらの方が緩やかに減っていきます。

このようにDCGを算出した上で正規化を行います。これは正解が多いクエリほど点が積み上がって高く出てしまうからです。

nDCG の n は normalized の頭文字です。

IDCGを点の高い順に完璧に並べた時のDCGと定義し、

nDCG = DCG / IDCG

をnDCGの定義とします。

今回は使わない

nDCGは今回は不採用とします。理由は適合度を決める根拠がないからです。

仮に点数をつけたとしても、その点数がどこからきた数字になるのかを説明する手段がないのです。

つまり、以下のような問題が発生します。

1. 正解データ作りのコストが上がる
2. その点数の妥当性を誰も保証することができない
3. 数字が動いたとき、検索が変わったのか点の付け方が甘かったのかを切り分けられない

根拠がないのに段階的な指標を使うと、精密そうに見えて中身は主観という一番最悪な状態を引き起こしてしまうため、nDCGの採用は見送ることとします。

ただ、書籍検索に全く適用できないかというとそういうわけではありません。

「分散システムについて学べる本」のような探索的な検索では、正解が一冊に定まらないケースがほとんどのため、役に立つ度合いを段階的な指標として考えることができるでしょう。

どう実装するか

では前述の2つの指標を算出するコードを実装してみましょう。

# Recall@10 (kは入力で可変、デフォルトで10)
def recall_at_k(ranked, gold, k = 10):
  return len(set(ranked[:k]) & set(gold)) / len(gold)

# MRR
def reciprocal_rank(ranked, gold, k = 10):
  # 正解が k 位なら 1 / k。最初に見つかった1件だけ見る
  for i, doc in enumerate(ranked[:k], 1):
    if doc in gold:
      return 1 / i
  return 0.0

上記のように指標は数行で書けるくらい単純なものです。

難しいのは後述の「何を正解と決めるか」の方です。

正解データをどう作るか

作業自体は至って単純で、

クエリを決めて、そのクエリで出て欲しい本を決める

これだけです。

ところが、実際に手を動かしてみると正解が1件に決まらないケースが次々に出てきます。

同じ本が複数ある

例えば、書名が同じでも出版年度が異なるようなケースがあります。

• プログラミングRust　2018年版と2022年版
• パーフェクトRuby on Rails　2014年版と2020年版
• Docker/Kubernetes実践コンテナ開発入門　2018年版と2024年版

などです。

これらに関しては、利用者は書名しか入力しないでしょう。

出版年度はクエリに含まれないため、評価者もどちらを探しているかを決めようがありません。

別版の現れ方

同じ書名をもつ別版の現れ方には以下のような3パターンがあります。

機械で検出の部分ですが、(a)パターンの場合は書名でグループ化すれば良いので簡単です。

(b)パターンの場合は、「第N版」の部分を取り除けばグループ化することができますが、実際には「新装版」や「改訂版」など表記が無数にあります。

取り除く処理のルールを足し続ける仕事が増えてしまいますし、本来は想定しないものもグループ化されてしまう恐れもあります。

(c)パターンの場合ですが、表の例での書名の共通部分は「達人プログラマー」です。

ですが、以下のような全く関係のない書名とも共通してしまいます。

• リファクタリング・ウェットウェア：達人プログラマーの思考法と学習法
• 実践JUnit：達人プログラマーのユニットテスト技法

つまり、「達人プログラマー」を含むかどうかでは、版違いと他人の区別がつかないのです。同じ本の第1版と第2版だと知っているのは人間だけです。

どちらの版を正解にするべきか

同じ書名を持つ本が複数ある場合は、新しい方を正解とすればいいのでは？という疑問が出てきます。

ただ、利用者は常に新しい方を求めているとは限りません。

今回の場合は、この検索は個人開発している読書管理アプリケーションの書籍検索に使います。

利用者は自分が持っている本を本棚に登録します。

つまり、2018年版と2022年版の書籍があったとして、自分が2018年版を持っているのであれば2018年版が正解なのです。

そして、「プログラミングRust」のようなクエリには、そのどちらを指しているのかという情報がないのです。

なので同じ書名を持つ書籍データに対してどれが正解なのかはわからないのです。

評価セットに入れてはいけないクエリ

ここまでは、正解が決まらない話でしたが、ここでは、そもそも評価に使ってはいけない話をします。

正解が索引にない

索引対象に含まれていない出版社の本を検索するクエリを残した場合、指標としては0がつきます。

ただ、この0はいくら検索を改善したとしても消えない0です。

これはカバレッジの問題なので検索の問題ではありません。

known-item search になっていない

known-item searchとは利用者が特定の1点を心に決めて探しにくる検索のことです。

「この本が欲しい」が先にある状態ということです。

これに対して、「分散システムについて学べる本」のようなテーマで探すような検索は正解が1つに決まらない検索になります。

クエリを見て、評価者が「この人はこの本を探している」と1作品に特定できないクエリは避けましょうという話になります。

例えば、「マスタリングTCP/IP」は複数版が存在する入門編のほかに、応用編やIPv6編など中身が違う本が並びます。

「マスタリングTCP/IP」の全ての本を正解にするとシリーズのどれか一冊以上が上位に出れば満点になってしまいます。

これは利用者が本当に欲しかった本を出せたのかどうかが測れなくなってしまいます。

そもそも評価者自身がどれを正解にすべきか決められないようなものは入れないようにしましょう。

決めた3つの方針

では、これらのことを踏まえて正解データの作り方の方針を決めていきます。

場当たりで判断すると、あとで自分の判断を再現できなくなるので先に決めて書き残しておきます。

P2、P3は「評価セットに入れてはいけないクエリ」で説明した通りです。

P1ですが、これは主指標にMRRを選んだから成り立ちます。

もしnDCGを採用していた場合、第1版と第2版に別の点数をつけなければならず、この問題が回避不能な壁になってしまいます。

正解データ作りは、性能を測る前段の雑用ではありません。

「何を正解と呼ぶか」を決める作業が、検索の設計判断そのものになっているのです。

第1版と第2版を両方正解にすると決めた瞬間に、この検索は「版を区別しない検索」だと決めることになります。

そして、その決定は正解データの中にしか書かれていないのです。

評価セットをどう設計するか

1つのクエリに対して、正解をどう決めるかは結論が出ました。

ここでは、そのクエリを何本集めて、どう運用するかという話をしていきます。

何クエリ必要か

MRRは n クエリの平均なので、1クエリが動かせる幅は 1 / n になります。

少なすぎると差が読めなくなります。

検索を改善して、「MRRが0.05よくなった」と言いたくても、クエリ1本の当たり外れで0.10動く評価セットでは何も言えません。

だからといって、多すぎても手がもたなくなります。

1クエリにつき検索結果の上位を数件ずつ目で見て、1件ずつ「これは同じ本か、別の本か」を判断していく作業を100件分行うというのは個人開発では現実的ではありません。

なので、落とし所として今回は30〜50とします。

また、0.05という差は目安になります。改善幅は事前にはわからないので仮置きとしておきます。

一度作ったら変えない

まず大原則として守らなければいけないのが、評価セットは途中で変えてはいけないということです。 検索は段階を追って作り替えていきます。そして、その都度異なる評価セットで評価していた場合、数字が動いた理由が「検索が変わったからなのか」「測る物差しが変わったから」なのかが判断できなくなるからです。

そして、一番危ないのが結果が悪かったクエリを評価セットから外すという行為です。

これを行うとMRRは必ず上がります。そして検索は少しも改善されていません。

仮に、50クエリの評価セットで MRR = 0.80 だったとします。

このうちどうやっても直せない1本（RR = 0）を外します。そうすると、残りのクエリは49本になり、RRの合計は40で変わらないので

MRR = 40 / 49 ≒ 0.82

検索は全く変わっていないのに 0.02 上がったという結果になります。

この連載の書籍検索は MRR を主指標にする

ここまでで材料は全て揃いました。

その上で今回は MRR を主指標にするとして理由をまとめていきます。

判断理由は以下の3つです。

1. known-item search だから。利用者は「その本」を知っていて探しにくる。本棚に登録したいだけなので、10件のどこかにあればいいのではなく1位に出したい
2. Recall だけ見ていると取りこぼす。冒頭の例は Recall@10 = 1.000 で満点なのに MRR = 0.333 だった。
3. 正解が2値なので nDCG の前提を満たさない。「その本か、そうでないか」しかなく、段階をつける根拠がない。

Recall@10ですが、こちらは副指標として残しておきます。捨てるわけではありません。

指標を2本持っておけば、取りこぼしと順位の低さを数字だけで切り分けることができます。

検索は既存のライブラリや拡張を使う方法もありますが、この連載では中身を理解するために自前で実装しています。

ただし、速さではCで書かれた既製品に勝てる見込みは薄いです。

なので、完了条件には次を置くことにします。

固定した評価セットの MRR

段階を進めるたびに同じ評価セットで測り、その数字だけを見比べることとします。

まとめ

今回は、検索の良し悪しをどのように測るかという話をまとめました。

そもそも指標というものを理解するところからでしたが、指標自体は実装も簡単でした。

難しいのは正解データをどのように決めて作成するかというところでした。

そして、その作り方によって何をよしとするかが決まるというのが今回の肝でした。

今回も最後までご愛読ありがとうございました。