情報検索の基礎

6. 情報検索の基礎#

本節では、今日、インターネット等を用いる上で避けて通ることのできない情報検索 (information retrieval)の仕組みについて学ぶ。

情報検索を指す英語にはsearchではなく、「失われたものを取り戻す」というニュアンスのretrieveが用いられるので注意してほしい (元々は古い文書から情報を取り戻す、という意味だったらしい)。

情報検索には、Google等のサーチエンジンのように、特定の単語を含む文章の計算から、とある文書と類似した文書を探す、はたまた、画像検索のように類似したメディアを探す、という処理まで幅広く含まれる。

本項では、特に日本語を対象として、単語ベースの文書検索ならびに類似度に基づく文書検索について紹介する。

6.1. 検索の準備#

以下の資料では、日本語版のWikipediaから収集した国連加盟国193ヶ国 (2024年5月27日現在)の記事情報を用いて演習を実施する。

圧縮したデータを以下のURLに用意してあるので、各自、ダウンロードと展開を済ませておくこと。

ファイルの展開

Windowsを使っている場合には、単にファイルをダブルクリックするだけでは展開されない。ファイルを右クリックして「全て展開」のメニューから内容を展開すること。

6.1.1. 日本語の取り扱い#

本項では、日本語を対象にした情報検索について取り扱う。しかし、日本語(や中国語等のいわゆるCJK言語)は、英語等の単語がスペース等で区切られた言語よりも一般に取り扱いが難しい。

このような言語を対象に、文章を単語に区切るための仕組みを形態素解析と呼ぶ。日本語向けの形態素解析のライブラリで、最も有名なものにMecabがある。

しかし、MecabはPythonで取り扱う際には、インストールに少々手間がかかるので、本項ではもう一つの有名ライブラリであるjanomeを用いる。ただし、janomeはMecabに比べると動作が遅いので、より最適化されたプログラムを作成したい場合には、Mecabの方を使うと良い。

janomeはpip等を用いて簡単にインストールできる。

pip install janome

使い方の詳細については、公式のドキュメントを参照のこと。以下では、単純な単語分割のやり方について紹介する。

6.1.2. janomeによる形態素解析#

まずはcountries/日本.txtを読み込んで、内容を表示してみよう(以下の例では最初の5行だけを表示)。ファイルはUTF-8でエンコードされているので注意すること。

# データのディレクトリは各自で読み替えること
lines = []
with open("data/countries/日本.txt", mode="r", encoding="utf-8") as f:
    lines = f.readlines()

建国諸説あり日本神話による初代神武天皇即位の日辛酉年月日。グレゴリオ暦換算での紀元前年月日紀元節は明治時代に推定された注釈。
日本国にほんこく、にっぽんこく、英、または日本にほん、にっぽんは、東アジアに位置する民主制国家。首都は東京都注釈。
全長キロメートル以上にわたる国土は、主に日本列島注釈および南西諸島伊豆諸島小笠原諸島などの弧状列島により構成される。大部分が温帯に属するが、北部や島嶼部では亜寒帯や熱帯の地域がある。地形は起伏に富み、火山地丘陵を含む山地の面積は国土の約を占め、人口は沿岸の平野部に集中している。国内には行政区分としての都道府県があり、日本人大和民族琉球民族アイヌ民族注釈外国系諸民族と外国人と数百人程度の無国籍者注釈が居住し、日本語を通用する。漢字文化圏に含まれる国のつでもある。
日本国憲法は、天皇を日本国の象徴と規定している。
日本の象徴として国樹は桜、国鳥はキジ、山国の象徴となる山は富士山、その他がある。

言うまでもなく、日本語の文書は単語ごとにスペースなどで区切られておらず、このまま、単語単位の検索をかけようとすると、各文の中に所望の単語が存在するかどうかを逐一チェックしなくてはならない。

このような検索には、一般に文の長さを\(N\)として線形時間、即ち\(O(N)\)の計算時間がかかってしまう。線形時間の計算は特別時間がかかる計算という訳ではないが、全ての文に同様の処理を行なわねばならないことを考えると、決して効率的な処理とは言えない。

形態素解析では、文章を最小の意味単位に区切る。この最小の意味単位のことをトークンと呼ぶ。

