概要

TFIDFに基づく検索において、検索対象とは異なるコーパスからIDFを計算した場合の、検索精度への影響について調査しました。
今回は、正例を含む検索対象コーパスから計算したIDFと正例を含まない非検索対象コーパスから計算したIDFを用いる場合の、どちらが検索精度が高いかを検証しました。結果として、非検索対象コーパスを用いたほうが精度が高いという仮説（直感）とは逆の結果が得られました。ただしこれは、実験設定が悪かった可能性も高いです。

背景

TFIDFはキーワード検索の指標としてよく使われます。計算方法はTF（term frequency）とIDF（inversed document frequency）の積です。IDFは、検索対象の文書集合に基づき、事前計算されることが多いですが、ときどき、検索対象とは別の文章でIDFを計算しておきたくなることがあります。例えば以下のような理由です。

検索対象が頻繁に更新され、その度にIDF辞書を更新するのが面倒
検索対象文書が少なく、IDFの妥当性に不安がある
- 例えば以下の記事では、コミック作品の説明文から求めたBM25の値を青空文庫より求めたIDF値で補正しています。
  pixivコミック作品のタグが自動生成されるまでの軌跡

そこで、検索対象とは異なるコーパスから算出されたIDF値を用いることが、検索精度にどう影響するのかに興味を持ちました。

今回は検証の第一歩として、検索対象外のコーパスから算出されたIDFを用いると検索対象のコーパスから算出されたIDFを用いる場合よりも検索精度が下がるのか、また、検索対象外のコーパスから算出されたIDFを用いる場合、検索対象外のコーパスサイズは検索精度にどう影響するのか、を中心に調べました。

仮説

前提として、検索対象コーパスと非検索対象コーパスの2種類があるとします。前者はクエリに対する正例を含むコーパス、後者は含まないコーパスです。このとき以下の仮説を検証します。

コーパスサイズが同程度の場合、検索対象コーパスから算出したIDFを用いた検索のほうが、非検索対象コーパスから算出したIDFを用いた検索よりも、精度が高い
非検索対象コーパスから算出したIDFを用いて検索する場合、非検索対象コーパスのサイズが大きいほど、精度が高い
サイズの小さい検索対象コーパスから算出されたIDFを用いるより、サイズの大きい非検索対象コーパスから算出されたIDFを用いるほうが、検索精度が高い場合がある。

本記事では、1つめの仮説の検証を行います。

方法

データセット

検索評価のデータセットとしてMIRACLを使います。

HuggingFace: https://huggingface.co/datasets/miracl/miracl
論文: https://arxiv.org/pdf/2210.09984.pdf

MIRACLはクエリと対応するWikipdeiaの記事で構成される多言語の検索評価用データセットです。日本語は860個のクエリとクエリに対する正例2000件ほどを含む約695万件の検索対象文書が用意されています。

評価指標

クエリは860件に対するrecall@nで評価します。nは適当に1,3,5,10,30,100で計算します。

実験1

仮説「コーパスサイズが同程度の場合、検索対象コーパスから算出したIDFを用いた検索のほうが、非検索対象コーパスから算出したIDFを用いた検索よりも、精度が高い」を検証します。

コーパスサイズを3000, 10000, 100000として検索対象コーパスと非検索対象コーパスを用いた場合で比較します。最小が3000なのは、クエリに対する正解例が合計2000くらいあり、それより多い数にしたかったためです。

実装

MIRACLデータセットの使い方は以下を参考にしました。
https://github.com/oshizo/JapaneseEmbeddingEval

まずライブラリをimportします。また、比較するコーパスサイズのリストを作ります。

import json
import os
import datasets
import tqdm
import MeCab
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import CountVectorizer
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity
import pandas as pd

TRAIN_CONDITIONS = [100000, 10000, 3000]

HuggingFaceからmiraclのデータセットをダウンロードします。
環境変数にHuggingFaceのアクセストークンをセットする必要があります。

# query and positives
full_ds = datasets.load_dataset(
    "miracl/miracl", "ja", use_auth_token=os.environ["HF_ACCESS_TOKEN"], split="dev"
)

