stop-the-world

takuya-a のブログ

論文メモ: Fast Approximate Filtering of Search Results Sorted by Attribute (SIGIR 2019)

前回に引き続き、 SIGIR 2019 の efficiency に関する論文を読んだメモです。

前回: stop-the-world.hatenablog.com

以下はチーム内でこの論文を紹介するときに使う予定のスライドです。あわせてご覧ください。 speakerdeck.com

1. Introduction

  • 通常、ユーザが検索で欲しいのは relevance を最大化した SERP
    • Web 検索、SNS、ストリーミングサービス、ECサイトなど
  • 多くのサービスでは、クエリに関連しつつも属性(時間やアイテムの価格など)でソートした検索に対応している
  • しかし、ソート順を指定すると、あまり関連のない結果が検索結果にたくさん現れ、ユーザ体験を損なう
    • たとえば amazon.com で "iphone" というクエリで検索すると、10万件以上の結果が得られる
    • 関連度順だと、いくつかの iPhone のモデルと関連するアクセサリが表示される
    • 価格の安い順にしたとき、最初のページには安い価格のカバーやガジェットが表示される
    • こうなると、ユーザは関連のあるアイテムを見つけるまでに、いくつかのアイテムを見て精査する必要があり、ユーザ体験がよくない
  • このような問題は Filtering task として扱うことができる
  • ソート順を崩さずに、元のリストから全体的な effectiveness を最大化する最大 k 件の結果を得るのがゴール
  • Filtering@k
    • relevance のリスト $R = [r_1, ..., r_n]$ (順序つき)が与えられる
    • メトリック $Q$ を最大化する、最大 $k$ 件の部分リストを返す
  • DCG のようなメトリクスを考慮した Filtering@k の解を見つけるのは難しい
  • 実際、最適な解を得るには、リストの最も関連性の高い結果を選択するだけでは不十分
    • かつ、k 件のサブシーケンスのみを考えるだけでもいけない
  • たとえば、$R = [2, 2, 4, 1]$ のとき、最適な DCG@3 は最初の2つの要素をフィルタすることで得られる($[4, 1]$ が最適な結果)
  • Filtering@k の先行研究: Spirin et al. [14]
  • この論文では $\epsilon$-Filtering という手法を提案
    • $\epsilon$ というパラメータで近似誤差をコントロールし、効率と効果をトレードする
    • $(1-\epsilon)$-optimal filtering
    • 時間計算量は $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$
  • $\epsilon$-Filtering を2つの公開データセットで実験し、速度が向上することを確かめた

2. Related Work

Optimal filtering

  • 時間計算量 $\Theta (nk)$ で最適な結果(近似なし)を計算できる
    • 動的計画法(メモ化)を使って計算
    • $n$, $k$ が大きくなると遅い

Heuristics

  • Cutoff-OPT
    • あらかじめ決めた relevance の閾値でフィルタしてから OPT でさらにフィルタ
    • 最悪ケースではエラー率(精度)の保証がない
      • 閾値の設定によるため
    • 時間計算量は改善せず最悪ケースで $\Theta (nk)$
  • Top$k$-OPT
    • top-$k$ のリストを求め、それをさらに OPT でフィルタする
      • $k$ 個未満のリストにすることでメトリックを最大化できることもあるため
    • 0.5-optimal(近似によるエラー率が 50%)であることが証明できる
    • 時間計算量は最悪で $\Theta (n \log{k} + k^{2})$

3. Approximate Filtering

3.1 Analysis of heuristics

  • Cutoff-OPT と Top$k$-OPT の効果 (effectiveness) を解析した
    • Cutoff-OPT は OPT よりも悪い
    • Top$k$-OPT は 0.5-optimal

Cutoff-OPT

  • パフォーマンスの理論保証はまったくない
  • 閾値の設定によるため
  • 以下のような最悪ケースがある
    • まったくフィルタできないパターン
      • このとき、OPT の時間計算量を改善できない
    • すべてをフィルタしてしまうパターン
      • このとき、$\Theta(nk)$ の時間がかかり、解も当然悪い

