[翻訳] 量子化ベクトル検索におけるランダム回転の利点

本記事は OpenSearch Project Blog に投稿された以下の記事を日本語に翻訳したものです。

https://opensearch.org/blog/the-benefits-of-random-rotation-in-quantized-vector-search/

RAG (Retrieval-Augmented Generation) パイプラインで使用されるような最新のベクトル検索システムは、豊富で多様な構造と特性を持つ幅広いデータセットを処理する必要があります。新しいデータセットに対して検索アルゴリズムがどのように動作するかを予測することは、しばしば困難です。パフォーマンスの予測可能性を高める方法の 1 つは、データを標準化する変換を行い、パイプラインの後段にある近似最近傍 (ANN) アルゴリズムにより適した形にすることです。

OpenSearch 3.2 では、データを標準化する変換としてランダム回転（random rotation）が導入されました。これは特にバイナリ量子化のコンテキストで有用です。ランダム回転は、すべてのデータベクトルとクエリベクトルをランダムな方向に回転させるだけです。以下の図に 2 次元の楕円形データセットの例を示します。ランダム回転 (ランダムに選ばれた 130.6 度) の前後の状態を示しています。

ランダム回転の利点

ランダム回転はデータをどのように変化させるのでしょうか。まず、変化しないものから説明します。すべての回転は等長変換 (isometry) であり、データ内のすべてのユークリッド距離とコサイン類似度を完全に保存します。したがって、厳密検索を使用する場合、ランダム回転を含むあらゆる回転の前後で、まったく同じ結果が得られます。言い換えれば、ユークリッド距離またはコサイン類似度による厳密検索は回転不変です。

しかし実際には、大規模データに対して厳密検索を使用することはほとんどなく、より効率的な近似手法を選択します。これらの手法の多くは回転不変ではありません。バイナリ量子化 (BQ) は各ベクトルをその座標の符号ベクトルで表現し、プロダクト量子化 (PQ) は次元を連続する座標ブロックに分割して各ブロックを量子化します。これらの操作は、データが整列している特定の座標系に大きく依存します。データを回転させると、同じ検索パラメータと量子化パラメータを使用しても、異なる再現率を持つまったく異なる量子化結果が得られる可能性があります。

以下の図に 4 つのクラスタを持つデータセットの例を示します。左側では、クラスタが x 軸と y 軸に強く整列しているため、各クラスタが 2 つの BQ 領域に分割されています。これは精度に悪影響を与えます。点 x は点 z よりも点 y にはるかに近いにもかかわらず、BQ は点 x と z に同じコード [1,1] を割り当て、点 y には異なるコード [1,0] を割り当てます。これにより、量子化後は x と z が同一に見え、y は両方から等距離に見えます。右側では、回転後、各クラスタが単一の BQ 領域に完全に収まっています。これで x と y は同じコードを取得し、z は異なるコードを取得します。このように、回転は等長変換であるにもかかわらず、BQ と組み合わせると精度に大きな影響を与える可能性があります。

これにより、データを回転させることを検討する動機が生まれます。1 つの選択肢は、最適化問題を解くことでデータに最適な回転を見つけることです。反復量子化 (ITQ) や最適化プロダクト量子化 (OPQ) など、Faiss で利用可能な手法がこの目的のために設計されています。これらの欠点は、最適化による最適な回転の探索が計算集約的になる可能性があること、そして一度見つかった回転が未知のデータ、分布シフト、または異なるデータとクエリの分布にうまく適応しない可能性があることです。

ランダム回転はより控えめな目的を持っています。軸との偽の相関を完全に除去し、データを量子化境界から切り離すことです。最適な回転を見つけようとするのではなく、最悪の回転を避けることだけを目指します。ランダム回転は最適化や学習を必要とせず、サンプリングするだけで済みます。また、データに依存しないため、未知のデータや分布シフトに関する懸念がありません。学習された回転とは異なり、データへの影響はデータセット内の特定の点だけでなく、任意の点に対して成り立ちます。

重要なのは、回転がランダムであることは、データへの影響が完全に予測不可能であることを意味しないということです。むしろ逆で、強い確率的集中により、ランダム回転は任意の点をすべての軸から遠ざける可能性が圧倒的に高くなります。直感的には、$R^d$ の単位球には $d$ 個の軸がありますが、指数関数的な体積 $\exp(d)$ を持つためです。したがって、回転後に点が軸の近くに落ちる確率は $d/\exp(d)$ のように振る舞い、$d$ が大きくなるにつれて急速に 0 に近づきます。その結果、ランダム回転はデータを「標準化」するものと見なすことができます。ほぼすべての点が軸から遠く離れている可能性が非常に高くなり、真の距離と角度を変えることなく、BQ のような量子化アルゴリズムのパフォーマンスをより予測可能にします。

数学的には、ランダム回転は BQ と特に相性が良く、以下のように作用します。ランダム回転後、すべての点のペア $x,y \in R^d$ 間の期待ハミング距離は $\frac{d}{\pi} \cdot \theta(x,y)$ に等しくなります。ここで $\theta(x,y)$ は $x,y$ 間の角度です。これは古典的な SimHash アルゴリズムの分析と期待値の線形性から導かれます。したがって、ランダム回転後、2 点の BQ コード間の期待ハミング距離は、元々量子化境界に対してどのように配置されていたかに関係なく、それらの角度距離に直接関連します。

