stop-the-world

takuya-a のブログ

論文 "BitFunnel: Revisiting Signatures for Search" を読んだメモ

まとめると

  • Bing で採用された BitFunnel アルゴリズムについての論文
  • シグネチャファイルという（転置インデックスではない）方式での検索
  • 索引を使った検索エンジンのアルゴリズムには何種類かある
    • 転置インデックス (inverted indexes)
      • ポスティングリスト (postings list) により索引をつくる
      • メジャーな検索エンジンはだいたいこの方式 (Elasticsearch, Solr, Groonga, ...)
      • 2.1 Inverted Indexes を参照
    • シグネチャファイル (signature files)
      • 文書に表れる単語をハッシュ関数にかけ、それらの論理和（OR での足し合わせ）をとったビット列（シグネチャ）により、文書の小さい表現を得る
      • 要するに Bloom Filter
      • false positive が発生する（単語が実際には含まれていなくてもヒットしてしまう）
      • シグネチャを小さくすると false positive の確率が高くなり、大きくすると I/O や CPU サイクルが増えて遅くなる
    • （他にもトライ木による方法などがある）
  • シグネチャーファイルはいくつかの制約があってメジャーではなかったが、それらの制約を克服する方法を MS が開発した
    • いま Bing 検索で使われている
    • 転置インデックスを使っていたより速くなった
    • BitFunnel という名前でエンジンの一部を OSS として公開している
  • 旧来の検索エンジンを超える高い QPS を実現 (Table 3)
    • 比較対象は PEG, MG4J, Lucene
    • 5 つの実験設定（文書長により分類）すべてで最も高い QPS (Query Per Second)
    • 容量効率は悪い（インデックスサイズが大きい）
    • ただし文書長が大きくなるほど QPS も容量効率も向上していく
    • 今回の実験では false positive は 1.62% ~ 4.32%
  • SIGIR 2017 の Best Paper

気になりポイント

  • false positive をどうやって抑えるのか
  • シグネチャファイルでは単語の頻度を考慮に入れられないけど、スコアリングどうするのか
  • AND クエリ以外、たとえば OR クエリの処理はどうするのか

1. Introduction

  • これまでの商用の検索エンジンは伝統的に転置インデックスが採用されている
  • これまでは転置インデックスがほとんどの条件でシグネチャファイルを上回ると思われていた
  • シグネチャーファイルによる検索には、4つの技術的課題がある
    1. クエリを実行するために全てのドキュメントを調べる必要があって遅い（時間計算量が文書数に比例）
    2. もっともレアな単語においても false positive を低く抑えようとすると大きいシグネチャ（ビット列）が必要
      • レアな単語ではヒットする文書数は非常に小さいが（数個とか）、それよりたくさんヒットしてしまう
    3. web において文書長はさまざまだが、もっとも大きい文書のシグネチャを考えると、そのぶん大きいシグネチャを用意する必要がある
    4. シグネチャファイルによる方法では、最適化のためのベストプラクティスが確立していない
  • これらの課題を克服するために以下のテクニックを開発し、Bing で採用した
    1. Higher rank rows: クエリを速くするために導入（計算量が文書数によらない？）
    2. Frequency-conscious signatures: メモリ使用量を減らすために採用（シグネチャの大きさを TF によって調整する？）
    3. Sharding by document length: 文書長のばらつきを減らして圧縮率や速度を上げるために、文書長ごとに文書集合 (Corpus) を分割したインデックス（シャード）をつくる
    4. システムのパフォーマンスのコストモデル（= たぶん損失関数のこと）をつくった
      • これにより、（Bloom filter のハッシュ関数などの）パラメータの最適化を行った
  • 以上の技術は、 Bing の検索エンジンで実際に 4 年間使われていて、数千台のサーバの上で動作している
    • 十分にスケールしている
  • Bing はこれまで転置インデックスベースのエンジンを使っていたが、BitFunnel にリプレースして query capacity が 10 倍に向上した（！）

2. Background and prior work

集合の定義

C: コーパス。文書の集合
D: 文書。タームの集合
Q: クエリ。タームの集合
M: クエリ Q にマッチする文書の集合
M': false positive を許す、クエリ Q にマッチする文書の集合
F: false positive の文書の集合