# all corpus texts
full_corpus = datasets.load_dataset("miracl/miracl-corpus", "ja")

実験に使う正例が含まれないことが保証された文書を必要件数+α取得しておきます。

ds = full_ds

# make subset of corpus to reduce filtering time
positive_docids = set()
for item in ds:
    for pp in item["positive_passages"]:
        positive_docids.add(pp["docid"])

max_corpus_size = max(TRAIN_CONDITIONS)*2 + len(positive_docids)
corpus_without_positive = full_corpus["train"].select(range(max_corpus_size)).filter(lambda x: x["docid"] not in positive_docids)

分かち書き用の関数を定義します。

mecab = MeCab.Tagger("-Owakati")

def tokenize_jp(text: str) -> str:
    tokens = mecab.parse(text).split()
    return tokens

正例なしの文書を分かち書きしておきます。必須ではありませんが、実験で一番時間がかかる前処理のため、再利用できるように結果を保存しておきます。

# corpusというディレクトリを作る
OUTPUT_DIR = "output/experiment1"
os.makedirs(OUTPUT_DIR, exist_ok=True)
# train_corpusのtextをtokenizeしてdocidとともにjsonlで保存
corpus_without_positive_json = []
corpus_without_positive_path = f"{OUTPUT_DIR}/corpus_without_positive.json"

if os.path.exists(corpus_without_positive_path):
    with open(corpus_without_positive_path) as f:
        corpus_without_positive_json = json.load(f)
else:
    for doc in tqdm.tqdm(corpus_without_positive):
        corpus_without_positive_json.append({"docid": doc["docid"], "text": tokenize_jp(doc["text"])})
    with open(corpus_without_positive_path, "w") as f:
        json.dump(corpus_without_positive_json, f, ensure_ascii=False)

全部の語彙を取得します。この値をTfidfVectorizerの初期化時に毎回渡すようにすることで、未知語が無視されることで結果が変わる可能性をなくします。

full_vocabulary = set()

for doc in tqdm.tqdm(corpus_without_positive_json):
    full_vocabulary.update(doc["text"])
for item in tqdm.tqdm(ds):
    query_text = item["query"]
    query_text = tokenize_jp(query_text)
    full_vocabulary.update(query_text)
    for pp in item["positive_passages"]:
        pp_text = pp["text"]
        pp_text = tokenize_jp(pp_text)
        full_vocabulary.update(pp_text)

TfidfVectorizerのインスタンスを作ります。まずは、非検索対象コーパスによるIDFを計算します。比較用に、IDFを使わない場合に相当するCountVectorizerも生成しておきます。

vectorizer_dict = {}
train_corpus = corpus_without_positive_json[:max(TRAIN_CONDITIONS)]

for train_condition in tqdm.tqdm(TRAIN_CONDITIONS):
    vectorizer = TfidfVectorizer(
        vocabulary=full_vocabulary
        , analyzer = lambda x: x
    )
    vectorizer.fit([doc["text"] for doc in train_corpus[:train_condition]])
    vectorizer_dict[f"train_{train_condition}"] = vectorizer

# TRAIN_CONDITION = 0のケース
vectorizer_dict[f"train_0"] = CountVectorizer(vocabulary=full_vocabulary, analyzer = lambda x: x)

同様に検索対象コーパスに基づくIDFも計算しておきます。
検索対象コーパスには正例が含まれる必要があるため、リストの先頭に含めておきます。

positive_corpus_json = []
done_docids = set()
for item in tqdm.tqdm(ds):
    for pp in item["positive_passages"]:
        if pp["docid"] in done_docids:
            continue
        positive_corpus_json.append({
            "text": tokenize_jp(pp["text"]),
            "docid": pp["docid"]
        })

test_corpus = positive_corpus_json + corpus_without_positive_json[max(TRAIN_CONDITIONS):max(TRAIN_CONDITIONS)*2]

for test_condition in tqdm.tqdm(TRAIN_CONDITIONS):
    vectorizer = TfidfVectorizer(vocabulary=full_vocabulary, analyzer=lambda x: x)
    vectorizer.fit([doc["text"] for doc in test_corpus[:test_condition]])
    vectorizer_dict[f"test_{test_condition}"] = vectorizer