Top$k$-OPT

  • 最悪時間計算量は $\Theta(n \log{k} + k^{2})$
    • $\Theta(n \log{k})$ で top-$k$ の要素を選択
    • そのあとそれらの要素に OPT でフィルタするのに $\Theta(k^{2})$ かかる
  • Theorem 1.
    • Top$k$-OPT は 0.5-optimal

3.2 $\epsilon$-Filtering

  • Cutoff や Topk などのヒューリスティックスではエラー率をコントロールできない
  • $\epsilon$-Filtering はエラー率を $\epsilon$ 以下に保証した近似解を、時間計算量 $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$ で見つける
    • $0 < \epsilon < 1$
  • $\epsilon$-Filtering は以下の3ステップからなる
    1. Right pruning
    2. Discretization
    3. Thresholding

Right pruning

  • ロスレスなフィルタリング(最適な結果に含まれるものを落とさない)
  • 右側に $k$ 個以上の自分以上の relevance をもつ要素がある場合、その要素を落とす
  • 例:元の relevance のリストが $R = [0.9, 1.0, 1.0, 1.0]$ で $k = 3$ のとき $0.9$ を落とす
    • $0.9$ を含むようなすべての解は最適ではない
    • 実際、 DCG 最大の解は $[1.0, 1.0, 1.0]$
  • right-$k$-maximal elements
    • 右側に自分以上の relevance をもつ要素が $k$ 個未満であるような要素
      • (つまり「落としてはいけない」要素)
    • $[0.9, 1.0, 1.0, 1.0]$ のとき $0.9$ は right-3-maximal でない
      • すべての $1.0$ は right-3-maximal
    • $[1.0, 1.1, 1.2, 0.9]$ のとき $1.0$ は right-3-maximal
      • というか全要素 right-3-maximal
    • 最適な解は right-$k$-maximal elements のみからなる (Lemma 4)
  • Right pruning は right-$k$-maximal elements だけを残すフィルタリング

f:id:takuya-a:20191109191841p:plain
Right pruning のアルゴリズム

  • 補助データ構造として優先度付きキューを使う
    • $\Theta (n \log k)$ で top-$k$ の要素を計算できるデータ構造
  • 後ろから配列を走査する
    • 優先度付きキューで最低の relevance よりその要素の relevance が大きければ結果リストに入れる
  • 最後に結果リストを reverse すれば right-$k$-maximal elements が求まる
  • ただし、Right pruning はフィルタリングの効率について理論的な保証はない
  • 元のリストによっては、まったくフィルタできないことがありえる
  • $[1.2, 1.1, 1.0, 0.9]$ のときすべての要素は right-3-optimal
  • 次のステップの Discretization でこのようなケースを改善する

