トップ > 情報検索 > 「情報検索：検索エンジンの実装と評価」1章 イントロダクション

「情報検索：検索エンジンの実装と評価」1章 イントロダクション

情報検索

この記事は何？

adventar.org

「情報検索 検索エンジンの実装と評価」Advent Calendarの1日目の記事です。
1章の「イントロダクション」をまとめます
深い話というよりは、今後の章で説明されるトピックについてさわりを紹介していく話となっています。

www.morikita.co.jp

情報検索とは何か

そもそも「情報検索」とは何かという話。本では、

情報検索（information retrieval, 以下IRと略す場合がある）は, 膨大な量の電子化されたテキストや人間の言語データをモデル化したり, 探索したり, 操作したりすることを表した言葉である.

と記述されていました。

情報検索といえば「探索」がメインかなと思いますが、そのために「モデル化」や「操作」といった手続きは当然必要です。
人間の言語データは、会話やスピーチ、電子メールの例が分かりやすいかなと思います。

情報検索の例

  • Web検索

みんな大好きGoogle。

  • デスクトップ検索（ファイルシステム検索）

ローカルディスク（ネットワーク）に保存されたファイルの検索です。
本自体が古いのでアレですが、現代ではクラウド上のファイル検索も重要だと思います。

Web検索との違いについて、以下のように記述されていました。

Web検索エンジンと違って, デスクトップ検索エンジンには, ファイルフォーマットとファイル作成時刻に関して, よりきめ細かな取扱いが求められる.

PCのファイルは急速に変化するので, これらの検索システムはオペレーティングシステムのファイルシステムレイヤに直接アクセスでき, かつ頻繁な更新を扱えるように設計する必要がある.

例えばファイルを作成してから1時間後にならないとそのファイルを検索できない〜というのは、とても不便です。

情報検索の応用分野

  • ルーティング・フィルタリング・選択配布

10章で詳しく説明されますが、新しいドキュメントについて、あらかじめユーザーが入力したクエリ集合と照らし合わせて配信する作業です。
例としては、ニュース収集サービスや電子メールのスパムフィルタが挙げられます。
選択配布（selective dissemination）という単語は初めて聞きました、概念自体は1950年代に提案されたもののようです*1。

  • テキストクラスタリング・分類
  • 要約
  • 情報抽出
  • トピック検索追跡

トピック検索追跡（topic detection and tracking）システムは, ニュースなどの情報源の中から特定の出来事を識別し, その進展を追跡する.

高間（2005）*2から引用します。

Topic Detection and Tracking（TDT）は, オンラインユースやニュース放送といったデータストリームから話題構造を自動的に得るための技術確立を目的として, DARPAのTIDES（Translingual Information Detection, Extraction, and Summarization）プログラムのもとで進められてきた技術研究開発プログラムである.

  • エキスパートサーチ
  • 質問応答
  • マルチメディア情報検索

最近だと深層学習技術の発展により、画像検索を搭載したサービスが流行っています。
about.mercari.com

情報検索の専門用語

（本の図1.1を参照）

  • 情報要求：ユーザーが持っている、何を検索したいのかという要求
  • クエリ：情報要求から、ユーザーが検索システムに入力する情報。検索システムによってはクエリ用の命令文（ANDとかORとか）を実装している。
  • 検索エンジン：ユーザーのクエリを処理する。対象とするドキュメントコレクションに対する転置インデックス（2章で詳しく説明）を整備・操作する。
  • ドキュメント：ユーザーへの検索結果として表示できるもの。電子メール・webページ・ニュース記事・動画・…

はるか昔大学の授業で、「文書が情報要求に適合している」「文書がクエリにマッチしている」は明確に区別してくださいって話があった記憶があります。

性能評価に関する専門用語

情報検索に限らない話ですが、効率（efficiency）・有効性（effectiveness）という2つの側面でシステムの性能は評価されます。

効率の指標の例

  • 応答時間：ユーザーがクエリを入力して、検索結果が表示されるまでの時間
  • スループット：1秒間に処理できるクエリ数（本では1秒と書いているが、1秒である必要は無い）

他にも、必要な記憶容量や消費電力なども効率の指標として挙げられます。

