情報検索 :検索エンジンの実装と評価　5章の「クエリ処理」

「情報検索:検索エンジンの実装と評価」(Buttcher本) Advent Calendar2020の5日目の記事です。

adventar.org

情報検索 :検索エンジンの実装と評価　5章の「クエリ処理」をまとめます。

この章ではランキング検索と軽快な実装とよばれる手法についての説明されています。本エントリーでは前半のクエリ処理について,DAATとTAATの違いについて扱います。

説明の前提位
- クエリ表現
- Okapi BM25
ドキュメントごとのクエリ処理
MaxScore
タームごとのクエリ処理
- accumulatorの刈込

説明の前提位

クエリ表現

検索エンジンでのクエリ表現は、連語表現(=AND検索)と選語表現(=OR)があります。

たとえば、Q = <"検索", "エンジン">というクエリに対して、

連語表現(=AND検索)では, 検索 AND エンジン と表現するのに対して

選語表現(=OR)では、 検索 OR エンジン と表現します。

ランキングを前提としたドキュメント検索の場合、選語表現(=OR)に比べて連語表現(=AND検索)は高速に検索することができます。なぜなら、連語表現(=AND検索)のほうはすべてのクエリを含むドキュメントが検索対象となるので、スコアを計算してランク付けするドキュメントが少なくすむからです。ただし、連語表現(=AND検索)は速度は早いものの、クエリが長くなるほど適切なドキュメントをかせなかったり、適切でない単語が一つでも含まれれば検索結果がほぼ意味の悪くなるということもありえます。

そこでこの章で説明される、ランキングのためのクエリ処理ではクエリを追加したときに検索結果を悪くしてはいけないという考えのもと選語表現(=OR)で以下に効率的にクエリ処理を行うかを説明されています。

Okapi BM25

検索エンジンのスコアリングにはOkapi BM25を採用検索エンジンのスコアリングにはOkapi BM25を採用しているという前提になっています。詳細については８章で説明されるようです。

ざっくり説明すると、Okapi BM25は、ドキュメントにおけるクエリタームの出現頻度に基づいてドキュメントを順位付けします。この章の説明はOkapi BM25について理解していなくても問題はないのですが、概要だけでも知りたいかたはこちらを参照してもらうとよさそうです。

https://mieruca-ai.com/ai/tf-idf_okapi-bm25/

ドキュメントごとのクエリ処理

ランキング検索のためのクエリ処理は、多くがドキュメントごとのクエリ処理(DAAT: document-at-a-time query prosessing)とよばれる処理を行っています。

DAATではクエリの単語を含むドキュメントごとに処理します。つまりクエリに含まれるタームのポスティングリストをすべて展開して、ドキュメントごとにスコア計算します。単純なアルゴリズムではすべてのドキュメントを計算した後に、スコアでソートされて上位k位のドキュメントのリストが返されます。

たとえば"検索 OR エンジン"というクエリの場合、以下のようにポスティングリストを持っていたとすると

doc_id:1のドキュメントのスコアが計算されて、次にdoc_id:3のスコアが計算されて〜最後のドキュメントであるdoc_id:5まで計算が終わった後にソートが行われます。この例では最終的にdoc_idが5,4,1,3の順で返却されます。

最後のドキュメントまで処理をすると、クエリに含まれるタームがどれだけ同じドキュメントに出現するかによって計算量が変わります。最悪の場合は、クエリに含まれる単語が全部のドキュメントに一つしか出現しない場合で、その際の計算量はクエリに含まれる単語のポスティングリストの総数になります。

この問題を解決するための方法が次に紹介するMaxscoreです。

MaxScore

MaxScoreはクエリに含まれる単語の最大スコアを保持しておきクエリ処理を効率化する方法です。

単純にするために、"検索 OR エンジン OR 本" というクエリで、ユーザの要求がk=1すなわち上位1件の結果を見たい場合を考えます。

このときの各タームのMaxScoreは、

検索: 10

エンジン: 4

本: 2

です。

ドキュメントを10件進めた際に、スコア1位のドキュメントのスコアが13点だとすると

resultのスコア > MaxScore('検索')

となるため、移行のドキュメントでエンジン・本を含まない検索だけを含むドキュメント(doc_id:11)が1位になることはありえません。また残りのタームのスコアだけが含まれるドキュメント(doc_id:12,13)も1位になることはありえません。そのためscoreを計算する必要がないためこれらのドキュメントをスキップすることができます。

このまま処理が進みdoc_id:20で

resultのスコア > MaxScore('検索')　+ MaxScore('エンジン')

となり、3つのタームすべてを含むドキュメント以外が1位になることがないため、doc_id:21以降のドキュメントでは3つのタームすべてを含まないドキュメントはスコア処理をスキップできます。

MaxScoreを用いることで、全ドキュメントのスコア処理場合と同じ結果になりますが処理時間を圧倒的に短くすることができます。

タームごとのクエリ処理

ドキュメントごとのクエリ処理とは異なり、タームごとにクエリ処理(TAAT: term-at-a-time query prosessing)を行う方法もあります。

こちらは名前のとおりタームごとにポスティングリストを調査して、各ドキュメントのスコア積算値(accumulator)を更新していきます。すべてのタームのポスティングリストを調査し終わったらaccumulatorがそのまま最終スコアになり、これをスコア順にソートした上位k位のドキュメントを返却します。

accumulatorの刈込

TAATでは利用するメモリがaccumulatorの数に依存します。したがってタームの数が数十などになってくる、もしくは巨大なポスティングリストを扱う場合にメモリを多く使うことになります。その解決方法として、QUITとCONTINUEという方法が紹介されています。そもそもTAATはインデックスがディスクに格納されていてタームのポスティングリストが大きすぎてメモリにのらない場合だそうです。そういう状況ではDAATでは、何度も複数のポスティングリストをディスクやメモリの読み込みが発生し数十タームを含むクエリで問題になる可能性があります。

TAATでもポスティングリストが大きすぎた場合にaccumulatorがメモリにのらないと実行できないため、accumulatorの上限(αmax)を設定したのがQUITとCONTINUEです。

QUITは、一つのタームの処理が終わるごとに|accumulator| > αmaxであるかを確認し、そうであればそこで処理をやめて現時点のaccumulatorを最終結果とする方法です。

CONTINUEは、一つのタームの処理が終わるごとに|accumulator| > αmaxであるかを確認し、そうであってもaccumulatorの更新は続けますがメモリ領域を新たに確保しないものです。

ただしaccumulatorの刈込で注意しなくてはいけないのが、DAATの場合のMaxScoreとことなり、accumulatorの刈込値つまりQUITで途中でとめたaccumulatorはすべてのポスティングリストを走査した結果と同じではなくあくまでも近似値であるということです。この近似値の正確さはaccumulatorの上限(αmax)によります。

TAATの場合、accumulatorの刈込を行う場合は特に、頻度の少ないタームから実装することが重要です。タームのtの重みがタームt'の重みより大きい場合、タームtを含むドキュメントはタームt'を含むドキュメントよりもtop-kに入る可能性が高くなります。そこでBM25などドキュメント数が少ないタームほどスコアが高くなるアルゴリズムの場合、ポスティングリストの短いタームから処理をしていく必要があります。