情報検索のブールモデル

情報検索の（標準）ブールモデル（BIR）^[1]は、古典的な情報検索（IR）モデルであると同時に、最初に採用された最も普及したモデルです。^[2] BIRは、検索対象の文書とユーザーのクエリの両方が用語の集合（バッグオブワードモデル）として考えられている点で、ブール論理と古典的な集合論に基づいています。検索は、文書にクエリ用語が含まれているかどうか、およびクエリで記述されたブール条件を満たしているかどうかに基づいて行われます。

索引用語は、ジャーナル記事に与えられたキーワードなど、文書を説明または特徴付ける語幹を成す可能性のある単語または表現です。 をそのような索引用語すべての集合とします。 $${\displaystyle T=\{t_{1},t_{2},\ \ldots ,\ t_{n}\}}$$

文書はの任意のサブセットです。をすべての文書の集合とします。 ${\displaystyle T}$$${\displaystyle D=\{D_{1},\ \ldots \ ,D_{n}\}}$$

${\displaystyle T}$は、一連の単語または短いフレーズ (索引用語) です。これらの単語または短いフレーズにはそれぞれ という名前が付けられ、 はシリーズ/リスト内の用語の番号です。 は 「用語」、 は「索引用語n」と考えることができます。 ${\displaystyle t_{n}}$${\displaystyle n}$${\displaystyle T}$${\displaystyle t_{n}}$

単語または短いフレーズ (索引用語) は、ドキュメント内に存在することがあります。これらのドキュメントは、各個別のドキュメントが と呼ばれるシリーズ/リストを形成します。これらのドキュメント ( ) には、 の用語やなどの単語または短いフレーズ (索引用語)を含めることができます。次のセクションにこの例があります。 ${\displaystyle t_{n}}$${\displaystyle D}$${\displaystyle D_{n}}$${\displaystyle D_{n}}$${\displaystyle t_{n}}$${\displaystyle D_{1}}$ ${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle T}$

索引用語は一般に、より意味があり、記事や文書の内容に対応する単語を表す必要があります。「the」や「like」などの用語はほぼすべての文書に出現しますが、「Bayesian」は文書のごく一部にしか出現しません。したがって、「Bayesian」などのまれな用語をセットで選択する方が適切です。これはエントロピー (情報理論)に関係します。クエリで使用される索引用語をより汎用的で関連性のあるものにするために、索引用語に適用できる操作には複数の種類があります。その 1 つがステミングです。 ${\displaystyle T}$

クエリは、正規形のブール式です。つまり、が のときに対して true であるときです。(同様に、は選言正規形で表現できます 。) ${\textstyle Q}$$${\displaystyle Q=(W_{1}\ \lor \ W_{2}\ \lor \ \cdots )\land \ \cdots \ \land \ (W_{i}\ \lor \ W_{i+1}\ \lor \ \cdots )}$$${\textstyle W_{i}}$${\displaystyle D_{j}}$${\displaystyle t_{i}\in D_{j}}$${\textstyle Q}$

クエリは、ブール演算子を使用して組み合わせられ、条件のセットを形成する 用語のセットから選択されたインデックス用語 (または)の選択です。${\displaystyle Q}$${\displaystyle t_{n}}$${\displaystyle W_{n}}$${\displaystyle T}$

これらの条件は、セット の同じ索引用語 ( ) を含む文書のセットに適用されます。 ${\displaystyle D}$${\displaystyle t_{n}}$${\displaystyle T}$

を満たす文書のセットを見つけようとします。この操作は検索と呼ばれ、次の 2 つのステップで構成されます。 ${\textstyle Q}$

1.のそれぞれについて、次を満たす文書のセットを探します。2. 次に、Q を満たす文書のセットは次のように与えられます。ここで、 はブール演算子としてORを意味し、AND を意味します。${\textstyle W_{j}}$${\textstyle Q}$${\textstyle S_{j}}$${\textstyle W_{j}}$$${\displaystyle S_{j}=\{D_{i}\mid W_{j}\}}$$$${\displaystyle (S_{1}\cup S_{2}\cup \cdots )\cap \cdots \cap (S_{i}\cup S_{i+1}\cup \cdots )}$$${\displaystyle \cup}$${\displaystyle \cap}$

元の（実際の）文書の集合を、例えば

${\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}}$

どこ

${\textstyle D_{1}}$=「ベイズの原理: パラメータを推定する際に、まず各可能な値が等しい確率 (一様事前分布) を持つと仮定するという原理。」

${\textstyle D_{2}}$=「ベイズ決定理論：効用関数と確率関数を前提とし、選択される行為はベイズ行為、すなわち主観的期待効用が最も高い行為であるという意思決定の数学的理論。あらゆる決定を下すための無制限の時間と計算力があれば、この手順はあらゆる決定を下すための最良の方法となるだろう。」

${\textstyle D_{3}}$=「ベイズ認識論：命題の認識論的地位（つまり、それがどれだけ十分に証明または確立されているか）は確率によって最もよく測定され、この確率を修正する適切な方法はベイズ条件付けまたは同様の手順によって与えられると主張する哲学理論。ベイズ認識論者は、確率を使用して、認識論的地位、サポート、説明力などの概念を定義し、それらの間の関係を調査する。」

用語の集合を次のようにします。 ${\textstyle T}$