有効性：人間の判断による評価、効率よりも評価が難しい

  • 関連性（relevance）：ドキュメントがクエリに表現された情報要求を満たしているかどうか。二値（関連性あり/なし）や階層（5段階評価とか）で関連値を割り当てる。
  • ドキュメントの特異性（specificity）：ドキュメントがどれだけ情報要求に対して焦点を絞れているか
  • ドキュメントの網羅性（exhaustivity）：ドキュメントが情報要求に関連する情報をどれだけ広く含んでいるか
  • 新規性（novelty）：1番目のドキュメント見る→内容を学んで情報要求が変化→2番目のドキュメントの内容に新規の情報が無いと、新しい情報要求に対して関連性が無いことになる

新規性について、検索結果のドキュメントを読むうちに情報要求が変化して〜という記述がありましたが、検索結果返す時点でユーザーに対して新規性のあるドキュメントを返す…という考え方もあると思います。
例えばレコメンドでは、既にユーザーが見た商品よりも、見たことないけど買ってくれそうな商品を返してあげたい…などが考えられます。
（レコメンドは情報検索とは分けて考えた方が良いんですかね？）

電子テキストの取扱い

情報検索システムで電子テキストを扱うために、電子テキストの内容をトークン化して転置インデックスを作ります。
英語文書においてはトークンは英数字からなる文字列ですが、XML文書の場合はタグもトークンに含める場合があります。
また、トークンをユニーク化（シンボル、ターム）して集めた集合を語彙とよびます。

例えば

<STAGEDIR>Thunder and lightning. Enter three Witches</STAGEDIR>

<SPEECH>
<SPEAKER>First Witch</SPEAKER>
<LINE>When shall we three meet again</LINE>
<LINE>In thunder, lightning, or in rain?</LINE>
</SPEECH>

という文書があったときに、XMLタグと英数字のひとまりを小文字化したものをトークンとして扱うと、

<STAGEDIR> thunder and lightning enter
three witches </STAGEDIR> <SPEECH> <SPEAKER>
first witch </SPEAKER> <LINE> when
shall we three meet again
</LINE> <LINE> in thunder lightning
or in rain </LINE> </SPEECH>

となります。

ターム分布

ターム分布はタームごとに文書に出現した頻度の分布です。

本ではシェイクスピア戯曲集を題材に、トークン化やターム分布の可視化を行なっていました。
シェイクスピア記事全部扱うのは面倒なので、「マクベス」を題材にPythonでトークン化などの実験をしてみます。
「マクベス」のXML版は https://www.ibiblio.org/ からダウンロードできます。

まずは「マクベス」文書をトークン化し、collections.Counterに突っ込みます

token_counter = Counter()

# 最初3行はXML宣言なのでスキップ
for line in macbeth_txt.split("\n")[3:]:
    # XMLタグを分割したいので ">" -> "> "および"<" -> " <"に置換しておく
    # "," "." "?"は消す（他にも消した方が良い文字あるかも）
    replaced_line = line\
        .replace(">", "> ")\
        .replace("<", " <")\
        .replace(",", "")\
        .replace(".", "")\
        .replace("?", "")
    for token in replaced_line.split(" "):
        if token == "":
            continue
        
        # XMLタグの場合はそのまま
        if "<" in token:
            token_counter[token] += 1
        # 英数字の場合は小文字化
        else:
            token_counter[token.lower()] += 1

頻出上位20タームを見てみます。

token_counter.most_common(20)

[('<LINE>', 2385),
 ('</LINE>', 2385),
 ('the', 735),
 ('<SPEAKER>', 650),
 ('</SPEAKER>', 650),
 ('<SPEECH>', 649),
 ('</SPEECH>', 649),
 ('and', 567),
 ('to', 381),
 ('of', 348),
 ('i', 313),
 ('macbeth', 273),
 ('a', 251),
 ('that', 225),
 ('in', 206),
 ('my', 192),
 ('you', 190),
 ('is', 185),
 ('<STAGEDIR>', 180),
 ('</STAGEDIR>', 180)]

LINE・SPEAKER・SPEECHのタグおよび、代名詞や前置詞がよく出現しています（納得）

出現頻度と順位のモデル化として有名な*ジップの法則*があります。
ジップの法則は
\log(\mathrm{frequency})=C-\alpha \cdot \log (\mathrm{rank})
もしくは式の形を変えて、
\mathcal{F}_i \sim \frac{1}{i^\alpha}
と表されます。ここで、frequencyはタームの頻度、rankはそのタームの頻度の順位、 \mathcal{F}_iはi番目に多く出現するタームの頻度です。

実際に「マクベス」文書におけるタームの頻度・順位をプロットしてみます。

