¿La similitud del coseno en subespacios implica similitud del coseno en altas dimensiones?

Considera esto: al medir la similitud del coseno de vectores de embeddings en espacios de alta dimensionalidad, ¿cómo implica su similitud en subespacios de menor dimensión la similitud general? ¿Existe una relación directa y proporcional, o la realidad es más compleja con datos de alta dimensionalidad?

Más concretamente, ¿una alta similitud entre vectores en sus primeras 256 dimensiones asegura una alta similitud en sus 768 dimensiones completas? Por el contrario, si los vectores difieren significativamente en algunas dimensiones, ¿esto significa una baja similitud general? Estas no son meras reflexiones teóricas; son consideraciones cruciales para la recuperación eficiente de vectores, la indexación de bases de datos y el rendimiento de los sistemas RAG.

Los desarrolladores a menudo confían en heurísticas, asumiendo que una alta similitud en el subespacio equivale a una alta similitud general o que diferencias notables en una dimensión afectan significativamente la similitud general. La pregunta es: ¿estos métodos heurísticos están construidos sobre una base teórica sólida, o son simplemente suposiciones por conveniencia?

Este post profundiza en estas preguntas, examinando la teoría y las implicaciones prácticas de la similitud en subespacios en relación con la similitud general de vectores.

tagAcotando la Similitud del Coseno

Dados los vectores $\mathbf{A}, \mathbf{B}\in \mathbb{R}^d$, los descomponemos como $\mathbf{A}=[\mathbf{A}_1, \mathbf{A}_2]$ y $\mathbf{B}=[\mathbf{B}_1, \mathbf{B}_2]$, donde $\mathbf{A}_1,\mathbf{B}_1\in\mathbb{R}^m$ y $\mathbf{A}_2,\mathbf{B}_2\in\mathbb{R}^n$, con $m+n=d$.

La similitud del coseno en el subespacio $\mathbb{R}^m$ está dada por $\cos(\mathbf{A}_1, \mathbf{B}_1)=\frac{\mathbf{A}_1\cdot\mathbf{B}_1}{\|\mathbf{A}_1\|\|\mathbf{B}_1\|}$; similarmente, la similitud en el subespacio $\mathbb{R}^n$ es $\cos(\mathbf{A}_2, \mathbf{B}_2)=\frac{\mathbf{A}_2\cdot\mathbf{B}_2}{\|\mathbf{A}_2\|\|\mathbf{B}_2\|}$.

En el espacio original $\mathbb{R}^d$, la similitud del coseno se define como:$$\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*}$$

Ahora, sea $s := \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$. Entonces, tenemos:$$\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*}$$

Fin de la demostración.

Nótese que en el paso final de la demostración, aprovechamos que la similitud del coseno siempre es menor o igual a 1. Esto forma nuestro límite superior. De manera similar, podemos mostrar que el límite inferior de $\cos(\mathbf{A},\mathbf{B})$ está dado por:

$$\cos(\mathbf{A},\mathbf{B}) \geq t \cdot \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$$, donde $t:= \min(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$.

Nótese que para el límite inferior, no podemos concluir apresuradamente que $\cos(\mathbf{A},\mathbf{B}) \geq t$. Esto se debe al rango de la función coseno, que abarca entre $[-1, 1]$. Debido a este rango, es imposible establecer un límite inferior más ajustado que el valor trivial de -1.

Así que en conclusión, tenemos la siguiente cota amplia: $$-1\leq\cos(\mathbf{A},\mathbf{B})\leq\max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2)).$$ y una cota más ajustada $$\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*}$$, donde $\gamma = \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$.

tagConexión con el Lema de Johnson–Lindenstrauss

El lema JL afirma que para cualquier $0 < \epsilon < 1$ y cualquier conjunto finito de puntos $S$ en $\mathbb{R}^d$, existe un mapeo $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ (con $k = O(\epsilon^{-2} \log |S|)$) tal que para todos $\mathbf{u}, \mathbf{v} \in S$, las distancias euclidianas se preservan aproximadamente:

