「情報検索：検索エンジンの実装と評価」9章言語モデルと関連分野

f:id:nogawanogawa:20201204230542p:plain

この記事は「情報検索：検索エンジンの実装と評価」（Buttcher本） Advent Calendar 2020の8日目の記事です。

こちらのアドベントカレンダーでは「情報検索：検索エンジンの実装と評価」（Buttcher本）を読んで、1日1章ずつまとめるといった内容になっています。

情報検索 :検索エンジンの実装と評価

発売日: 2020/10/30
メディア: 単行本

本日は、9章の「言語モデルと関連分野」について勉強していきます。

なるべく、自分の理解のために噛み砕いてこの記事を書いたつもりですが、間違っているところを見つけた方はDMとかでこっそり教えていただけれると嬉しいです。

背景
言語モデルに基づく情報検索
- 言語モデル is なに?
  - 平滑化：ドキュメントに含まれない単語をクエリに使用可能にする補正
- 言語モデルを用いたランキング
KL情報量によるアプローチ
DFRに基づくアプローチ
例:パッセージ検索
- テキスト区間の検討
- パッセージの評価
感想

背景

情報検索に関するシステムでは、下記に示すような確率的ランキング原理が前提にあります。

ある情報検索システムのクエリそれぞれに対する応答が, 対象とするドキュメントコレクションにおいての確率的関連性順位の降順で示されるのであれば, ユーザに対するシステム全体としての有効性は最大化される.

もっとシンプルに言えば、「ユーザーの操作によって出力された応答が、ユーザーにとって有益なものから順に並んでいるほど、その検索システムは優れている」といった考えが、情報検索の根底の考えとなっています。

そのため、この確率的ランキング原理を十分に満たすことが、検索システムの果たすべき役割と考えることもできます。

7章まででは、関連する可能性のある情報を効率よく見つけ出すことための技術について紹介されていたかと思います。本章では、関連する可能性のある情報の集合について、ユーザーにとって有益なものから順に並べるためのランキングについて考えます。

8章においては、確率的ランキング原理を考慮したOkapi BM25に代表される手法でランキング問題を解決する方法が紹介されています。 9章では、8章とは異なり、言語モデルを用いることでランキング問題を解決するアプローチについて考えます。

言語モデルに基づく情報検索

ここでは、「そもそも言語モデルとはなにか？」というところから話を始め、それを用いてどのようにランキングに適用していくかについて確認します。

言語モデル is なに?

言語モデルというものについて考える前に、まず検索という行為について簡単に考えます。

検索という行為が行われる際には、ユーザーは見つけたいドキュメントに関する用語を組み合わせて検索窓に入力するなどして、検索システムに見つけたいドキュメントに関する情報を伝えることになります。

f:id:nogawanogawa:20201206234014j:plain

このような、「検索を行う背景」について踏まえた上で、言語モデルについて考えます。

誤解を恐れず言えば、ここで言う言語モデルは「語彙の確率分布」を意味します。 各ドキュメントは、言語モデルによって生成されており、各ドキュメントに含まれるタームは言語モデルが持つ確率分布に従って生成されたものであると考えます。

f:id:nogawanogawa:20201206234027j:plain

各ドキュメントは何らかの言語モデルにしたがって生成される、というようにドキュメントの生成過程を捉えているのが特徴的な点と言えるでしょう。

平滑化：ドキュメントに含まれない単語をクエリに使用可能にする補正

上述のように言語モデルを用いて、ドキュメントdが与えられたときそのドキュメントの検索に使用されるであろうクエリqを単純に考えてみます。この場合、ドキュメントを生成した言語モデルに基づいて特徴的なタームを選択し、それらによってクエリが生成されていると考えることができます。

f:id:nogawanogawa:20201206234038j:plain

