直積量子化とは｜1件512バイトを4バイトにしたら、再現率は8.8%だった

1件512バイトを4バイトにしたら、再現率は8.8%だった

区画の数を変えて実際に測りました。4区画で1件4バイト・再現率8.8%、16区画で16バイト・31.3%です。

直積量子化がどこまで容量を削れるのかを、実装して測りました。用意したのは64次元のベクトル20,000件です。

区画ごとの代表点づくりも検索も本当に実行しています。並べ直しは入れていないので、再現率は候補をそのまま結果にした場合の数字です。

function searchPQ(ix, q) {
  // 区画ごとに、問い合わせと各代表点の距離をあらかじめ表にしておく
  const table = [];
  for (let p = 0; p < ix.m; p++) {
    const row = new Float64Array(ix.kc);
    for (let c = 0; c < ix.kc; c++) {
      let s = 0;
      for (let d = 0; d < ix.sub; d++) { const t = q[p * ix.sub + d] - ix.books[p][c][d]; s += t * t; }
      row[c] = s;
    }
    table.push(row);
  }
  // 各件は、区画ごとの番号を引いて足すだけ
  const cand = [];
  for (let i = 0; i < N; i++) {
    let s = 0;
    for (let p = 0; p < ix.m; p++) s += table[p][ix.codes[i][p]];
    cand.push({ i, d: s });
  }
  return topK(cand, K);
}

登録 20,000件（64次元）・上位10件・問い合わせ 200回
元の大きさ 1件あたり 512 バイト

区画数  1区画の次元  代表点の数  1件の大きさ  全体   再現率   元に対する比  1回あたり
   4区画       16次元        256個          4B  0.08 MB     8.8%          0.8%       3952 μs
   8区画        8次元        256個          8B  0.15 MB    16.5%          1.6%       3982 μs
  16区画        4次元        256個         16B  0.31 MB    31.3%          3.1%       4199 μs

参考: 元のまま持つと全体で 9.8 MB、全探索は1回 5245 マイクロ秒

容量の削り方が桁違いです。9.8MBが0.08MB。ただし再現率は8.8%で、正解の10件のうち1件も取れていない問い合わせが多数あります。

なぜここまで小さくなるのか

各区画を代表点の番号だけで持つためです。16次元ぶんの値が、1バイトの番号1つに置き換わります。

16次元は元の形式で128バイトです。それが1バイトになるので、128分の1になります。4区画で1件4バイトという数字は、そこから出ています。

区画を増やすと戻る

区画を増やすと、1区画あたりの次元が減って粗さがやわらぎます。4区画8.8%、8区画16.5%、16区画31.3%と上がっていきます。

ただし容量も比例します。16区画では1件16バイト、元の3.1%です。削りたい量と、許せる粗さの両方から決めることになります。

この規模では速くならない

所要時間を見てください。全探索の5245マイクロ秒に対して3952マイクロ秒で、1.3倍程度にとどまります。

距離の表を先に作る工夫で1件あたりの計算は軽くなりますが、全件を見る点は変わりません。この手法の効き目は速さではなく容量にあります。

直積量子化とはどういう仕組みなのか

次元を区画に分け、区画ごとに代表点の一覧を作り、各ベクトルを代表点の番号の並びとして持ちます。

直積量子化は、ベクトルの次元をいくつかの区画に分け、区画ごとに代表点の番号だけを持つ手法です。

作るときの手順

1. 次元を区画に分ける。64次元を4区画なら、16次元ずつ
2. 区画ごとに代表点を作る。登録データから256個ずつ
3. 各ベクトルを番号に置き換える。区画ごとに最も近い代表点の番号
4. 元の値を捨てる。並べ直せなくなる

4番目は避けてください。元の値がなければ、後で正確に並べ直せません。

引くときの工夫

検索では、問い合わせと各代表点の距離を先に表にしておきます。4区画で256個なら、1,024回の計算で表ができます。

あとは各件について、区画ごとの番号で表を引いて足すだけです。1件あたり4回の足し算で距離が出ます。

他の削り方との違い

各次元を粗く丸める方法もあります。そちらはバイナリ量子化の記事で扱っており、8ビットで容量12.5%・再現率94.8%でした。

pgvectorでは、表そのものの型を精度の低いものに変える手も案内されています。削り方はいくつもあり、削れる量と落ちる精度が違います。

この再現率で何に使うのか

候補を粗く絞る段に使います。最終の順位は、残った候補を元の値で計算し直して決めます。

直積量子化の再現率8.8%という数字を見て、使えないと結論するのは早計です。この手法は、最終結果を出すためのものではありません。

2段構えの前段

使い方は2段になります。小さくした値で候補を数百件まで粗く絞り、その候補だけを元の値で計算し直して並べます。

pgvectorでも、並べ直しと組み合わせることで、規模が大きくても索引を記憶上に保つ使い方が案内されています。前段は速さと容量、後段は正確さを担います。

上位10件で測ると低く見える

前の節の8.8%は、上位10件だけを見た数字です。候補生成として使うなら、見るのは上位数百件になります。

その範囲に正解が入っていれば、並べ直しで拾えます。測るべき指標が、用途によって変わるということです。

そもそも要るかどうか

前提として、この手法が要るのは容量が問題になってからです。20,000件で9.8MBなら、削る必要はありません。

件数が増えて記憶上に載らなくなったときに、初めて選択肢に入ります。載っているうちは、精度を落とす理由がありません。