情報を探す能力が著しく欠如しているため情報検索に入門した

はじめに
導入
情報検索とは
今までは具体的にどうやって検索を実現してきたのか？
検索モデルについて
終わりに
参考文献

はじめに

随分久しぶりにブログを書いているが、前回投稿したのが3月15日だったので、すでに5ヶ月以上も経過しているということになる。5ヶ月あっても僕の知り合いのニートは技術はあっても社会に還元せず、家族に視線がれいとうビームされながらも田舎で親のスネを齧り、悠々自適なフリーター生活を続けている。羨ましい。
どうでも良いが、今回のブログでは情報検索(Information Retrieval)を取り扱う。また、筆者は自然言語処理にも情報検索にも詳しくなく、数学はおろか算数も怪しい。そのため、解釈や内容に間違いがあった場合は優しく指摘していただけると幸いです。

導入

近年、Google検索は利用者に使いやすいようにと日々進化を続けている。それにも関わらず、僕のような無能にはGoogle検索はオーバーテクノロジーだ。気がついたら検索したい内容を上手く言語化できず「なんかあれ」とか「最高」とか検索キーワードに入れて検索している。そして、僕がオプションで上手く使えるのは「filetype:pdf」だけだが、「Google Scholarを使った方が良くね」と言われるレベルの情弱さである。そこで、そもそもの検索の仕組みを理解した気になることでGoogle検索も使えるようになるのではと考えた。申し訳ないが、読者の方々には私の自慰行為に付き合ってもらう。今回は下記の書物を主な教科書にして勉強を進めていく。

『情報検索と言語処理』
http://amzn.asia/5YazRgz
ブログ更新しなさすぎてamazonのアフィリエイトの審査に落ちたの悲しすぎる。

情報検索とは

情報検索と何となくそれっぽい学問を選んだが、果たして情報検索とは何なのか。
『情報検索と言語処理』のP7にはこう書かれている。

情報検索(information retrieval)(広義)
ユーザの持つ問題(情報要求)を解決できる情報を見つけ出すこと
情報検索(information retrieval)(狭義)
ユーザの検索質問(query)に適合する文書(document)を文書集合(document collection)の中から見つけ出すこと

狭義の情報検索は今の検索エンジン(Google, yahoo, bingなど)が当てはまると言える。
ここで、情報要求という言葉が出てきたが、こちらは『情報検索と言語処理』のP3に定義が書かれている。

情報要求(information need)
ユーザがある目的を達成するために現在持っている知識では不十分であると感じている状態

例えば、今AKBにいるのかわからないが「小嶋陽菜」の画像を全て集めたいというユーザの目的を達成するためには「こじはるにゃんにゃんこじぱﾆｬﾛこじまるこじまるさん小嶋さん陽菜陽菜ちゃんぱるぱるさんにゃんなんにゃん」などの愛称(AKB48メンバー愛称から引用)を全て知らないといけないと感じているという状態だろうか。
もう少し情報要求の段階を細かい分類をTaylorさんが1968年に"Question-Negotiation and Information Seeking in Libraries"という論文で提案していて、下記がその分類となる。(これもP3に書いてある)

$Q_1$ :直観的要求(visceral need)
現状に満足していないことは認識しているが、それを具体的に言語化して上手く説明できない状態
$Q_2$ :意識された要求(conscious need)
頭の中では問題を意識できるが、曖昧な表現やまとまりのない表現でした言語化できない状態
$Q_3$ :形式化された要求(formalized need)
問題を具体的な言語表現で言語化することができる状態
$Q_4$ :調整済みの要求(compromised need)
問題を解決するために必要な情報の情報源が同定できるくらい問題が具体化された状態

先ほどの「小嶋陽菜」の例でいうと、愛称が分からないということが分かっているのであれば、あとはgoogle先生に「小嶋陽菜愛称」とでも打って愛称を探して、個々の愛称を画像検索すればいい。そのため、この場合は問題が同定できて、具体的に問題解決の方法が見えている状態なので、 $Q_4$ にあたる。

情報要求が分かったので、情報検索の広義の意味は理解できたと思いたい。次に情報検索の基本的なモデルの図(P7)が整理されていてよかったため、一部手を加えて記載する。

f:id:gat-chin321:20170624161038p:plain
図：情報検索の基本モデル