Discretization

  • Right pruning での最悪ケースにおいて、選択される要素数を減らすのがこのステップの目的
  • $R$ から、以下を満たすような新しいリスト $R_{\epsilon}$ をつくる
    • (要素数は $R$ と同じで)ユニークな要素数が $R$ より少なくなるように
    • $R_{\epsilon}$ に対して最適フィルタリングをかけたとき、少なくとも元の relevance の $(1-\epsilon)$ 倍以上を保証するように
  • これにより、 Right pruning は最適な解をほぼ保ったまま、より効果的に要素をフィルタすることができる
  • このステップでは近似誤差と、得られるユニークな要素数トレードオフを行う
  • $r_{max}$ をリストの最大の relevance、 $r_{min}$ を最小の relevance とする
  • 範囲 $[r_{min}, r_{max}]$ を m 個のインターバルに分割するのが、Discretization ステップの基本的なアイデア
    • 同じインターバル内の要素は、そのインターバルで最小の値に近似する
  • 近似誤差 $\epsilon$ とインターバルの数 m を保証するように $[r_{min}, r_{max}]$ をどう分割するかがトリッキー
    • $g(r) = 2^{r} - 1$ を DCG のゲインとする
    • 分割した部分の最小値と最大値のゲインの比が、少なくとも $(1-\epsilon)$ になるようにインターバルへと分割する
    • このように作ったインターバルを $\epsilon$-intervals と呼ぶ
  • 前に見た、 Right pruning での最悪ケースで、このステップがどのように実行されるかを次の例で見る
  • Example 5.
    • $R = [3.00, 2.99, 2.98, ..., 0.01]$(300個の要素をもつリスト)
    • $\epsilon = 0.5$(望んでいる近似誤差 50%)
    • ゲイン (gain function) $g(r) = 2^{r} - 1$ (DCGを仮定)
    • $R$ の $\epsilon$-intervals は以下のような10個のインターバル
      • $[0.01, 0.019)$
      • $[0.019, 0.039)$
      • ...
      • $[1.45, 2.17)$
      • $[2.17, 3.0)$
    • それぞれのインターバルにおいて、最大のゲインと最小のゲインの比は $(1-\epsilon)$ におさまる
      • たとえば最後のインターバルでは $g(2.17)/g(3) \approx 0.5$
    • $R_{\epsilon}$ は $[2.17, ..., 2.17, 1.45, ..., 1.45, ..., 0.01]$
      • (要素数は変わらず 300個)
  • 以下の Lemma 6 は Lemma 4 を $R_{\epsilon}$ に拡張し、
    • $R_{\epsilon}$ の right-$k$-maximal elements が $R$ の $(1 - \epsilon)$-optimal なフィルタリングを見つけるのに役立つことがわかる
  • Lemma 6.
    • $R_{\epsilon}$ の right-$k$-maximal elements のみからなる $R$ の $(1-\epsilon)$-optimal なフィルタリングが存在する
  • $R$ を $R_{\epsilon}$ に離散化すると、ユニークな要素数が $n$ 個から $m$ 個に減る
  • また、以下の性質は $m$ の上限を与える
  • Property 7.
    • $R$ の $\epsilon$-intervals の数 m は、$m \leq \lceil \log_{(1-\epsilon)} (g(r_{min}) / g(r_{max})) \rceil$ を満たす
  • Discretization と Right pruning を組み合わせることで、フィルタによって選ばれる要素数を最大でも $mk$ にできる
    • m は Property 7 の右辺によって bound される
  • しかし、 m の上限は $R$ の最大の relevance $r_{max}$ と最小の relevance $r_{min}$ の両方に依存している
    • これらの比が大きければ、 m の上限も大きくなってしまう
  • 実際、離散化が効率的でなくなるような、敵対的な $R$ を設計することができる
    • $r_{min}$ を固定し、 m が $n$ と等しくなるように $r_{max}$ を十分に大きくすると可能
  • このとき、$R$ はそれぞれの $\epsilon$-interval につき 1 つだけの要素をもつ、単調減少するリストであり、 $R_{\epsilon}$ は $R$ と一致する
    • Right pruning してもすべての要素($m = n$)が選ばれてしまう

