rank_bm25のインスタンスをオーバーライドなしで高速にマージする方法の速度・精度比較

# 概要
rank_bm25のインスタンスをオーバーライド無しで高速にマージする方法を検討しました。

結論としては、オーバーライドなしだと、速度と精度を文句なしに両立できる方法はありませんでした。
オーバーライド含む実装の手間と速度や精度のトレードオフでちょうどよいところを用途ごとに選ぶのが良いと思います。

# 背景
以前、[関数をオーバーライドすることでrank_bm25のインスタンスを高速にマージすることができた](https://qiita.com/shimajiroxyz/items/01b6b02e18fb19de1113)のですが、オーバーライドはライブラリ全体への影響が未知数で怖いのでできたら避けたいです。

そこで、プラパティとしてもともと保持されているidf辞書や文書レベルでの文書頻度を活用することで、オーバーライドなしで、全コーパスから計算するよりは高速なマージ方法の実現を目指しました。

# 実装
コーパス全体の文書頻度を求めることができれば、idfも計算できます。
コーパス全体の文書頻度を求める方法として、大きく、BM25Okapiのプラパティであるidfとdoc_freqsを用いる方法が思いつきます。
以下、コーパス全体の文書頻度を求める部分に絞って実装を検討していきます。

## idf
BM25Okapi.idfから文書頻度を計算します。
BM25Okapiの_calc_idf関数では文書頻度（nd）をidfに変換するために以下の式が使われています。


```math
\text{idf} = \log\left(\frac{N - \text{nd} + 0.5}{\text{nd} + 0.5}\right)
```

Nはコーパスサイズであり、ソースコード中ではself.corpus_sizeです。
これをdfについて解くと以下が得られます。

```math
\text{nd} = \frac{N + 0.5 - 0.5e^{\text{idf}}}{e^{\text{idf}} + 1}
```

この式を用いてidfからndを求める処理を実装します。
ただし、_calc_idf関数では、idfが負になる場合は、epsilonという定数に置き換えられます。
このため、idfがepsilonの場合、対応するndを厳密に計算することはできません。

対応策は、idfがepsilonの場合、ndを適当な定数とみなすことです。
idfの計算式からndがN/2より大きいとidfが負になります。
よって例えばidf = epsilonのときnd=N/2とする、などが考えられます。

以上を踏まえ、idf辞書からコーパス全体のndを求める処理は以下のようにかけます。

```Python
def merge_nd_using_idf(bm25_list: list[BM25Okapi]) -> dict:
    merged_nd = {}
    for bm25 in bm25_list:
        for word, idf in bm25.idf.items():
            if idf == bm25.epsilon * bm25.average_idf:
                # For epsilon cases, set df = N / 2
                df = bm25.corpus_size // 2
            else:
                try:
                    exp_idf = math.exp(idf)
                    df = int((bm25.corpus_size + 0.5 - 0.5 * exp_idf) / (1 + exp_idf))
                except OverflowError:
                    # If idf is too large, set df to 0
                    df = 0

            if word in merged_nd:
                merged_nd[word] += df
            else:
                merged_nd[word] = df
    return merged_nd
```

## idf_and_doc_freqs
idf=epsilonの場合に、機械的にnd=N/2とすると誤差が大きくなりすぎる可能性があります。
そこで、idf=epsilonの場合には、doc_freqsを用いて、厳密な文書頻度（df）を求めるようにすることが考えられます。
doc_freqsの各要素は注目する文章における単語の出現頻度の辞書です。
単語の文書頻度はコーパスにおけるその単語が登場する文章の個数であるため、doc_freqsのうちkeys()にその単語を含む要素の個数として計算できます。

以上を踏まえ、idf=epsilonの場合に、doc_freqsから厳密な文書頻度を求めるように改修したものが以下です。

```Python
def merge_nd_using_idf_and_doc_freqs(bm25_list: list[BM25Okapi]) -> dict:
    merged_nd = {}
    for bm25 in bm25_list:
        for word, idf in bm25.idf.items():
            if idf == bm25.epsilon * bm25.average_idf:
                df = len([_ for doc_freq in bm25.doc_freqs if word in doc_freq])
            else:
                try:
                    exp_idf = math.exp(idf)
                    df = int((bm25.corpus_size + 0.5 - 0.5 * exp_idf) / (1 + exp_idf))
                except OverflowError:
                    # If idf is too large, set df to 0
                    df = 0

            if word in merged_nd:
                merged_nd[word] += df
            else:
                merged_nd[word] = df
    return merged_nd
```

## doc_freqs
idf辞書を使わずにdoc_freqsのみからコーパス全体の文書頻度を算出する方法も考えられます。
これはdoc_freqsの各要素のkeys()を取得し、Counterで単語の出現頻度を数え上げることで得られます。

```Python
def merge_nd_using_doc_freqs(bm25_list: list[BM25Okapi]) -> dict:
    merged_doc_freq_keys = []
    for bm25 in bm25_list:
        for doc_freq in bm25.doc_freqs:
            merged_doc_freq_keys += doc_freq.keys()
    merged_nd = Counter(merged_doc_freq_keys)
    return merged_nd
```

# 評価
コーパス全体の文書頻度（merged_nd）を求める手法として、前節であげた3つを比較します。
## 準備
### ベースライン
ベースラインとして、関数をオーバーライドしてnd辞書から計算する方法（merge_nd_using_nd）と、全コーパスでBM25Okapiを初期化する方法を用います。

merge_nd_using_ndの実装は以下のとおりです。
merge_nd_using_ndを用いるためには、事前にBM25Okapiの_initialize関数をオーバーライドしてndをプラパティに保存できるようにする必要があるため、その処理も合わせて記載しています。

```Python
from rank_bm25 import BM25Okapi
def _initialize(self, corpus):
    nd = {}  # word -> number of documents with word
    num_doc = 0
    for document in corpus:
        self.doc_len.append(len(document))
        num_doc += len(document)

        frequencies = {}
        for word in document:
            if word not in frequencies:
                frequencies[word] = 0
            frequencies[word] += 1
        self.doc_freqs.append(frequencies)

        for word, freq in frequencies.items():
            try:
                nd[word]+=1
            except KeyError:
                nd[word] = 1

        self.corpus_size += 1

    self.avgdl = num_doc / self.corpus_size
    # ndを保存
    self.nd = nd
    return nd
BM25Okapi._initialize = _initialize

def merge_nd_using_nd (bm25_list: list[BM25Okapi]) -> dict:
    merged_nd = {}
    for bm25 in bm25_list:
        for word, nd in bm25.nd.items():
            merged_nd[word] = merged_nd.get(word, 0) + nd
    return merged_nd
```

### BM25Okapiインスタンスのマージャー
merge_nd_using_...関数を使って、インスタンス全体をマージする関数を作っておきます。
第二引数にndをマージする関数を与えることで、内部で使用してくれます。

```Python
from typing import Callable
def merge_bm25(bm25_list: list[BM25Okapi], merge_nd_func: Callable[[list[BM25Okapi]], dict]) -> BM25Okapi:
    if not bm25_list:
        raise ValueError("The bm25_list is empty")

    # Combine all tokenized corpora
    merged_corpus_size = 0
    merged_doc_freqs = []
    merged_doc_len = []
    
    for bm25 in bm25_list:
        merged_corpus_size += bm25.corpus_size
        merged_doc_freqs += bm25.doc_freqs
        merged_doc_len += bm25.doc_len
    
    merged_nd = merge_nd_func(bm25_list)
            
    merged_bm25 = BM25Okapi(["a"]
                            , tokenizer = bm25_list[0].tokenizer
                            , k1 = bm25_list[0].k1
                            , b = bm25_list[0].b
                            , epsilon = bm25_list[0].epsilon)
    
    merged_bm25.corpus_size = merged_corpus_size
    merged_bm25.doc_freqs = merged_doc_freqs
    merged_bm25.doc_len = merged_doc_len
    merged_bm25.avgdl = sum(merged_doc_len) / merged_corpus_size
    
    merged_bm25._calc_idf(merged_nd)
    
    return merged_bm25
```

### コーパス
処理時間や精度の差がわかりやすいように大きめのコーパスを準備します。
ag_newsから50000件のサブコーパスを２つ作ります。
検証用のクエリも合わせて定義しておきます。クエリは適当です。

```Python
from datasets import load_dataset

# Load the AG News dataset
dataset = load_dataset('ag_news')

# Define sub-corpus size
sub_corpus_size = 50000

# Extract the text data from the dataset
corpus_a = [item['text'] for item in dataset['train'].select(range(sub_corpus_size))]  # First sub_corpus_size items for corpus_a
corpus_b = [item['text'] for item in dataset['train'].select(range(sub_corpus_size, 2 * sub_corpus_size))]  # Next sub_corpus_size items for corpus_b

# Tokenize the corpora
def tokenize(text):
    return text.split()

tokenized_corpus_a = [tokenize(doc) for doc in corpus_a]
tokenized_corpus_b = [tokenize(doc) for doc in corpus_b]

queries = [item['text'] for item in dataset['test'].select(range(1000))]
tokenized_queries = [tokenize(query) for query in queries]
```

## 速度
### 実装
マージの速度を比較します。
関数の処理時間を測定する関数を作り、それぞれの関数の速度を比較します。
ベースラインのシンプル条件だけは、マージャーを使わないため、独立に実行し、それ以外はndのマージャーを入れ替えるだけなのでforループで実行しています。

```Python
import time
import numpy as np

iterations = 100

def measure_execution_time(func, *args, iterations=10, **kwargs):
    times = []
    for _ in range(iterations):
        start_time = time.time()
        func(*args, **kwargs)
        end_time = time.time()
        times.append(end_time - start_time)
    
    average_time = np.mean(times)
    std_dev_time = np.std(times)
    
    return average_time, std_dev_time

bm25a = BM25Okapi(tokenized_corpus_a)
bm25b = BM25Okapi(tokenized_corpus_b)
bm25_list = [bm25a, bm25b]


for merge_nd_func in [merge_nd_using_nd, merge_nd_using_idf, merge_nd_using_idf_and_doc_freqs, merge_nd_using_doc_freqs]:
  # Measure time for merging BM25
  average_time_merge, std_dev_time_merge = measure_execution_time(merge_bm25, bm25_list, merge_nd_func, iterations=iterations)
  print(f"{merge_nd_func.__name__} function over {iterations} iterations: {average_time_merge} ± {std_dev_time_merge} seconds")

# Measure time for initializing BM25
average_time_init, std_dev_time_init = measure_execution_time(BM25Okapi, tokenized_corpus_a+tokenized_corpus_b)
print(f"BM25Okapi function over {iterations} iterations: {average_time_init} ± {std_dev_time_init} seconds")
```
### 結果

```
merge_nd_using_nd function over 100 iterations: 0.14476179599761962 ± 0.018721121284374143 seconds
merge_nd_using_idf function over 100 iterations: 0.19107056856155397 ± 0.010826960159610011 seconds
merge_nd_using_idf_and_doc_freqs function over 100 iterations: 0.2715064835548401 ± 0.011546251666798525 seconds
merge_nd_using_doc_freqs function over 100 iterations: 0.4932803511619568 ± 0.035805771287059696 seconds
BM25Okapi function over 100 iterations: 1.2019258499145509 ± 0.03856424170131221 seconds
```

## 精度
オーバーライドなしの方法のうち、特にidfからndを計算する方法はidf=epsilonの場合の近似や、切り捨て誤差などにより、ベースライン手法と比べて誤差が生じることが予想されます。
そこで、シンプルなベースラインとの検索結果の一致度合いから、各手法の精度を評価しました。


### 実装
速度の評価でも使った50000件のサブコーパス２つを用いて、クエリに対する検索結果を取得し、ベースラインとの検索結果の類似度をjaccard係数を用いて評価しました。
クエリは最初1000件分の平均を取ろうと思いましたが、時間がかかりすぎたので10件分の平均を取りました。

まず、bm25インスタンスを作成します。

```Python
bm25a = BM25Okapi(tokenized_corpus_a)
bm25b = BM25Okapi(tokenized_corpus_b)
bm25_list = [bm25a, bm25b]

merged_bm25_nd = merge_bm25(bm25_list, merge_nd_func=merge_nd_using_nd)
merged_bm25_idf = merge_bm25(bm25_list, merge_nd_func=merge_nd_using_idf)
merged_bm25_idf_and_doc_freqs = merge_bm25(bm25_list, merge_nd_func=merge_nd_using_idf_and_doc_freqs)
merged_bm25_doc_freqs = merge_bm25(bm25_list, merge_nd_func=merge_nd_using_doc_freqs)
merged_bm25_simple = BM25Okapi(tokenized_corpus_a+tokenized_corpus_b)
```

次に、条件ごと、top_nごとのjaccard係数を求めprintします。最後にテーブル形式でも表示させます。

```Python
import numpy as np
from tqdm import tqdm
# Calculate Jaccard coefficients for BM25 models using get_batch_scores
bm25_models = {
    "nd": merged_bm25_nd,
    "idf": merged_bm25_idf,
    "idf_and_doc_freqs": merged_bm25_idf_and_doc_freqs,
    "doc_freqs": merged_bm25_doc_freqs
}

# Define the number of top ranks to consider
top_ns = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1000]
#top_ns = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
max_n = max(top_ns)
corpus_size = len(tokenized_corpus_a) + len(tokenized_corpus_b)
query_size = 10
# Get scores and ranks for the simple model
scores_simple = []
for tokenized_query in tqdm(tokenized_queries[:query_size]):
    scores_simple.append(merged_bm25_simple.get_scores(tokenized_query))
ranks_simple = np.argsort(scores_simple, axis=1)[:, ::-1]

import pandas as pd

# Initialize a DataFrame to store the Jaccard coefficients
jaccard_df = pd.DataFrame(columns=["Model"] + [f"Top {n}" for n in top_ns])

for model_name, bm25_model in bm25_models.items():
    scores = []
    for tokenized_query in tqdm(tokenized_queries[:query_size]):
        scores.append(bm25_model.get_scores(tokenized_query))
    ranks = np.argsort(scores, axis=1)[:, ::-1]
    
    jaccard_scores_dict = {"Model": model_name}
    for n in top_ns:
        jaccard_scores = []
        for i in range(len(tokenized_queries[:query_size])):
            set_ranks = set(ranks[i, :n])
            set_simple = set(ranks_simple[i, :n])
            intersection = set_ranks.intersection(set_simple)
            union = set_ranks.union(set_simple)
            jaccard = len(intersection) / len(union) if union else 0
            jaccard_scores.append(jaccard)
        
        average_jaccard = np.mean(jaccard_scores)
        std_dev_jaccard = np.std(jaccard_scores)
        print(f"Jaccard coefficient for top {n} ranks ({model_name} vs simple): {average_jaccard:.4f} ± {std_dev_jaccard:.4f}")
        
        # Store results in the dictionary
        jaccard_scores_dict[f"Top {n}"] = f"{average_jaccard:.4f} ± {std_dev_jaccard:.4f}"
    
    # Append results to the DataFrame
    jaccard_df = pd.concat([jaccard_df, pd.DataFrame([jaccard_scores_dict])], ignore_index=True)

# Display the DataFrame
print(jaccard_df)
```

以下の標準出力が得られました。

```
100%|██████████| 10/10 [00:12<00:00,  1.23s/it]
100%|██████████| 10/10 [00:12<00:00,  1.27s/it]
Jaccard coefficient for top 1 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 2 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 3 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 4 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 5 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 6 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 7 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 8 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 9 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 10 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 100 ranks (nd vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 1000 ranks (nd vs simple): 1.0000 ± 0.0000
100%|██████████| 10/10 [00:12<00:00,  1.28s/it]
Jaccard coefficient for top 1 ranks (idf vs simple): 0.9000 ± 0.3000
Jaccard coefficient for top 2 ranks (idf vs simple): 0.6333 ± 0.3786
Jaccard coefficient for top 3 ranks (idf vs simple): 0.6200 ± 0.3458
Jaccard coefficient for top 4 ranks (idf vs simple): 0.6467 ± 0.3347
Jaccard coefficient for top 5 ranks (idf vs simple): 0.6167 ± 0.3317
Jaccard coefficient for top 6 ranks (idf vs simple): 0.6629 ± 0.3416
Jaccard coefficient for top 7 ranks (idf vs simple): 0.5983 ± 0.3311
Jaccard coefficient for top 8 ranks (idf vs simple): 0.5696 ± 0.2963
Jaccard coefficient for top 9 ranks (idf vs simple): 0.5505 ± 0.3052
Jaccard coefficient for top 10 ranks (idf vs simple): 0.5449 ± 0.3049
Jaccard coefficient for top 100 ranks (idf vs simple): 0.4730 ± 0.3367
Jaccard coefficient for top 1000 ranks (idf vs simple): 0.4271 ± 0.3361
100%|██████████| 10/10 [00:12<00:00,  1.27s/it]
Jaccard coefficient for top 1 ranks (idf_and_doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 2 ranks (idf_and_doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 3 ranks (idf_and_doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 4 ranks (idf_and_doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 5 ranks (idf_and_doc_freqs vs simple): 0.9667 ± 0.1000
Jaccard coefficient for top 6 ranks (idf_and_doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 7 ranks (idf_and_doc_freqs vs simple): 0.9750 ± 0.0750
Jaccard coefficient for top 8 ranks (idf_and_doc_freqs vs simple): 0.9333 ± 0.1018
Jaccard coefficient for top 9 ranks (idf_and_doc_freqs vs simple): 0.9600 ± 0.0800
Jaccard coefficient for top 10 ranks (idf_and_doc_freqs vs simple): 0.9636 ± 0.0727
Jaccard coefficient for top 100 ranks (idf_and_doc_freqs vs simple): 0.9442 ± 0.0345
Jaccard coefficient for top 1000 ranks (idf_and_doc_freqs vs simple): 0.9484 ± 0.0343
100%|██████████| 10/10 [00:12<00:00,  1.25s/it]
Jaccard coefficient for top 1 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 2 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 3 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 4 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 5 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 6 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 7 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 8 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 9 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 10 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 100 ranks (doc_freqs vs simple): 1.0000 ± 0.0000
Jaccard coefficient for top 1000 ranks (doc_freqs vs simple): 1.0000 ± 0.0000

              Model            Top 1            Top 2            Top 3  \
0                 nd  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   
1                idf  0.9000 ± 0.3000  0.6333 ± 0.3786  0.6200 ± 0.3458   
2  idf_and_doc_freqs  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   
3          doc_freqs  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   

             Top 4            Top 5            Top 6            Top 7  \
0  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   
1  0.6467 ± 0.3347  0.6167 ± 0.3317  0.6629 ± 0.3416  0.5983 ± 0.3311   
2  1.0000 ± 0.0000  0.9667 ± 0.1000  1.0000 ± 0.0000  0.9750 ± 0.0750   
3  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   

             Top 8            Top 9           Top 10          Top 100  \
0  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   
1  0.5696 ± 0.2963  0.5505 ± 0.3052  0.5449 ± 0.3049  0.4730 ± 0.3367   
2  0.9333 ± 0.1018  0.9600 ± 0.0800  0.9636 ± 0.0727  0.9442 ± 0.0345   
3  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000  1.0000 ± 0.0000   

          Top 1000  
0  1.0000 ± 0.0000  
1  0.4271 ± 0.3361  
2  0.9484 ± 0.0343  
```

テーブル形式の出力が見にくかったので、notebook上でdisplay関数を使って表示させました。
結果は次小節に記載します。
```Python
from IPython.display import display
display(jaccard_df)
```

```
	Model	Top 1	Top 2	Top 3	Top 4	Top 5	Top 6	Top 7	Top 8	Top 9	Top 10	Top 100	Top 1000
0	nd	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000
1	idf	0.9000 ± 0.3000	0.6333 ± 0.3786	0.6200 ± 0.3458	0.6467 ± 0.3347	0.6167 ± 0.3317	0.6629 ± 0.3416	0.5983 ± 0.3311	0.5696 ± 0.2963	0.5505 ± 0.3052	0.5449 ± 0.3049	0.4730 ± 0.3367	0.4271 ± 0.3361
2	idf_and_doc_freqs	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	0.9667 ± 0.1000	1.0000 ± 0.0000	0.9750 ± 0.0750	0.9333 ± 0.1018	0.9600 ± 0.0800	0.9636 ± 0.0727	0.9442 ± 0.0345	0.9484 ± 0.0343
3	doc_freqs	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000	1.0000 ± 0.0000
```

## 結果
モデルごと、top_nごとのjaccard係数は以下のようになりました。

| Model             | Speed (mean±SD) (sec) | Top 1           | Top 3           | Top 5           | Top 10          | Top 100         | Top 1000        |
|:------------------|:----------------------|:----------------|:----------------|:----------------|:----------------|:----------------|:----------------|
| nd                | 0.144 ± 0.018         | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   |
| idf               | 0.191 ± 0.010         | 0.900 ± 0.300   | 0.620 ± 0.346   | 0.617 ± 0.332   | 0.545 ± 0.305   | 0.473 ± 0.337   | 0.427 ± 0.336   |
| idf_and_doc_freqs | 0.271 ± 0.011         | 1.000 ± 0.000   | 1.000 ± 0.000   | 0.967 ± 0.100   | 0.964 ± 0.073   | 0.944 ± 0.035   | 0.948 ± 0.034   |
| doc_freqs         | 0.493 ± 0.035         | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   | 1.000 ± 0.000   |
| Simple (Baseline) | 1.201 ± 0.038         | -               | -               | -               | -               | -               | -               |

# 考察
速度と抜粋した精度の結果を改めて以下にまとめます。

| Model             | Speed (mean±SD) (sec) | Top 1           | Top 3           | Top 5           | Top 10          | Top 100         | Top 1000        |
|:------------------|:----------------------|:----------------|:----------------|:----------------|:----------------|:----------------|:----------------|
| nd (Baseline)        | 0.144 ± 0.018         | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 |
| idf               | 0.191 ± 0.010         | 0.9000 ± 0.3000 | 0.6200 ± 0.3458 | 0.6167 ± 0.3317 | 0.5449 ± 0.3049 | 0.4730 ± 0.3367 | 0.4271 ± 0.3361 |
| idf_and_doc_freqs | 0.271 ± 0.011         | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 0.9667 ± 0.1000 | 0.9636 ± 0.0727 | 0.9442 ± 0.0345 | 0.9484 ± 0.0343 |
| doc_freqs         | 0.493 ± 0.035         | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 |
| Simple (Baseline) | 1.201 ± 0.038         | -               | -               | -               | -               | -               | -               |

まずベースラインの１つであるnd条件は速度と精度を最も両立できています。
オーバーライドが可能であれば、この方法を採用するのが良いと考えられます。

オーバーライドを不要とする提案手法のうち、idf条件は速度ははやいものの、top100の精度はあまり高くありません。jaccard係数が0.4くらいということは、提案手法の検索結果のうち6割くらいは、ベースライン手法の検索結果に含まれている見積もりになるため、全く使えないほど悪いということではありませんが、他の方法に比べて積極的に採用するメリットはなさそうです。

idf_and_doc_freqsは、ベースライン条件と完全に一致こそしないものの、idf条件に比べれば、速度と精度のバランスが良いように思われます。許容範囲に入る可能性はあるかもしれません。
doc_freqs条件は、nd条件等に比べるとかなり遅いものの、シンプルなベースラインよりは速く、精度も十分なため、オーバーライドが難しい状況における有力な候補になりそうです。

以上を踏まえると以下のようなことがいえそうです。

- コーパスサイズが少なく速度が気にならない場合は、実装が簡単なシンプルなベースラインを使う
- 速度が気になる場合、関数メソッドのオーバーライドが許容できるならnd条件を採用する。
- 速度が気になるが、オーバーライドをしたくないときは、速度重視のidf_and_doc_freqsか精度重視のdoc_freqsを使う。

# おわりに
rank_bm25のマージ時にオーバーライドを避ける方法を検討しました。
idfベースの計算の誤差が思ったより大きいことが、本格的にアプリ等に組み込む前にわかってよかったです。