recallの計算に使うため、各vectorizerにおいて、各クエリに対する正例文書の順位を取得し、結果を保存します。

if os.path.exists(f"{OUTPUT_DIR}/rank_dict.json"):
    with open(f"{OUTPUT_DIR}/rank_dict.json") as f:
        rank_dict = json.load(f)
else:
    rank_dict = {}
    query_texts = [tokenize_jp(query["query"]) for query in ds]

    def calc_result(test_corpus, vectorizer):
        global query_texts, ds
        
        test_matrix = vectorizer.transform([doc["text"] for doc in test_corpus[:test_condition]])
        query_matrix = vectorizer.transform(query_texts)

        # 類似度行列を計算し、queryのdocidのランクを取得
        similarity_matrix = cosine_similarity(query_matrix, test_matrix)
        ranking_matrix = np.argsort(similarity_matrix, axis=1)[:, ::-1]

        test_docid2indice = {item["docid"]: i for i, item in enumerate(test_corpus)}    

        query_result = []
        for item, ranking in zip(ds, ranking_matrix):
            # rankingの何番目にdocidがあるかを取得
            docids = [pp["docid"] for pp in item["positive_passages"]]
            docid_indices = [test_docid2indice[docid] for docid in docids if docid in test_docid2indice]
            ranks = [list(ranking).index(docid_index) for docid_index in docid_indices]
            query_result.append({
                "query_id": item["query_id"],
                "ranks": ranks
            })
        return query_result

    #for test_condition in tqdm.tqdm(TEST_CONDITIONS):
    for test_condition in tqdm.tqdm(TRAIN_CONDITIONS):

        # train_vectorizer
        keyname = f"train_{test_condition}"
        vectorizer = vectorizer_dict[keyname]
        result = calc_result(test_corpus[:test_condition], vectorizer)
        rank_dict[f"{keyname}_test_{test_condition}"] = result

        # test_vectorizer
        keyname = f"test_{test_condition}"
        vectorizer = vectorizer_dict[keyname]
        result = calc_result(test_corpus[:test_condition], vectorizer)
        rank_dict[f"{keyname}_test_{test_condition}"] = result

        # count_vectorizer
        keyname = f"train_0"
        vectorizer = vectorizer_dict[keyname]
        result = calc_result(test_corpus[:test_condition], vectorizer)
        rank_dict[f"{keyname}_test_{test_condition}"] = result

    with open(f"{OUTPUT_DIR}/rank_dict.json", "w") as f:
        json.dump(rank_dict, f, ensure_ascii=False)

recallを計算し表示します。

ns = [1, 3, 5, 10, 30, 100]
rows = []    
for keyname, ranks in rank_dict.items():
    row = {"keyname": keyname}
    for n in ns:
        recall = 0
        for rank in ranks:
            recall += sum([1 if r < n else 0 for r in rank["ranks"]]) / len(rank)
        recall /= len(ranks)
        #print(keyname, n, recall)
        row[f"recall@{n}"] = recall
    rows.append(row)
df = pd.DataFrame(rows)
df.to_csv(f"{OUTPUT_DIR}/result.csv", index=False)
print(df)

keyname  recall@1  recall@3  recall@5  recall@10  \
0  train_100000_test_100000  0.278682  0.473031  0.552143   0.642019   
1   test_100000_test_100000  0.276463  0.463881  0.543175   0.636757   
2       train_0_test_100000  0.050403  0.088943  0.112385   0.136940   
3    train_10000_test_10000  0.421941  0.648099  0.736269   0.813614   
4     test_10000_test_10000  0.417066  0.641006  0.729451   0.808226   
5        train_0_test_10000  0.102448  0.180953  0.208894   0.256381   
6      train_3000_test_3000  0.445265  0.698564  0.787850   0.857891   
7       test_3000_test_3000  0.451961  0.702595  0.784082   0.857100   
8         train_0_test_3000  0.129065  0.216113  0.255414   0.312784   

   recall@30  recall@100  