現実世界の情報とユーザの情報要求の2つがあり、この2つは直接比較することが現状不可能である。
現実世界の情報を解釈した結果が文書として存在していると仮定し、ユーザはユーザの情報要求を検索質問という形で表現する。
どちらもそのままではコンピュータで扱うことが難しいので、内部表現という形に落としこむこと(索引付け)で比較を可能にして、最もマッチする情報を見つけ出す。
狭義の情報検索では、検索質問という形式で与えられることを仮定しているため、ユーザ側の情報要求そのものを考慮していない。
例えば、「なんかまるいやつ」という検索質問が与えられたときに、ユーザが「卵」を想像していても、検索エンジンはそれを考慮して検索を行わない。
検索エンジンに能力がないことを言いたいわけではなく、ユーザ自身の情報要求に対する解釈の精度が検索に大きな影響を与えてしまうため、検索は難しいことが言いたかったわけである。
あまり人の文章を引用するのは好きではないのだが、この辺の定義については勝手に解釈を述べてしまうと大変なことになると考えたため、ほとんど引用という形になってしまった。これらを踏まえた上で学習を進めていく。

今までは具体的にどうやって検索を実現してきたのか？

当時(2012年周辺)では、「文書の内容を表していると考えられる要素(索引語)を文書から取り出して、その集合を使って文書の内容を近似する」ことが一般的なアプローチとして用いられていたらしい。
索引語を取り出す際に問題となるのが、日本語の場合、英語とは違って単語間に空白がないため、機械的に単語を分割することが難しい。
そこで、形態素解析という処理を行って、単語の分割を行う。ただ、形態素解析も精度は100%というわけにも行かないという問題がある。
漢字のように一つの文字が意味を持っている日本語や中国語の場合は、1文字を1つの索引語として使うこともあったらしいが、この場合、意味が多様すぎるため、記事の内容を表現することが難しい。

人手での索引付けの場合

当初は文書から形態素解析で索引語を機械的に抽出した後、人の手で索引語を追加・編集したり、削除したりして、上手く内容を表現できていそうな形に修正する索引付けを行っていたようだ。
しかし、索引付けを人手で行っても、索引付けに一貫性を持たせることが困難(特に複数人の場合)である。複数人で同じ文書の索引付けを行う実験を行ったところ、それぞれの索引付けの一致度はせいぜい30%程度という結果(Cleverdon,1984)になった。

機械的な索引付けの場合

一方で索引付けを機械的に行う方法では同じ一貫性は保つことができるが、機械は意味を理解しない。何の工夫もなければ、同義語や重要度の高い語句が出た時に優先的に結果に表示するなどの対応が難しい。だが、精度に関しては人が行うのと同等かそれ以上の精度を叩き出していたようなので、徐々に一般的になり始めたようだ。
そのため、大まかには下記の流れで典型的な自動索引付けは行われてきた。

(1) 形態素解析による単語の分割
(2) 不要語(stop word)の削除
(3) 接辞の処理
(4) 検索質問拡張
(5) 語の頻度をもとにして索引語に重み付け

上記だけを見ても、自然言語処理の知識のない方からすると、ピンとこないと思う。少なくとも私にはピンと来なかった。そのため、より具体的に説明していく。

(1) 形態素解析による単語の分割

形態素解析のWikipediaにおける定義は下記の通りである。

文法的な情報の注記の無い自然言語のテキストデータ（文）から、対象言語の文法や、辞書と呼ばれる単語の品詞等の情報にもとづき、形態素（Morpheme, おおまかにいえば、言語で意味を持つ最小単位）の列に分割し、それぞれの形態素の品詞等を判別する作業である。
形態素解析 - Wikipediaより引用

定義を見ても良く分からないかもしれないが、形態素解析で行うことは、主に下記の3種類の処理である。
・単語分割
　単語になる位置(単語の境界)を判別し、その場所で文字を区切ることで分割を行う。
　例)「大きな栗の木の下で」->「大きな / 栗 / の / 木 / の / 下 / で」
また、形態素解析の一部である具体的なPython+MeCabを用いた分かち書き(単語分割)の処理の実装例を下記に示す。

import MeCab

document = '労働は人類史上最大の悪であり、我々はこの悪に立ち向かわなければならない。'
tagger = MeCab.Tagger("-Owakati")
# 分かち書きしたら、改行コード\nが後ろに挿入されるので消す。
wakati = tagger.parse(document).strip()
print(wakati)

・品詞推定
　単語分割された文における単語の品詞を当てる。
　例) 「人生に悩み、苦しむ」の悩みは動詞、「悩みのない人生」の悩みは名詞。

・語義の推定
　単語のうち、表記上意味が曖昧な語を特定する。
　例) 「さんぽ」は「散歩」、「三歩」などの漢字への変換により違う意味を持つ語がどれに当てはまるのかを判断する。
　参考資料:形態素解析の過去・現在・未来

また、この他にも形態素解析で行う処理は存在するらしいが、形態素解析という枠組みではどこまでやるのかは曖昧なようだ。

(2) 不要語(ストップワード)の削除

