stop-the-world

takuya-a のブログ

論文メモ: Accelerated Query Processing Via Similarity Score Prediction (SIGIR 2019)

IR Reading 2019秋で標題の論文を紹介しました。 発表で使ったスライドは以下です：

speakerdeck.com

以下は、この論文を読んだときのメモです。

概要

  • 検索エンジンで top-k のクエリ処理を高速化するのが目的
  • クエリ処理中の動的な文書の pruning（枝刈り）に着目
  • 通常のアルゴリズムでは、それまでに処理した文書の top-k のスコアを保持
    • このスコアより小さいスコアの文書はスキップしてよい
    • クエリ処理中の top-k のスコアを閾値として使っている
  • この方法はロスレス、つまり正確な top-k の文書が得られる
  • 閾値の初期値は通常、文書集合のなかの最低のスコアを使う
  • この論文では、機械学習を使ってクエリの特徴量から最終的な閾値の予測をする
    • これにより、多くの文書をスキップできるようになる = 高速化できる
  • 予測した閾値が実際より高いと結果が不正確になる
    • 正確な結果を得るためには再計算が必要になる
    • 予測値が実際より低いとより多くの文書を処理しないといけない = 遅くなる

1. Introduction

  • Web 検索においてクエリ処理に多くの電気代、ハードウェアコストがかかっている
  • その効率を上げることで金銭コストと環境への負荷を減らせる
  • ほとんどの Web 検索において、ターム（単語）は文書において独立に生起し、スコアは各タームの貢献度 (contribution) の総和として計算できると仮定している
    • 少なくとも最初のフェーズでは（リランキングではもっと複雑なモデルで計算されることもある）
    • 各タームの貢献度は文書のインデキシング時に決定できる（事前計算可能）
  • k 個のスコアトップの文書をクエリへの戻り値とする
    • そのままユーザに表示してもよいし、リランクフェーズへの入力としてもよい
  • クエリ処理の効率化の方法として MaxScore や WAND が開発された
  • どちらも、クエリ処理中の top-k スコアを閾値 \theta とし、スコアがそれ以下となる文書をスキップする
  • すべての文書についてクエリ処理すると、 \theta は、その文書集合 D に対するクエリ Q の top-k スコア \Theta_k (D, Q) に収束する

f:id:takuya-a:20191028010014p:plain

Research Questions

  • RQ1
  • RQ2
    • もし前もって \Theta_k (D, Q) を推定できるなら、その事前知識によってどの程度クエリ処理を速くできるか？
  • RQ3
    • \Theta_k (D, Q) の事前知識を使って MaxScore、WAND、BMWのような手法を改良できるか？

2. Background

事前知識と関連研究

Term-Weighted Similarity Scoring

  • クエリ Q = {t_1, t_2, ..., t_q} （q 個のタームを含む）と文書 d に対しての類似度スコア (similarity) として以下の形を仮定する:
  • S(d, Q) = f_1(d) + \Sigma_{i=1}^{q} f_2(t_i, Q) \cdot C(t_i, d)
    • f_1(\cdot): 文書のみに依存する関数
      • インデキシング時に事前計算可能
    • f_2(\cdot, \cdot): タームとクエリの関数
      • 文書に依存しないのでクエリ処理時に1回だけ計算すればよい
    • C(t,d): 文書 d におけるターム t の相対的な重要度
      • クエリに依存しない
  • この形は BM25 にも当てはまる
    • f_1(\cdot) = 0 かつ f_2(\cdot, \cdot) は定数

Query Processing

  • 一般的な転置インデックスでのクエリ処理を考える
    • タームとポスティングリストが保存されている
    • ポスティングリストには文書 ID （ソート済み）の集合が入っている
    • その他、タームごとの最大スコアなどの補助的なデータを格納できるとする
  • document-at-a-time (DAAT) によるクエリ処理を想定
    • タームごとにポスティングリストを処理するのではなく、
    • 複数のポスティングリストを同時にカーソルで処理
    • すべてのカーソルを一番前にセットし、その文書のクエリ処理が終わったら後ろにずらす
    • すべてのカーソルが最後までいったら終了、top-k の文書集合を返す
  • WAND
  • BMW
    • 最新の研究では block-max WAND を可変長ブロックにした手法が提案されている
    • この研究では可変長ブロック版の block-max WAND を使う
  • Q_k
    • 各ポスティングリストにおいて、 k 番目に大きい部分スコア（ C(t, d) ）をインデックスに保存しておく
      • k はよく使用されるものについてだけ記録（10, 100, 1000など）
    • クエリ Q は複数のタームを含むが、上記のスコアのうち、最大のものを Q_k とする
    • Q_k は閾値 \theta の安全な初期値として使える [13, 25]
      • ただし、「f_1(\cdot) = 0 かつ f_2(\cdot, \cdot) が定数」が成り立つときのみ
      • BM25 ではこれが成り立つ
    • この Q_k より良く \Theta_k を推定するのが、この研究のゴール