janomeを用いた形態素解析にはTokenizerというクラスを用いる。Tokernizerクラスにはtokenizeという関数が用意されており、この関数に日本語の文書をテキストとして渡すことで、形態素解析が実行される。

戻り値はトークン化された結果で、各トークンには、単語そのものの他に、品詞などの情報が付随している。

# janomeのインポート
from janome.tokenizer import Tokenizer

# Tokenizerの初期化
tkz = Tokenizer()

# 文書の内容を結合
body = "".join(lines)

# 形態素解析の実行 (少し時間がかかる)
tokens = list(tkz.tokenize(body))

実際に、単語分割結果を見てみると、元の単語と品詞のほか、読み方などの情報も含まれていることが分かる。

建国	名詞,サ変接続,*,*,*,*,建国,ケンコク,ケンコク
諸説	名詞,一般,*,*,*,*,諸説,ショセツ,ショセツ
あり	動詞,自立,*,*,五段・ラ行,連用形,ある,アリ,アリ
日本	名詞,固有名詞,地域,国,*,*,日本,ニッポン,ニッポン
神話	名詞,一般,*,*,*,*,神話,シンワ,シンワ
による	助詞,格助詞,連語,*,*,*,による,ニヨル,ニヨル
初代	名詞,一般,*,*,*,*,初代,ショダイ,ショダイ
神武	名詞,固有名詞,人名,一般,*,*,神武,ジンム,ジンム
天皇	名詞,一般,*,*,*,*,天皇,テンノウ,テンノー
即位	名詞,サ変接続,*,*,*,*,即位,ソクイ,ソクイ

一見、左列の単語情報だけがあれば十分に見えるが、右列の付属情報は同音異義語などを識別する際に役に立つ。ただし、以下の説明では、特に同音異義語を区別することなく計算を実行することとする。

トークンと単語

トークンは概ね単語と同義と考えて良いが、あえて異なる用語として使っている本などもあるので、その点は注意してほしい。以下では、トークンと単語は同義であるとして説明を続ける。

6.1.3. 分かち書き#

以後の処理を簡単にするために各文書ファイルの分かち書きを行なっておこう。分かち書きとは、日本語のように、本来は単語と単語の境目が明らかでない言語で書かれた文章に対して、単語間にスペースを入れて記したものを指す。

janomeのTokernizerには分かち書きモードが用意されていて、tokernize関数にwakati=Trueというパラメータを渡すと、品詞などの属性情報を含まない単語分割の結果だけを得ることができる。

# 文書の読み込み
doc = "data/countries/日本.txt"
with open(doc, mode="r", encoding="utf-8") as f:
    text = f.read()

# 分かち書きモードでトークン化する
tkz = Tokenizer()
wakati = list(tkz.tokenize(text, wakati=True))

# 必要に応じてファイルを保存
with open("data/countries/日本_wakati.txt", mode="w", encoding="utf-8") as f:
    f.write(" ".join(wakati))

分かち書きを行なった結果は、以下のように単語の間にスペースが入ったものになっていはずなので、各自..._wakati.txtファイルを開いて、このような形式になっているかを確認しておくと良い。

建国 諸説 あり 日本 神話 による 初代 神武 天皇 即位 の 日 辛 酉 年月日 。 グレゴリオ 暦 換算 で の 紀元前 年月日 紀元節 は 明治 時代 に 推定 さ れ た 注釈 。 
 日本 国 に ほん こく 、 にっぽん こく 、 英 、 または 日本 に ほん 、 にっぽん は 、 東アジア に 位置 する 民主 制 国家 。 首都 は 東京 都 注釈 。 
 全長 キロメートル

日本語の取り扱い

  • 情報検索などの自然言語処理で日本語を扱う場合には、あらかじめ形態素解析を行う

  • 形態素解析は日本語の文法を解析して、単語あるいはトークンの列に変換する役割を持つ

  • 日本語の文章の単語と単語の間にスペースを入れたような形式を「分かち書き」と呼ぶ

6.2. 検索クエリによる文書検索#

インターネット上のサーチエンジンを用いる場合、いわゆる検索窓に調べたい語句を入力する。このような検索対象となる語句のことを検索クエリと呼ぶ。

