部分空間におけるコサイン類似度は高次元空間のコサイン類似度を示唆するか？

考えてみてください：高次元空間における embedding ベクトルのコサイン類似度を測定する際、より低次元の部分空間での類似度は全体の類似度にどのように影響するのでしょうか？直接的な比例関係があるのでしょうか、それとも高次元データではより複雑な関係があるのでしょうか？

より具体的には、ベクトルの最初の 256 次元での高い類似度は、768 次元全体でも高い類似度を保証するのでしょうか？逆に、いくつかの次元で大きな違いがある場合、それは全体の類似度が低いことを意味するのでしょうか？これらは単なる理論的な考察ではなく、効率的なベクトル検索、データベースのインデックス作成、RAG システムのパフォーマンスにとって重要な検討事項です。

開発者は多くの場合、部分空間での高い類似度は全体の高い類似度を意味する、あるいは一つの次元での顕著な違いが全体の類似度に大きく影響するといったヒューリスティックに頼っています。問題は、これらのヒューリスティック手法が確固たる理論的根拠に基づいているのか、それとも単なる便宜的な仮定なのかということです。

この投稿では、これらの疑問について、部分空間の類似度と全体のベクトル類似度の関係について、理論と実践的な意味の両面から検討します。

tagコサイン類似度の境界

ベクトル $\mathbf{A}, \mathbf{B}\in \mathbb{R}^d$ について、$\mathbf{A}=[\mathbf{A}_1, \mathbf{A}_2]$ と $\mathbf{B}=[\mathbf{B}_1, \mathbf{B}_2]$ に分解します。ここで $\mathbf{A}_1,\mathbf{B}_1\in\mathbb{R}^m$ および $\mathbf{A}_2,\mathbf{B}_2\in\mathbb{R}^n$ であり、$m+n=d$ です。

部分空間 $\mathbb{R}^m$ でのコサイン類似度は $\cos(\mathbf{A}_1, \mathbf{B}_1)=\frac{\mathbf{A}_1\cdot\mathbf{B}_1}{\|\mathbf{A}_1\|\|\mathbf{B}_1\|}$ で与えられ、同様に部分空間 $\mathbb{R}^n$ での類似度は $\cos(\mathbf{A}_2, \mathbf{B}_2)=\frac{\mathbf{A}_2\cdot\mathbf{B}_2}{\|\mathbf{A}_2\|\|\mathbf{B}_2\|}$ となります。

元の空間 $\mathbb{R}^d$ でのコサイン類似度は以下のように定義されます：$$\begin{align*}\cos(\mathbf{A},\mathbf{B})&=\frac{\mathbf{A}\cdot\mathbf{B}}{\|\mathbf{A}\|\|\mathbf{B}\|}\\&=\frac{\mathbf{A}_1\cdot\mathbf{B}_1+\mathbf{A}_2\cdot\mathbf{B}_2}{\sqrt{\|\mathbf{A}_1\|^2+\|\mathbf{A}_2\|^2}\sqrt{\|\mathbf{B}_1\|^2+\|\mathbf{B}_2\|^2}}\\&=\frac{\cos(\mathbf{A}_1, \mathbf{B}_1)\|\mathbf{A}_1\|\|\mathbf{B}_1\|+\cos(\mathbf{A}_2, \mathbf{B}_2)\|\mathbf{A}_2\|\|\mathbf{B}_2\|}{\sqrt{\|\mathbf{A}_1\|^2+\|\mathbf{A}_2\|^2}\sqrt{\|\mathbf{B}_1\|^2+\|\mathbf{B}_2\|^2}}\end{align*}$$

ここで、$s := \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$ とすると、以下が成り立ちます：$$\begin{align*}\cos(\mathbf{A},\mathbf{B})&\leq\frac{s\|\mathbf{A}_1\|\|\mathbf{B}_1\|+s\|\mathbf{A}_2\|\|\mathbf{B}_2\|}{\sqrt{\|\mathbf{A}_1\|^2+\|\mathbf{A}_2\|^2}\sqrt{\|\mathbf{B}_1\|^2+\|\mathbf{B}_2\|^2}}\\&=\frac{\|\mathbf{A}_1\|\|\mathbf{B}_1\|+\|\mathbf{A}_2\|\|\mathbf{B}_2\|}{\sqrt{\|\mathbf{A}_1\|^2+\|\mathbf{A}_2\|^2}\sqrt{\|\mathbf{B}_1\|^2+\|\mathbf{B}_2\|^2}}\cdot s\\&=\cos(\underbrace{[\|\mathbf{A}_1\|, \|\mathbf{A}_2\|]}_{\mathbb{R}^2}, \underbrace{[\|\mathbf{B}_1\|, \|\mathbf{B}_2\|]}_{\mathbb{R}^2})\cdot s\\&\leq 1\cdot s \\&= \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))\end{align*}$$

