Означает ли косинусное сходство в подпространстве высокую косинусную схожесть в многомерном пространстве?

Подумайте об этом: при измерении косинусного сходства векторов эмбеддингов в пространствах высокой размерности, как их сходство в подпространствах меньшей размерности влияет на общее сходство? Существует ли прямая пропорциональная зависимость, или реальность с данными высокой размерности более сложна?

Если конкретнее, гарантирует ли высокое сходство между векторами в их первых 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Связь с леммой Джонсона–Линденштрауса

Лемма 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 включает линейные преобразования, которые часто используют случайные матрицы, взятые из гауссова распределения). Например, если мы хотим сохранить 1-е, 3-е и 5-е измерения из 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$ диагональной матрицей, такая подходящая $f$ может не существовать в этом ограниченном классе для применения границ леммы JL.

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)))
Копировать

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Заблуждения и предостережения

Переоценка важности подпространства: Распространенным заблуждением является переоценка важности определенного подпространства. Хотя высокое сходство в одном подпространстве является хорошим индикатором, оно не гарантирует высокого общего сходства из-за влияния других подпространств.

Игнорирование отрицательных сходств: В случаях, когда косинусное сходство в подпространстве отрицательное, это указывает на противоположные отношения в этом измерении. Программисты должны быть осторожны с тем, как эти отрицательные сходства влияют на общее сходство.