Machine Learning for Efficiency

  • 検索結果候補を生成するステージと、LTR 取得ステージ（LTR retrieval stage）がある
    • ほとんどの効率ベースの機械学習研究は後者にフォーカスしている
  • プロダクションの検索エンジンにおいて、LTR で効率ベースの機械学習の手法としては LambdaMART や GBRT がいまだ SOTA だと考えられている
    • それらの改良手法も多く提案されている
  • リランクされる文書数を減らすアプローチもある
    • 初期のステージでの効率改善のために ML を適用した研究は少なく、ML の予測コストが容易にそれによるベネフィットを超えてしまう
  • 近年の LTR の研究はニューラル IR にフォーカスしている
    • 効率的なエンドツーエンドの検索についての研究もあるが、効率という意味ではこの研究と競合するとは言えない

3. Exploring Potential Gains

Oracle Evaluation

  • RQ2: もし前もって \Theta_k (D, Q) を推定できるなら、その事前知識によってどの程度クエリ処理を速くできるか？
  • \Theta_k (D, Q) をクエリ処理の前に計算しておき、各枝刈りアルゴリズムに閾値として渡してしまう
    • 最適な閾値が分かっている状態での、MAX パフォーマンスを計測
  • 実験条件
    • Gov2 データセット、5,000 クエリで実行時間をミリ秒単位で計測
    • 枝刈りアルゴリズムとして MaxScore, WAND, BMW の 3 つを使って比較
    • \nabla: そのスコア関数でとりうる最低のスコア（BM25なので0に設定）を \theta の初期値として実行
    • Q_k: クエリ Q において k 番目に大きい contribution （部分スコア）
    • \Theta_k (D, Q): オラクルを \theta の初期値として与えて実行

f:id:takuya-a:20191028005928p:plain

  • 実行時間の単位はミリ秒
  • オラクルを使うと \nabla よりも 30% から 50% ほどスピードアップ

Sensitivity

f:id:takuya-a:20191028010103p:plain

  • 初期値を \Theta_k の 0% から 100% まで変えながらクエリの実行時間を計測
  • \Theta_k の 75% 以下の初期値では十分なゲインを得られない
  • \Theta_k におけるスピードに匹敵するには 0.9 \Theta_k くらいの初期値でなければならない

Failure Detection

  • \Theta_k の推定値 \Theta_k が実際より大きいとき、得られる top-k の結果は正確ではなくなる
  • 計算結果が k 件になっているかどうかをチェックして、結果が正確かどうかを確認できる場合もある
  • 実際にはもっと微妙なケースがあり、ヒープには k 件の文書があるが、その最小スコアが推定値 \hat{\Theta}_k より小さい場合がある
  • このような場合、推定値が大きすぎたということなので、全体の再計算が必要になる
  • ただし、ヒープの最小のスコアを新たな初期値とできる
    • すくなくともそれ以上のスコアをもつ文書が k 個以上あることがわかっているため
    • この再計算は正確であることが保証される

Query Processing Revisited

f:id:takuya-a:20191028010138p:plain

  • L2: 閾値の予測値を \theta の初期値とする
  • L3: 優先度付きキュー（ヒープ）の最小スコア
  • L5 - L6: スコアの upper bound が \theta を超える文書だけスコア計算
  • L7 - L8: 文書のスコアがヒープの最小スコアより大きければヒープに入れる
  • L9 - L13: ヒープサイズが k 個を超えたときの処理
  • L15 - L17: この場合、正確な top-k が得られていないので再計算

