부분 공간의 코사인 유사도가 고차원 코사인 유사도를 의미하는가?

다음과 같이 생각해 보세요: 고차원 공간에서 임베딩 벡터의 코사인 유사도를 측정할 때, 더 낮은 차원의 부분 공간에서의 유사도는 전체 유사도를 어떻게 암시할까요? 직접적이고 비례적인 관계가 있을까요, 아니면 고차원 데이터에서는 더 복잡한 현실이 있을까요?

더 구체적으로, 벡터의 처음 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$과 $\mathbb{R}^d$에서의 임의의 유한한 점들의 집합 $S$에 대해, 다음과 같이 모든 $\mathbf{u}, \mathbf{v} \in S$에 대해 유클리드 거리가 근사적으로 보존되는 매핑 $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ ($k = O(\epsilon^{-2} \log |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 코드는 이 개념을 구현합니다. 고차원 공간에서 무작위로 벡터 쌍을 생성하고 그들의 코사인 유사도를 계산합니다. 그런 다음 각 벡터를 두 개의 부분 공간으로 나누고, 각 부분 공간 내에서의 코사인 유사도를 계산하며, 부분 공간 유사도를 기반으로 전체 차원 코사인 유사도의 상한과 하한을 평가합니다.

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)))
Copy

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경계 이해하기

간단히 말해서, 고차원 벡터를 비교할 때 전체 유사도는 하위 공간의 최고 및 최저 유사도 사이에 있으며, 이는 전체 구조에서 해당 하위 공간이 얼마나 크거나 중요한지에 따라 조정됩니다. 이것이 고차원에서의 코사인 유사도 경계가 직관적으로 나타내는 것입니다: 가장 유사한 부분과 가장 덜 유사한 부분 사이의 균형이 상대적 크기나 중요도에 따라 가중치가 부여됩니다.

다중 부품 객체(예를 들어, 두 개의 고급 펜)를 전체적인 유사도를 기준으로 비교하려 한다고 상상해보세요. 각 펜은 몸체와 캡이라는 두 가지 주요 구성 요소를 가지고 있습니다. 우리가 결정하려는 것은 펜 전체(몸체와 캡 모두)의 유사도입니다:

tag상한 ($\gamma \cdot s$)

$s$를 펜의 대응하는 부분들 간의 가장 좋은 매칭이라고 생각하세요. 캡은 매우 유사하지만 몸체는 그렇지 않다면, $s$는 캡의 유사도입니다.

$\gamma$는 각 부분의 크기(또는 중요도)에 기반한 스케일링 팩터와 같습니다. 한 펜이 매우 긴 몸체와 짧은 캡을 가지고 있고, 다른 펜이 짧은 몸체와 긴 캡을 가지고 있다면, $\gamma$는 이러한 비율의 차이를 고려하여 전체 유사도를 조정합니다.

상한은 일부 부분이 얼마나 유사하든지 상관없이 전체 유사도가 이 "최상의 부분 유사도"에 비례 팩터를 곱한 값을 초과할 수 없다는 것을 알려줍니다.

tag하한 ($\gamma \cdot t$)

여기서 $t$는 가장 매칭이 안 되는 부분들의 유사도입니다. 펜의 몸체가 매우 다르지만 캡은 유사하다면, $t$는 몸체의 유사도를 반영합니다.

마찬가지로, $\gamma$는 각 부분의 비율에 따라 이를 조정합니다.

하한은 전체 유사도가 각 부분의 비율을 고려한 후 이 "최악의 부분 유사도"보다 나쁠 수 없다는 것을 의미합니다.

tag경계의 의미

임베딩, 벡터 검색, 검색 또는 데이터베이스 작업을 하는 소프트웨어 엔지니어에게 이러한 경계를 이해하는 것은 특히 고차원 데이터를 다룰 때 실용적인 의미가 있습니다. 벡터 검색은 종종 데이터베이스에서 주어진 쿼리 벡터와 가장 가까운(가장 유사한) 벡터를 찾는 것을 포함하며, 일반적으로 코사인 유사도를 근접도의 측정 기준으로 사용합니다. 우리가 논의한 경계는 이러한 작업에서 하위 공간 유사도 사용의 효과와 한계에 대한 통찰력을 제공할 수 있습니다.

tag순위 결정을 위한 하위 공간 유사도 사용

안전성과 정확성: 상위 k개 결과의 순위 결정과 검색을 위해 하위 공간 유사도를 사용하는 것은 효과적일 수 있지만, 주의가 필요합니다. 상한은 전체 유사도가 하위 공간의 최대 유사도를 초과할 수 없음을 나타냅니다. 따라서 한 쌍의 벡터가 특정 하위 공간에서 매우 유사하다면, 고차원 공간에서도 유사할 가능성이 높은 후보가 됩니다.

잠재적 위험: 하지만 하한은 한 하위 공간에서 낮은 유사도를 보이는 두 벡터도 전체적으로는 꽤 유사할 수 있다는 것을 시사합니다. 따라서 하위 공간 유사도에만 의존하면 일부 관련 결과를 놓칠 수 있습니다.

tag오해와 주의사항

하위 공간 중요도의 과대 평가: 흔한 오해는 특정 하위 공간의 중요도를 과대 평가하는 것입니다. 한 하위 공간에서의 높은 유사도는 좋은 지표이지만, 다른 하위 공간의 영향으로 인해 전체적인 높은 유사도를 보장하지는 않습니다.

음의 유사도 무시: 하위 공간에서 코사인 유사도가 음수인 경우, 이는 해당 차원에서 반대되는 관계를 나타냅니다. 엔지니어는 이러한 음의 유사도가 전체 유사도에 미치는 영향에 주의해야 합니다.