9.1 検索精度の定義

再現率と適合率

- 適合ドキュメント 非適合ドキュメント
検索結果に含まれる tp (true positives) fp (false positives)
検索結果に含まれない fn (false negatives) tn (true negatives)
  • 適合率 (Precision)：\(P = \displaystyle\frac{tp}{tp + fp}\)
  • 再現率 (Recall)：\(R = \displaystyle\frac{tp}{tp + fn}\)
  • F値 (F-measure)：\(F_{measure} = \displaystyle \frac{1}{\frac{1}{2P} + \frac{1}{2R}} = \frac{2PR}{P + R}\)

ランキング

ユーザは検索結果の上位いくつかだけを見て離脱する傾向があるため、適合率が低くて適合ドキュメントを上位に掲出できればユーザ満足度は高くなる。 → ランキングの評価も重要

9.2 再現率と適合率の改善

アナライザの変更による改善

トークナイザ / フィルタ 種類 改善が期待される点
JapaneseTokenizerFactory 日本語トークナイザ 適合率
SynonymFilterFactory シノニムフィルタ 辞書の同義語が当たるようになるため、再現率が改善
CJKBigramFilterFactory
NGramTokenizerFactory		 N-gram フィルタ / トークナイザ N-gram 分割によりヒットする単語が増えるため、再現率が改善

各種辞書の活用

シノニム辞書

ケース 例
略語 アルバイト バイト, 東大 東京大学
同義語 登山 山登り
外来語 Web ウェブ, サンドイッチ サンドウィッチ
表記ゆれ ビックカメラ ビッグカメラ, ビトン ヴィトン
送り仮名 焼肉 焼き肉, 割引 割り引き

処理タイミング・展開タイプによるメリット・デメリット

  • クエリ時
    • シノニム展開
      • メリット：インデックス更新を待たず辞書が利用できる
      • デメリット：クエリタームが増えるのでクエリのパフォーマンスに影響
    • シノニム正規化
      • メリット：（影響なし）
      • デメリット：インデックス側でも正規化しないと再現率が下がる
  • インデクシング時
    • シノニム展開
      • メリット：ヒットする可能性が上がる
      • デメリット：辞書更新時にインデックスの全件更新が必要になる & インデックスのサイズが増えるためインデクシングとクエリのパフォーマンスに影響
    • シノニム正規化
      • メリット：インデックスサイズを小さくできる
      • デメリット：辞書更新時にインデックスの全件更新が必要になる

日本語トークナイザのユーザ辞書

  • メンテナンスコストが大きい
    • 新語のような辞書にないテキストを常に更新して最新の状態に保つ必要がある
    • 更新時にはインデックスを全件更新する必要がある
  • 精度の担保が難しい
    • どのようにトークナイズされるべきかの設定が間違っていると、せっかく登録したキーワードがノイズの原因になる

9.3 ランキングの改善

キーワードと文書の類似度

TFIDFSimilarity

Solr 5 以前のデフォルトの Similarity。名称通りの計算ではなく、tf, idf にも変換がかかっている。

\[score(t, f) = tf(t, f) \times idf(t, f) \times fieldNorm \times Boost\]
  • \[tf(t, f)\]
    • ターム t がフィールド f に含まれる出現頻度
    • 頻度そのままではなく、平方根を取ることで1つのフィールドに大量に同じ単語が含まれる場合の悪影響を軽減
  • \[idf(t, f)\]
    • コレクション内のドキュメント総数 \(maxDocs\) に対する t が f に含まれるドキュメント数 \(docFreqs\) の割合の逆数
    • t を含む文書の数が非常に少ない場合に大きくなりすぎるため、一般には log を取ったものが使われる
    • t を含む文書数が0だとエラーになることと、idf が通常は積の形でスコアに関わることから、小さな値になりすぎないよう必要なところに1を足している：\(\displaystyle 1 + \log{\frac{maxDocs + 1}{docFreqs + 1}}\)
  • \[fieldNorm\]
    • ヒットしやすいドキュメント（文章が長いなど）にかかるペナルティ
    • テキストフィールドに含まれるユニークなターム数の平方根の逆数
  • \[Boost\]
    • クエリブーストとドキュメントブースト

BM25Similarity

拡張版 tf-idf。

ファンクションクエリの活用

ファンクションクエリでできること

  • フィールド値を利用したブースト
    • 日付・CTR・レビュー・ポピュラリティなどをブースト用の素性としてフィールドにセットしておき活用
  • サブクエリによるブースト
    • 特定の条件下でサブクエリを発行し、それにマッチしたフィールドをブースト

これらのブースト値は BM25 によるベーススコアに対して加算 or 乗算で補正を行う。 加算・乗算のどちらになるかはクエリパーサに依存する

ランキング改善の例

  • フレッシュネスブースト
    • 最近登録 or 更新されたものをブースト