4. Threashold Prediction Models

  • 複雑なモデルを使うと予測精度が上がる可能性があるが、予測が遅くなる
  • Table 1 では速い場合、top-k クエリは 5-20 msec で実行が完了するので、閾値の予測によってクエリを速くするためには、もっと短い時間で予測を完了する必要がある
    • GPU を使うと転送コストが高い
  • CPU 時間で1ミリ秒以内に予測できるシンプルなモデルを調べることにする

Algorithmic Predictor

  • \nabla が1つめのベースライン
  • Q_k を2つめのベースラインとする
    • \nabla よりは予測値として良く、決定的

Probabilistic Predictor

  • 確率的なモデルを最初のアプローチとして採用
    • 予測値 \hat{\Theta}_k の分布を生成する確率モデル
  • 学習後に分布が見られるメリットがある

f:id:takuya-a:20191028010216p:plain

  • ガウス分布のときの例
  • q は quantile（分位点）
  • 学習後の分布で、 q を決めてそれを予測値とする方法もある
    • q = 0.5 は攻めすぎ（overestimate したときのペナルティが大きいため）
    • q = 0.1 は保守的（underestimate になりがちで計算コストは高いまま）
  • 非対称な損失関数を考えることでペナルティを定式化し、その効果を織り込むことができる
    • overestimate に対して underestimate の \alpha 倍の損失を与える
  • Minimum Bayes Risk (MBR)
    • 予測分布の上で、損失の期待値が最小となるような \hat{\Theta}_k を選択できる
    • 最適値は 1/(\alpha + 1) の quantile となることが証明されている [6]
    • たとえば、 \alpha = 3 のとき 0.25 quantile (四分位点) が最適
  • 確率的なアプローチの利点
    • 損失関数がモデルから独立しているので、
      • テスト時に何回もモデルを訓練することなく、並列で予測値を取り出せる
      • クエリごとの損失が定義できる
  • 確率的なアプローチの欠点
    • 高速に予測できるようなモデルは限られている
    • モデルには Bayesian Linear Regression (BLR) を使った
    • これは解析的に（閉形式で）解が求められるので高速に計算できる
    • サンプリングのような古典的なベイズ推論では遅すぎる

Loss-Based Predictor

  • 損失関数を使った機械学習モデルも考える
    • 分布を生成できないが、与えられた損失関数に対して直接学習しようとする
  • 損失関数には非対称にした Huber loss [22] を採用
    • over-estimate に対してより大きな損失を与える

f:id:takuya-a:20191028010333p:plain

  • マルチレイヤーパーセプトロン (MLP) を採用
    • MLP-L2: 2層（隠れ層が 2）の MLP
    • MLP-L4: 4層（隠れ層が 4）の MLP
    • いずれも CPU でも効率的に計算可能
  • MLP の学習
    • 隠れ層のユニット数はすべて入力層と同じ
    • Adam で学習
    • 学習率は 0.001
    • dev set で early stopping
    • バッチ正則化
    • ドロップアウト率 0.25
  • 損失ベースのアプローチの欠点
    • 損失が訓練時にわかっている必要がある
    • 異なる損失には異なるモデルが必要
      • クエリごとに損失を変えようとしたらたくさんのモデルが必要になる
    • 損失を変えようとしたら再訓練しなければならない

Data, Features and Costs

  • モデルの学習に使ったクエリログ
    • 2006 Microsoft Query log
    • 8,073,821 クエリ
  • データセット（詳細は Section 5 で）
    • Gov2
    • ClueWeb09B
  • 特徴量
    • Table 2
    • インデックスに保存
    • 1ポスティングあたり 7.5 bits (Gov2) 6.6 bits (ClueWeb09B)
  • 学習後のモデルサイズ
    • 1.0 MB (BLR), 1.7 MB (MLP-L4), 0.9 MB (MLP-L2)
  • 学習は 30 分以内に終わった

Prediction Speed

  • 0.6 ms (MLP-L2)
  • 0.9 ms (MLP-L4)
  • 0.6 ms + 0.1 ms (BLR)
    • クエリの予測分布を得るのに 0.6 ms
    • 分位点を得るのに 0.1 ms
  • C/C++ から Python を呼ぶオーバーヘッドを含んだ実行時間
    • プロダクションでは C/C++ で書けばもっと速い

5. Experiments

Data Resources

  • Gov2
  • ClueWeb09B
    • 2009年にクロールされた 5000 万の Web 文書
  • クエリログ