不要語の削除についてだが、不要語とは文字通り、内容を表現するにあたり、不要な語句のことである。
例えば、「、」や「。」、「を」、「ある」などの文の内容に影響を与えないものを取り除く。
理解を進めるため、これを実装した簡易的なソースコードを下記に記述する。

# ストップワードの削除を行うメソッド 
def remove_words(words, stop_words):
    return [word for word in words if word not in stop_words]

stop_words = ['、', '。']
result = remove_words(wakati.split(" "), stop_words)
print(result)

pythonのライブラリでもストップワードの削除を行う機能がついているものもある。有名なものだとscikit-learnとかgensimには引数にリストを渡すとストップワードの削除をしてくれる機能がある。
「なぜ、ストップワードを削除するのか」という点が気になる方もいるかもしれない。この理由は分類する上で余計な単語を削除することにより、メモリの消費を抑えたり、処理を効率化できたり、精度が上がったりするためである。

ストップワードを削除したあとは、ジップの法則(Zipf's law)を用いて全文書において、稀にしか出現しない低頻度語や逆にほぼ全ての文書で存在する高頻度語を削除するのが一般的とされている。なぜこんなのことをするのかというと、実際にデータを分析すると、ストップワードだけでは網羅できない検索を行う上で不要な単語が何かしら出現するはずであり、それらの語に対して対応するためである。低頻度語と高頻度語を削除する理由についてより詳細に説明していく。

・低頻度語について
稀にしか出現しない単語が索引語として用いられたときを考えてみる。3万件の文書中で1回しか出てこない単語があるとすると、その文書集合の中で1つしか出ないことはあまり文書の内容を表現する際に重要でない語であり、網羅性に欠けることから索引語として適切でないとされている。例えば、読んだことはないが、女性誌の記事であまり出現しなさそうな「ディープラーニング」という単語の場合、女性誌の文書を検索する場合「ディープラーニング」は文書を特徴づける単語ではない。一方、「ギャル」という単語なら一部雑誌ではそこそこ出てくると思うので、ギャル系雑誌(?)というような文書群を特徴付ける単語と言えると考えられる。
また、索引語の頻度を索引語の重み(大きいと重要度が高い)として用いる場合、低頻度の索引の重みは自動的に小さくなるため、無視しても検索にはあまり影響がない。そして、索引語の数は少ない方が計算量が少なくなり、メモリ上に配置するデータ量も少なくなるため、システムを構築する際には無視した方が良いとも考えられる。

・高頻度語について
どの文書にでも良く用いられるような頻度で出現するような単語を索引語として使うと、検索する際にどの文書にでも存在する単語なので検索結果としてはどの文書でも表示してしまうことになるため、網羅性が高くなりすぎる。そのため、索引語としては適切でないと考えられる。例えば、先ほどの女性誌の例でいくと「可愛い」という単語はどの雑誌でも出てくると思うので、該当の女性誌がどういう内容なのかを特徴付ける単語ではないと考えられる。

具体的に中程度の頻度をどのような基準で判断するのかというと、下記の2つのZipfの法則(Zipf's law)というものが使われる。

Zipfの第1法則:
$\begin{eqnarray} r \cdot f = C \end{eqnarray}$
$r$ : 出現頻度の順位
$f$ : 単語の出現頻度
$C$ : 定数
細かい内容は省くが、Zipfの第1法則は文書中の語を出現順位順に並べたときに順位 $r$ と頻度 $f$ の積が定数 $C$ になるということを経験的に主張したものである。
この式(1)は高頻度の単語には当てはまるが、低頻度の単語については同順位の語が多くなるため、うまく当てはまらない。

下記の図は私が趣味で収集しているとあるクラスタのツイート3万件(一部だけ使った)のデータにおいて、単語ごとの出現頻度を左から降順にソートしたものがある。
x軸のラベルを単語にしているのだが、単語数が多すぎて、真っ黒になってしまっているところは気にしないで欲しい。
f:id:gat-chin321:20170902235845p:plain

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

def zipf1(frec, rank):
    c = frec * rank
    return c

# datasetの中の単語を数え上げ
counter = Counter(dataset)
for word, cnt in counter.most_common():
    words.append(word)
    counts.append(cnt)

# 出現頻度の順位をつける
ranks = []
for index, v in enumerate(types.values()):
    ranks += [index+1 for _ in v]

# zipfの第一法則の計算
zipf1_score = [zipf1(cnt, rank) for cnt, rank in zip(counts, ranks)]

# 描画の処理
mpl.rcParams['font.family'] = 'AppleGothic' # 日本語のフォントを読み込む(フォントインストールするの面倒だったので、AppleGothicにした)
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_xticks([i for i in range(1,len(words)+1)])
ax.set_xticklabels(words, rotation=90,fontsize='small')
# zipfの第一法則の計算結果を描画
ax.plot(zipf1_score)
plt.show()

また、実際にこのデータでZipfの第1法則の $C$ を計算してみると下記となった。
f:id:gat-chin321:20170701125426p:plain

頻度の低い単語と比べて、頻度が高い単語が少ないためわかりづらいが、左端の部分に一部 $C$ の値が比較的一定なところがあるため、その部分を拡大してみたものがこちらとなる。
f:id:gat-chin321:20170701131510p:plain

さらに拡大してみたものがこちら。
f:id:gat-chin321:20170701125950p:plain

綺麗に一直線になってくれるのを期待していたが、そうはならなかった。
部分部分で結構な上下はあるが、比較的一定なところが見つかった。不穏な単語が多いが気にしないで欲しい。
実は見つけられていないだけでもっといい感じの場所はあるのかもしれない。

Zipfの第2法則:
$\begin{eqnarray} \frac{F_1}{F_f}=\frac{f(f+1)}{2} \end{eqnarray}$
$f$ : 単語の出現頻度
$F_f$ : 単語の出現頻度 $f$ の語の異なり数

Zipfの第2法則は低頻度語に対して成り立つ。頻度 $f$ の語の異なり数というのが何なのか分からなかったので、調べたところ、異なり語数とも呼ばれていて、
単語の種類数のことを指しているようだった。*1
つまり、頻度1の異なり語数を出現頻度 $f$ の異なり語数で割った値が $\frac{f(f+1)}{2}$ に等しくなるということだろう。

という訳で実際に計算してプロットして行ってみよう。左辺と右辺をそれぞれプロットすることにした。
f:id:gat-chin321:20170701153936p:plain

この図だとほとんどの語で左辺と右辺が等しくなっているように見えているが、これはy軸の単位が大きすぎるためだ。
そこで、少し拡大してみる。
f:id:gat-chin321:20170701162512p:plain

図をみていくと、高頻度のものはかなり左辺と右辺が離れているが、頻度が低くなるにつれて徐々に値が近づいていくのがわかる。
また、さらに拡大してみたものを下記に示す。
f:id:gat-chin321:20170701154503p:plain

最終的に1.0で一致するが、1.0は式(2)の右辺から考えると頻度1の単語となっていることがわかる。

ちなみにこれらの図は下記のソースにより計算した。

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

# zipfの第2法則の関数(left_sideに左辺、right_sideに右辺)
def zipf2(f1_type, frec, ff_type):
    left_side = f1_type/ff_type
    right_side = frec*(frec+1)/2
    return left_side, right_side

words = []
counts = []

# datasetの中の単語を数え上げ
counter = Counter(dataset)
for word, cnt in counter.most_common():
    words.append(word)
    counts.append(cnt)

# 単語の出現頻度ごとの語の異なり数の算出
types = {cnt:[] for cnt in counts}
for cnt, word in zip(counts, words):
    types[cnt].append(word)

# zipfの第二法則の計算
left_sides = []
right_sides = []
for cnt in counts:
    left, right = zipf2(len(types[1]), cnt, len(types[cnt]))
    left_sides.append(left)
    right_sides.append(right)

# 描画の処理
mpl.rcParams['font.family'] = 'AppleGothic'
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_xticks([i for i in range(1,len(words)+1)])
ax.set_xticklabels(words, rotation=90, fontsize='small')

# 左辺の描画
ax.plot(left_sides, 'b', label='left')

# 右辺の描画
ax.plot(right_sides, 'r', label='right')

plt.show()

Zipfの第1法則は高頻度語に、第2法則は低頻度語に対して成り立つので、両方の式が成り立つ語は中頻度語であると考えようというのが基本的な考え方である。
ただ、この2つの法則をどう反映すれば、中頻度語が抽出できるのかというと、下記の式によってある程度の目安を算出することができる。
$\begin{eqnarray} f =\frac{\sqrt{8F_1+1}-1}{2} \end{eqnarray}$
式(1)は同じ順位の語がないという仮定を置いているため、式(1)と式(2)の両方が成り立つ境界を求める場合、式(2)では頻度 $f$ の異なり語数が1であるもののみを考慮すれば良い。つまり、 $F_f=1$ であるから、式(2)より、
$\begin{equation} F_1 =\frac{f(f+1)}{2} \end{equation}$
これを $f$ について解いていく。
$\begin{equation} F_1 =\frac{f^2+f}{2} \end{equation}$
$\begin{equation} 2F_1 =f^2+f \end{equation}$
左辺と右辺を入れ替えて、右辺を左辺に移行すると
$\begin{equation} f^2+f - 2F_1 = 0 \end{equation}$
これを二次方程式の解の公式*2に当てはめると、
$\begin{equation} f = \frac{-1 \pm \sqrt{1-8F_1}}{2} \end{equation}$
$F_1 \geq 1$ であることと頻度に負の値はありえないことから、整理すると
$\begin{equation} f =\frac{\sqrt{8F_1+1}-1}{2} \end{equation}$
となり、式(3)が導出される。

今回使ったデータで式(3)を下記のプログラムを使って計算してみたところ、371.88201887460326となった。

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

import math
# zipfの法則で中頻度を算出する関数
def zipf(f1_type):
    freq = math.sqrt(8 * f1_type + 1) - 1
    return freq

# 単語の出現頻度ごとの語の異なり数の算出
types = {cnt:[] for cnt in counts}
for cnt, word in zip(counts, words):
    types[cnt].append(word)

# 頻度1の語の異なり数を渡すと、計算結果が返ってくる
print(zipf(len(types[1])))

頻度372周辺が中頻度ということになる。どこまでの範囲を考慮するのかは特に記述はなかったが、
これを参考に任意で境界線を決めてくれということだろうか。

用途がよくわからなかったので、いくつかの論文に目を通してみた。
下記の論文では、ベイズ情報量基準(BIC)を用いて単語の上限と下限を調整した上限・下限の値をzipfの法則で算出した中頻度と見比べた時に、上限と下限の真ん中あたりに中頻度がきていて、最良推定で行ったものよりもうまくバランスが取れていれば良いというような答え合わせに使うような使い方がされている。
http://db-event.jpn.org/deim2009/proceedings/files/B6-6.pdf

下記の論文では、出現数1位から中頻度語までの単語を取り出し、出現数1位から中頻度語までの単語数と同じ数分だけ中頻度語以降の頻度の単語を取り出して使うことで、低頻度語をうまく弾くために使用されている。
http://www.ieice.org/iss/de/DEWS/proc/2004/paper/3-C/3-C-02.pdf

下記の論文では、zipfの法則を中頻度の算出に使うというよりかはデータの性質の説明のために記載されている感じがする。
https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=11187&item_no=1&page_id=13&block_id=8

調査してみた感じでは、特にカチッと良い感じの語を取り出せるような便利なものではないような印象となった。そんな便利なものなら前処理が不要になってるはずなので当たり前といえば当たり前だ。

前処理の全体の話題については下記が詳しいので、ご参考ください。
自然言語処理における前処理の種類とその威力 - Qiita

接辞の処理

語形の多様性を正規化する処理。日本語での接辞処理は形態素解析とほぼ同義となるため、語の境界が曖昧な日本語ではあまり意識されない。しかし、英語のように語の境界が明確で、語が屈折したり、接辞により派生する言語では問題になるらしい。例えば、英語では"Bob plays soccer very well"と"Bob is a good soccer player "という文章では、サッカーをする内容を"player"(名詞)、"plays"(動詞)などのそれぞれ別の品詞で表現することができる。どのような品詞で表現できる。この場合、"player"と"plays"は両方とも"play"に正規化するらしい。
この正規化を行う方法で紹介されているのは下記の3つである。
・Lovinsの方法
・Porterの方法
・Paice/Huskの方法
このうち、『情報検索と言語処理』では、Paice/Huskの方法が取り上げられて詳しく説明されていた。
私としては日本語の文書を検索したいので、ここについてはこの辺で切り上げて次に行きたいと思う。

検索質問拡張

例えば、「お母さん」、「母親」、「ママ」などの表現の多様性(語選択の多様性)に対応するための処理。
『情報検索と言語処理』では、具体的なアプローチについては触りだけだが、ルールベースによる方法とLSI(latent semantic indexing)が紹介されている。
これについては今回は触れないこととする。

語の頻度をもとにして索引語に重み付け

索引語の重要度を付与するために重み付けを行うが、重み行列Wは行列の形で下記のような表現される。
\[
W = \left(
\begin{array}{cccc}
w^1_{1} & w^1_{2} & \ldots & w^1_{n} \\
w^2_{1} & w^2_{2} & \ldots & w^2_{n} \\
\vdots & \vdots & \ddots & \vdots \\
w^m_{1} & w^m_{2} & \ldots & w^m_{n}
\end{array}
\right)
\]
『情報検索と言語処理』では、列が文書 $d$ で行が単語 $t$ で表されている。
$w$ を決めるための重み付けのアプローチについては下記の方法が紹介されている。
・索引頻度(term frequency)
・IDF(Inverse Document Frequency)
・信号/雑音比(singnal-noise ratio)
・索引語の識別値(term discrimination value)
これらをより具体的に説明していく。

索引頻度(term frequency)

文書 $d$ に出現する索引語 $t$ の頻度 $tf(t, d)$ を重み $w^d_{t}$ として使う方法。つまり、
$\begin{eqnarray} w^d_{t} = tf(t, d) \end{eqnarray}$

この重みづけには文書が長くなった場合に他の短い文書と比べて、索引語に対する重みが大きくなってしまうという問題がある。
そのため、下記の計算で正規化することが考えられる。
$\begin{eqnarray} w^d_t = \frac{tf(t, d)}{\sum_{s \in d}tf(s, d)} \end{eqnarray}$
式(5)では何をしているのかというと、例えば、「労働は人類史上最大の悪」という文であれば、「労働」という索引語の重みを求める際に、「労働」という索引語の出現頻度(=1)から該当の文書全ての索引語の出現数(=7)で割った相対頻度を求めている。
この例で言えば、「労働」の重みは $\frac{1}{7}$ となる。

IDF(Inverse Document Frequency)

索引語頻度による重み付けは各文書中の索引語の頻度については考慮しているが、全体の文書における索引語の分布を考慮していない。
どの文書でも出現している索引語があった場合、その索引語はそれぞれの文書の内容を表現するのに重要ではないと考えられる。
そこで、下記のIDFの重み付けが利用されることもある。
$\begin{eqnarray} w^d_t = idf(t) = log \frac{N}{df(t)}+1 \end{eqnarray}$
$N$ : 検索対象になる文書集合中の全文書数
$df(t)$ : 索引語 $t$ が出現する文書数
ここで、対数をとっている理由は文書の規模に対してIDFの値の変化を小さくするためである。
この対数をとる効果の検証のため、実際に文書数10件,100件,1000件,10000件の4パターンでのIDFの値を実験して確認する。*3

信号/雑音比(singnal-noise ratio)

情報理論のエントロピー(entropy)という尺度を用いることで、ある索引語が文書集合中の各文書における出現数にどれくらい偏って出現するかを数値化する方法。
エントロピーは $H(P)$ ある確率変数 $P$ が事象 ${E_1, E_2, ..., E_n}$ を値でとり、それぞれの事象の生起確率*4が ${p_1, p_2,...,p_n}$ である時、下記の式で定義される。
$\begin{eqnarray} H(P) = - \sum^n_{i=1} p_i log_2 p_i \end{eqnarray}$
エントロピーは各事象が一様分布にしたがって生起する時に最大となり、生起確率が偏ると小さくなる。
ちなみに一様分布にしたがって生起する時に最大になることはラグランジュの未定乗数法を用いることで求められる。*5
直感的にはエントロピーが高くなるのは情報を全く含まない最も普遍的な分布である。つまり、全ての事象の生起確率が等しいような生起する事象を予測するのが困難な情報ほどエントロピーが大きくなる。
より具体的な説明については『情報検索と言語処理』の例がとても分かりやすかったので、ぜひ買って読んで欲しい。

では、どうやってエントロピーを索引語の重みに応用していくのか。
まず、ある索引語 $t$ が文書 $d_k = {d_1, d_2, ..., d_N}$ に出現する確率を $p^k_t$ で表す。
この場合、式(7)から確率変数のエントロピー $n_t$ は下記で定義される。
$\begin{eqnarray} n_t = - \sum^N_{t=1} p_t log_2 p_t \end{eqnarray}$

この確率 $p^k_t$ は索引語 $t$ の総出現数と文書 $d_k$ 中の出現数の相対頻度で推定できるので、
$\begin{eqnarray} n_t = - \sum^N_{t=1} \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} log_2 \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} \end{eqnarray}$
となる。 $\frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)}$ は微妙に式(5)で計算している内容と似ているが、別物であることに注意したい。
式(5)ではある文書での索引語の出現数を文書中の全ての索引語の出現数で割っているのに対し、式(9)ではある文書
での索引語の出現数を文書全体での索引語 $t$ の総出現数で割っている。つまり、式(5)では分母がある文書の全ての索引語の出現数を求めているのに対し、式(9)では文書全体でのある索引語 $t$ の出現数を求めているため、別の計算をしていることを留意しておく必要がある。