recip(ms(NOW,mydatefield),3.16e-11,1,1)
# recip(x,m,a,b) = a/(m*x+b)
# 3.16e-11 は1年をミリ秒で表した数の逆数
  • サブクエリによるブースト（サブクエリのスコアを利用）
    • query 関数の結果得られるスコアを使ってブースト
boost=product(field1,query($hoge))&hoge={!defType=lucene}field2:apple
  • サブクエリによるブースト（サブクエリの結果をフラグとして利用）
    • 特定フィールドの有り無しをフラグにブースト値を分岐させる
boost=product(field1,map(query($hoge),0,0,0.01,1))&hoge={!defType=lucene}field2:apple
  • Relevance Functions によるブースト
boost=product(field1,map(termfreq(field1,'apple'),0,0,0.01,1))

クエリリランキング

  • ファンクションクエリを使った複雑なリクエストをすると、処理が複雑すぎて検索パフォーマンスが劣化することがある。
  • クエリリランキング：
    1. ドキュメントセットを取得する
    2. 取得したうちの上位 N 件だけに対してより複雑なクエリを実行し、ランキングを改善する
パラメータ デフォルト値 説明
reRankDocs 200 元のクエリの Top 何件に対してリランキングを適用するか
reRankQuery - 必須。リランク対象のドキュメントに対して適用するクエリ
reRankWeight 2.0 リランククエリによるスコアに対する重み。(元クエリのスコア + weight * リランククエリのスコア) が最終的なスコアになる 
rq={!rerank reRankQuery=$rqq reRankDocs=1000 reRankWeight=10}&rqq=termfreq(field1,apple)

9.4 検索精度の評価

オフライン評価

予め用意したテストコレクションに対して検索精度を測る。

指標の区分 指標 テストコレクション
ランキングを考慮しない指標 再現率、適合率、F値 ・ドキュメントのセット
・検索クエリのセット
・各クエリ・ドキュメントのペアについての適合/不適合の正解2値ラベル
ランキングを考慮する指標 適合率-再現率曲線、11点補完平均適合率、Precision at k、MAP ・ドキュメントのセット
・検索クエリのセット
・各クエリ・ドキュメントのペアについての適合/不適合の正解2値ラベル
クエリとドキュメントの関連度を考慮する指標 DCG（NDCG） ・ドキュメントのセット
・検索クエリのセット
・各クエリ・ドキュメントのペアについて関連度を表す正解多値ラベル

正解データの作成方法は次のものが考えられる

  • 人手（アノテータ）による作成
  • ログデータによる作成

F値

\[F_{measure} = \displaystyle \frac{1}{\frac{1}{2P} + \frac{1}{2R}} = \frac{2PR}{P + R}\]

算術平均 \(\displaystyle \frac{P + R}{2}\) でなく調和平均を取るのは、P, R の一方だけが極端に高くもう一方が極端に低いシステムを高く評価しないようにするため。

再現率・適合率のどちらかを重視したい場合は、以下のように \(0 \le \alpha \le 1.0\) であるようなパラメータ \(\alpha\) を導入する。

\[F_{measure} = \displaystyle \frac{1}{\alpha\frac{1}{P} + (1-\alpha)\frac{1}{R}}\]

適合率-再現率曲線 (PR 曲線)

あるクエリに対する適合ドキュメントが全部で10件あるとき、ある検索システムで以下のランキング結果が出たとする。

順位 適合 この順位まで見たときの R, P
1 o R = 0.1, P = 1.0
2 x R は変わらない
3 o R = 0.2, P = 0.667
4 x R は変わらない
5 o R = 0.3, P = 0.6
6 o R = 0.4, P = 0.667
7 x R は変わらない
8 o R = 0.5, P = 0.625
9 x R は変わらない
10 x R は変わらない
… … …

上位 N 件をみていき、初めて再現率 R がその値になったときの適合率 P をプロットしていき、R が100%になるまでの R-P 曲線を描く。

20171029_precision_recall

グラフが右上にある（= 再現率が上がっても適合率が下がりにくい）ほど精度が高いと言える。

補完適合率

  • 表のように、再現率を上げていくと適合率は通常上がったり下がったりする（0.667 → 0.6 → 0.667）
  • 単調減少する扱いやすい値として、その再現率以上における最大の適合率の値（補完適合率）を使うこともある
  • 上の例だと、R = 0.3 以上における P の最大値は R = 0.4 のときの 0.667 なので、R = 0.3 の補完適合率は 0.667 となる

11点補完平均適合率

  • 前述の適合率-再現率曲線は特定の1つのクエリについてしか評価できない。 → テストセットの全クエリについて、ひとまとめに評価できるグラフが欲しい
  • 11点補完平均適合率
    • 適合率-再現率曲線の各再現率レベルにおいて、評価対象の全クエリの補完適合率の平均を取ったもの
    • 適合率0.0〜1.0の範囲を0.1刻み11点で平均を取ることが名称の由来

