子空间余弦相似度是否意味着高维空间的余弦相似度？

考虑这样一个问题：在高维空间中测量嵌入向量的余弦相似度时，它们在低维子空间的相似度如何影响整体相似度？这是一种直接的、成比例的关系，还是在高维数据中存在更复杂的关系？

更具体地说，向量在其前 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\|])$。

tag与 Johnson–Lindenstrauss 引理的联系

JL 引理指出，对于任何 $0 < \epsilon < 1$ 和任何有限点集 $S$ 在 $\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 代码片段实现了这一概念。它随机生成高维空间中的向量对并计算它们的余弦相似度。然后，将每个向量分为两个子空间，计算每个子空间内的余弦相似度，并基于子空间相似度评估全维度余弦相似度的上界和下界。

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使用子空间相似度进行排序

安全性和准确性：使用子空间相似度进行排序和检索 top-k 结果可以是有效的，但需要谨慎。上界表明整体相似度不能超过子空间的最大相似度。因此，如果一对向量在特定子空间中高度相似，它很可能在高维空间中也是相似的。

潜在陷阱：然而，下界表明在一个子空间中相似度较低的两个向量整体上仍可能相当相似。因此，仅仅依赖子空间相似度可能会遗漏一些相关结果。

tag误解和注意事项

过高估计子空间重要性：一个常见的误解是过高估计某个特定子空间的重要性。虽然在一个子空间中的高相似度是个好的指标，但由于其他子空间的影响，这并不能保证整体相似度也很高。

忽视负相似度：在子空间中余弦相似度为负的情况下，表示在该维度上存在对立关系。工程师应该注意这些负相似度如何影响整体相似度。