2.1 Inverted Indexes

自明なので省略

2.2 Bit-String Signatures

ハッシュ関数 H(n, t)

  • n: Bloom filter のビットの位置

シグネチャの定義

s_t: ターム t のシグネチャ (n bits)
s_D: 文書 D のシグネチャ。文書 D に表れるすべてのターム t のシグネチャ s_t の論理和
s_Q: クエリ Q のシグネチャ。クエリ Q に表れるすべてのターム t のシグネチャ s_t の論理和

2.3 Bit-Sliced Signatures

  • bit-string signatures の方法は効率が悪い
    • すべてのビットを読む必要があった
  • クエリ Q のシグネチャ s_Q で 1 が立っているビットだけ調べればよい
  • 全文書のシグネチャ（ベクトル）を転置する
  • ビットが立っているデータだけ読めばよくなる
  • マッチする文書集合 M' を求めるには、スライスから縦がすべて 1 になっている文書を探す
    • Figure 2: クエリ Q で立っているビット 2, 5, 9 のスライス。この中では文書 B, F がマッチ
    • 2, 5, 9 の横のベクトル（スライス）の論理積をとれば、ビット演算だけで M' が計算できる

2.4 Bit-Sliced Blocked Signatures

  • bit-sliced signatures は bit-string signatures よりもかなりよくなったが、依然効率は悪い
  • レアな（TFが小さい）タームにおいては、スライスのほとんどのビットが 0 （文書がそのタームを含んでいない）にもかかわらず読まないといけない
  • blocked signatures: 複数の文書で 1 つの列を「シェアする」ことで、もっと短い行ベクトルにする
  • 複数の文書で 1 つの列を共有
    • bit-sliced signatures では 1 文書につき 1 列が一対一対応だった
    • blocking factor: 1 つの列を共有する文書数
  • この方法 (blocked signatures) は、 false positive の確率を上げてしまう
  • たとえば、同じ列に 2 つの文書（"dog" のみを含む文書と "cat" のみを含む文書）が対応づけられていたとする
    • クエリ Q が {"dog", "cat"} だとすると、この 2 つの文書が両方マッチしてしまう
  • 4.1 の Higher Rank Rows という手法によりこの問題を解決する

3. THE BITFUNNEL SYSTEM

  • 4年前から BitFunnel が Bing 検索のバックグラウンドとして稼働している
  • 数千台のマシン、いくつかのデータセンターに分散して配置
  • このシステムで Bing にくるすべてのクエリを処理している

3.1 Architectural Overview

  • Bing のインデックスは複数の BitFunnel ノードにシャーディングされている
  • Figure 3: BitFunnel クラスタの図
  • （分散検索の仕組みは Elasticsearch/Solr とかとだいたい同じ）