検索クエリは通常、複数の単語から構成されており、その中で全ての単語を含むような文書や、いずれかの単語を含む文書などを検索することができる。

6.2.1. 転置インデックス#

検索クエリによる検索には、転置インデックスと呼ばれるデータ構造を用いることが一般的である。

転置インデックス (inverted index)とは、文書内に現れる単語について、その出現位置をインデックス化したものを指す。まずは、短い文章で、その概念を理解しよう。

一例として、「すもももももももものうち」という文章が与えられたとする。これを形態素解析すると、

すもも、も、もも、も、もも、の、うち

のように分割される。各単語が現れる位置は、

  • すもも: 0

  • も: 3, 6

  • もも: 4, 7

  • の: 9

  • うち: 10

のようになる。このように文書に現れる単語ごとに、出現位置をリスト化したものを転置インデックスと呼ぶ。

転置インデックスを各文書に対して計算するため、文書内に現れる各単語の出現位置を調べる。

先ほど用意しておいた分かち書きのファイルを読み込んで、半角スペースで区切って単語に分割しておく。

# 分かち書きファイルの読み込み
tokens = []
with open("data/countries/日本_wakati.txt", mode="r", encoding="utf-8") as f:
    tokens = f.read().split()

# 各単語の出現位置を調べる
n = 0
indices = []
for tk in tokens:
    indices.append((n, tk))
    n += len(tk)

この時点では、単語は出現順に並んでおり、その単語に出現位置が付与されているだけなので、単語をキーとする辞書を作成し、出現位置を表すインデックスを辞書の値として持たせる。

# 転置インデックスを作成
ii = {s: [] for n, s in indices}
for n, s in indices:
    ii[s].append(n)

作成した辞書を最初の出現位置が早い順にいくつか表示すると、以下のようになる。