これでエントロピーの計算ができたが、これ単体ではある索引語がどれだけその索引語が出現する文書を当てることが難しいのかということが分かるようになった。
ただこれをそのまま何もせず重みとして使うと、エントロピーが大きい索引語が出現する文書ほど当てることが困難になることから、重要でないと考えられる索引語の重みが大きくなってしまうので、あまり好ましくない。そこで、この式(9)の $n_t$ を索引語 $t$ の雑音と呼び、索引語の重みは下記で計算する。
$\begin{eqnarray} w^d_t = s_t = log_2 \sum^N_k=1 tf(t,k) - n_t = log_2 \sum^N_k=1 tf(t,k) + \sum^N_{t=1} \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} log_2 \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} \end{eqnarray}$
これにより、全文書中の索引語の総和という重みから索引語のエントロピーを引くことで、索引語の重要度が低いものは重みが小さくなり、逆の場合は重みが大きくなるように調整される。

索引語の識別値(term discrimination value)

重みを出したい索引語を入れた時と除いた時の2つの文書 $d_i$ と $d_j$ の平均類似度の差を使うことで、索引語の重みを算出する方法。
ここで用いる類似度は0〜1の間の値をとるように正規化されていることを前提にしている。
$\begin{eqnarray} d_{v_t} = \delta(+t) - \delta(-t) \end{eqnarray}$
$\sigma(+t)$ : 索引語 $t$ を追加した場合の平均類似度
$\sigma(-t)$ : 索引語 $t$ を取り除いた場合の平均類似度
また、 $\sigma$ そのものは下記の数式により定義する。
$\begin{eqnarray} \delta = \frac{1}{N(N-1)}\sum^{N}_{i=1} \sum^N_{j=1(i \neq j)} \sigma(d_i, d_j) \end{eqnarray}$
$N$ : 文書集合中の総合文書数
・内積
$\begin{eqnarray} \sigma (d_x, d_y) = \sum^T_{i=1}x_i \cdot y_i \end{eqnarray}$
・Dice 係数 (Dice coefficient)
$\begin{eqnarray} \sigma (d_x, d_y) = \frac{2\sum^T_{i=1}x_i \cdot y_i}{\sum^T_{i=1}x^2_i + \sum^T_{i=1}y^2_i} \end{eqnarray}$
・Jaccard 係数 (Jaccard coefficient)
$\begin{eqnarray} \sigma (d_x, d_y) = \frac{\sum^T_{i=1}x_i \cdot y_i}{\sum^T_{i=1}x^2_i + \sum^T_i y^2_i - \sum^T_{i=1} x_i \cdot y_i} \end{eqnarray}$
・余弦
$\begin{eqnarray} \sigma (d_x, d_y) = \frac{\sum^T_{i=1} x_i \cdot y_i}{\sqrt{\sum^T_{i=1}x^2_i \times \sum^T_{i=1} y^2_i }} \end{eqnarray}$
$x_i$ : 文書 $d_x$ の索引語 $i$ に対する重みもしくは索引語の有無の2値変数(索引語がある時に1, ない時に0とする重み)
$T$ : 索引語の総数

