La similarité cosinus dans un sous-espace implique-t-elle une similarité cosinus dans un espace de haute dimension ?

Considérez ceci : lors de la mesure de la similarité cosinus de vecteurs d'embedding dans des espaces de haute dimension, comment leur similarité dans des sous-espaces de dimension inférieure implique-t-elle la similarité globale ? Existe-t-il une relation directe et proportionnelle, ou la réalité est-elle plus complexe avec des données de haute dimension ?

Plus concrètement, une forte similarité entre les vecteurs dans leurs 256 premières dimensions assure-t-elle une forte similarité dans leurs 768 dimensions complètes ? À l'inverse, si les vecteurs diffèrent significativement dans certaines dimensions, cela implique-t-il une faible similarité globale ? Ce ne sont pas de simples réflexions théoriques ; ce sont des considérations cruciales pour la recherche efficace de vecteurs, l'indexation des bases de données et la performance des systèmes RAG.

Les développeurs s'appuient souvent sur des heuristiques, supposant qu'une forte similarité dans un sous-espace équivaut à une forte similarité globale ou que des différences notables dans une dimension affectent significativement la similarité globale. La question est : ces méthodes heuristiques reposent-elles sur des bases théoriques solides, ou sont-elles simplement des hypothèses de commodité ?

Cet article se penche sur ces questions, examinant la théorie et les implications pratiques de la similarité des sous-espaces par rapport à la similarité vectorielle globale.

tagDélimitation de la Similarité Cosinus

Étant donné les vecteurs $\mathbf{A}, \mathbf{B}\in \mathbb{R}^d$, nous les décomposons comme $\mathbf{A}=[\mathbf{A}_1, \mathbf{A}_2]$ et $\mathbf{B}=[\mathbf{B}_1, \mathbf{B}_2]$, où $\mathbf{A}_1,\mathbf{B}_1\in\mathbb{R}^m$ et $\mathbf{A}_2,\mathbf{B}_2\in\mathbb{R}^n$, avec $m+n=d$.

La similarité cosinus dans le sous-espace $\mathbb{R}^m$ est donnée par $\cos(\mathbf{A}_1, \mathbf{B}_1)=\frac{\mathbf{A}_1\cdot\mathbf{B}_1}{\|\mathbf{A}_1\|\|\mathbf{B}_1\|}$ ; de même, la similarité dans le sous-espace $\mathbb{R}^n$ est $\cos(\mathbf{A}_2, \mathbf{B}_2)=\frac{\mathbf{A}_2\cdot\mathbf{B}_2}{\|\mathbf{A}_2\|\|\mathbf{B}_2\|}$.

Dans l'espace original $\mathbb{R}^d$, la similarité cosinus est définie comme :$$\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*}$$

Maintenant, soit $s := \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$. Alors, nous avons :$$\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 démonstration.

Notez que dans la dernière étape de la preuve, nous utilisons le fait que la similarité cosinus est toujours inférieure ou égale à 1. Cela forme notre borne supérieure. De même, nous pouvons montrer que la borne inférieure de $\cos(\mathbf{A},\mathbf{B})$ est donnée par :

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

Notez que pour la borne inférieure, nous ne pouvons pas conclure hâtivement que $\cos(\mathbf{A},\mathbf{B}) \geq t$. Cela est dû à l'intervalle de la fonction cosinus, qui s'étend entre $[-1, 1]$. En raison de cet intervalle, il est impossible d'établir une borne inférieure plus stricte que la valeur triviale de -1.

Donc en conclusion, nous avons la borne large suivante : $$-1\leq\cos(\mathbf{A},\mathbf{B})\leq\max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2)).$$ et une borne plus stricte $$\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*}$$, où $\gamma = \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$.

tagConnexion au Lemme de Johnson–Lindenstrauss

Le lemme JL affirme que pour tout $0 < \epsilon < 1$ et tout ensemble fini de points $S$ dans $\mathbb{R}^d$, il existe une application $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ (avec $k = O(\epsilon^{-2} \log |S|)$) telle que pour tous $\mathbf{u}, \mathbf{v} \in S$, les distances euclidiennes sont approximativement préservées :

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

