スマートフォンで撮った1枚の写真に「これと似た商品」を返す、あるいは文章を埋め込みベクトルにして「意味が近い文書」を引いてくる——こうした検索の裏側では、クエリのベクトルに最も近いベクトルをデータベースから探すという計算が走っています。データが数千件なら、全部と距離を測る「全探索」で十分です。ところが現実のサービスでは、ベクトルの数が数千万〜数十億になります。
ここで2つの壁にぶつかります。1つ目はメモリです。128次元の float32 ベクトルは1本あたり512バイト。10億本なら $512\text{B}\times 10^9 = 512\text{GB}$ となり、普通のマシンの RAM(16〜64GB)には到底乗りません。2つ目は速度です。1回のクエリで10億本すべてと距離を測れば、数十億回の乗算が必要で、リアルタイム応答は望めません。
Product Quantization(積量子化、以下 PQ)(Jégou, Douze, Schmid, IEEE TPAMI 2011)は、この2つの壁を同時に崩す技術です。アイデアは単純で、ベクトルを $m$ 個の短い部分ベクトルに割り、各部分を「あらかじめ用意した代表点(セントロイド)の番号」に置き換えるだけ。これで1本のベクトルが、たった $m$ バイト(典型的には8〜16バイト)に圧縮されます。512バイトが8バイトになれば、10億本でも8GBで RAM に乗ります。しかも距離計算は「事前に作った小さな表を引いて足す」だけになり、桁違いに速くなります。PQ は、世界中で使われるベクトル検索ライブラリ FAISS の心臓部であり、近似最近傍探索(ANN)の事実上の標準部品です。
PQ が活きる場面は、たとえば次のようなものです。
- 画像・商品の類似検索：何億枚もの画像を特徴ベクトルにして、似た見た目の商品を即座に返す。元の画像ベクトルをそのまま持つのは非現実的なので、PQ で圧縮して RAM に常駐させる。
- テキスト・RAG の意味検索：文章を埋め込みベクトルにして、意味が近い文書を引く。大規模なナレッジベースでも、PQ で圧縮すれば1台のマシンで検索できる。
本記事では、PQ の中心にある 量子化器の定義、ベクトルを部分に割って $k^m$ 通りの代表点を $mk$ 個のセントロイドで表す 直積構造、距離計算を表引きに変える SDC(対称)／ADC(非対称)、そして大規模化のための IVFADC までを、数式の導出と Python のスクラッチ実装で順に組み上げます。すべてのコードは実際に動かし、本文に書いた recall や圧縮率の値と一致することを確認しています。
本記事の内容
- ベクトル量子化と「コードブック」という考え方の直感的理解
- ベクトルを部分に割る積量子化：$k^m$ 個の代表点を $mk$ 個のセントロイドで表す直積構造
- 距離テーブルによる高速化：SDC と ADC の違いと精度差
- IVFADC(転置ファイル + PQ)による大規模化と、recall@R・圧縮率のスクラッチ実測
前提・関連記事
この記事は、ベクトルどうしの距離と k-means クラスタリングを土台にします。先に目を通しておくと理解が深まります。
なぜ圧縮が必要か：メモリの壁を絵で見る
具体的な数字で壁の高さを実感しておきましょう。次元 $D=128$ の float32 ベクトル(1要素4バイト)を、ベクトル数 $N$ を変えながら、全探索でそのまま持つ場合と、PQ で8バイトに圧縮した場合のメモリ量を比べます。
横軸はベクトル数、縦軸はメモリ量(GB、両対数)です。点線は一般的な RAM の16GBを示します。全探索(赤)は $N=10^8$ あたりですでに RAM を超え、$N=10^9$ では512GBに達します。一方、PQ(緑)は同じ10億本でもわずか8GBで、16GB の RAM に収まります。圧縮しなければ「そもそもメモリに乗らない」——これが PQ を使う最大の動機です。乗らなければ遅いディスクへのアクセスが発生し、速度は壊滅的に落ちます。
では、どうやってベクトルを8バイトに圧縮するのか。鍵は「ベクトル量子化」という考え方です。
ベクトル量子化：代表点の番号で表す
圧縮の発想自体は身近です。色を「RGB の3つの数値」ではなく「256色パレットの番号」で表す、いわゆるインデックスカラー画像を思い出してください。色そのものを持つ代わりに、あらかじめ決めた代表色の番号を1つ持てば済みます。番号は0〜255なので1バイト。ベクトル量子化(Vector Quantization, VQ)は、これをベクトルに対してやるものです。
ベクトル量子化器(quantizer)とは、入力ベクトル $x \in \mathbb{R}^D$ を、有限個の代表点(セントロイド)の集合 $\mathcal{C} = \{c_1, \dots, c_k\}$ のどれか1つに対応づける関数です。「最も近い代表点に丸める」のが自然なので、量子化器 $q$ は次のように定義されます。
$$ \begin{equation} q(x) = \arg\min_{c_i \in \mathcal{C}} \; \| x – c_i \|^2 \end{equation} $$
この $\mathcal{C}$ をコードブック(codebook)、各 $c_i$ をコードワード、そして選ばれた代表点の番号 $i$ をコードと呼びます。ベクトルを保存するときは、$x$ そのものではなく、コード $i$(整数1個)だけを持ちます。$k$ 個の代表点を区別するには $\lceil \log_2 k \rceil$ ビットあれば十分です。たとえば $k=256$ なら8ビット=1バイトで足ります。
良いコードブックとは、どんな入力 $x$ が来ても「近い代表点が必ず存在する」ものです。これは入力データの分布をよく代表する代表点を選ぶ問題であり、まさに k-means クラスタリングそのものです。学習データ集合に対して量子化誤差(歪み)
$$ \begin{equation} \text{distortion} = \frac{1}{N}\sum_{n=1}^{N} \| x_n – q(x_n) \|^2 \end{equation} $$
を最小にするようセントロイドを決めれば、それが良いコードブックになります。k-means の Lloyd 法は、まさにこの歪みを下げる反復アルゴリズムでした。
ここで素朴な疑問が湧きます。「では $D=128$ 次元のベクトル全体を、十分に細かく量子化すればいいのでは?」と。残念ながら、これは破綻します。次の節で、その理由と PQ の核心的な工夫を見ましょう。
なぜ部分に割るのか：直積構造の威力
128次元空間を細かく覆うには、途方もない数の代表点が要ります。たとえば1バイトに圧縮したい(8ビット=256通り)なら $k=256$ ですが、128次元空間を256個の代表点で覆っても粗すぎて、量子化誤差が大きく実用になりません。十分な精度を出すには $k$ を $2^{64}$ のような天文学的な数にする必要があり、(1) コードブック(セントロイド)を保持するだけで $k \times D$ のメモリが爆発し、(2) 量子化(式1の $\arg\min$)に $k$ 回の距離計算がかかって学習も符号化も不可能になります。これが「高次元を1つの量子化器で扱う」ことの限界です。
PQ の工夫は、ベクトルを $m$ 個の短い部分ベクトルに分割し、それぞれを独立に量子化することです。$D$ 次元ベクトル $x$ を、長さ $D^* = D/m$ の部分ベクトル $u_1(x), \dots, u_m(x)$ に区切ります。
上の図は $D=16$ を $m=4$ に割った例です。各部分(色分け)を、その部分空間専用のコードブックで「最も近いセントロイドの番号」に置き換えます。4つの部分がそれぞれ1バイトの番号(例: 37, 201, 5, 128)になり、合わせて4バイトになります。元の64バイト(16次元×4バイト)が4バイト、16倍の圧縮です。各部分空間 $j$ には専用の量子化器 $q_j$(コードブック $\mathcal{C}_j$、サイズ $k$)があり、ベクトル全体の量子化器は部分の連結
$$ \begin{equation} q(x) = \big( q_1(u_1(x)),\; q_2(u_2(x)),\; \dots,\; q_m(u_m(x)) \big) \end{equation} $$
になります。$x$ を保存するときは、$m$ 個のコード(各 $\log_2 k$ ビット)を並べた PQ コード $(b_1, \dots, b_m)$ を持ちます。$m=8$、$k=256$ なら $8 \times 8\text{bit} = 8\text{バイト}$。これが PQ の圧縮の正体です。
ここからが PQ の最も美しい点です。部分ごとに独立な量子化器を組み合わせると、全体としては $k^m$ 通りの異なる量子化点を表現できます。部分1が $k$ 通り、部分2が $k$ 通り…と独立なので、組み合わせは積になるからです。$k=256$、$m=8$ なら $256^8 \approx 1.8\times 10^{19}$ 通り。にもかかわらず、実際に保持するセントロイドは各部分空間の $k$ 個 × $m$ 部分 = $mk$ 個(この例では $256\times 8 = 2048$ 個)だけ。この「$k^m$ 個の代表点を $mk$ 個のパラメータで表す」性質を直積構造(product structure)と呼び、これが PQ という名前(Product Quantization)の由来です。
横軸は部分空間の数 $m$、縦軸はセントロイド数(対数)です。赤の「表現できるセントロイド総数 $k^m$」は $m$ とともに爆発的に増えるのに対し、緑の「実際に保持する数 $mk$」は $m$ に比例して緩やかにしか増えません。$m=8$ で $256^8$ という巨大な量子化点を、たった2048個のセントロイドで実現している——この差こそが、PQ が高次元を扱える理由です。少ないメモリと計算で、空間を十分細かく覆えるのです。
直積構造の代償は、部分空間どうしの相関を無視することです(各 $q_j$ は独立)。元の次元の並び順によっては相関が偏り、誤差が増えます。これを和らげる工夫(各部分空間のエネルギーを揃える次元の並べ替えや回転、OPQ など)もありますが、本記事では基本形に集中します。では、このコードブックを実際に学習し、ベクトルを符号化する実装に進みましょう。
コードブックの学習と符号化：実装
実装の方針はシンプルです。学習データを $m$ 個の部分に縦に割り、各部分で k-means を回して $k$ 個のセントロイドを得ます。これが $m$ 個のコードブックです。符号化(encode)は、各部分について「最も近いセントロイドの番号」を求めて並べるだけです。
まず、コードブック学習に使う k-means(Lloyd 法)を用意します。空クラスタは最も外れた点で再初期化しておきます。
import numpy as np
def kmeans(X, k, n_iter=25, seed=0):
"""素朴なLloyd法。空クラスタは最遠点で再初期化。"""
rng = np.random.default_rng(seed)
n = len(X)
C = X[rng.choice(n, k, replace=False)].copy()
for _ in range(n_iter):
d2 = ((X[:, None, :] - C[None, :, :])**2).sum(2) # n×k 距離^2
a = d2.argmin(1)
for j in range(k):
mask = a == j
if mask.any():
C[j] = X[mask].mean(0)
else:
C[j] = X[d2.min(1).argmax()] # 空なら最も外れた点へ
return C
次に、PQ 本体をクラスにまとめます。fit で部分空間ごとにコードブックを学習し、encode でベクトルを PQ コード(各部分のセントロイド番号)に変換、decode で復元します。
class PQ:
def __init__(self, m, k=256, seed=0):
self.m = m; self.k = k; self.seed = seed
def fit(self, X):
n, D = X.shape
assert D % self.m == 0
self.D = D; self.dsub = D // self.m # 各部分の次元 D* = D/m
self.codebooks = np.zeros((self.m, self.k, self.dsub))
for j in range(self.m):
sub = X[:, j*self.dsub:(j+1)*self.dsub] # 第j部分空間を切り出す
self.codebooks[j] = kmeans(sub, self.k, seed=self.seed + j)
return self
def encode(self, X):
"""各ベクトル→mバイトのPQコード(各部分の最近傍セントロイド番号)。"""
n = len(X); codes = np.empty((n, self.m), dtype=np.uint8)
for j in range(self.m):
sub = X[:, j*self.dsub:(j+1)*self.dsub]
d2 = ((sub[:, None, :] - self.codebooks[j][None, :, :])**2).sum(2)
codes[:, j] = d2.argmin(1) # 最も近いセントロイド番号
return codes
def decode(self, codes):
"""PQコード→復元ベクトル(セントロイドを連結)。"""
n = len(codes); X = np.empty((n, self.D))
for j in range(self.m):
X[:, j*self.dsub:(j+1)*self.dsub] = self.codebooks[j][codes[:, j]]
return X
encode の出力は uint8 の $n \times m$ 配列です。各要素が0〜255の番号なので、1ベクトルが文字どおり $m$ バイトになっています。decode は番号からセントロイドを引いて連結するだけ。元のベクトルは戻ってきませんが、「近いセントロイド」で近似されます。
クラスタ構造のある合成データ(DB 10000本、クエリ 200本、$D=32$)で動かし、圧縮率と量子化誤差を確かめます。
def make_data(n_db=10000, n_q=200, D=32, n_clusters=24, seed=1):
rng = np.random.default_rng(seed)
centers = rng.normal(0, 6.0, size=(n_clusters, D))
def sample(n):
c = rng.integers(0, n_clusters, n)
return centers[c] + rng.normal(0, 1.0, size=(n, D))
return sample(n_db).astype(np.float32), sample(n_q).astype(np.float32)
DB, QS = make_data()
n_db, D = DB.shape
M, K = 8, 256
pq = PQ(M, K, seed=0).fit(DB)
codes = pq.encode(DB) # 10000×8 uint8 = 8バイト/ベクトル
bytes_orig = D * 4 # float32 D次元
bytes_pq = M * 1 # k=256 → 8bit → 1バイト/部分
print("圧縮率 %dB -> %dB = %.1fx" % (bytes_orig, bytes_pq, bytes_orig / bytes_pq))
recon = pq.decode(codes)
mse = ((DB - recon)**2).sum(1).mean()
print("再構成MSE(distortion) =", round(float(mse), 4))
実行すると、圧縮率 128B -> 8B = 16.0x、再構成MSE(distortion) = 12.3424 と出ます。$D=32$ の float32 は128バイト、PQ は8バイトなので16倍の圧縮です。$D=128$ なら512バイト→8バイトで64倍になり、冒頭のメモリ図の数字につながります。量子化誤差 MSE=12.34 は、各部分空間を256個の代表点で丸めたときの「丸め誤差の総量」です。元ベクトルと復元ベクトルを1本だけ重ねて見ましょう。
青が元ベクトル、赤の破線が PQ で復元したベクトル、オレンジの帯がその差(量子化誤差)です。8バイトという極端な圧縮にもかかわらず、復元は元の大まかな形をよく追えています。各次元でぴたり一致はしませんが、後で見るように、最近傍探索の用途ではこの程度の近似で十分に役立ちます。次に、各部分空間のコードブックが何を学習したのかを覗いてみましょう。
3つの部分空間それぞれについて、データ点(灰)とコードブックのセントロイド(赤×)を、最初の2次元に投影して描いたものです。セントロイドがデータの広がる領域にまんべんなく配置され、その部分空間の分布をよく代表していることが分かります。各部分空間で独立に k-means を回すため、コードブックは部分空間ごとに別々です。これら $m$ 個のコードブックがそろえば、いよいよ「圧縮したまま距離を計算する」という PQ の本領に入れます。
圧縮したまま距離を測る：SDC と ADC
ここまでで、ベクトルを8バイトに圧縮できました。しかし最近傍探索のゴールは「クエリ $y$ に最も近い DB ベクトル $x$ を見つける」こと。圧縮した8バイトのコードから、どうやって距離 $\|y – x\|$ を計算するのでしょうか。いちいち decode して元次元で距離を測っては、圧縮の旨味が消えてしまいます。
PQ の答えは、距離を部分空間ごとの距離の和に分解することです。ユークリッド距離の二乗は次元方向に足し合わせられるので、ベクトルを $m$ 部分に割った場合、
$$ \begin{equation} \| y – x \|^2 = \sum_{j=1}^{m} \| u_j(y) – u_j(x) \|^2 \end{equation} $$
と部分ごとの和に書けます。$x$ は PQ コードで持っているので、各部分 $u_j(x)$ はセントロイド $c_{j, b_j}$(部分空間 $j$ のコードブックの $b_j$ 番)で近似されています。これを使うと、距離計算には2つの流儀があります。
SDC：対称距離計算(クエリも量子化する)
1つ目は SDC(Symmetric Distance Computation)。クエリ $y$ も DB と同じく PQ で量子化してしまい、両方ともセントロイドの番号で距離を測ります。
$$ \begin{equation} \hat{d}_{\text{SDC}}(y, x)^2 = \sum_{j=1}^{m} \big\| c_{j, a_j} – c_{j, b_j} \big\|^2 \end{equation} $$
ここで $a_j$ はクエリの第 $j$ 部分のコード、$b_j$ は DB ベクトルの第 $j$ 部分のコードです。セントロイドどうしの距離は有限個しかない($k \times k$ 通り)ので、各部分空間について $k \times k$ の距離表 $\| c_{j,a} – c_{j,b} \|^2$ を事前に1回だけ計算しておけば、あとは表を引いて足すだけ。距離計算が「表引き $m$ 回 + 加算 $m-1$ 回」になります。
ADC：非対称距離計算(クエリは生のまま)
2つ目は ADC(Asymmetric Distance Computation)。こちらはクエリ $y$ を量子化せず、生のベクトルのまま使います。
$$ \begin{equation} \hat{d}_{\text{ADC}}(y, x)^2 = \sum_{j=1}^{m} \big\| u_j(y) – c_{j, b_j} \big\|^2 \end{equation} $$
「非対称」と呼ぶのは、クエリ側だけ量子化していないからです。クエリ1本が来たら、各部分空間 $j$ について「クエリの部分 $u_j(y)$ と、その部分のコードブックの全 $k$ 個のセントロイドとの距離」を計算し、$m \times k$ の距離テーブルを作ります。
$$ \begin{equation} \text{tab}[j, i] = \big\| u_j(y) – c_{j, i} \big\|^2, \quad i = 0, \dots, k-1 \end{equation} $$
このテーブルさえ作れば、任意の DB ベクトル(PQ コード $(b_1, \dots, b_m)$)に対する近似距離は
$$ \begin{equation} \hat{d}_{\text{ADC}}(y, x)^2 = \sum_{j=1}^{m} \text{tab}[j, b_j] \end{equation} $$
と、テーブルを $m$ 回引いて足すだけで求まります。クエリ1本あたりテーブル作成に $O(mk)$、その後は DB ベクトル1本につき $O(m)$ の加算で済みます。$N$ 本に対して $O(mk + Nm)$。$m$ は8〜16と小さいので、これが「全探索 $O(ND)$ より桁違いに速い」理由です。下の図でテーブルと距離分解を可視化します。
左は、あるクエリに対して事前計算した $m \times k$ の距離テーブル(各行が1つの部分空間、各列がセントロイド番号、色が距離)です。右は、ある DB ベクトルの近似距離を計算する様子で、各部分空間 $j$ について「自分のコード $b_j$ の列」をテーブルから1つずつ引いて(青いバー)、それらを足し上げた値が近似距離になります。距離計算が乗算ではなくテーブル引きの加算に変わっているのが要点です。
SDC と ADC の違いは、図にすると一目瞭然です。
1次元の部分空間で、クエリ点(緑の星)と DB 点(青)を考えます。左の SDC は、クエリも DB も「最も近いセントロイド」に丸めてから距離を測ります。クエリが量子化された分、誤差が両側で発生します。右の ADC は、クエリを生のまま使い、DB 側だけセントロイドで近似します。量子化誤差が片側だけになるため、ADC のほうが真の距離に近く、精度が高くなります。
SDC の利点は、距離表を $k \times k$ × $m$ で全 DB に共通して事前計算でき、クエリごとのテーブル作成すら不要なこと(クエリのコードさえ分かれば即座に表引き)。一方 ADC は、クエリごとに $m \times k$ のテーブルを作る手間がありますが、その分精度が高い。実運用では、検索精度が重視されるため ADC が主流です。両者の精度差を、実装して数値で確かめましょう。
SDC と ADC の精度を実測する
距離テーブルと recall を計算します。recall@R は「真の最近傍が、近似距離で並べた上位 $R$ 件に入っている割合」で、近似探索の精度指標の定番です。まず ADC のテーブルと距離、SDC 用のセントロイド間距離表を PQ クラスに足します。
def adc_table(self, q):
"""ADC: クエリ部分ベクトルと各コードブックの距離^2テーブル m×k。"""
tab = np.empty((self.m, self.k))
for j in range(self.m):
qj = q[j*self.dsub:(j+1)*self.dsub]
tab[j] = ((self.codebooks[j] - qj[None, :])**2).sum(1)
return tab
def adc_dist(self, q, codes):
"""ADC近似距離^2 = Σ_j table[j, code_j]。テーブル引きの総和。"""
tab = self.adc_table(q)
return tab[np.arange(self.m)[None, :], codes].sum(1)
def build_sdc_tables(self):
"""各部分空間のセントロイド間距離^2を事前計算(k×k × m)。"""
self.D_centroids = np.zeros((self.m, self.k, self.k))
for j in range(self.m):
C = self.codebooks[j]
self.D_centroids[j] = ((C[:, None, :] - C[None, :, :])**2).sum(2)
def sdc_dist(self, qcode, codes):
"""SDC: クエリもコード化。事前計算したセントロイド間距離^2を引く。"""
d = np.zeros(len(codes))
for j in range(self.m):
d += self.D_centroids[j][qcode[j], codes[:, j]]
return d
全探索で求めた「真の最近傍」を正解として、ADC と SDC の recall@R を測ります。
def brute_knn(q, DB, k):
d2 = ((DB - q[None, :])**2).sum(1)
return np.argsort(d2)[:k]
GT1 = np.array([brute_knn(q, DB, 1)[0] for q in QS]) # 真の最近傍(全探索)
pq.build_sdc_tables()
qcodes = pq.encode(QS) # SDC用にクエリも符号化
def recall_at_R(dist_fn, Rs=(1, 5, 10, 50, 100)):
res = {R: 0 for R in Rs}
for qi, q in enumerate(QS):
order = np.argsort(dist_fn(qi, q))
for R in Rs:
if GT1[qi] in order[:R]:
res[R] += 1
return {R: res[R] / len(QS) for R in Rs}
adc_recall = recall_at_R(lambda qi, q: pq.adc_dist(q, codes))
sdc_recall = recall_at_R(lambda qi, q: pq.sdc_dist(qcodes[qi], codes))
print("ADC recall@R", {k: round(v, 3) for k, v in adc_recall.items()})
print("SDC recall@R", {k: round(v, 3) for k, v in sdc_recall.items()})
実行すると、ADC は {1: 0.135, 5: 0.38, 10: 0.55, 50: 0.9, 100: 0.975}、SDC は {1: 0.075, 5: 0.21, 10: 0.315, 50: 0.675, 100: 0.835} となります。棒グラフで比べましょう。
どの $R$ でも ADC(水色)が SDC(オレンジ)を一貫して上回ります。これは前節の図のとおり、ADC がクエリを量子化しない分、誤差が小さいからです。注目したいのは数字の読み方です。recall@1(真の最近傍がぴたり1位)は ADC でも0.135と低めですが、recall@50 は0.9、recall@100 は0.975に達します。これは PQ の実運用での使い方を示しています。PQ は「上位の候補を高速にふるい分ける」段で使い、その少数の候補だけを元ベクトルで正確に測り直す(re-rank する)のが定石です。8バイトの粗い近似で上位100件まで絞れば、その中に真の最近傍が97.5%の確率で入っている。あとは100件を厳密に測ればよい——全探索の数万倍速く、ほぼ正確な答えが得られます。距離の近似がどれくらい速いかを、演算量で見ておきます。
左は、クエリごとに「ADC で並べた上位100件が、真の上位100件をどれだけ捕えているか(recall@100)」のヒストグラムで、平均0.59です。粗い8バイトでも真の近傍集合の約6割を1発で回収できています。右は距離計算の演算量(対数)で、全探索が DB 全体に対し $O(N \cdot D)$ の乗算を要するのに対し、ADC はテーブルを作った後は $O(N \cdot m)$ の加算だけで済みます($m \ll D$)。精度をある程度保ちつつ、距離計算を加算の和に落とす——これが PQ の速さの源です。次に、精度とメモリのトレードオフを握る2つのつまみ、$m$ と $k$ の効きを見ます。
m と k のトレードオフを調べる
PQ には調整つまみが2つあります。部分空間の数 $m$ と、コードブックのサイズ $k$ です。$m$ を増やすと符号は $m$ バイトに長くなりますが、空間をより細かく割れるので精度が上がります。$k$ を増やすと各部分空間の代表点が増えて誤差が下がりますが、符号は $m \log_2 k$ ビットに伸びます。まず $m$ を振って、再構成誤差と recall@1 がどう動くかを見ます。
ms = [1, 2, 4, 8, 16]
for m in ms:
p = PQ(m, 256, seed=0).fit(DB); cd = p.encode(DB)
mse = ((DB - p.decode(cd))**2).sum(1).mean()
r = sum(GT1[qi] == int(p.adc_dist(q, cd).argmin()) for qi, q in enumerate(QS)) / len(QS)
print(f"m={m:2d} MSE={mse:6.2f} recall@1={r:.3f}")
横軸が $m$(= 圧縮後のバイト数、$k=256$ 固定)、左軸(赤)が再構成 MSE、右軸(緑)が recall@1 です。$m$ を増やすほど MSE は単調に下がり($m=1$ の27→$m=16$ で2.9 程度)、recall@1 は上がります($m=16$ で約0.46)。これは直感どおりで、符号を長くする(メモリを使う)ほど精度が上がるという王道のトレードオフです。$m=1$ は「ベクトル全体を1つの量子化器で256通りに丸める」極端なケースで、誤差が大きく recall もほぼ0。部分に割ること(直積構造)がいかに効くかが、$m=1$ と $m \ge 4$ の差に表れています。次に $k$ を振ります($m=8$ 固定)。
ks = [16, 32, 64, 128, 256]
for k in ks:
p = PQ(8, k, seed=0).fit(DB); cd = p.encode(DB)
mse = ((DB - p.decode(cd))**2).sum(1).mean()
print(f"k={k:3d} ({8*int(np.log2(k))}bit) MSE={mse:7.2f}")
横軸が $k$、縦軸が再構成 MSE で、各点に符号長(ビット)を添えています。$k$ を増やすほど MSE は下がります(115→12 程度)。$k=256$ がよく使われるのは、(1) 8ビット=1バイトにちょうど収まりメモリ配置が綺麗、(2) ADC テーブル作成 $O(mk)$ と SDC 表 $O(mk^2)$ が許容範囲に収まる、というバランスの良さからです。$k$ をさらに増やせば精度は上がりますが、テーブルが大きくなり、クエリごとのテーブル作成コストや距離表のメモリが増えます。
つまみの効きが分かったところで、残るのは「数十億本に対して、それでも全件にテーブルを引くのは多すぎる」という問題です。最後に、PQ を大規模化する仕組み IVFADC を見ます。
大規模化：IVFADC(転置ファイル + PQ)
ADC は距離計算を加算に落としましたが、それでも全 DB ベクトルに対してテーブルを引いて足す必要があります。10億本なら10億回の足し算で、まだ重い。そこで使うのが IVFADC(Inverted File with Asymmetric Distance Computation) です。アイデアは「そもそも全件を見ない」こと。
まず、DB ベクトル全体を比較的少数(例: 数千〜数万)の粗いセントロイドで k-means クラスタリングし、各ベクトルを最寄りのセル(クラスタ)に割り当てます。これを粗量子化(coarse quantizer)と呼びます。検索時には、クエリに近いセルだけを選び、その中のベクトルにだけ ADC を適用します。クエリから遠いセルは丸ごとスキップ。これにより、距離計算の対象が DB 全体から「近傍数セルの中身」だけに激減します。
2次元に投影した図です。色の異なる点群が、粗量子化で分けられたセル(クラスタ)で、黒い×が粗セントロイド。クエリ(赤い星)が来たら、最も近い数個のセル(赤丸)だけを選び、その中のベクトルにだけ PQ の ADC で距離を計算します。探索するセル数(nprobe)を増やすほど取りこぼしは減りますが、その分だけ遅くなる——ここにも精度と速度のトレードオフがあります。
実用上はもう一工夫あります。セル内では「ベクトルそのもの」ではなく「ベクトルとセル中心の残差 $r = x – c_{\text{coarse}}$」を PQ で符号化します。残差は分布の広がりが小さく、同じ $m, k$ でも量子化誤差を抑えられるからです。FAISS の IndexIVFPQ はまさにこの構成で、(1) 粗量子化で候補セルを絞り、(2) 残差を PQ 符号で持ち、(3) ADC で高速に距離を測り、(4) 上位候補を元ベクトルで re-rank する、という流れで数十億規模の検索を実現します。
ここまでを振り返ると、PQ は「圧縮(直積構造)」「高速距離(ADC テーブル)」「絞り込み(IVF)」という3つの工夫を組み合わせ、メモリと速度の壁を同時に崩していることが分かります。最後に要点を整理しましょう。
まとめ
本記事では、Product Quantization(積量子化)について、量子化器の定義から IVFADC までを、スクラッチ実装で動かしながら解説しました。
- ベクトル量子化は、ベクトルをコードブック中の最近傍セントロイドの番号で表す圧縮。番号は $\log_2 k$ ビットで済む(式1)。コードブックは k-means で学習する。
- 積量子化は、ベクトルを $m$ 部分に割り各部分を独立に量子化する(式3)。直積構造により、$k^m$ 通りの量子化点を $mk$ 個のセントロイドで表せる。これが高次元を少ないメモリで覆える鍵。$m=8, k=256$ で1ベクトルが8バイトに。
- 距離はテーブル引きの和に分解できる(式4)。SDC(対称、クエリも量子化、式5)と ADC(非対称、クエリは生のまま、式6〜9)があり、ADC のほうが誤差が片側だけで高精度。実測でも全 $R$ で ADC が SDC を上回った。
- m・k は精度とメモリのトレードオフを握るつまみ。大きくするほど誤差は減るが符号は長くなる。$k=256$(1バイト)が定番。
- IVFADC は粗量子化で候補セルを絞り、残差を PQ 符号で持ち、ADC で測る。これが FAISS の
IndexIVFPQの正体で、数十億規模の検索を可能にする。 - PQ は単独で完璧な最近傍を返すのではなく、高速に候補を絞り、元ベクトルで re-rank する前段として真価を発揮する(recall@100=0.975)。
近似最近傍探索には、PQ 以外にもグラフ探索(HNSW)やハッシュ(局所性鋭敏ハッシュ, LSH)といった系統があります。PQ が「ベクトルを圧縮してメモリに乗せ、距離を表引きで速くする」のに対し、HNSW は「探索のグラフ構造で速くする」、LSH は「衝突しやすいハッシュで候補を絞る」アプローチです。これらは排他的でなく、FAISS では PQ と HNSW を組み合わせる構成もあります。次のステップとして、以下の記事も参考にしてください。