しかし、このように素朴に考えた際にはそれぞれのドキュメントを生成したであろう言語モデルは、ドキュメントに含まれる単語しか反映することができません。そのため、ドキュメントに含まれない単語については、言語モデルとして単語の存在確率が0というようにみなされてしまうことになり、クエリ中にドキュメントに存在しない単語が含めることができず柔軟性が非常に悪くなってしまいます。

f:id:nogawanogawa:20201206234047j:plain

そこで、本書ではコレクションモデルを使用した平滑化を行うことでこの問題を解決しています。ここでは、検索として想定しうるドキュメントすべてからなるコレクションについて、コレクションに含まれる単語の語彙からなるコレクションモデルを使用します。

このコレクションモデルとドキュメント言語モデルを組み合わせることで、各ドキュメントには含まれない語彙の単語からクエリが構成されることに対応可能になります。

f:id:nogawanogawa:20201206234056j:plain

組み合わせの方法としては、ドキュメント言語モデルとコレクションモデルを単純に線形結合するものと、各ドキュメントに対してコレクションに含まれるすべての単語が一定の確率で出現しうることを想定するものの2種類が紹介されています。

言語モデルを用いたランキング

上記のような前提を踏まえた上で、言語モデルを用いたランキングの方法について考えてみます。

言語モデルを用いた際のランキングの基本的な考え方としては、「関連ドキュメントdが与えられたとき、qがクエリとして入力される確率」を推定し、その確率に従ってドキュメントをランク付けしていきます。

ユーザーの思考としては、「関連するドキュメントには頻繁に登場し、関連しないドキュメントにはほとんど登場しないようなタームを使用してクエリを作成する」と予想できます。検索システムに入力されたクエリは関連するドキュメントと関連しないドキュメントを区別できるようなタームが使用されていると仮定すると、クエリから逆算してユーザーが見つけたい言語モデルにより適合するドキュメントを逆算的に順位付けすることができるのです。

dが関連ドキュメント例として与えられたとき、クエリに出現するタームに関して独立性を仮定したとき、qがクエリとして入力される確率を $p(q|d)$ は、

$p(q|d) = p(|q| = n) \cdot \prod_{i=1}^{n} p(t_i|d)$

と記述することができます。ここで、 $p(|q| = n)$ は長さnのクエリが入力される確率を表し、長さnのときだけ考えると $p(|q| = n)$ は一定で無視して構わなくなります。

そのため、

$p(q|d) = \prod_{i=1}^{n} p(t_i|d)$

と考えることができます。この式では、ドキュメントdが与えられたとき、クエリにターム $t_i$ が出現する確率をn個のタームに関してかけ合わせた結果がスコアとなることを示しています。

ここでクエリ中のタームの順序は重要ではないと考えられ、qをtの集合として取り扱うと、

$p(q|d) = \prod_{t \in q} p(t|d)^{q_t}$

ドキュメント言語モデル $M_d(t)$ を用いて

$p(q|d) = \prod_{t \in q} M_d(t)^{q_t}$

のように表すことができます。

このような形でドキュメントdとクエリqのペアについて言語モデルを使用して評価することで、ランキングに使用するスコアを算出することができ、スコアによって並べ替えを行えば関連性の高いドキュメントからランキングすることができると考えられます。

本書では、上記の評価式を変形することで2章や8章のランキング式との比較を行っていますが、ここでは割愛します。

KL情報量によるアプローチ

上記で紹介したようなアプローチとは別に、カルバック-ライブラー情報量（KL情報量）を使用したアプローチによっても解釈することができます。

KL情報量は、相対エントロピーとしても知られており、2つの確率分布を比較することで得られる値です。 KL情報量は値が大きいほど2つの確率分布が乖離していることを意味します。

離散分布に関するKL情報量は

$\sum_{x} f(x) \cdot log (\frac{g(x)}{f(x)})$

として表されます。ドキュメント、クエリのそれぞれから言語モデル $M_{d}(t)$ , $M_{q}(t)$ を構築し、それらを上式に代入することで下記の式が得られます。