この式をそのまま全ての文書ペアに対して計算すると文書の量が多いとかなりの計算量になってしまうため、下記の式で全ての文書の重心と比較する。
$\begin{eqnarray} \bar{tf}(t,c) = \frac{1}{N} \sum^N_{i=1} tf(t, d_i) \end{eqnarray}$

TF-IDF重み付け

現在でも簡単な文書の分類などに用いられる索引頻度とIDFを掛け合わせることで組み合わせた重み付けの方法。おそらくこの中では一番有名だろう。
$\begin{eqnarray} w^d_t = tf(t, d) \cdot idf(t) \end{eqnarray}$
他にも同様に索引頻度と組み合わせた下記のような重み付けも存在する。
$\begin{eqnarray} w^d_t = tf(t, d) \cdot s(t) \end{eqnarray}$
$\begin{eqnarray} w^d_t = tf(t, d) \cdot dv(t) \end{eqnarray}$

検索モデルについて

ブーリアンモデル(Boolean retrieval)

論理式で検索に使う質問を表現して検索するアプローチでいわゆる世に出回っているAND検索やらOR検索やらである。これは論理検索(logical retrieval)とも呼ばれる。
例えば、 $t_1 AND t_2$ で検索したいとして、 $t_1$ と $t_2$ がそれぞれを含む文書が下記の通りの時を考える。
$t_1$ を含む文書集合: ${d_1, d_2, d_3, d_4, d_5}$
$t_2$ を含む文書集合: ${d_2, d_5, d_8}$
この場合、論理式のANDで検索しているため、両方を含む文書を探す。この場合だと ${d_2, d_5}$ が検索結果となる。
高速化したくなった場合は、B木構造やTrie構造などを使ったりして高速化するらしい。
ブーリアンモデルにおける欠点は索引語の重要度を扱えないため、検索結果をスコアリングして順位付けができないという点である。