Thresholding

  • このステップでは、与えられた閾値を下回る要素をフィルタする
  • この方法で $r_{min}$ の値を大きくすることができ、結果として $\epsilon$-intervals の数 m を減らすことができる
  • このステップで得られるリストを $R^{-}$ とする
  • 閾値は以下を満たすように選ばれる
    • $R^{-}$ に対する最適フィルタリングの relevance は、もとの $R$ に対してのものの少なくとも $(1-\epsilon)$ 倍になる
    • m の値が常に十分小さくなることが保証される
  • Example 8.
    • $R = [5, 0.1, ..., 0.1]$(要素は10個)
    • 最適フィルタリングはすべての要素を残したときで、DCG はおよそ 31.25
    • すべての 0.1 の要素をフィルタしたとき、 $R^- = [5]$
    • $R^{-}$ の最適フィルタリングは DCG が 31 になる
      • 0.99-approximation
  • Lemma 9.
    • $R$ から、閾値 $t = g^{-1}(\epsilon g(r_{max}/k))$ 以下の要素をフィルタし、残りの要素を $\epsilon$-intervals で離散化したリストを $R_{\epsilon}^{-}$ としたとき、 $R_{\epsilon}^{-}$ の最適フィルタリングは $(1-\epsilon)$-approximationとなる
  • Discretization と Thresholding を組み合わせて、 $R$ のユニークな要素を減らすことができる。実際、閾値 $t$ は $\epsilon$–intervals の数を制限し、right-$k$-maximal elements の計算に関係するユニークな要素数を制限する
  • とくに、Property 7 の $r_{min}$ を Lemma 9 のなかの閾値 $t$ で置き換えると、すぐに以下の性質を得る
  • Property 10.
    • $R_{\epsilon}^{-}$ の $\epsilon$-intervals の数 m は、 $m \leq \lceil \log_{(1-\epsilon)} (\epsilon / k) \rceil$ を満たす
  • $R_{\epsilon}^{-}$ の $\epsilon$-intervals の最大の数を bound するというこの性質は、$R$ やその要素からは独立である
  • 各 right-$k$-maximal element $r$ の後ろには、 $r$ 以上の relevance をもつ要素が最大 $k$ 個続くため、$R_{\epsilon}^{-}$ の right-$k$-maximal elements の数は、$\epsilon$ と $k$ のみに依存する
  • 実際 $R_{\epsilon}^{-}$ の right-$k$-maximal elements は最大でも $km \leq k \log_{(1-\epsilon)}{(\epsilon/k)}$ である
  • $R_{\epsilon}^{-}$ の right-$k$-maximal elements をみつけるこの方法を、 $\epsilon$-Pruning とする

f:id:takuya-a:20191109192005p:plain
ε-Pruning のアルゴリズム

  • $R_{\epsilon}^{-}$ の right-$k$-maximal elements の最大の数は $km$ なので、 Algorithm 2 の時間計算量は $\Theta (n + km \log{k})$
    • 最初の項は $R$ を線形にスキャンするコスト
    • 2つ目の項は、サイズ $k$ の優先度付きキューを $\Theta (km)$ 回更新するコスト
  • このように、 $\epsilon$-Pruning は、効率的かつ効果的に OPT で処理される要素の数を減らすことができる

$\epsilon$-Filtering

  • $\epsilon$-Filtering は 2 つのフェーズからなる
    • $\epsilon$-Pruning してから OPT にかける
    • $\epsilon$-Pruning により $R_{\epsilon}^{-}$ の right-$k$-maximal elements をみつける
  • 以下の定理は、 $\epsilon$-Filtering が $(1-\epsilon)$-最適な解をみつけ、近似誤差 $\epsilon$ を通して効果と効率のトレードオフをとることを示す
  • Theorem 11.
    • $\epsilon$-Filtering は $(1-\epsilon)$-最適なフィルタリングを時間計算量 $\Theta (n + k^{2} \log_{(1 - \epsilon)}{(\epsilon / k)})$ で見つける
  • Theorem 11 の証明
    • $\epsilon$-Pruning の時間計算量は $\Theta (n + km \log{k})$
    • OPT に渡される要素数は $\Theta (km)$
    • そのため、OPT の時間計算量は $\Theta (k^{2} m)$
    • Property 10 より $m \leq \lceil \log_{(1-\epsilon)} (\epsilon / k) \rceil$ なので、命題は証明された
  • $\epsilon$-Filtering は OPT と 3つのステップ(right pruning, discretization, thresholding)を組み合わせることで relevance-aware のフィルタリング問題を解決する
  • $\epsilon$-Filtering はフィルタ済みのリストに関しての強い保証と、近似誤差 $\epsilon$ による効率と効果のトレードオフを提供する

Distributed setting