$$(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

Para hacer que $f$ funcione como una selección de subespacio, podemos usar una matriz diagonal para la proyección, como una matriz $5 \times 3$ $f$, aunque no aleatoria (nota, la formulación típica del lema JL involucra transformaciones lineales que a menudo utilizan matrices aleatorias extraídas de una distribución gaussiana). Por ejemplo, si queremos retener la 1ª, 3ª y 5ª dimensiones de un espacio vectorial de 5 dimensiones, la matriz $f$ podría diseñarse de la siguiente manera: $$f = \begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$
Sin embargo, al especificar que $f$ sea diagonal, limitamos la clase de funciones que pueden usarse para la proyección. El lema JL garantiza la existencia de una $f$ adecuada dentro de la clase más amplia de transformaciones lineales, pero cuando restringimos $f$ a ser diagonal, puede que no exista tal $f$ adecuada dentro de esta clase restringida para aplicar las cotas del lema JL.

tagValidando las Cotas

Para explorar empíricamente las cotas teóricas de la similitud del coseno en espacios vectoriales de alta dimensionalidad, podemos emplear una simulación de Monte Carlo. Este método nos permite generar un gran número de pares de vectores aleatorios, calcular sus similitudes tanto en el espacio original como en los subespacios, y luego evaluar qué tan bien se mantienen en la práctica los límites teóricos superior e inferior.

El siguiente fragmento de código Python implementa este concepto. Genera aleatoriamente pares de vectores en un espacio de alta dimensionalidad y calcula su similitud del coseno. Luego, divide cada vector en dos subespacios, calcula la similitud del coseno dentro de cada subespacio y evalúa los límites superior e inferior de la similitud del coseno en dimensión completa basándose en las similitudes de los subespacios.

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

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

tagEntendiendo los Límites

En resumen, al comparar dos vectores de alta dimensionalidad, la similitud general se encuentra entre las mejores y peores similitudes de sus subespacios, ajustadas según qué tan grandes o importantes son esos subespacios en el esquema general. Esto es lo que los límites para la similitud del coseno en dimensiones superiores representan intuitivamente: el equilibrio entre las partes más y menos similares, ponderadas por sus tamaños o importancia relativa.

Imagina que estás tratando de comparar dos objetos de múltiples partes (digamos, dos bolígrafos elegantes) basándote en su similitud general. Cada bolígrafo tiene dos componentes principales: el cuerpo y la tapa. La similitud del bolígrafo completo (tanto cuerpo como tapa) es lo que estamos tratando de determinar:

tagLímite Superior ($\gamma \cdot s$)

Piensa en $s$ como la mejor coincidencia entre las partes correspondientes de los bolígrafos. Si las tapas son muy similares pero los cuerpos no, $s$ es la similitud de las tapas.

Ahora, $\gamma$ es como un factor de escala basado en el tamaño (o importancia) de cada parte. Si un bolígrafo tiene un cuerpo muy largo y una tapa corta, mientras que el otro tiene un cuerpo corto y una tapa larga, $\gamma$ ajusta la similitud general para tener en cuenta estas diferencias en las proporciones.

El límite superior nos dice que sin importar qué tan similares sean algunas partes, la similitud general no puede exceder esta "similitud de la mejor parte" escalada por el factor de proporción.

tagLímite Inferior ($\gamma \cdot t$)

Aquí, $t$ es la similitud de las partes que menos coinciden. Si los cuerpos de los bolígrafos son bastante diferentes pero las tapas son similares, $t$ refleja la similitud del cuerpo.

Nuevamente, $\gamma$ escala esto basado en la proporción de cada parte.

El límite inferior significa que la similitud general no puede ser peor que esta "similitud de la peor parte" después de tener en cuenta la proporción de cada parte.

tagImplicaciones de los Límites

Para los ingenieros de software que trabajan con embeddings, búsqueda vectorial, recuperación o bases de datos, entender estos límites tiene implicaciones prácticas, particularmente cuando se trata de datos de alta dimensionalidad. La búsqueda vectorial a menudo implica encontrar los vectores más cercanos (más similares) en una base de datos para un vector de consulta dado, típicamente usando la similitud del coseno como medida de cercanía. Los límites que discutimos pueden proporcionar información sobre la efectividad y las limitaciones de usar similitudes de subespacios para tales tareas.

tagUso de la Similitud de Subespacios para la Clasificación

Seguridad y Precisión: Usar la similitud de subespacios para clasificar y recuperar los k mejores resultados puede ser efectivo, pero con precaución. El límite superior indica que la similitud general no puede exceder la similitud máxima de los subespacios. Por lo tanto, si un par de vectores es altamente similar en un subespacio particular, es un fuerte candidato para ser similar en el espacio de alta dimensionalidad.

Posibles Errores: Sin embargo, el límite inferior sugiere que dos vectores con baja similitud en un subespacio aún podrían ser bastante similares en general. Por lo tanto, confiar únicamente en la similitud de subespacios podría perder algunos resultados relevantes.

tagConceptos Erróneos y Precauciones

Sobreestimar la Importancia del Subespacio: Un concepto erróneo común es sobreestimar la importancia de un subespacio particular. Si bien la alta similitud en un subespacio es un buen indicador, no garantiza una alta similitud general debido a la influencia de otros subespacios.

Ignorar Similitudes Negativas: En casos donde la similitud del coseno en un subespacio es negativa, indica una relación opuesta en esa dimensión. Los ingenieros deben ser cautelosos sobre cómo estas similitudes negativas impactan la similitud general.