Software Resources

  • Indri でインデキシング
  • recursive graph bisection で処理
  • PISA experimentation platform に与える
  • BMW は可変長ブロックのものを使い、ブロックに含まれる要素数は平均 40

Model Distribution Trade-Offs

f:id:takuya-a:20191028010421p:plain

6. Refinements

Over-Prediction Risk

  • 閾値を overestimate したとき、 Algorithm 1 では L15 - L17 で再計算が走る
  • これが重い

f:id:takuya-a:20191028010454p:plain

  • \hat{\Theta}_k が実際の値（オラクル）より大きかったときに、MaxScore, WAND, BMW でどれくらい再計算が走りうるか
  • 閾値の初期値を、オラクルより徐々に大きくしていって、各アルゴリズムが返す結果が正しい確率を調べた
    • ただし tie-breaking のために文書の順番が入れ替わるのは許す
  • データセットは ClueWeb09B、 k = 1000 で固定
  • BMW は文書をスキップする能力が高いので、overestimate に対して頑健ではない

Reducing the Re-Computation

f:id:takuya-a:20191028010523p:plain

  • クエリには q 個のタームが含まれている
  • 最大で [tex:2q - 1] のタームの組み合わせがある
    • それぞれの組み合わせごとに U_bound が計算できる
    • サブクエリと呼ぶことにする
  • いずれかのサブクエリの U_bound が \hat{\Theta}_k を超えているはず
    • 少なくとももとのクエリ（すべてのタームを含む）は超えている
  • また、いずれかのサブクエリの U_bound は h_threshold を下回っていることが予想される
    • これらのタームの組み合わせは安全に無視できる
  • この範囲 [h_threshold, \hat{\Theta}_k] の範囲に U_bound が入っているサブクエリだけ、スコアを評価すればよい
    • スコアはこれらのタームの貢献度 C(t, d) を足し合わせる
  • このサブクエリの評価では、その中のタームは AND (conjunction) クエリでよい（件数は少ない）
    • 非常に高速に処理できる
  • 改良済みのアルゴリズムは Algorithm 2

Overestimation Refinements

f:id:takuya-a:20191028010556p:plain

  • Algorithm 1 と 2 を比較
  • すべてのパーセンタイル、および quantile (0.5, 0.3, 0.1, 0.05, 0.01) で Algorithm 2 のほうが速い
    • quantile 0.5 はよりアグレッシブな（大きい）閾値
  • 最大で 22% 速くなっている
    • quantile が大きいほうがより性能差がある

f:id:takuya-a:20191028010623p:plain

  • Algorithm 1 と 2 で、再計算にかかるコストを比較
  • Algorithm 2 は再計算のときにスコア計算が必要となる文書数が明らかに少ない
    • この改良で効率的になっていることが示されている

7. Conclusion

  • ヒープの閾値が予測できることを示した (RQ1)
  • また、それらが動的枝刈りアルゴリズムのパフォーマンスを改善することを示した (RQ2)
  • アルゴリズム的な改善が可能であることも示した (RQ3)

感想

  • 損失の係数 \alpha をどうやって決めるか
    • MBR に与える \alpha や MLP の Huber Loss の q はハイパーパラメータだが、再計算のペナルティはデータセット上で計測できるはずなので、直接、損失関数に組み込んでしまってもいいのではないか？
    • 損失関数の \alpha はクエリごとに変えるべきだろうか？
  • k 番目のスコアを保存しているが、 k \in {10, 100, 1000} と決め打ちであり恣意的
    • これは Q_k を初期値として使うアプローチも同様
    • パフォーマンス最適化のために k を変えるには再インデキシングが必要
  • 確率モデルベースの手法は、損失ベースのものに比べてモデルの汎用性がある
    • とはいえ、コーパスの性質が変わると再学習はしたほうがよさそう
    • 日本語と英語のコーパスで同じモデルでいいとは思えない
  • 決定的な方法（ Q_k を使う）でも十分では？
    • Table 4 をみると、ベースラインからの差はそれほど大きくない
    • Algorithm 2 で多少改善するとはいえ、差分はせいぜい 20% 程度
    • 枝刈りアルゴリズムの差のほうが大きい
    • 仕組みがシンプルな Q_k のほうが取り回しやすい（機械学習いらないし）
  • もっといいモデルを作れる余地はある

参考

動的枝刈りアルゴリズムの詳細については以下の解説記事がおすすめ！