#はじめに
この記事は、TextRetrieval と 検索エンジン1-1 Natural Lanaguage Content Analysis & 1-2 テキストアクセスの続編になります。第二回目です。
1-3 文書検索の問題
テキスト検索（Text Retrieval）とは？
テキスト検索は、よく Information Retrieval とも言われますが、テキスト検索（Text Retrieval）よりも、Information Retrieval の方が意味が広いです。
Information Retrieval は、音楽や動画、写真なども対象にしますが、テキスト検索は、テキストドキュメントを対象にします。
テキスト検索は、大まかにいうと次の図のようなことができるようなシステムをいいます。
##テキスト検索 v.s. データベース検索
格納してある情報をとってくるシステムで、有名なのは、MySQLやPostgreSQLをはじめとするデータベースですが、検索エンジンとデータベースの違いは何でしょうか？
テキスト検索とデーターベース検索には次のような違いがあります。
| カテゴリ | テキスト検索 | データベース検索 |
|---|---|---|
| 情報 | 非構造化データ 曖昧なデータ |
構造化データ 明確なデータ |
| クエリ | 曖昧なクエリ フリーワード |
明確なクエリ |
| 検索結果 | 関係がありそうなドキュメント | クエリに該当したレコード |
| データ構造 | 転置インデックス | B-Tree |
まず、データベースは、エクセルのようなテーブル構造をしています。
例えば、下のような感じです。
| id | user | title | content |
|---|---|---|---|
| 1 | aaa | 晴れとは | 晴れとは、大気がある天体において、雲が少ないか全く無い天気を指します。 |
| 2 | bbb | 私のウォーキングコース | 私のウォーキングコースは、晴れた日はホゲホゲ通りです。晴れの日はたんぽぽがきれいです。 |
| 3 | ccc | 検索エンジン | 検索エンジンはとてもおくが深く面白いテクノロジーです。 |
このデータにたいして、次のようなクエリを発行することで、データが取得できます。
select content from text_table where user=aaa
少しでも、SQLを触ったことがある人は、上のクエリに大して、どのレコードが取得できるかわかるはずです。
では、検索エンジンはどうでしょうか？
グーグルのように、検索窓に自由にクエリを、例えば、「晴れ」と入力して、どのレコード（とは検索エンジンではいいませんが）引っかかるかわかるでしょうか？
aaa さんも、bbbさんも「晴れ」に関係がありそうなことを書いていますが、どちらがよりユーザーが欲しいドキュメントでしょうか？
どちらがよりユーザーが欲しいドキュメントかという質問は、「晴れ」と検索したユーザーが、aaaさんのような「晴れ」についての定義が知りたかったのか、「晴れ」の日に散歩すると気持ちがいい場所を知りたかったのかによって答えが変わってしまいます。
データベースと違いクエリが曖昧であることが多く、ユーザーがクエリに込める意図によっては、欲しいドキュメントが異なるのが検索エンジンの特徴であり大きな課題でもあります。
この検索エンジンの特徴から、検索エンジンは、数学的に甲乙をつけることができません。
また、ユーザーのフィードバックを使って実験的に評価しなければ、どちらの検索エンジンが「良い」のかも判断できないのです。
正式なテキスト検索の定義
| 名前 | 定義 |
|---|---|
| Vocabulary | $V = {w_1, w_2, w_3, ..., w_n}$ |
| Query | $q = q_1,...q_m \ $ where $\ q_i \in V$ |
| Document | $d_i = d_{i1},...,d_{im}\ $where $\ d_{ij} \in V $ |
| Collection | $C =$ { $d_1,..., d_M $ } |
| Set of Relevant Documents | $R(q) \subseteq C$ |
$R(q)$ は、基本的に、ユーザーに依存します。
また、クエリ $q$ は、R(q)を求めるためのヒントです。
これらの定義に対して、やりたいことは、$R(q)$ の近似である$R'(q)$を求めることです。
#二つの作戦
では、どのように、$R'(q)$ を計算すればいいでしょうか？
これには、2つのやり方があります。
- ドキュメント選択
$R'(q) = $ { $ d \in C \ \mid \ f(d,q) = 1$}
$R'(q)$ は、ドキュメントが関係あるかないかでの、二項分類を行う関数と定義する方法です。
- ドキュメントランキング
$R'(q) = $ { $ d \in C \ \mid \ f(d,q) > \theta$ } where $f(d,q) \in \mathbb{R}$
ドキュメントランキングでは、$R'(q)$を、関係性を表す関数として定義します。
$\theta$は、そのドキュメントが有用か有用じゃないかの境目を表します。この境目は、ユーザーによって決められます。
ドキュメント選択とドキュメントランキングの違いを図で表すと次のような感じです。
Solr を含む、一般的な検索エンジンは、次の理由から、ドキュメントランキングを採用しています。
- 分類は、正確ではない。
- 関係ないドキュメントを返しすぎてしまうことがある。
- 関係のあるドキュメントでも、例えば10'000件ドバッと返されても、困る。
- これら極端な場合を考慮して、丁度いいところ（何件返すか）を探すのが難しい。
- 全てのドキュメントが等しく関連があるわけではない。
- すごく役に立つドキュメントと、ちょっとだけ役に立つドキュメントがあるように、
プライオリティーを設ける必要がある。
- すごく役に立つドキュメントと、ちょっとだけ役に立つドキュメントがあるように、
ランキングの理論的正当化
Probability Ranking Principle [Robertson 77]
Returning a ranked documents is relevant to the query is the optimal strategy >under the following two assumptions.
- the utility of a document to a user is independent of the utility of any other document.
- a user would browse the result sequentially
現在のIR研究は、この二つの仮定を元にして行われています。
#1-4 Text Retrievalモデル概要
ランキング関数の設計
上記での定義を振り替えります。
| 名前 | 定義 |
|---|---|
| Query | $q = q_1,...q_m \ $ where $\ q_i \in V$ |
| Document | $d_i = d_{i1},...,d_{im}\ $where $\ d_{ij} \in V $ |
| Ranking Function |
$f(q,d) \in \mathbb{R}$ |
良いランキング関数は、関係性のあるドキュメントをランキングの上位に持ってくるような関数である必要があります。
さて、このランキング関数での課題は、あるドキュメント $d_i$ とクエリ $q$ の類似性をどのように数値化するか？ということです。
この課題を考えるために、関連性を計算できるように形式化しなければなりません。
形式化した形をRetrieval Modelといいます。
##様々な Retrieval Model
一言で、「関連性を計算できるようにする」と言っても、その方法はいろいろあります。
- 類似性を元にするモデル $f(q,d) = similarity(q,d)$
- ベクトル空間モデル
- 確率を元にするモデル $f(q,d) = p(R\ =1 \mid q,d)$ where R $\in$ { $0,1$ }
- 確率的モデル
- 言語モデル
- Divergence-from-randomness model
- 確率的推論モデル $f(q,d) = p(d \rightarrow q)$
- 公理的モデル $f(q,d)$ は制約を満たしていなければならない。とする。
##これらRetrieval Modelの共通の考え方
いろいろな、Retrieval Model を紹介しましたが、これら Modelには、共通の考え方があります。
例えば、"ボルダリング 服装"というクエリを入力したとします。
そうすると、ランキング関数は $f(q=$"ボルダリング 服装"$,d)$ のようになります。
まずは、問題を簡単にするために、キーワードを区切ります。
$g($"ボルダリング"$)$ と $g($"服装"$)$ といった具合です。
$g($"ボルダリング"$)$ について、次の3つの値を調べます。
- ドキュメント $d$ の中に、"ボルダリング" という単語が何回現れるか？
- これを **Term Frequency(TF)**といい $count($"ボルダリング"$,d)$ もしくは、$c($"ボルダリング"$,d)$書く。
- ドキュメント $d$ の長さは？
- これを Document Lengthといい $|d|$ 書く。
- Collection $C$ の中に、"ボルダリング" という単語が何回現れるか？
- これを **Document Frequency(DF)**といい$df($"ボルダリング")$ や $P($"ボルダリング"$,C)$ と書く。
どれがいいの？
基本的に、最適化すれば、下記モデルのパフォーマンスは同じくらいいいとされています。
- Pivoted Length Normalization
- BM25
- Query Likelihood
- PL2
この中では、BM25が一番有名です。
Solr でもデフォルトでは、BM25 を使っています。
No Shingle Winner なのです。
The State of Art Ranking Function
最近のランキング関数では、次の3つの考え方を使っていることが多いです。
- Bag of Words
- 各単語の Term Frequency と Document Frequency
- Document Length