# ターム分布
num_tokens = len(token_counter)
xs = np.arange(1, num_tokens + 1)
ys = [freq for _, freq in token_counter.most_common()]
plt.scatter(xs, ys, marker="+")

# ジップの法則
alpha = 1
C = 3e3  # アドホックに決めた
ys_zipf = C * 1 / xs ** alpha
plt.plot(xs, ys_zipf, ls="--", c="gray", label="Zipf's law")

plt.xscale("log")
plt.yscale("log")
plt.legend()
plt.xlabel("rank")
plt.ylabel("frequency")

確かに、おおよそ直線に乗っています。

また、英語の場合はジップの法則における \alphaはほとんどの場合約1となるようです。

言語モデル

（言語モデルに関しては、各所から出版されている自然言語処理本や記事の方が詳しいかと思いますが、、）

marujirou.hatenablog.com

新しいテキストに関する内容予測は、言語モデル（language model）とよばれる語彙の確率分布モデルに基づいて行われる.

まずは最も単純な言語モデル（bag of words モデル）から紹介します。
語彙中のシンボル \sigmaの固定出現確率分布 \mathcal{M}(\sigma)を
\sum_{\sigma \in \mathcal{V}} \mathcal{M}(\sigma) = 1
と表します。

既知のテキストから上の言語モデルを作るとすると、例えば
\mathcal{M}(\sigma) = \frac{\mathrm{frequency}(\sigma)}{\sum_{\sigma' \in \mathcal{V}} \mathrm{frequency}(\sigma ')}
と定義できます。

上の「マクベス」文書でターム頻度を求めておいたので、簡単に M(\sigma)を求めることができます。

token_counter["the"] / sum(token_counter.values())
# 0.028090961207720238

token_counter["scotland"] / sum(token_counter.values())
# 0.00042040894324479265

次に、高次の言語モデルで文脈を扱えるようにします。
例えば、"our"の次には普通名詞が出現しやすくて、"the"は出現しにくい、ということを扱えるようにします。

1次の言語モデルは
\mathcal{M}_1(\sigma_2|\sigma_1) = \frac{\mathrm{frequency}(\sigma_1 \sigma_2)}{\sum_{\sigma' \in \mathcal{V}} \mathrm{frequency}(\sigma_1 \sigma ')}
と表されます。

また、未知のシンボルの組み合わせに対応するために、1次モデルと0次モデルを組み合わせて平滑化する方法が紹介されていました。
バイグラムは新規ドキュメントでは出現しにくいので \mathcal{M}_1が0になりやすく、ドキュメント生成確率に0が割り当てられてしまいがちですが、平滑化により値を割り当てます。

\mathcal{M}'_1(\sigma_2|\sigma_1)=\gamma \cdot \mathcal{M}_1(\sigma_2|\sigma_1)+(1-\gamma) \cdot \mathcal{M}_0(\sigma_2)

テストコレクション

検索手法の評価を目的として作成された文書およびタスクセットで、TREC（Text REtrieval Conference）が有名です。
Text REtrieval Conference (TREC) Home Page

TREC 1999におけるアドホックタスクのトピック例

<top>

<num> Number: 426
<title> law enforcement, dogs

<desc> Description:  Provide information on the use of dogs worldwide for
law enforcement purposes.

<narr> Narrative:  Relevant items include specific information on the
use of dogs during an operation. Training of dogs
and their handlers are also relevant.

</top>
  • titleフィールド：検索エンジンに入力されるようなクエリとして使う
  • descriptionフィールド：トピックの情報要求を文書形式で記述している。このフィールドもクエリに使うことができる。
  • narrativeフィールド：title・descriptionフィールドを補充する内容が記述されている

2000年以前のTRECでは新聞やニュース配信サービスの記事、アメリカ政府の出版物から選ばれたドキュメントをCDに記録して配布していましたが、最近のタスクではwebからクロールして取得したドキュメントを利用しています。

データサイズ規模感→Test Collections

オープンソースIRシステム

以下のシステムが紹介されていました。

  • Lucence
  • Indri
  • Wumpus

どこもかしこもLucene（Solr、Elasticsearch）を使っていると思います…
実際、本でも

Luceneは最も成功したオープンソース検索エンジンである.

と記述されています。

まとめ

イントロダクションなので深入りする話は少なかったです。
とはいえ、情報検索を専門にする人にとっては知ってて当然？のような話が盛り込まれていたので、まさにイントロダクションという意味では重要な章だったかな…という感想です。

*1:Selective dissemination of information - Wikipedia

*2:TDT (Topic Detection and Tracking)