0   0.759830    0.837303  
1   0.755813    0.836410  
2   0.182717    0.257245  
3   0.883225    0.920221  
4   0.881255    0.921481  
5   0.343419    0.475493  
6   0.910396    0.944419  
7   0.909718    0.945775  
8   0.437882    0.585221

グラフでも結果を確認してみます。

# rank_dictを折れ線グラフにする。縦軸がrecall、横軸がrecall_at、線がkeyname
import matplotlib.pyplot as plt
# 画像のサイズを指定
plt.figure(figsize=(5, 5))
# 縦軸の範囲を指定
plt.ylim(0, 1)
# 横軸の範囲を指定
plt.xlim(0, 100)
# 横軸の目盛りを指定
plt.xticks([1, 3, 5, 10, 20, 30, 50, 100])
# 縦軸の目盛りを指定
plt.yticks([0, 0.2, 0.4, 0.6, 0.8, 1.0])
# グラフの描画。
for keyname, ranks in rank_dict.items():
    recall_list = []
    for n in ns:
        recall = 0
        for rank in ranks:
            recall += sum([1 if r < n else 0 for r in rank["ranks"]]) / len(rank)
        recall /= len(ranks)
        recall_list.append(recall)
    plt.plot(ns, recall_list, label=keyname, marker="o")
# 凡例の表示
plt.legend()
# グラフの表示
plt.show()

結果

結果を整理したものが以下です。

サイズ	コーパス	r@1	r@3	r@5	r@10	r@30	r@100
100000	非検索	0.279	0.473	0.552	0.642	0.760	0.837
100000	検索	0.276	0.464	0.543	0.637	0.756	0.836
100000	なし	0.050	0.089	0.112	0.137	0.183	0.257
10000	非検索	0.422	0.648	0.736	0.814	0.883	0.920
10000	検索	0.417	0.641	0.729	0.808	0.881	0.921
10000	なし	0.102	0.181	0.209	0.256	0.343	0.475
3000	非検索	0.445	0.699	0.788	0.858	0.910	0.944
3000	検索	0.452	0.703	0.784	0.857	0.910	0.946
3000	なし	0.129	0.216	0.255	0.313	0.438	0.585

考察

「検索」と「非検索」を比較すると特に検索」のほうが精度が明確に高いということはなさそうです。よって仮説は支持されませんでした。
一方で「なし」の条件では明確に精度が下がっていることから、IDFによる重み付けをすること自体は意味がありそうです。

一つ懸念として、文書数が3000の時点で十分に多いため、非検索と検索の差が見えにくかったのではないかという点があります。
この懸念を払拭するために、クエリ数を少なくした上で、より小さな文書でも実験してみます。

実験2

文書数3000がコーパスによる検索精度の差をみるには大きすぎた可能性を払拭するためにより小さなコーパスで検証してみます。

実装

ほぼ実験1と同様のため、差異だけ示します。

TRAIN_CONDITIONを実験条件に合わせます。

TRAIN_CONDITIONS = [3000, 1000, 500, 100]

クエリ（ds）を実験1ではfull_ds全部を使っていましたが、今回は30件だけを使います。

ds = full_ds.select(range(30))

# make subset of corpus to reduce filtering time
positive_docids = set()
for item in ds:
    for pp in item["positive_passages"]:
        positive_docids.add(pp["docid"])

max_corpus_size = max(TRAIN_CONDITIONS)*2 + len(positive_docids)
corpus_without_positive = full_corpus["train"].select(range(max_corpus_size)).filter(lambda x: x["docid"] not in positive_docids)

あとは同じです。

結果

整理したものだけ示します。

サイズ	コーパス	r@1	r@3	r@5	r@10	r@30	r@100
3000	非検索	0.475	0.719	0.811	0.844	0.900	0.944
3000	検索	0.525	0.708	0.811	0.844	0.889	0.944
3000	なし	0.061	0.131	0.161	0.261	0.372	0.497
1000	非検索	0.619	0.797	0.844	0.900	0.944	0.978
1000	検索	0.669	0.808	0.844	0.867	0.944	0.978
1000	なし	0.092	0.250	0.328	0.394	0.497	0.681
500	非検索	0.664	0.836	0.933	0.944	0.978	0.989
500	検索	0.597	0.814	0.933	0.944	0.978	0.989
500	なし	0.136	0.361	0.439	0.481	0.586	0.844
100	非検索	0.708	0.925	0.978	0.978	0.989	1.000
100	検索	0.731	0.925	0.978	0.978	0.989	1.000
100	なし	0.214	0.428	0.492	0.553	0.878	1.000