ベクトル空間モデル

下記のような縦が文書、横が単語として対応しているように索引付けを行った重みの行列で表現して、文書のベクトルと質問文(クエリ)のベクトルの間の類似度を用いtることで検索質問に似ているものを提示するアプローチ。
\[
W = \left(
\begin{array}{cccc}
w^1_{1} & w^1_{2} & \ldots & w^1_{n} \\
w^2_{1} & w^2_{2} & \ldots & w^2_{n} \\
\vdots & \vdots & \ddots & \vdots \\
w^m_{1} & w^m_{2} & \ldots & w^m_{n}
\end{array}
\right)
\]

確率モデル

確率モデルのアプローチとして提示された下記の3パターンが紹介されている。

MaronとKuhnsのアプローチ

下記の2点を仮定したアプローチ。

ある文書がある検索質問に対して適合するかどうかが確率的に決定されること
ある文書が検索質問に適合するかどうかは他の文書がその検索質問に適合するかどうかとは独立であること(文書間の独立性)

もし、ある文書がある検索質問に適合する確率を調べたければ、ある検索質問を使ったユーザーのうち、その文書がその検索質問に適合すると判断したかで求められる。ただ、検索質問のバリエーションは無数にあるので、全ての検索質問を数え上げることは現実的ではないため、文書に人手でつけたディスクリプタ(discripter)と呼ばれる一種の索引語に対して推測されるものにのみ絞って確率を推定する。
ディスクリプタが何なのかよく分からなかったので軽く調べたら下記のサイトでそれっぽい定義が見つかった。