$\sum_{t \in \nu} M_{q}(t) \cdot log (\frac{M_{d}(t)}{M_{q}(t)}) = \sum_{t \in \nu} M_{q}(t) \cdot log (M_{q}(t)) - \sum_{t \in \nu} M_{q}(t) \cdot log (M_{d}(t))$

第一項はドキュメント間で一定のため無視するとして、第2項から符号を除いた下記の式を考えます。

$\sum_{t \in \nu} M_{q}(t) \cdot log (M_{d}(t))$

この式は、KL情報量が減少する（クエリとドキュメントのそれぞれの言語モデルが似通っている）ほど増加するため、この値を高い順に並べることでクエリとドキュメントの言語モデルが近い順にランキングする事が可能です。

このようにKL情報量を使用して言語モデルを適用するアプローチが紹介されています。

DFRに基づくアプローチ

ランダム性からの距離（divergence from reandomness, DFR）を用いることでも、ドキュメントのランク付けが可能です。

例として、ドキュメントにランダムにタームが分布している状況を考えます。そのようなランダムにタームが分布する状況と比較して、特定のドキュメントには一定の傾向に基づいたタームの分布を示すことが予想されます。 DFRによってランキングを考える際には上記のような予想をもとに、評価式を考えます。

任意のドキュメントdがタームtの出現頻度としてちょうど $f_{t,d}$ を持つ確率を $P_1$ 、任意のドキュメントdにtが少なくとも1回は出現する確率を $P_2$ として、

$(1 - P_2) \cdot (-log(P_1))$

のように表現されています。上の式は単一のタームに関する場合を表現しており、複数のタームを含むクエリに対応するために下記のように拡張します。

$\sum_{t \in q} q_t \cdot (1 - P_2) \cdot (-log(P_1))$

こちらの評価式によってランキングを行うことができます。

式展開の詳細は割愛しますが、 i番目のドキュメントにおけるいタームtの出現頻度を $f_{t, i}$ とし、N個のドキュメントに渡って分布するタームtの出現回数 $l_t$ として

$f_{t, 1} + f_{t, 2} \cdots + f_{t, N} = l_t$

このとき、

$P_1 = (\frac{1}{1+l_t /N})(\frac{l_t /N}{1+l_t /N})$

$P_2 = \frac{f_{t, d}}{f_{t, d} + 1}$

のように表現でき、上で書いたランキング式の中身を計算することができます。

例:パッセージ検索

最後に、パッセージ検索にランキング手法を適用する事を考えます。

パッセージ検索とは、質問応答などに代表されるような、答えを含む可能性のあるドキュメントではなく、検索されたドキュメントの内容の断片を提供しようとする検索形態を想像していただければイメージしやすいかと思います。

テキスト区間の検討

2章で紹介されたタームの近接度に基づく素朴なランキング手法で、カバーという概念を導入しました。今回は、カバーの概念を拡張して、m-カバーという概念を導入します。

今、n個のタームから構成されるクエリについて考えると、コレクション中の区間 $[u, v$ ]がm-カバーであるとき下記の条件を満たすとします。

区間 $[u, v$ ]が少なくともm個( $n \geqq m$ )の異なるクエリタームを含む
区間 $[u, v$ ]の中に上の条件を満たす別の区間が存在しない

このm-カバーを使用することで、区間に含まれるクエリタームの組み合わせと区間長さに関するトレードオフの関係を考慮して、最良の区間を探索することを考えていく必要があります。

パッセージの評価

いま、クエリqと検索対象のドキュメントが得られているとします。このとき、ドキュメントの中から $l = v - u +1$ の区間に関して、「現実のターム分布とランダムなターム分布の関係」を推定すれば、その確率が高い順に並べ替えればユーザーが期待する検索への応答になっていることが予想されます。この部分に関する考え方はDFRに基づくアプローチと同じになっています。