4. Experiments

  • 2つのデータセット(GoogleLocalRec, AmazonRel)を使った
    • どちらも、クエリに対して何らかの relevance をもつリストが紐付けられたデータセット
  • GoogleLocalRec
    • Google Local のデータ(場所が入っている)から作成
    • sequential recommendation [11] タスクの SoTA である TransFM という推薦システムをデータに適用
    • 各ユーザに対して、そのユーザとある場所がどのくらい relevant か、というデータ
    • 10,000 ユーザ、各ユーザに対してちょうど 16,000 のレコメンデーション
  • AmazonRel
    • Crowdflower Search Results Relevance という Kaggle コンペのデータ
      • Amazon の商品データで拡張
    • Kaggle コンペの winning solution を使ってアイテムの relevance を計算
    • 250 クエリ
      • データセットに含まれる 260 クエリのなかから、結果が 500 件未満の 10 クエリを除いたもの
    • 1クエリあたり平均で 100,000 個の要素 (relevance) をもつリスト

Metric

  • 2 つのメトリックで比較
    • DCG([$r_1, ..., r_n$])
      • \Sigma^{n}_{p=1} \frac{2^{r_{p}} - 1}{\log_{2}{p + 1}}
    • DCG-LZ([$r_1, ..., r_n$])
      • \Sigma^{n}_{p=1} \frac{r_p}{p}

Filtering methods

  • Spirin+[14] で提案された3つのアルゴリズム(OPT, Top$k$-OPT, Cutoff-OPT)に対してパフォーマンスを比較
  • Cutoff-OPT の閾値は $(r{max} + r{min}) / 2$ を使った
    • $r_{max}$ はリストの最大の、$r_{min}$ は最小の relevance

Testing details

  • C++11 で実装
  • GCC 5.4.0 を使って最大の最適化でコンパイル
  • 8個の Core i7 7700 (3.60 GHz)
  • 64GiB RAM
  • 実験は各5回ずつ実行し、平均実行時間をミリ秒単位で報告

Reproducibility

4.1 Assessment of $\epsilon$-Filtering

  • $\epsilon$-Filtering のパフォーマンスを解析した
    • $\epsilon$, $k$, $n$ を変えながら実験
  • スペースの都合上、 GoogleLocalRec でのみ実験
  • 10,000 のテストクエリ

Assessment by varying $\epsilon$ and k

f:id:takuya-a:20191109192737p:plain
Figure 1 (top)

  • 予想通り、近似誤差 $\epsilon$ を小さくするとフィルタリングの時間は増える
  • $\epsilon$ が 0.05 以下ではゆるやかな増加
    • 時間の制約が厳しいオンラインアプリケーションに対しても feasible であるといえる
  • $\epsilon$ を小さくするより $k$ を増やしたときのインパクトが大きいことがわかる
    • $k$ に関わる計算コストは $k$ の二乗オーダーであるため(Theorem 11 参照)

f:id:takuya-a:20191109192628p:plain
Figure 1 (bottom)

  • $\epsilon$ を下げていくと、実際の近似誤差は一気に下がる
  • $\epsilon$-Filtering は実用上、非常に良好な近似誤差を達成している

Assessment by varying n

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

  • $k = 100$ に固定して実験
  • OPT は n を増やすと計算時間は急激に増えるが、$\epsilon$-Filtering はゆっくり
  • n を 1,000 から 16,000 に増やしたとき、OPT は計算時間が 17 倍になるのに対し、$\epsilon$-Filtering は2倍ほど
  • 特筆すべきは、$\epsilon$-Filtering での $\epsilon$ を変えたときの変化は、 n を増やしてもコンスタントであること
  • 実際、$\epsilon$-Filtering の平均のフィルタ時間はリストの長さによってあまり影響を受けない
  • つまり、結果リストが非常に長い場合でも $\epsilon$-Filtering が feasible である

Speedup

  • $\epsilon$ は $\epsilon$-Pruning によってフィルタされる要素数に影響を与える
    • ここでフィルタされ、残った要素だけが OPT にかけられる

