nlist と nprobe の意味と最適化

FAISS（Facebook AI Similarity Search）における「nlist」および「nprobe」は、特に近似最近傍検索を行うインデックス（例：IVF系、特に IndexIVFFlat や IndexIVFPQ）において、検索精度と速度のバランスを制御するための重要なパラメータです。以下、それぞれの意味と最適化方法について詳しく説明します。

---

1. nlist（ナビゲーションクラスタ数）

意味

• nlist は、インデックスのクラスタ数（セントロイド数）を表します。

• ベクトル空間をクラスタリング（通常はk-means）して分割した「部分空間（インバーテッドリスト）」の数です。

• インデックスの構築（index.train()）時に使われる。

役割

• 各データベクトルは、最も近いクラスタ（セントロイド）に割り当てられる。

• 検索時には、まずクエリベクトルがどのクラスタに属するかを調べ、そのクラスタ内のベクトルに対して検索を行うことで、計算量を削減する。

値の選び方（目安）

• 一般的には、データベクトル数の平方根程度を目安とすることが多い。

  • 例：データが100万件 → nlist = 1000 〜 10000

• ただし、あまりに大きすぎると、クラスタあたりのベクトルが少なくなり、検索精度が低下する。

---

2. nprobe（検索対象クラスタ数）

意味

• nprobe は、検索時に探索対象とするクラスタの数を表します。

• クエリベクトルに最も近い nprobe 個のクラスタを対象に、そこでの近傍ベクトルを探索する。

役割

• nprobe が小さいと検索は速いが、精度は低下しやすい。

• nprobe を大きくすると、より多くのクラスタを検索するため精度は上がるが、計算時間が増える。

値の選び方（目安）

• 小さい値（例：nprobe = 1）は高速だが粗い。

• 大きい値（例：nprobe = 64）は精度が向上する。

• 実運用では、nprobe = 5 〜 nprobe = 64 の範囲で精度と速度のトレードオフを見ながら調整する。

---

3. nlist と nprobe の最適化

チューニング戦略

1. まずは nlist を決定：

   • データサイズの平方根程度を初期値とする。

   • 例：データが100万件 → nlist = 1000 〜 4096

2. 次に nprobe を調整：

   • 小さい値から開始し、検索精度が不十分な場合に徐々に増やす。

   • 検索精度（recall）や応答時間を評価しながらチューニング。

3. 評価指標の活用：

   • 検索結果のrecall（再現率）

   • 平均応答時間（latency）

   • スループット（queries/sec）

最適化の考慮事項

• nlist を増やす → 各クラスタが小さくなり、高速だがクラスタ選択の精度が重要。

• nprobe を増やす → 精度が向上するが、計算量とメモリ使用量が増加。

• 大規模データでは、nlist を大きく、nprobe を適度に設定することが一般的。

---

4. 実装例（Python）

python
import faiss

d = 128  # 次元数
nb = 100000  # データ数
nlist = 1024
nprobe = 16

quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

# トレーニング（必要）
index.train(data_vectors)

# ベクトル追加
index.add(data_vectors)

# nprobe の設定
index.nprobe = nprobe

# クエリ検索
D, I = index.search(query_vectors, k=10)

---

まとめ表