Pour faire fonctionner $f$ comme une sélection de sous-espace, nous pouvons utiliser une matrice diagonale pour la projection, comme une matrice $5 \times 3$ $f$, bien que non aléatoire (notez que la formulation typique du lemme JL implique des transformations linéaires qui utilisent souvent des matrices aléatoires tirées d'une distribution gaussienne). Par exemple, si nous visons à conserver les 1ère, 3ème et 5ème dimensions d'un espace vectoriel à 5 dimensions, la matrice $f$ pourrait être conçue comme suit : $$f = \begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$
Cependant, en spécifiant $f$ comme diagonale, nous limitons la classe de fonctions qui peuvent être utilisées pour la projection. Le lemme JL garantit l'existence d'un $f$ approprié dans la classe plus large des transformations linéaires, mais lorsque nous restreignons $f$ à être diagonal, un tel $f$ approprié peut ne pas exister dans cette classe restreinte pour appliquer les bornes du lemme JL.

tagValidation des Bornes

Pour explorer empiriquement les bornes théoriques de la similarité cosinus dans des espaces vectoriels de haute dimension, nous pouvons employer une simulation de Monte Carlo. Cette méthode nous permet de générer un grand nombre de paires de vecteurs aléatoires, de calculer leurs similarités à la fois dans l'espace original et dans les sous-espaces, puis d'évaluer comment les bornes théoriques supérieures et inférieures se comportent en pratique.

Le snippet de code Python suivant implémente ce concept. Il génère aléatoirement des paires de vecteurs dans un espace de haute dimension et calcule leur similarité cosinus. Ensuite, il divise chaque vecteur en deux sous-espaces, calcule la similarité cosinus dans chaque sous-espace, et évalue les bornes supérieures et inférieures de la similarité cosinus en dimension complète basée sur les similarités des sous-espaces.

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

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

tagComprendre les bornes

En bref, lors de la comparaison de deux vecteurs de grande dimension, la similarité globale se situe entre les meilleures et les pires similarités de leurs sous-espaces, ajustées en fonction de la taille ou de l'importance de ces sous-espaces dans le schéma global. C'est ce que représentent intuitivement les bornes de similarité cosinus dans les dimensions supérieures : l'équilibre entre les parties les plus et les moins similaires, pondéré par leur taille ou importance relative.

Imaginez que vous essayez de comparer deux objets composés de plusieurs parties (disons, deux stylos de luxe) en fonction de leur similarité globale. Chaque stylo a deux composants principaux : le corps et le capuchon. La similarité du stylo entier (corps et capuchon) est ce que nous essayons de déterminer :

tagBorne supérieure ($\gamma \cdot s$)

Pensez à $s$ comme la meilleure correspondance entre les parties correspondantes des stylos. Si les capuchons sont très similaires mais pas les corps, $s$ est la similarité des capuchons.

Maintenant, $\gamma$ est comme un facteur d'échelle basé sur la taille (ou l'importance) de chaque partie. Si un stylo a un corps très long et un capuchon court, tandis que l'autre a un corps court et un capuchon long, $\gamma$ ajuste la similarité globale pour tenir compte de ces différences de proportions.

La borne supérieure nous indique que quelle que soit la similarité de certaines parties, la similarité globale ne peut pas dépasser cette "meilleure similarité de partie" multipliée par le facteur de proportion.

tagBorne inférieure ($\gamma \cdot t$)

Ici, $t$ est la similarité des parties les moins correspondantes. Si les corps des stylos sont assez différents mais les capuchons sont similaires, $t$ reflète la similarité du corps.

Encore une fois, $\gamma$ adapte cela en fonction de la proportion de chaque partie.

La borne inférieure signifie que la similarité globale ne peut pas être pire que cette "pire similarité de partie" après prise en compte de la proportion de chaque partie.

tagImplications des bornes

Pour les développeurs travaillant avec des embeddings, la recherche vectorielle, la récupération ou les bases de données, la compréhension de ces bornes a des implications pratiques, particulièrement lors du traitement de données de grande dimension. La recherche vectorielle implique souvent de trouver les vecteurs les plus proches (les plus similaires) dans une base de données pour un vecteur de requête donné, généralement en utilisant la similarité cosinus comme mesure de proximité. Les bornes que nous avons discutées peuvent fournir des insights sur l'efficacité et les limitations de l'utilisation des similarités de sous-espaces pour de telles tâches.

tagUtilisation de la similarité des sous-espaces pour le classement

Sécurité et précision : L'utilisation de la similarité des sous-espaces pour le classement et la récupération des k premiers résultats peut être efficace, mais avec précaution. La borne supérieure indique que la similarité globale ne peut pas dépasser la similarité maximale des sous-espaces. Ainsi, si une paire de vecteurs est très similaire dans un sous-espace particulier, c'est un candidat fort pour être similaire dans l'espace de grande dimension.

Pièges potentiels : Cependant, la borne inférieure suggère que deux vecteurs ayant une faible similarité dans un sous-espace pourraient toujours être assez similaires globalement. Par conséquent, se fier uniquement à la similarité des sous-espaces pourrait manquer certains résultats pertinents.

tagIdées fausses et mises en garde

Surestimation de l'importance des sous-espaces : Une idée fausse courante est de surestimer l'importance d'un sous-espace particulier. Bien qu'une haute similarité dans un sous-espace soit un bon indicateur, elle ne garantit pas une haute similarité globale en raison de l'influence des autres sous-espaces.

Ignorer les similarités négatives : Dans les cas où la similarité cosinus dans un sous-espace est négative, cela indique une relation opposée dans cette dimension. Les développeurs doivent être attentifs à la façon dont ces similarités négatives impactent la similarité globale.