$${\displaystyle T=\{t_{1}={\text{ベイズの原理}},t_{2}={\text{確率}},t_{3}={\text{意思決定}},t_{4}={\text{ベイズ認識論}}\}}$$

すると、ドキュメントの セットは次のようになります。${\textstyle D}$

$${\displaystyle D=\{D_{1},\ D_{2},\ D_{3}\}}$$

どこ$${\displaystyle {\begin{aligned}D_{1}&=\{{\text{probability}},\ {\text{Bayes' principle}}\}\\D_{2}&=\{{\text{probability}},\ {\text{decision-making}}\}\\D_{3}&=\{{\text{probability}},\ {\text{Bayesian epistemology}}\}\end{aligned}}}$$

クエリを("確率" AND "意思決定") とします。 ${\textstyle Q}$

$${\displaystyle Q={\text{probability}}\land {\text{decision-making}}}$$次に、関連するドキュメントを取得します。

1. まず、次の文書のセットとが 取得（取得）されます。は、 「確率」という用語を含む文書と「意思決定」という用語を含む文書に対応します。${\textstyle S_{1}}$${\textstyle S_{2}}$${\textstyle D_{i}}$$${\displaystyle {\begin{aligned}S_{1}&=\{D_{1},\ D_{2},\ D_{3}\}\\S_{2}&=\{D_{2}\}\end{aligned}}}$$${\displaystyle S_{1}}$${\displaystyle S_{2}}$
2. 最後に、への応答として次のドキュメントが取得されます。クエリでは、交差演算子を使用して両方のセットに含まれるドキュメントを検索します。${\textstyle D_{i}}$${\textstyle Q}$$${\displaystyle Q:\{D_{1},\ D_{2},\ D_{3}\}\ \cap \ \{D_{2}\}\ =\ \{D_{2}\}}$$${\displaystyle S}$

つまり、元の文書はに対する回答です。 ${\displaystyle D_{2}}$${\textstyle Q}$

同じ表現（索引用語の同じサブセット）を持つ文書が複数ある場合は、そのような文書がすべて取得されます。そのような文書は、BIR では区別できません（つまり、同等です）。 ${\displaystyle t_{n}}$

• クリーンな形式主義
• 簡単に実装できる
• 直感的なコンセプト
• 結果のドキュメント セットが小さすぎるか大きすぎる場合、どの演算子がそれぞれ大きいセットまたは小さいセットを生成するかが直接明らかになります。
• これにより、（熟練した）ユーザーはシステムを制御しているという感覚を抱くことができます。クエリを実行すると、ドキュメントが取得された理由がすぐにわかります。

• 完全一致では、検索される文書が少なすぎたり多すぎたりする場合があります。
• クエリをブール式に変換するのが難しい
• 検索しにくい概念には効果がない^[3]
• すべての用語は同等に重み付けされる
• 情報検索というよりはデータ検索に近い
• 部分一致の概念のないバイナリ決定基準に基づく検索
• 文書のランク付けが提供されていない（評価尺度がない）
• 情報ニーズはブール式に変換する必要があるが、ほとんどのユーザーにとって扱いにくい
• ユーザーが作成したブールクエリは、ほとんどの場合、単純すぎる。
• モデルは、ユーザーのクエリに対して、ドキュメントが少なすぎるか多すぎるかを返すことがよくある。

純粋に形式的な数学的観点から見ると、BIRは単純明快です。しかし、実用的な観点からは、用語の選択（手動または自動選択、あるいはその両方）、ステミング、ハッシュテーブル、逆ファイル構造など、アルゴリズムとデータ構造に関連するいくつかのさらなる問題を解決する必要があります。^[4]

ハッシュ セットを使用することもできます。各ドキュメントは、そのドキュメントのすべての用語を含むハッシュ テーブルによって表されます。ハッシュ テーブルのサイズは用語の追加と削除に伴ってリアルタイムで増減するため、各ドキュメントがメモリ内で占めるスペースは大幅に少なくなります。ただし、ビット ベクターよりも操作が複雑なため、パフォーマンスが低下します。最悪の場合、パフォーマンスは O( n ) から O( n ² ) に低下する可能性があります。平均的なケースでは、パフォーマンスの低下はビット ベクターよりもそれほど悪くなく、スペースの使用ははるかに効率的です。

各文書は、その文書内の単語セットを表すブルーム フィルタで要約できます。これは、署名と呼ばれる固定長のビット文字列に格納されます。署名ファイルには、コレクション内の各文書に対して 1 つのこのような重ね合わせたコードビット文字列が含まれます。各クエリも、クエリ内の単語セットを表すブルーム フィルタで要約できます。これは、同じ固定長のビット文字列に格納されます。クエリ ビット文字列は、各署名に対してテストされます。^{[5] [6] [7]}

アプローチされた署名ファイルはBitFunnelで使用されます。

転置索引ファイルには2つの部分が含まれています。コレクションで使用されているすべての用語を含む語彙と、各用語ごとにその用語に言及しているすべての文書をリストする転置索引です。^{[5] [6]}

• Lashkari, AH; Mahdavi, F.; Ghomi, V. (2009)、「検索エンジン向け情報検索のブールモデル」、2009 International Conference on Information Management and Engineering、pp. 385–389、doi :10.1109/ICIME.2009.101、ISBN 978-0-7695-3595-1、S2CID  18147603