単語 出現位置
0 建国 [0, 14406, 14436, 14459, 14650, 14691, 14820, ...
1 諸説 [2, 14084, 75602, 91246]
2 あり [4, 275, 507, 2003, 2912, 3388, 7627, 10627, 1...
3 日本 [6, 62, 83, 139, 361, 375, 421, 427, 435, 449,...
4 神話 [8, 8371, 14630, 14768, 36570]
5 による [10, 1286, 2520, 6265, 9891, 14478, 17141, 177...
6 初代 [13, 11406, 14481, 37229, 55089, 72372, 103990]
7 神武 [15, 11411, 13245, 14483, 14541, 14550, 14555,...
8 天皇 [17, 358, 8198, 9050, 9459, 10593, 10669, 1070...
9 即位 [19, 14487, 14678, 14733, 14917, 14981, 103846...

転置インデックスにおいて、単語の集合のことを特に辞書と呼び、出現位置を表すインデックスのリストのことをポスティング・リストと呼ぶ。

ここまで、「日本」というWikipediaの記事について転置インデックスの計算を行なったが、以下の演習では、データベースにある193ヶ国分の文書について、転置インデックスが計算済みであるとする。

6.2.2. 単語による文書検索#

転置インデックスが取得できたら、とある検索語が文書に存在するかを調べることは非常に容易である。即ち、とある単語をキーとして転置インデックスを評価したときに、出現位置のリストが空でなければ、その文書内に検索語が存在することになる。

query = "東京"

if query in ii:
    print(f'"{query}" is in the document.')
else:
    print(f'"{query}" is NOT in the document.')

"東京" is in the document.

同様にして、複数の単語のいずれかが含まれるか(OR検索)、あるいは複数の単語の全てが含まれるか(AND検索)についても、同様の方法で容易に実装できる。

q1 = "東京"
q2 = "大阪"

# 各クエリが文書内に出現するかを調べる
q1_ok = q1 in ii
q2_ok = q2 in ii

# 以下はAND検索の例
if q1_ok and q2_ok:
    print(f'"{q1}" and "{q2}" are both contained in the document.')
else:
    print(f'"both {q1}" and "{q2}" are not contained in the document.')

"東京" and "大阪" are both contained in the document.

上記の計算では、各単語が文書内に存在するかどうかを、辞書内の検索によって実現している。

「日本」という記事において、辞書の大きさは6915であり、計算機から見ればそれほど大きな数ではないが、上記の計算にかかる計算量には注意を払っておく必要がある。

Pythonの辞書型はハッシュテーブルを使って実装されているので、辞書型のキーに指定した単語が含まれているかどうかは定数時間で計算できる。

以上のことから、文書内の各文について、単語が含まれるかを見ていくのに比べ、転置インデックスを利用する方が圧倒的に効率的な探索が可能であることが分かる。

6.2.3. 連語検索#

では「東京オリンピック」のような連語を検索したい場合にはどうすれば良いだろうか？

「東京オリンピック」という単語は、形態素解析によって「東京」「オリンピック」という2語に分割されるので、転置インデックスの辞書に「東京オリンピック」は存在しない。

query = "東京オリンピック"

if query in ii:
    print(f'"{query}" is in the document.')
else:
    print(f'"{query}" is NOT contained in the document.')

"東京オリンピック" is NOT contained in the document.

そこで、「東京オリンピック」という単語が含まれるための必要条件として、「東京」と「オリンピック」の各語が文書に含まれるかどうかを最初に確認する。

q1 = "東京"
q2 = "オリンピック"

# 各クエリが文書内に出現するかを調べる
q1_ok = q1 in ii
q2_ok = q2 in ii

# 以下はAND検索の例
if q1_ok and q2_ok:
    print(f'"{q1}" and "{q2}" are both contained in the document.')
else:
    print(f'"both {q1}" and "{q2}" are not contained in the document.')

"東京" and "オリンピック" are both contained in the document.

ここまでで、「東京」、「オリンピック」の2語が文書に含まれていることは分かった。しかし、これらの単語が連続しているかどうかはまだ分からない。転置インデックスのポスティングリストに単語の出現位置を記録しておいたことがここで役に立つ。

「東京」という単語は長さが2の単語なので、「東京」が現れる位置から2文字進んだところに「オリンピック」という単語が現れていれば、「東京オリンピック」という連語が文書内に存在しているかが分かる。

list1 = ii[q1]
list2 = ii[q2]

for i in list1:
    if i + len(q1) in list2:
        print(f'"{q1 + q2:s}" appears at position {i:d}.')

"東京オリンピック" appears at position 4454.
"東京オリンピック" appears at position 8072.
"東京オリンピック" appears at position 23152.
"東京オリンピック" appears at position 89928.
"東京オリンピック" appears at position 105036.

このように、同文書内に「東京オリンピック」という連語が5回出現することが確認できた。

この考え方は、より多くの単語が結合された連語に対しても適用できる。例えば「東京株式取引所」という単語が含まれいるかを知りたければ、「東京」という単語の出現位置から2文字進んだ位置に「株式」という単語が出現し、なおかつ、そこからさらに2文字進んだ位置に「取引所」という単語が存在するかを確認すれば良い。

6.2.4. 検索順位の計算#

複数の文書が与えられた時、特定の検索クエリに対応する文書も複数存在するとしよう。この場合、文書の総数が少なければ、それら全てを順不同に表示すれば良いだろう。

しかし、インターネット上にあふれるデータは非常に多く、全文書を順不同で示すことは現実的ではない。そのため、通常の検索エンジンには検索順位を計算する仕組みが用意されているのが一般的である。

以下の例では、辞書型の変数inv_idsに国名をキーとして各文書の転置インデックスが含まれているものとして、検索ランキングの考え方について説明する。

最も単純には、単語の出現回数が多い順にページを表示すれば良いだろう。前述の連語検索の考え方を利用して、「世界遺産」という単語が各文書に何回ずつ出現するかを計算してみる。

q1 = "世界"
q2 = "遺産"

count = {c: 0 for c in countries}
for c in countries:
    if not q1 in inv_ids[c] or not q2 in inv_ids[c]:
        continue

    l1 = inv_ids[c][q1]
    l2 = inv_ids[c][q2]
    for i in l1:
        if i + len(q1) in l2:
            count[c] += 1
国 出現回数
0 スペイン 5
1 ベトナム 5
2 トルコ 4
3 アゼルバイジャン 3
4 イラン 3
5 エストニア 3
6 エチオピア 3
7 オーストラリア 3
8 カーボベルデ 3
9 シエラレオネ 3

この結果を見てみると、一見自然には見えるが、中には直感的に「世界遺産」とは結びつきづらい国名が現れていることも事実である。

出現回数だと、単純に長い文書の順位が高くなりやすいので、その影響があるのかもしれない。出現回数の代わりに出現確率を指標として用いるとどうなるだろうか。

prob = [(c, v / len(inv_ids[c])) for c, v in count]
prob.sort(key=lambda x: x[1], reverse=True)
国 出現確率
0 スリナム 0.003584
1 セントルシア 0.003160
2 ドミニカ国 0.002954
3 バルバドス 0.002688
4 エストニア 0.002660
5 カーボベルデ 0.002443
6 シエラレオネ 0.002360
7 アゼルバイジャン 0.002229
8 レソト 0.002010
9 サンマリノ 0.002006

残念ながら、今度は比較的短い文書に対して有利な結果になってしまい、逆に直感的でない検索ランキングとなってしまった。

6.2.5. TF-IDF#

TF-IDFはterm frequencyとinverse document frequencyを組み合わせた値で、各文書に現れる単語の重要度を表すために用いられる指標の一つである。

TF (term frequency)は、各文書において、単語が現れる頻度を用いた指標で、文書\(d\)に単語\(t\)が現れる頻度を\(f_{t,d}\)としたとき、以下の式が用いられることが多い [6-1]。

\[\begin{split} \mathrm{TF}(t, d) = \begin{cases} \log (f_{t, d}) + 1 & (f_{t,d} > 0) \\ 0 & (\text{Otherwise}) \end{cases} \end{split}\]

一方、IDF (inverse document frequency)は、文書の数\(N\)と、単語\(t\)が現れる文書の数\(0 \leq N_t \leq N\)と用いて以下のように定義される。

\[ \mathrm{IDF}(t) = \log \left( \frac{N}{N_t} \right) \]

TF-IDFはTF値とIDF値の積で計算される。

(6.1)#\[ \mathrm{TF}\text{-}\mathrm{IDF}(t, d) = \mathrm{TF}(t, d) \cdot \mathrm{IDF}(t) \]

TF-IDFを計算するために、まずは全文書に現れる全単語のリスト (コーパスと呼ぶ)を取得しよう。コーパスの取得には、重複をなくしたデータ集合を扱うsetを用いると良い。

# コーパスの取得
corpus = set()
for c, ii in inv_ids.items():
    corpus.update(ii.keys())

corpus = sorted(list(corpus))

コーパスが取得できたら、後の処理のために、記事名(=国名)と単語にインデックスを振っておく。

n_countries = len(countries)
n_words = len(corpus)
i_countries = {c: i for i, c in enumerate(countries)}
i_words = {w: i for i, w in enumerate(corpus)}

このインデックスを元に、各記事における各単語の出現回数をNumPyによる二次元配列のデータとして計算する。

freq = np.zeros((n_countries, n_words), dtype="int32")
for c, ii in inv_ids.items():
    for t in ii.keys():
        i_c = i_countries[c]
        i_w = i_words[t]
        freq[i_c, i_w] = len(ii[t])

各単語の出現回数が得られたら、(6.1)の定義に基づき、TF-IDFを計算する。

N = len(freq)  # 記事の総数
N_t = np.sum(freq != 0, axis=0, keepdims=True)  # 各単語が出現する文書の数

# 以下、定義式に基づきTF-IDFを計算
tf = np.log(1.0 + freq)
idf = np.log(N / N_t)
tfidf = tf * idf

TF-IDFが計算できたら、検索クエリに含まれる単語のTF-IDF値の積を指標として検索ランキングを計算してみよう。

q1 = "世界"
q2 = "遺産"
scores = {c: 0.0 for c in countries}

for c in countries:
    if not q1 in inv_ids[c] or not q2 in inv_ids[c]:
        continue

    l1 = inv_ids[c][q1]
    l2 = inv_ids[c][q2]
    for i in l1:
        if i + len(q1) in l2:
            i_c = i_countries[c]
            i_w1 = i_words[q1]
            i_w2 = i_words[q2]
            scores[c] += tfidf[i_c, i_w1] * tfidf[i_c, i_w2]

ここで計算したscoresに基づく検索ランキングは以下のようになる。

国名 TF-IDF
0 スペイン 0.137280
1 ベトナム 0.132768
2 ロシア連邦 0.093656
3 トルコ 0.092913
4 ドイツ 0.078629
5 オーストラリア 0.067139
6 日本 0.062272
7 イラン 0.060474
8 フィリピン 0.056141
9 ラオス 0.052969

結果を確認してみると、若干ではあるが、世界遺産が多そうな国が上位にならび、やや直感的に近づいた結果となったことが確認できる。

なお、2024年5月27日現在、世界遺産登録数が多い順に国名を列挙すると、

  • イタリア

  • 中華人民共和国

  • ドイツ

  • フランス

  • スペイン

のようなになるので、Wikipediaの記事に単語が現れているかどうかを調べただけでは、そこまで正確な結果が得られているとは言えないかもしれない。

単語を用いた文書検索

  • 複数の単語からなる検索クエリを用いた文書検索には転置インデックスが広く用いられる

  • 転置インデックスは、文書が含む単語のリストである辞書と、各単語の出現位置の集めたポスティング・リストからなる

  • 検索ランキングを与えるには、TF-IDFなどの単語重要度を考慮したスコアが利用される

6.3. 類似文書検索#

6.3.1. 文書間類似度#

文書の類似度を調べる場合にも、上記のTF-IDFの値を用いると良い。この値によって、各文書は全出現単語を次元とするベクトルとして表現される。

ベクトル同士の距離を計算する指標は様々あるが、文書の類似度を比較する場合には、コサイン類似度が比較的よく用いられる。

\[ S_{\mathrm{cosine}}(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x}}{\lVert \mathbf{x} \rVert} \cdot \frac{\mathbf{y}}{\lVert \mathbf{y} \rVert} \]

今、各単語のTF-IDFの値は正であるので、\(\mathbf{x}\)や\(\mathbf{y}\)などのベクトルは必ず第1象限に含まれている。従って、コサイン類似度は0から1の間の値を取り、1に近ければ近いほど、二つの文書\(\mathbf{x}\)と\(\mathbf{y}\)は類似していることを意味する。

距離と類似度

「距離」という言葉と「類似度」という言葉はしばしば混同して用いられるが、一般に、より近いデータであれば高い値を取る指標が類似度であり、より近い値に対して0に近い非負の値を取る指標を距離と呼ぶ。

この意味で、実際、前述のコサイン類似度を「コサイン距離」と呼ぶのは誤りであるので注意してほしい。

ここで、コサイン類似度を用いて「日本」により近い内容を持つ文書を探してみよう。

v_japan = tfidf[i_countries["日本"], :]

dists = []
for c in countries:
    v = tfidf[i_countries[c], :]
    d = np.dot(v_japan, v) / (np.linalg.norm(v_japan) * np.linalg.norm(v))
    dists.append((c, d))

このようにして計算されたコサイン類似度が高い順に国名を列挙すると以下のようになる。

国名 コサイン類似度
0 日本 1.000000
1 韓国 0.260421
2 北朝鮮 0.215774
3 アメリカ合衆国 0.198374
4 ロシア連邦 0.190575
5 中華人民共和国 0.185069
6 ドイツ 0.167426
7 ベトナム 0.159030
8 インド 0.155713
9 シンガポール 0.154870

結果を見てみると、直感的には日本と関係が深そうな各国や北朝鮮が上位に来ており、類似度評価はかなり上手くいっているように見える。

一方、コサイン類似度を用いた文書の類似度は、古くは比較する文書の長さがおよそ同等であった時代に考案されたもの[6-1]であり、コサイン類似度を求める際に、各文書を表すベクトルを正規化してしまうと、文書の長さの影響を上手く捉えることができないことがある。

そこで、ベクトルを正規化しない類似度の計算法として、コサイン類似度と似た指標がいくつも提案されている。以下では、一例としてOkapi BM25という指標について紹介する。

Okapi BM25 (以下では単にBM25とする)は、ロンドン大学シティ校のRobertsonらが開発した検索システムであるOkapiに用いられていた類似度指標である。なお、BMはBest Matchingの略であり、25は同指標が実装されたOkapiのバージョン番号である [6-1]。

BM25は、TF-IDFのTFの計算方法を改良しており、以下の式を用いる。

\[ \mathrm{TF}_{\mathrm{BM25}}(t, d) = \frac{f_{t,d} (k_1 + 1)}{k_1 ((1 - b) + b (l_d / l_{\mathrm{avg}})) + f_{t,d}} \]

この式において、\(l_d\)は文書\(d\)に現れる単語数であり、\(l_{\mathrm{avg}}\)は各文書に現れる単語数の平均値である。なお、\(k_1\)と\(b\)はパラメータであり、\(k_1 = 1.2\)、\(b = 0.75\)を規定値として用いる。

この式に基づき、BM25では、以下のようにして、クエリ文書\(q\)に単語\(t\)が現れる回数を\(q_t\)でTF-IDF値を重み付けて、以下のように類似度スコアを計算する。

(6.2)#\[ S_{\mathrm{BM25}} = \sum_{t \in q} q_t \cdot \mathrm{TF}\text{-}\mathrm{IDF}_{\mathrm{BM25}}(t, d) \]

では、(6.2)に基づき、「日本」の記事と各文書の類似度を計算してみよう。

# 文書長に関する変数
l_d = np.sum(freq, axis=1, keepdims=True)
l_avg = np.mean(l_d)

# BM25版TF-IDFの計算
k1 = 1.2
b = 0.75
tf_bm25 = (freq * (k1 + 1.0)) / (k1 * ((1.0 - b) + b * (l_d / l_avg)) + freq)
tfidf_bm25 = tf_bm25 * idf

# BM25に基づく文書間類似度の計算
dists = []
q_t = freq[i_countries["日本"], :]
for c in countries:
    v = tfidf_bm25[i_countries[c], :]
    d = np.dot(q_t, v)
    dists.append((c, d))
国名 Okapi BM25
0 日本 39460.698893
1 韓国 18590.990600
2 北朝鮮 16353.442688
3 アメリカ合衆国 15821.683293
4 ロシア連邦 15610.194962
5 中華人民共和国 14811.119422
6 ベトナム 14670.974348
7 ドイツ 14342.732113
8 インド 14065.494369
9 フランス 13639.038075

今回の例では、BM25を用いたことで、それほど大きな変化は得られなかったが、これは日本の記事と、日本に関連が深い国の記事が、それ相応の長さを持っていることに起因する可能性がある。

他の国に関する文書との類似度を用いた場合に、コサイン類似度とBM25を用いる場合とでどのような変化が生じるかは、練習問題を通じて確認してみてほしい。

6.3.2. Word2Vec#

word2vecは2013年にGoogleの研究者であったMikolov氏らが提案した手法[6-2]で、与えられた文書集合に含まれる各単語を特徴ベクトル化する技術の一種である。

word2vecは、各単語をベクトル化するために、CBoW (continuous bag of words)とskip-gramと呼ばれる2つの異なる教師付き学習の枠組みを用いる。

CBoWは、ある単語\(a_i\)の周りに存在する単語\(\ldots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \ldots\)から、\(a_i\)を予想する、という問題を機械学習で解く。反対にskip-gramでは、単語\(a_i\)から、周囲に存在する単語のいずれかを予想するという問題を解く。

以下では、機械学習ライブラリのgensimを用いてword2vecによる単語のベクトル表現を利用してみよう。

gensimはpipを用いて簡単にインストールができる。この際、gensimの内部でSciPyが使われており、そのバージョンによってエラーが生じる可能性があるので、SciPyのバージョンを指定して一緒にインストールすると良い。

pip install gensim scipy==1.12

学習データの用意#

word2vecで用いられるCBoWとskip-gramはいずれも教師付き学習に基づくアプローチなので、これらを利用するには訓練データを用意する必要がある。

gensimで用いる訓練データは文書の全文を1つの要素とする文字列型の配列である。今回は、各国の文書を要素として持つ長さ193の配列を訓練データとして用いる。

日本語を扱う場合、各文書は分かち書きされている必要があるので、本項の始めに用意しておいた分かち書き処理済みのファイルを読み込んで、各文書に含まれる単語のリスト (出現順)を訓練データとして用いる。

# 国名リストの読み込み
countries = []
with open("data/countries/list.txt", mode="r", encoding="utf-8") as f:
    countries = f.readlines()

countries = [c.strip() for c in countries]

# 分かち書き済みの文書の読み込み
sentences = []
for c in countries:
    doc = f"data/countries/{c:s}_wakati.txt"
    with open(doc, mode="r", encoding="utf-8") as f:
        sentences.append(f.read().split())

モデルの訓練#

訓練データ (sentences)が用意できたら、gensimのWord2Vecクラスのコンストラクタに与えて、モデルの訓練を実行する。Word2Vecにはいくつかのパラメータが必要であり、各単語を表すベクトルの次元数を表すvector_sizeや、各単語の周囲何単語を訓練データに含めるかを決めるwindow、CBoWかskip-gramのどちらを使うかを表すsg (sg=1のときはskip-gram, そうでないときはCBoW)、最低何回出現する単語を学習に含めるかを決めるmin_countなどを指定する。

from gensim.models import Word2Vec

model = Word2Vec(
    sentences=sentences,
    vector_size=128,
    window=11,
    sg=1,
    min_count=1,
)

文書のベクトル化#

Word2Vecはインスタンス化とともにモデルの訓練が実行され、model.wvが単語をキーとし、ベクトル表現を値とする辞書型として与えられる。

各文書をベクトル化する方法にはいくつかあるが、以下では、単純に文書に現れる単語のベクトル表現の和を取る。

vectors = {c: np.zeros(128) for c in countries}
for i, c in enumerate(countries):
    words = sentences[i]
    vectors[c] = sum([model.wv[w] for w in words])

このようにして得られた各文書のベクトル表現のユークリッド距離に基づき、文書間の類似度を決める。今回はユークリッド距離が小さい方が、より類似した文書となるので注意すること。

v_jp = vectors["日本"]
dists = {c: 0.0 for c in countries}
for c in countries:
    v = vectors[c]
    d = np.linalg.norm(v_jp - v)
    dists[c] = d

dists = [(c, d) for c, d in dists.items()]

計算された距離に基づいて国名を昇順で並べ替えると以下のようになる。

国名 w2vによる類似度
0 日本 0.000000
1 韓国 49601.210938
2 北朝鮮 54023.609375
3 アメリカ合衆国 68701.414062
4 ロシア連邦 74003.460938
5 ポーランド 74063.250000
6 インド 75751.828125
7 ブラジル 79953.578125
8 アルゼンチン 80023.554688
9 フランス 80235.757812

いかがだろうか。word2vecを用いた場合も、かなり直感に近い類似度を得ることができた。ただ、今回の単語ベクトルの「和」と、ユークリッド距離を用いたアプローチは文書の長さによる影響を受ける可能性がある。

前述の通り、日本語のWikipediaの記事は日本と関連の深い国の文書が長い可能性があることには注意が必要である。

類似文書の検索

  • 文書の類似度計算にも、単語を検索クエリに用いる場合と同様、TF-IDFを基本とした指標が用いられる

  • 類似度指標の計算方法は多数あり、コサイン類似度の他、Okapi BM25などの指標がある

  • word2vecを用いると単語のベクトル表現が得られるので、それを用いて文書をベクトル化する方法もある

6.4. 練習問題#

問1

演習用データを用いて各国の記事に対する転置インデックスとTF-IDF値を計算せよ。また、それらを用いて、いくつかの連語に対する検索ランキングを計算し、出現頻度、出現確率、TF-IDFの各指標がランキングに与える影響について論ぜよ。

問2

本文の指示に従い、コサイン類似度やOkapi BM25、word2vecを利用して、「日本」以外の記事についても文書間の類似度を調べ、各国の記事の関係や類似度指標の違いについて論ぜよ。

問3

word2vecを用いて、検索クエリに現れる単語のベクトル表現の和を取って得られる合計ベクトルを用いて、各文書と検索クエリの類似度を調べることができる。いくつかの検索クエリに対して、word2vecを用いた検索ランキングを試し、その結果について考察せよ。

6.5. 参考文献#

6-1(1,2,3)

Steven Buttcher, Charles L. A. Clarke, Gordon V. Cormack, and Bob Kummerfeld. 情報検索 検索エンジンの実装と評価. 森北出版, 2020. ISBN 978-4-627-81761-6.

6-2

Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint:1301.3781, 2013.

目次