証明終了。

証明の最後のステップでは、コサイン類似度が常に 1 以下であることを利用しています。これが上界を形成します。同様に、$\cos(\mathbf{A},\mathbf{B})$ の下界は以下のように示すことができます：

$$\cos(\mathbf{A},\mathbf{B}) \geq t \cdot \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$$、ここで $t:= \min(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$ です。

下界について、$\cos(\mathbf{A},\mathbf{B}) \geq t$ と性急に結論付けることはできないことに注意してください。これはコサイン関数の値域が $[-1, 1]$ の範囲にあるためです。この値域により、自明な値 -1 よりも厳密な下界を確立することは不可能です。

結論として、以下の緩い境界が得られます：$$-1\leq\cos(\mathbf{A},\mathbf{B})\leq\max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$$そしてより厳密な境界：$$\begin{align*} \gamma \cdot t\leq&\cos(\mathbf{A}, \mathbf{B}) \leq\gamma\cdot s\\\gamma \cdot \min(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2)) \leq &\cos(\mathbf{A}, \mathbf{B}) \leq \gamma \cdot \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))\end{align*}$$、ここで $\gamma = \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$ です。

tagJohnson-Lindenstrauss の補題との関連

JL 補題は、任意の $0 < \epsilon < 1$ と任意の有限点集合 $S$ in $\mathbb{R}^d$ に対して、写像 $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ が存在する（ここで $k = O(\epsilon^{-2} \log |S|)$）ことを主張します。このとき、全ての $\mathbf{u}, \mathbf{v} \in S$ に対して、ユークリッド距離はおおよそ保存されます：

$$(1 - \epsilon) \|\mathbf{u} - \mathbf{v}\|^2 \leq \|f(\mathbf{u}) - f(\mathbf{v})\|^2 \leq (1 + \epsilon) \|\mathbf{u} - \mathbf{v}\|^2$$

Johnson–Lindenstrauss lemma - Wikipedia

Wikimedia Foundation, Inc.Contributors to Wikimedia projects

$f$ を部分空間選択のように機能させるために、対角行列を射影に使用できます。例えば、$5 \times 3$ 行列 $f$ を使用する場合（ただしランダムではありません。なお、JL 補題の典型的な定式化では、ガウス分布からのランダム行列を利用する線形変換を含みます）。例えば、5 次元ベクトル空間から第 1、第 3、第 5 次元を保持したい場合、行列 $f$ は以下のように設計できます：$$f = \begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$
しかし、$f$ を対角行列に指定することで、射影に使用できる関数のクラスが制限されます。JL 補題は、より広いクラスの線形変換の中に適切な $f$ が存在することを保証しますが、$f$ を対角行列に制限すると、JL 補題の境界を適用するための適切な $f$ がこの制限されたクラス内に存在しない可能性があります。

tag境界の検証

高次元ベクトル空間におけるコサイン類似度の理論的境界を実証的に探るため、モンテカルロ シミュレーションを使用できます。この方法により、多数のランダムなベクトルペアを生成し、元の空間と部分空間の両方で類似度を計算し、理論上の上界と下界が実際にどの程度成り立つかを評価することができます。

以下の Python コードスニペットはこの概念を実装しています。高次元空間でランダムなベクトルのペアを生成し、そのコサイン類似度を計算します。次に、各ベクトルを 2 つの部分空間に分割し、各部分空間内でのコサイン類似度を計算し、部分空間の類似度に基づいて全次元のコサイン類似度の上界と下界を評価します。

import numpy as np


def compute_cosine_similarity(U, V):
    # Normalize the rows to unit vectors
    U_norm = U / np.linalg.norm(U, axis=1, keepdims=True)
    V_norm = V / np.linalg.norm(V, axis=1, keepdims=True)
    # Compute pairwise cosine similarity
    return np.sum(U_norm * V_norm, axis=1)


# Generate random data
num_points = 5000
d = 1024
A = np.random.random([num_points, d])
B = np.random.random([num_points, d])

# Compute cosine similarity between A and B
cos_sim = compute_cosine_similarity(A, B)

# randomly divide A and B into subspaces
m = np.random.randint(1, d)
A1 = A[:, :m]
A2 = A[:, m:]
B1 = B[:, :m]
B2 = B[:, m:]

# Compute cosine similarity in subspaces
cos_sim1 = compute_cosine_similarity(A1, B1)
cos_sim2 = compute_cosine_similarity(A2, B2)

# Find the element-wise maximum and minimum of cos_sim1 and cos_sim2
s = np.maximum(cos_sim1, cos_sim2)
t = np.minimum(cos_sim1, cos_sim2)