ディスクリプタとは、実際の索引に使用される語のことです。ある概念を表す用語が複数存在する場合には、それぞれの用語で表現された情報を一箇所に集めるためにディスクリプタが選定されます。それ以外の同義語(略語や異表記も含む)は、ディスクリプタに関連付けて登録されています。
索引情報（キーワードなど）｜医中誌データベース情報｜医中誌ユーザ向け情報｜医学中央雑誌より参照

また、『図書館情報学用語辞典』(ISBN:4621043625)では下記の通り定義されているらしい。

シソーラスにおいて、ある概念を索引付けする際、一貫して用いると決められた語その他の記号。シソーラスにおける優先語であり、索引の一貫性保持、検索の再現率向上を目的に設定される。
ディスクリプタとは - はてなキーワードより参照

色々と定義を見たところ、文書の内容を表していると考えられる重要語をディスクリプタとして登録しているということだと理解したけど、あってるのだろうか。

そして、MaronとKuhnsは考えたこのアプローチは一貫性を持って推定することは困難であり、実験により有効性が試されることはなかったらしい。
ただ、なぜこのアプローチが一貫性を持って推定することは困難なのか説明がなく分からなかったが、多分ディスクリプタを人手でつけるからだろうなという想像をした。

元の論文はこちらにあるけど、29ページと量が多く諦めた。暇な時に読もうと思った。