クエリは以下のように実行される:

  1. クエリをパースして実行計画をつくる
  2. 実行計画にしたがって、（コンパイルした）クエリを複数のノードに投げる
  3. 各ノードでクエリを実行し、実行計画をつくったノードに結果を返す
  4. 結果をアグリゲーション
  5. スコアリングやスニペット (caption) 作成のため、別のシステムにマッチした文書集合 (M') を渡す

3.2 The Cost of False Positives

  • exact match が欲しい場合には、false positive を除外する必要がある
  • Web 検索の場合には、このコストは無視できる程度に小さい
  • なぜなら、Web 検索のゴールはユーザのクエリにマッチする文書を見つけることではなく、ユーザの意図 (intent) に最も合う文書を見つけることだから
  • Bing では、ランキングのためのシステム (Oracle) は別にある
  • ランキングシステム
    • 文書とクエリからスコアを計算する
    • 文書がどれだけユーザの意図にマッチしているかを、単なるキーワードだけでなく、様々なシグナルから計算している
    • 機械学習が使われていて、内部の動作は外からはわからない
  • BitFunnel は（ランキングシステムがスコアが低いと判定するであろう文書を通さない）「フィルター」としての役割
  • end-to-end で考えた場合、ランキングシステムが（BitFunnel による）false positive をスコアリングする時間を考慮する必要がある
  • ランキングシステムが十分に速い場合、BitFunnel が false positive を発生させることによるコストは小さいと考えることができる

4. BITFUNNEL INNOVATIONS

  • bit-string signatures と bit-sliced signatures の速度とサイズの問題を改善する 3 つのテクニックを紹介
    1. Higher Rank Rows
    2. Frequency Conscious Signatures
    3. Sharding by Document Length

4.1 Higher Rank Rows

  • bit-sliced blocked signatures の応用
    • 異なる blocking factor (1 つの列を共有する文書数) のビット列（タームごとにそれぞれ長さが異なるビット列）に対してもクエリを実行できる
    • Higher rank row では、blocking factor を 2 の累乗とする
  • bit-sliced signatures では、文書数が多い時、たくさんのビットを読まないといけなかった
  • Higher rank row では、文書の数だけあったビットを「折りたたむ」
  • Rank が高くなるにつれて false positive が起こりやすくなる
    • 1つのビットに対応する文書の数が多くなっていくため
  • たとえば 3 つのタームからなるクエリで検索することを考える
  • ファイル（メモリ）から読み込むビットは減っているのでクエリは速くなる
    • その代償としてfalse positive の確率が上がる

4.2 Frequency Conscious Signatures

  • シグナルの定義について
  • 定数 k: Bloom filter で使用するハッシュ関数の数
  • one-size-fits-all k 問題
    • すべてのタームに対して同じ k を使うのは無駄が多い
    • タームのレア度に応じて最適な k は異なるはず
  • シグナルノイズ比を導入することで false positive の量を考えることができる
  • Bloom filter を、タームのハッシュをとったときに、高々 k 個のビットが立つように設定する
    • こうすることでシグナルノイズ比が計算できる
  • シグナル s: 「ターム t が実際に文書 D に含まれている確率」と定義
    • これは単にコーパスに表れるタームの "frequency" に一致する
    • （ここでは frequency という言葉は、TF のことではなく、DF （を文書数で割ったもの）のことを言ってそう）
      • （"picture" の frequency が 0.1、みたいな記述がある）
  • ノイズ α: 「Bloom filter が誤ってターム t を文書 D に入っていると答えてしまう確率」と定義
  • 平均ビット密度 d: Bloom filter で立っているビットの期待値の逆数
    • Bloom filter の出力は平均ビット密度 d になるように設定されているとする
  • ノイズ α は (1 - f) * dk
  • シグナルノイズ比 ϕ は s/α なので、 ϕ = s / (1 - s) * dk と表せる
  • これを k について解くと k = log_d( s / (1 - s) * ϕ)
  • 目指すシグナルノイズ比 ϕ に対して、タームの頻度（= s）ごとにどれくらいの k が必要かが計算できる
  • シグナルノイズ比 ϕ を 10 以上にするためには
    • frequency 0.1 のターム "picture" に対しては k = 2 でよい
    • frequency 0.0001 のターム "rotisserie" に対しては、シグナルノイズ比を 10 にするために k = 5 が必要
  • 古典的な Bloom filter では、もっともレアな（s が小さい）タームに対して許容できる false positive から設定を行う必要があった
  • BitFunnel では各タームごとにどれくらいの行数（ビット列の数）が必要かを決定するのにこの方法を使っている

4.3 Sharding by Document Length

  • bit-sliced signatures はシグネチャのビット数が決め打ち
    • 文書長が違っても固定のビット数、同じハッシュ関数を使わないといけない
  • 実際に、文書長は非常に多様
    • Wikipedia では、10個に満たないタームの文書もあるし、数千個のタームからなる文書もある
  • このような場合には、bit-sliced signatures は容量効率が悪い
  • 近い長さの文書をまとめるシャーディングが 90 年代後半に提案された
    • が、1台のマシンで動かすときには効率が悪い
    • シャード数に比例してディスクのシーク（ランダムアクセス）が発生してしまう
    • 当時はメモリが高価で容量が小さく、SSD が普及していなかった
    • 現代のマシンでは影響は小さい
  • BitFunnel では1つのインスタンスごとに1つの（近い文書長でわけた）シャードを管理し、クラスタ構成を組んでいる
    • ランダムアクセスの問題が起こりにくい

5. PERFORMANCE MODEL AND OPTIMIZATION

  • シグネチャを使う方法はパラメータが多くて最適化が難しかった
  • この章ではほしいシグナルノイズ比を達成する最適化のアルゴリズムを紹介
  • 指定されたシグナルノイズ比を下限とする制約付きの最適化
  • 最適化対象のコスト関数は DQ (コーパスサイズ（の小ささ） D と QPS Q の積) を表す（そのものではない）
    • あとで定義する

5.1 Prerequisites

  • row のランクのビット密度・ノイズについて議論
  • rank-0 equivalent rows のノイズには2種類ある
    • 5.2, 5.3, 5.4 で議論する

5.1.1 Signal in a Higher Rank Row

  • s_0: rank-0 の行のシグナル
  • s_r: rank-r の行のシグナル
  • s_r は s_0 の関数として書き下せて
    • s_r = 1 - (1 - s_0)^(2^r)
  • rank-r のビットがシグナルであるためには、対応する rank-0 のビット（2^r 個ある）の少なくとも1つがシグナルである必要がある

5.1.3 Correlated and Uncorrelated Noise

  • U: Uncorrelated noise
  • C: Correlated noise
  • n_r: rank-r の行 R のノイズ
  • n_0: その R に対応する rank-0 の行のノイズ
  • n_0 は r s_0 n_r の関数として書ける（？）
  • ...
  • n_0 は以下の式で計算できる
    • n_0 = n_r + s_r - s_0
  • 変形すると
    • n_0 - n_r = s_r - s_0
  • 5.1.1 のより s_r = 1 − (1 − s_0)^(2^r) なので
    • n_0 - n_r = 1 − (1 − s_0)^(2^r) - s_0

5.5 Choosing Term Configurations

  • ここまでの結果を使って、最適な設定を求める
    • 求めるべきなのは、各ランク（Rank 0 - Rank 6 の7段階で十分）に必要な行数 k（0 - 9 の10段階で十分）の最適値
    • たとえば、ターム movies に対しては、 Rank 1 * 3 + Rank 5 * 1（ランク1の行を3つ、ランク5の行を1つ）など
  • それぞれのタームの IDF に対して求めればよい
  • 最適な設定を決めるために、制約付き最適化を行う
    • 制約：シグナルノイズ比 ϕ が一定の閾値以上になること
    • 関数：DQ（単位ストレージあたりの文書数 * 単位計算あたりのクエリ処理数） -> 最大化
      • D は文書あたりに必要なストレージ容量に比例
      • Q は1回のクエリ処理でアクセスする機械語のワード数に反比例
      • ストレージ効率とクエリ効率のバランスがとれた設定を求めることができる
  • DQ は 5.3 で求めた (5) 式と 5.4 で求めた (6) 式を使って書ける
    • D は (6) に反比例
    • Q は (5) に反比例
  • (7) 式の右辺を最大化するパラメータを求めればよい
    • ランクと k の取りうる値はそれぞれ7通りと10通り
    • つまり、パラメータ空間は 107
    • グリッドサーチによる全探索でも十分に速く計算できる
  • タームの IDF は実数パラメータだが、実用上は各タームごとに厳密に計算する必要はない
  • IDF が 0.1 から 10.0 まで、0.1 刻みで 100 個のバケットをつくり、それぞれごとに最適値（ランクと k の組）を予め計算しておく
    • 最近のマルチコア CPU なら数秒で完了する
  • （単語の IDF が計算できたら、バケットからそれに対応する最適設定を取り出して、シグネチャをつくればよい）

6. EXPERIMENATAL EVALUATION

  • コーパス
  • 前処理
    • Apache Tika でタームの抽出
    • 小文字に変換
    • ステミングはしない
  • テストに使った BitFunnel のシャード
    • A ~ E の 5つのシャードを使う
    • A: ターム数がもっとも少ないシャード (64 - 127)
    • E: ターム数がもっとも多いシャード (2,048 - 4,095)
    • Table 1: インデキシング後の各シャードの統計情報
  • クエリログ（検索のテストに使用）
    • TREC 2006 Efficiency Topics を使用
    • クエリから句読点を除去
    • そのあと、コーパスに出てこないタームを含むクエリは除去
  • 計算機環境
  • BitFunnel の設定（FC, FC+HRR 共通）
    • シグナルノイズ比の下限 ϕ を 10 に設定

6.1 Match Time vs. Quadwords

  • 5.3 でつくったコストモデルの予測性能を検証
  • Figure 11: 散布図

6.2 Impact of Frequency Conscious Signatures and Higher Rank Rows

  • 比較した手法
    • BSS: Bit-Sliced Signatures
    • BSS-FC: Bit-Sliced Signatures + Frequency Conscious Signatures
    • BTFNL: Bit-Sliced Signatures + Frequency Conscious Signatures + Higher Ranked Rows
  • BSS-FC でストレージ効率は3.2倍（46.7 -> 14.7 bits/postings）に、クエリ速度は2.6倍（9.1 -> 21.4 kQPS）に (d = 0.15)
    • Frequency Conscious Signatures はストレージ効率とクエリ速度、どちらも向上させる
  • BTFNL で BSS-FC のさらに2.4倍（24.0 -> 57.0 kQPS）に (d = 0.15)
    • Higher Ranked Rows はクエリ速度に対する効果が大きい
    • 逆にストレージ効率は BSS-FC 単体より少し上がっただけ（bits/posting が減った）

6.3 Comparison with Contemporary Indexes

  • BitFunnel と他の全文検索ライブラリとの比較
  • Bing で動いているプロダクション版の BitFunnel では、BM25F のランキングのためにターム頻度 (TF) を順方向のインデックスとして持っている
  • （なんかよくわからないけど）このランキングのコードが使えなかったので、実験は AND 検索 (conjunctive boolean matching) でだけ行った
    • （実務の全文検索では OR 検索してスコアリングしたい場面が多いので、やや不公平感がある）
  • 比較対象
  • 設定
    • インデックスファイルはメモリマップドファイルとして開く
    • タームのポジション（位置情報）は持たない
    • スコアリングしない
  • スコアリングしないので、ターム頻度の情報はインデックスファイルには不要
    • PEF と MG4J はターム頻度 (TF) は別ファイルになるので、今回の実験設定ではペナルティがない
    • Lucene はポスティングリストと同じファイルにターム頻度も保存されるが、ターム頻度の情報を読み飛ばすコストは不明である
      • （実際に TF のデータ読込みは行われるのでそれなりに不利だと思う）
  • 実験の方法
    • 1 プロセス 8 スレッドで実行
    • 98,000 のクエリログを 2 回走らせて 2 回目の計測を記録
      • クエリに関連するインデックスがページインされた状態のパフォーマンスを調べるため
      • プロダクション環境下での負荷に近いはず
  • Table 3: 実験結果
    • BitFunnel は 5 つのシャードすべてで非常に高い QPS を達成している
    • ポスティングあたりに必要なビット (bits-per-posting) は大きい
      • = インデックスサイズが大きい
      • Lucene の結果が書かれてないのは、必ずターム頻度 (TF) も一緒に保存してしまうから？
    • 5 でシステムの利用効率の指標として導入した DQ (QPS と bits-per-posting の比) でも PEF にやや勝ってる？
      • シャード C, D, E で勝ち
      • とくに文書長の大きいシャード E では 4.2 倍の DQ
    • （本文では触れられていないが数%くらい false positive が発生している）
  • 文書長が大きい文書が多いコーパスでは BitFunnel が有利という結果

「Elasticsearch での類似文書検索と More Like This Query API 詳解」というタイトルで発表しました

　Elasticsearch 勉強会 in 大阪・京都で発表しました。

　最近、興味をもって調べていた More Like This Query API について、改めてソースコードリーディングしながら整理した内容になっています。

　この発表で使ったスライドを Speaker Deck にアップしました。大阪と京都で同内容の発表でしたが、スライドの体裁をよくして見やすくした、京都での発表スライドをアップしています。

Elasticsearch での類似文書検索と More Like This Query API 詳解 // Speaker Deck

　関西では初の開催ということで、何を発表するか、かなり悩みました。

　先月の Hatena Engineer Seminar #5 では、どちらかというと事例についての発表だったので、もうちょっと汎用的に使える知識を、とはいえ、入門的な話は johtani さんがしてくださるので、より発展的な内容を、ということで類似文書検索に着地しました。

　ただ、両日ともに全文検索より Kibana 等の分析系のほうに興味がある方が多かったようで、参加者の興味を外していた感が否めませんでしたが。。（あとで Twitter を見返してみると、何人かの方には刺さっていたようでした）

類似文書検索とそのアプリケーションについて

　類似文書検索は、 Web 検索のみならず、社内文書の検索や、特許検索など、多くの検索アプリケーションで有用な技術です。

　ブログの関連エントリー機能などでも使われている技術だと思いますが、類似文書を関連エントリーとしてよいかどうかは、一考の余地があります。要するに、文章が似ているからといって、そのエントリーがブログの読者にとって有益かどうかはまた別問題、ということです。

　これについては、 id:skozawa さんが以前に発表した以下のスライドが参考になるかと思います（はてなブックマークの関連エントリー機能で、実際に Elasticsearch を使って実現されている技術について解説されています）。

優先度つきキューによる Top-K retrieval

　スライドの中で、優先度つきキュー (PriorityQueue) を使ってスコア上位 K 個の語（ターム）を求めるアルゴリズムが出てきました。発表では時間がなくて話せなかったので、ここで補足しておきます。

　Top-K を求めるアルゴリズムは、全文検索エンジンにとって最もコアであり、性能が求められる部分です。なぜなら、全文検索というのは、「与えられたクエリでの文書のスコアを計算し、スコア上位 K 件の文書を返す」という処理に他ならないからです。Lucene レベルでも、でかい転置インデックスから文書の Top-K を計算しており、そこにサイズ制限のある優先度つきキューが使われています。優先度つきキューを使用する際には、スコアを優先度とみなし、優先度の高い文書(= スコアの高い文書)を取り出します。

　Elasticsearch の More Like This Query API でも、膨大な数の語（ターム）の Top-K を計算するために、このアルゴリズムが使われています（こちらは文書ではなく、各タームのスコアを計算してスコア上位のタームを求めていることに注意）。

　優先度つきキューは、（プリミティブな）配列を使って実装できるため、定数オーダーの操作も高速ですが、これを使って Top-K を求めると、普通にソートするのと比べると、計算量のオーダーも下がるため、ソート対象が大きい場合には劇的な効果があります。

バイナリヒープを用いた制限のある優先度つきキューの実装

　優先度付きキュー (Priority Queue) はヒープ 、とくにバイナリヒープで実装されることが多いようです。ここで、ヒープとしては Min-Heap （最小値をもつ要素が先頭になるヒープ）を使うところがポイントです。

　サイズ制限のある優先度付きキューの実装は、普通に Max-Heap を使って実装すると、

  1. delete-min: ヒープから優先度の低いノードを削除 (O(N))
  2. insert: ノードを追加 (O(1))

ですが、 Min-Heap を使うと、

  1. extract-min: ヒープから優先度の低いノードを削除 (O(log N))
  2. insert: ノードを追加 (O(1))

となります。もう少し補足します。

　ルートノードは優先度が最も低いことが保証されているため、これは削除してよいということになります。上述の通り、先頭の要素の削除は O(log N) で可能です。単純に Max-Heap を使って、先頭以外の要素の削除をした場合には O(N) ですから、相当に高速化できました。

　最後に、サイズが k の配列を用意し、そこにバイナリヒープから順番に取り出した要素を、逆順に詰めていきます。詰め終わった配列を見ると、 Top-k の要素がソートされた状態で得られることになります。

（なお、ここでの優先度つきキューは、最初に要素の追加をすべて済ませ、最後にまとめて優先度の高い要素を取り出す、というタイプのものです。ジョブキューのような、追加の途中で削除があるような用途には使えません）

　バイナリヒープを配列で実装する方法については、以下の PDF が参考になります。

　Lucene での優先度つきキューの実装については、以下のソースを参照してください。

あとがき

　大阪では、ヤフー大阪支社の方々にお世話になりました。勉強会のあとの懇親会も楽しかったです。ありがとうございました。

　また、両日ともに elastic 社の方々には大変お世話になりました。また、 Elasticsearch: The Definitive Guide を献本いただいたり、 elastic ロゴ入りのビーチボールや sugru などの elastic な販促グッズもいただきました。

　京都での開催については、発表者全員のスライドが揃いましたら、開催報告エントリーを上げようと思います。