norm_A1 = np.linalg.norm(A1, axis=1)
norm_A2 = np.linalg.norm(A2, axis=1)
norm_B1 = np.linalg.norm(B1, axis=1)
norm_B2 = np.linalg.norm(B2, axis=1)

# Form new vectors in R^2 from the norms
norm_A_vectors = np.stack((norm_A1, norm_A2), axis=1)
norm_B_vectors = np.stack((norm_B1, norm_B2), axis=1)

# Compute cosine similarity in R^2
gamma = compute_cosine_similarity(norm_A_vectors, norm_B_vectors)

# print some info and validate the lower bound and upper bound
print('d: %d\n'
      'm: %d\n'
      'n: %d\n'
      'avg. cosine(A,B): %f\n'
      'avg. upper bound: %f\n'
      'avg. lower bound: %f\n'
      'lower bound satisfied: %s\n'
      'upper bound satisfied: %s' % (
          d, m, (d - m), np.mean(cos_sim), np.mean(s), np.mean(gamma * t), np.all(s >= cos_sim),
          np.all(gamma * t <= cos_sim)))
コピー

d: 1024
m: 743
n: 281
avg. cosine(A,B): 0.750096
avg. upper bound: 0.759080
avg. lower bound: 0.741200
lower bound satisfied: True
upper bound satisfied: True

tag境界の理解

要するに、高次元ベクトルを比較する際、全体の類似度は部分空間の最良と最悪の類似度の間に位置し、それらの部分空間が全体の中でどれだけ大きいか、または重要かによって調整されます。これが高次元におけるコサイン類似度の境界が直感的に表現するものです：最も類似した部分と最も類似していない部分のバランスを、それらの相対的なサイズや重要性で重み付けしたものです。

複数のパーツからなる2つのオブジェクト（例えば、2本の高級ペン）の全体的な類似度を比較しようとしているとイメージしてください。各ペンには2つの主要な構成要素があります：本体とキャップ。ペン全体（本体とキャップの両方）の類似度が、私たちが決定しようとしているものです：

tag上限 ($\gamma \cdot s$)

$s$ をペンの対応するパーツ間の最良のマッチとして考えてください。キャップは非常に似ているが本体は似ていない場合、$s$ はキャップの類似度となります。

$\gamma$ は各パーツのサイズ（または重要性）に基づくスケーリング係数のようなものです。一方のペンが長い本体と短いキャップを持ち、もう一方が短い本体と長いキャップを持つ場合、$\gamma$ はこれらの比率の違いを考慮して全体の類似度を調整します。

上限は、一部のパーツがどれだけ似ていても、全体の類似度はこの「最良のパーツの類似度」に比率係数を掛けた値を超えることができないことを示しています。

tag下限 ($\gamma \cdot t$)

ここで、$t$ は最も一致しないパーツの類似度です。ペンの本体が全く異なるがキャップは似ている場合、$t$ は本体の類似度を反映します。

同様に、$\gamma$ は各パーツの比率に基づいてこれをスケーリングします。

下限は、全体の類似度が各パーツの比率を考慮した後の「最悪のパーツの類似度」よりも悪くなることはできないことを意味します。

tag境界の意味

エンベディング、ベクター検索、検索、またはデータベースを扱うソフトウェアエンジニアにとって、これらの境界を理解することには実践的な意味があります。特に高次元データを扱う際に重要です。ベクター検索では、通常、コサイン類似度を近さの尺度として使用し、与えられたクエリベクトルに最も近い（最も類似した）ベクトルをデータベースから見つけることが多くあります。私たちが議論した境界は、そのようなタスクに部分空間の類似度を使用する際の有効性と限界について洞察を提供できます。

tagランキングのための部分空間類似度の使用

安全性と正確性：トップkの結果のランキングと検索に部分空間類似度を使用することは効果的ですが、注意が必要です。上限は、全体の類似度が部分空間の最大類似度を超えることができないことを示しています。したがって、ベクトルのペアが特定の部分空間で高い類似度を持つ場合、高次元空間でも類似している可能性が高いことを示します。

潜在的な落とし穴：しかし、下限は、1つの部分空間で低い類似度を持つ2つのベクトルが、全体としてはかなり類似している可能性があることを示唆しています。したがって、部分空間の類似度だけに依存すると、関連する結果を見逃す可能性があります。

tag誤解と注意点

部分空間の重要性の過大評価：よくある誤解は、特定の部分空間の重要性を過大評価することです。一つの部分空間での高い類似度は良い指標ですが、他の部分空間の影響により、必ずしも全体の高い類似度を保証するものではありません。

負の類似度の無視：部分空間でのコサイン類似度が負の場合、その次元での対立的な関係を示します。エンジニアはこれらの負の類似度が全体の類似度にどのように影響するかに注意を払う必要があります。