f:id:takuya-a:20191109192502p:plain
Figure 3 (top)

  • $\epsilon$-Pruning によってフィルタされた平均割合
  • 予想通り、 $\epsilon$ を減らすと、捨てられる要素は増えるが、 $\epsilon$ が 0.01 より小さくなるとほぼフラットになる
  • とくに $k$ が 100 までのとき、平均して 95% 以上の要素が $\epsilon$-Pruning でフィルタできる

f:id:takuya-a:20191109192528p:plain
Figure 3 (bottom)

  • OPT と比較したときの $\epsilon$-Filtering の速度比
  • ほとんどのパラメータの組み合わせで 10 倍以上の速度向上
  • DCG-LZ のほうが DCG よりも OPT と比較したときの速度向上が小さい
    • DCG-LZ のほうが計算コストが小さいため

4.2 Experimental Comparisons

  • $\epsilon$-Filtering と [14] で導入された 3 つの SoTA (OPT, Top$k$-OPT, Cutoff-OPT)を比較
  • Table 1 も Table 2 もメトリックは DCG-LZ(速い方)

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

  • $n = 16,000$(GoogleLocalRec で利用できる最大)
  • $k \in { 20, 50, 100, 200 }$
  • 以下を表記
    1. フィルタに要した平均の時間(ミリ秒)
    2. OPT との速度比(何倍速いか)
    3. 全クエリのなかで最悪の近似誤差
  • $k$ が大きくなると Top$k$-OPT のほうが強い
    • ($\epsilon$-Filtering は $k^{2}$ についている log の項(kが大きくなるとlogで大きくなる)が効いている?)

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

  • AmazonRel データセットは最大でクエリあたり 600,000 の結果リストがある
  • $n$ を変えながら実験したのが Table 2
  • $n \in { 50000, 100000, 200000, 500000 }$($k = 100$ で固定)
  • $n$ が増えると、 Top$k$-OPT は $\epsilon$-Filtering よりも不利
    • 理論解析での時間計算量の差が実証された形

5. Conclusion and Future Work

  • $\epsilon$-Filtering を提案
    • relevance-aware なフィルタリング問題を解くための効率的な近似アルゴリズム
    • 結果として得られる結果リストの relevance について、近似精度に対する強い保証がある
  • 提案したアルゴリズムは、与えられた近似誤差 $\epsilon$ のもと、 (1-$\epsilon$)-optimal filtering を見つけることができる
    • 得られるリストの relevance は、少なくとも最適なリストの (1-$\epsilon$) 倍
  • $\epsilon$-Filtering と SoTA の手法 3つ(OPT, Top$k$-OPT, Cutoff-OPT)を比較する評価を行った
    • 2つのパブリックデータセット (GoogleLocalRec, AmazonRel) を使った
  • 近似誤差を非常に小さく抑えながら、OPT に対して最大 2 桁の高速化
    • 実際、小さな $\epsilon$ (たとえば 0.01, 0.001)に対して、$\epsilon$-Filtering の近似誤差は常に 0 だった
    • すべてのテストクエリに対して最適な結果リストを返した
    • かつ、OPT に対して 10 倍から 147 倍高速だった
  • 今後、right-$k$-maximal elements をさらに制限したクラスについての調査を計画している
    • right-$k$-maximal elements は我々の研究に対して中心的な役割を果たしている
    • 効率的に特定できるこれらの要素のクラスが発見できると、近似アルゴリズムのさらなる高速化につながる
  • また、実世界の分散検索クエリで $\epsilon$-Filtering のパフォーマンスを評価する予定である

感想

  • Top$k$-OPT は $\epsilon$-Filtering と同等に高速ながら、十分に低い近似誤差
    • 0.5-approximation (最大で 0.5 の近似誤差)だが実験では 0.05 ~ 0.15
    • $\epsilon$-Filtering はほしい要素数 $k$ が大きいとき、効果が薄い
      • $k$ を大きくするとTop$k$-OPT のほうが速くなる(Table 1)
    • 実装も簡単そうなので実用上は Top$k$-OPT で十分かもしれない