On Relevance, ProbabiUstic Indexing and Information Retrieval
http://ctp.di.fct.unl.pt/~jmag/wamse/papers/1960.On%20Relevance,%20Probabilistic%20Indexing%20and%20Information%20Retrieval.pdf

RobertsonとSparck Jonesのアプローチ

下記2つの仮定を置いて、検索質問中の索引語を基礎として確率を計算するアプローチ。

文書が検索質問に適合しようがしまいが、個々の索引語の出現は独立の事象である。
文書が検索質問に適合する確率は全ての索引語の情報を用いて計算されるべきである。

上記の仮定から
$g(d) = log \frac{P(R|d)}{P(\bar{R}|d)}$
が導出できる。これをベイズの公式 $P(Y|X)=\frac{P(Y)P(X|Y)}{P(X)}$ を使うと
$P(R|d) = \frac{P(d)P(d|R)}{P(R)}$ と $P(\bar{R}|d) = \frac{P(d)P(d|\bar{R})}{P(R)}$ より、
これを代入すると
$g(d) = log \frac{P(d)P(d|R)}{P(R)} \cdot \frac{P(\bar{R})}{P(d)P(d|\bar{R})}$
整理して
$g(d) = log \frac{P(d|R)}{P(d|\bar{R})} + log \frac{P(R)}{P(\bar{R})}$
となる

そのあと色々あって、文書 $d$ の適合度は下記が導出される。*6
$g(d) = \sum_{t_i \in T} log \frac{p_i(1-\bar{p_i})}{\bar{p_i}(1-p_i)}$
$t_i$ :索引語
$T$ :検索質問に含まれる索引語集合の部分集合
$p_i$ :検索質問に適合する文書に索引語 $t_i$ が付与されている確率
$\bar{p_i}$ :検索質問に適合しない文書に索引語 $t_i$ が付与されている確率

終わりに

情報検索の基礎的な内容について実践を踏まえて、気の赴くままに書き綴った。
当初の予想通り、ある程度情報検索について知ることができたが、情報を探す能力が強化された気は全くしない。
ただ、情報検索については興味が湧いてきたので、もっと最新の研究を調べたいという気持ちは高まった。
まだあまり調べられていないが、おそらく分散表現が主流になっていそうな気がしている。
『Analysis of the Paragraph Vector Model for Information Retrieval』を読んでみたら割と面白かったので、気が向いて実装できれば記事をまた書きたい。(書くとは言っていない)