考察

今度は、コーパスサイズが500の場合を除き、検索対象コーパスのほうが精度が高い結果となりました。
しかし、実験１の場合も含めて、検索と非検索の差異に一貫性がないことを踏まえると、抽出するコーパスの文書による差異が大きく、そもそも効果が見えにくくなっているのかもしれません。

そこで最後に、コーパスサイズを固定して、何度もコーパスのサンプリングを行い、統計的な差異を評価します。

実験3

クエリ数30、コーパスサイズ500に固定して、recall@5を100回ずつ計算し、平均値を比較します。

実装

コーパスのダウンロードまでは実験1,2と一緒です。
その後、クエリとコーパスをランダムに取得する関数を作ります。

def get_corpus(query_size, corpus_size):
    # ランダムにクエリを選択
    ds = full_ds.select(random.sample(range(len(full_ds)), query_size))

    positive_corpus_json = []
    query_texts = []
    done_docids = set()
    for item in ds:
        query_texts.append(tokenize_jp(item["query"]))
        for pp in item["positive_passages"]:
            if pp["docid"] in done_docids:
                continue
            positive_corpus_json.append({
                "text": tokenize_jp(pp["text"]),
                "docid": pp["docid"]
            })
    positive_docids = set([x["docid"] for x in positive_corpus_json])

    # ランダムにコーパスを選択
    max_corpus_size = corpus_size*2 + len(positive_docids)
    corpus_without_positive = full_corpus["train"].select(random.sample(range(len(full_corpus["train"])), max_corpus_size)).filter(lambda x: x["docid"] not in positive_docids)
    corpus_without_positive_json = [{"docid": doc["docid"], "text": tokenize_jp(doc["text"])} for doc in corpus_without_positive]

    train_corpus = corpus_without_positive_json[:corpus_size]
    test_corpus = positive_corpus_json + corpus_without_positive_json[corpus_size:corpus_size*2-len(positive_corpus_json)]
    assert len(test_corpus) == corpus_size
    assert len(train_corpus) == corpus_size
    return ds, query_texts, train_corpus, test_corpus

recallの計算を100回実施します。

CORPUS_SIZE = 500
QUERY_SIZE = 30
train_recalls = []
test_recalls = []
for _ in tqdm.tqdm(range(100)):
    ds, query_texts, train_corpus, test_corpus = get_corpus(QUERY_SIZE, CORPUS_SIZE)
    
    def calc_result(test_corpus, vectorizer, n = 5):
        global query_texts, ds
        
        test_matrix = vectorizer.transform([doc["text"] for doc in test_corpus])
        query_matrix = vectorizer.transform(query_texts)

        # 類似度行列を計算し、queryのdocidのランクを取得
        similarity_matrix = cosine_similarity(query_matrix, test_matrix)
        ranking_matrix = np.argsort(similarity_matrix, axis=1)[:, ::-1]

        test_docid2indice = {item["docid"]: i for i, item in enumerate(test_corpus)}    

        query_result = []
        for item, ranking in zip(ds, ranking_matrix):
            # rankingの何番目にdocidがあるかを取得
            docids = [pp["docid"] for pp in item["positive_passages"]]
            docid_indices = [test_docid2indice[docid] for docid in docids if docid in test_docid2indice]
            ranks = [list(ranking).index(docid_index) for docid_index in docid_indices]
            query_result.append({
                "query_id": item["query_id"],
                "ranks": ranks
            })
        
        # recall@nを計算
        recall_at_n = np.mean([np.mean([1 if rank < n else 0 for rank in item["ranks"]]) for item in query_result])
        return recall_at_n
    full_vocabulary = set()

    for query_text in query_texts:
        full_vocabulary.update(query_text)
    for doc in train_corpus + test_corpus:
        full_vocabulary.update(doc["text"])

    train_vectorizer = TfidfVectorizer(analyzer=lambda x: x, vocabulary=full_vocabulary)
    train_vectorizer.fit([x["text"] for x in train_corpus])

    test_vectorizer = TfidfVectorizer(analyzer=lambda x: x, vocabulary=full_vocabulary)
    test_vectorizer.fit([x["text"] for x in test_corpus])
    
    train_recall = calc_result(test_corpus, train_vectorizer, 5)
    test_recall = calc_result(test_corpus, test_vectorizer, 5)

    train_recalls.append(train_recall)
    test_recalls.append(test_recall)