Precision at k (P@k)

  • 上位 k 件まで見たときの適合率
  • それぞれのクエリに特有の適合ドキュメント数の影響を受けやすく、全クエリで平均を取ることが難しい
  • Precision@k を参照

MAP

= Mean Average Precision

MAP を参照

DCG/NDCG

  • Discounted Cumulative Gain / Normalized DCG
  • クエリにドキュメントが適合する/しないの2値ではなく、どの程度関連するかという関連度を考慮した指標で、以下の仮定に基づく
    • 関連度の高いドキュメントは、それよりも関連度の低いドキュメントより有用である
    • 下位にランキングされるドキュメントは精査されにくいため、ユーザにとって有用性が低い
  • 変数定義：
    • \(DCG\left(j, k\right)\)：クエリ \(q_j\) に対する上位 \(k\) 件までの検索結果の評価
    • \(rel_{ji}\)：クエリ \(q_j\) と \(i\) 番目にランキングされたドキュメントとの関連度。あらかじめ人手で割り当てる
    • \(IDCG\left(j,k\right)\)：上位 \(k\) 件が理想的に並んだ場合の DCG（Ideal DCG）
  • \[DCG\left(j, k\right) = \displaystyle \sum_{i=1}^{k} \frac{2^{rel_{ji}}-1}{log_2{(i+1})}\]
  • \[NDCG\left(j, k\right) = \displaystyle \frac{DCG\left(j,k\right)}{IDCG\left(j,k\right)}\]

オンライン評価とオフライン評価

　 オフライン評価 オンライン評価
メリット データセットを作れば何度も試行錯誤ができる サービスの改善効果を直接推定できる
デメリット ・データセット作成コストが高い
・サービスに影響しうる複雑な要因を扱えない		 ・現在のサービスが劣化するおそれがある
・試行錯誤の回数が限定的

A/B テスト

一部のユーザに対して新しい手法のシステム、残りのユーザに対して従来手法のシステムを適用し、KPI の違いを調べる評価手法。 時期的なユーザの振る舞いの違いが影響しにくい。

  1. テストユーザのランダムサンプリング
  2. KPI の測定
  3. 統計処理・結果の解釈

の3手順からなる。

KPI としては以下の様なものが考えられる。

指標＼改善目標 再現率 適合率 ランキング
クリック率 o o o
レスポンスタイム o o o
ヒット件数 o o x
ゼロ件ヒット回数 o x x
サーバ負荷 o △ o

結果の解釈において、施策の有意性についてはカイ2乗検定がよく使われる。

A/A テスト

A/B テストの仕組みが正しく作られているかの確認のために実施するもので、A と B のテスト条件を同一にした A/B テストを本番環境で実施し、以下について確認を行う

  • 各テスト条件が想定通りの数でランダムサンプリングされているか
  • KPI の値に有意差がないか

A/A テストの実施により、次のことが確認できる

  • A/B テストの実装に問題がないこと
  • 偶然の範囲内でどれくらい値が揺らぐのか

ボンフェローニ法

例えば有意水準5%で様々なテストを10回行った場合、全てのテストで有意差が出たとしても、\(1-(1-0.05)^{10} > 0.40\) すなわち40%以上の確率で最低1つは偽陽性（実際には有意差がない）となる。 これを解決するための手法の1つにボンフェローニ法があり、有意水準に応じたp値をテスト回数で割り、有意差の判定基準を厳しくする。 上の例なら、\(p < 0.05/10\) の場合に有意差ありと判定されることになり、テストを10回しても偽陽性が起こる確率は \(1-(1-0.05/10)^{10} < 0.05\) と大幅に改善される。

9.5 機械学習による検索の改善

Learning To Rank

機械学習を使い、ドキュメントのランキングアルゴリズムを導出する手法のこと。

ex. rankSVM

  • ランキングアルゴリズムの式を最適化
    • Solr で各フィールドの類似度の和を取るときのブースト値（重み）を導出する、など
  • クエリ・ドキュメント・関連度のデータを pair-wize 法で解釈
    • pair-wize: 単一のクエリで2つのドキュメントの関連度の大小を比較する手法
  • SVM を利用

9.6 Solr をレコメンドエンジンとして使う

  • レコメンドは検索の特殊ケース
    • ユーザの検索行動という情報が足りないだけで、レコメンドもランキングの一種
  • Tips
    • ファンクションクエリを活用すれば自由度の高いレコメンドアルゴリズムが実現可能
    • クリックログを用い、そのドキュメントを購入したユーザと行動が近いユーザにそのドキュメントをレコメンドする
    • etc…

（以下略）