軸との有害な相関の別の例を見てみましょう。2 次元で x 軸と強く相関したデータセットをシミュレートするために、独立した座標を持つ 2D ガウス分布から 10,000 点をサンプリングします。x 座標は N(0,1) から、y 座標は N(0,0.1) からサンプリングします。これは本記事の冒頭ですでに示した楕円形データセットです。以下の図では、最近傍と異なる BQ コードになった点をオレンジ色で強調表示しています。これは望ましくないケースです。回転後、x 軸との相関が除去されたため、このようなケースの数は 123 から 55 に減少しました。55% の減少です。

これは高次元でも発生します。これを確認するために、今度は 100 次元で独立した平均 0 のガウス分布に従う座標を持つデータセットを再度サンプリングします。最初の座標の分散は 1 で、他のすべての座標の分散は 0.1 です。各点 x について、点を x からの BQ コードのハミング距離でソートしたときの真の最近傍の順位を調べます。これは真の最近傍を見つけるためにスキャンする必要がある量子化候補の数であり、順位が低いほど良いです。以下の表に、ランダム回転の前後のすべての点に対する分位数を示します。ランダム回転後、順位が顕著に小さくなっていることがわかります。スキャンする必要がある候補の中央値は 12% 減少し、0.9 分位数 (つまり最も困難なクエリ) では 26% 減少しています。

分位数	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
回転前の NN 順位	10	30	63	110	186	302	495	956	1795
回転後の NN 順位	9	25	55	97	164	265	421	678	1325

ランダム回転のコスト

ランダム回転にはいくつかの計算コストが発生します。ランダム回転のサンプリングは $O(d^3)$ の時間で行うことができます。実装例については付録を参照してください。これはインデックス作成フェーズで一度だけ行う必要があり、最新の大規模ベクトル検索シナリオで使用される次元では通常許容範囲内です。最近の科学文献には、(近似) 回転行列のより高速な近似サンプリングのためのいくつかの方法が含まれており、これがボトルネックになる場合にこの実行時間を軽減できます。

さらに、すべてのデータポイントとすべてのクエリを回転行列で乗算する必要があり、インデックス作成時とクエリ時に一定の追加計算コストが発生します。また、ベクトルデータベースが回転に関して一貫性を保つための整合性管理も必要ですが、OpenSearch がこれを処理します。ランダム回転の利点とオーバーヘッドのトレードオフは、特定のデータセットに依存する決定です。精度が期待よりも低い場合は試してみてください。

OpenSearch でのランダム回転の使用

OpenSearch インデックスでランダム回転を有効にするには、インデックス作成時にインデックスマッピングで random_rotation オプションを true に設定します。詳細な手順については、ADC と RR による検索品質の向上を参照してください。

まとめ

ランダム回転は、ANN 検索アルゴリズムに入力する前にデータをより標準的にするための有用なツールです。考慮すべき計算コストがありますが、精度低下につながる軸との偽の相関を除去できます。BQ を使用した ANN パイプラインが期待されるパフォーマンスを達成できない場合は、ランダム回転を試してみてください。非常に少ないオーバーヘッドで精度が大幅に向上する可能性があります。

付録: ランダム回転のサンプリング方法

この付録では、ランダム回転の実装に関する技術的な詳細について詳しく説明します。技術的には、$d$ 次元でのランダム回転とは、$d \times d$ 直交行列の群（一般に $O(d)$ と表記）から一様ランダムな行列 $\Pi$ をサンプリングし、すべてのベクトルに $\Pi$ を乗算することを意味します。「ランダム回転」という用語を口語的に使用していますが、$O(d)$ には純粋な回転だけでなく反射も含まれることに注意してください。反射も等長変換であるため、私たちのアプリケーションでは反射を含めるかどうかは問題になりません。したがって、元のデータセット $x_1,x_2,x_3,\ldots \in R^d$ は $\Pi x_1,\Pi x_2,\Pi x_3,\ldots \in R^d$ に置き換えられ、同様に、すべてのクエリベクトル $q \in R^d$ は $\Pi q \in R^d$ に置き換えられます。

直交行列上の一様分布は Haar 測度として知られています。これからサンプリングするアルゴリズム的な方法がいくつかあります。OpenSearch は、独立同分布の正規エントリを持つランダムな $d \times d$ 行列 $G$ をサンプリングし、グラム・シュミット法を使用してその行を正規直交化します。NumPy で実装しやすい別の方法は、QR 分解 $G=QR$ を計算し、$S$ を $R$ の主対角線の符号の対角行列とすることです。行列 $\Pi=QS$ は Haar 測度からサンプリングされたランダム回転です。以下の Python 関数は、この QR 分解アプローチを実装しています。

import numpy as np

def sample_random_rotation(dimension):
    M = np.random.standard_normal((dimension, dimension))
    Q, R = np.linalg.qr(M)
    return Q * np.sign(np.diag(R))