# 平均と標準偏差を計算
train_recall_mean = np.mean(train_recalls)
train_recall_std = np.std(train_recalls)
test_recall_mean = np.mean(test_recalls)
test_recall_std = np.std(test_recalls)
# 表示
print(f"train recall@5: {train_recall_mean} ± {train_recall_std}")  
print(f"test recall@5: {test_recall_mean} ± {test_recall_std}")

対応ありのt検定で結果を比較します。

# recallsを対応ありのt検定で比較
from scipy import stats
t, p = stats.ttest_rel(train_recalls, test_recalls)
print(f"t検定: t={t}, p={p}")

結果

各条件におけるrecallの平均値と標準偏差は以下の通りです。trainが非検索対象コーパス、testが検索対象コーパスです。

train recall@5: 0.8964511664261664 ± 0.04661392374955171
test recall@5: 0.8862122775372776 ± 0.04984320112025396

対応ありt検定の結果は以下です。

t検定: t=5.004463367082107, p=2.435972729064351e-06

有意に非検索対象コーパスのほうが検索精度が高いという結果になりました。

考察

有意に非検索対象コーパスのほうが検索精度が高く、仮説とは逆の結果となりました。コーパスサイズ等を変えての検証はしていませんが、おそらく結果は同様と思われます。

全体考察

実験1,2,3を通して、仮説とは逆の結果が得られました。つまり、検索対象コーパスにもとづくIDFを用いると、非検索対象コーパスを用いる場合よりも検索精度が下がってしまうことが示唆されました。

理由として考えられるのは、検索対象コーパスには正例が含まれるため、正例に含まれる語彙の希少性が薄れ、IDFが小さくなってしまうことです。

例えば、ループの途中の状態を取得して、とあるクエリに含まれる語彙のIDFをtrain_vectorizerとtest_vectorizerで比較してみます。

print(query_texts[0])
id = train_vectorizer.vocabulary_["サッカー"]
print("サッカー")
print(train_vectorizer.idf_[id])
print(test_vectorizer.idf_[id])
id = train_vectorizer.vocabulary_["発祥"]
print("発祥")
print(train_vectorizer.idf_[id])
print(test_vectorizer.idf_[id])```

['サッカー', 'の', '発祥', '地', 'は', 'どこ']
サッカー
5.830311739964975
5.270695952029551
発祥
7.2166061010848646
5.607168188650765

「サッカー」も「発祥」も検索対象コーパスから計算されたIDFが小さくなっています。したがって、これらの語彙が検索順位に与える影響は相対的に弱まってしまい、正例が上位になりにくくなることが考えられます。

このような効果は一般的に見られるものかというと、そうではないと思われます。今回はmiraclという１つのデータセットから検索対象コーパスと非検索対象コーパスを取り出しています。つまり、両者の性質は似通っており、違いは正例の有無のみという状況です。このような場合では正しい例を含むことが検索精度にネガティブな影響をもたらすのかもしれません。一方で、このような状況は現実ではあまり起こらないとも思われます。

つまり、今回の実験の前提がそもそも悪かった可能性があります。検索対象コーパスと非検索対象コーパスは全く別ドメインの文章から取ってきたほうが、検証したいことの意図に近くなる気がします。

おわりに

ここまでやってみて、結局、実験のやり方に問題があったのではないかという気がしています。
ただやってみないと気づけなかったのでやってみてよかったです。