La similarità del coseno nei sottospazi implica una similarità del coseno in alta dimensionalità?

Considera questo: quando si misura la similarità del coseno di vettori di embedding in spazi ad alta dimensionalità, come la loro similarità in sottospazi di dimensione inferiore implica la similarità complessiva? Esiste una relazione diretta e proporzionale, o la realtà è più complessa con i dati ad alta dimensionalità?

Più concretamente, un'alta similarità tra vettori nelle loro prime 256 dimensioni garantisce un'alta similarità nelle loro 768 dimensioni complete? Al contrario, se i vettori differiscono significativamente in alcune dimensioni, questo implica una bassa similarità complessiva? Queste non sono mere riflessioni teoriche; sono considerazioni cruciali per il recupero efficiente dei vettori, l'indicizzazione dei database e le prestazioni dei sistemi RAG.

Gli sviluppatori spesso si affidano a euristiche, assumendo che un'alta similarità nel sottospazio equivalga ad un'alta similarità complessiva o che differenze notevoli in una dimensione influenzino significativamente la similarità complessiva. La domanda è: questi metodi euristici sono basati su solide basi teoriche o sono semplicemente assunzioni di convenienza?

Questo post si addentra in queste domande, esaminando la teoria e le implicazioni pratiche della similarità nei sottospazi in relazione alla similarità vettoriale complessiva.

tagDelimitare la Similarità del Coseno

Dati i vettori $\mathbf{A}, \mathbf{B}\in \mathbb{R}^d$, li decomponiamo come $\mathbf{A}=[\mathbf{A}_1, \mathbf{A}_2]$ e $\mathbf{B}=[\mathbf{B}_1, \mathbf{B}_2]$, dove $\mathbf{A}_1,\mathbf{B}_1\in\mathbb{R}^m$ e $\mathbf{A}_2,\mathbf{B}_2\in\mathbb{R}^n$, con $m+n=d$.

La similarità del coseno nel sottospazio $\mathbb{R}^m$ è data da $\cos(\mathbf{A}_1, \mathbf{B}_1)=\frac{\mathbf{A}_1\cdot\mathbf{B}_1}{\|\mathbf{A}_1\|\|\mathbf{B}_1\|}$; similmente, la similarità nel sottospazio $\mathbb{R}^n$ è $\cos(\mathbf{A}_2, \mathbf{B}_2)=\frac{\mathbf{A}_2\cdot\mathbf{B}_2}{\|\mathbf{A}_2\|\|\mathbf{B}_2\|}$.

Nello spazio originale $\mathbb{R}^d$, la similarità del coseno è definita come:$$\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*}$$

Ora, sia $s := \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$. Quindi abbiamo:$$\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*}$$

Fine della dimostrazione.

Nota che nell'ultimo passaggio della dimostrazione, sfruttiamo il fatto che la similarità del coseno è sempre minore o uguale a 1. Questo forma il nostro limite superiore. Similmente, possiamo dimostrare che il limite inferiore di $\cos(\mathbf{A},\mathbf{B})$ è dato da:

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

Nota che per il limite inferiore, non possiamo concludere frettolosamente che $\cos(\mathbf{A},\mathbf{B}) \geq t$. Questo è dovuto all'intervallo della funzione coseno, che spazia tra $[-1, 1]$. A causa di questo intervallo, è impossibile stabilire un limite inferiore più stretto del valore triviale di -1.

Quindi in conclusione, abbiamo il seguente limite ampio: $$-1\leq\cos(\mathbf{A},\mathbf{B})\leq\max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2)).$$ e un limite più stretto $$\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*}$$, dove $\gamma = \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$.

tagConnessione con il Lemma di Johnson–Lindenstrauss

Il lemma JL afferma che per ogni $0 < \epsilon < 1$ e qualsiasi insieme finito di punti $S$ in $\mathbb{R}^d$, esiste una mappatura $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ (con $k = O(\epsilon^{-2} \log |S|)$) tale che per tutti $\mathbf{u}, \mathbf{v} \in S$, le distanze euclidee sono approssimativamente preservate:

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

Per far funzionare $f$ come una selezione di sottospazio, possiamo usare una matrice diagonale per la proiezione, come una matrice $5 \times 3$ $f$, anche se non casuale (nota, la formulazione tipica del lemma JL coinvolge trasformazioni lineari che spesso utilizzano matrici casuali estratte da una distribuzione gaussiana). Per esempio, se vogliamo mantenere la 1ª, 3ª e 5ª dimensione da uno spazio vettoriale 5-dimensionale, la matrice $f$ potrebbe essere progettata come segue: $$f = \begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$
Tuttavia, specificando $f$ come diagonale, limitiamo la classe di funzioni che possono essere utilizzate per la proiezione. Il lemma JL garantisce l'esistenza di una $f$ adatta all'interno della classe più ampia di trasformazioni lineari, ma quando limitiamo $f$ ad essere diagonale, tale $f$ adatta potrebbe non esistere all'interno di questa classe ristretta per applicare i limiti del lemma JL.

tagValidare i Limiti

Per esplorare empiricamente i limiti teorici della similarità del coseno in spazi vettoriali ad alta dimensionalità, possiamo impiegare una simulazione Monte Carlo. Questo metodo ci permette di generare un grande numero di coppie di vettori casuali, calcolare le loro similarità sia nello spazio originale che nei sottospazi, e poi valutare quanto bene i limiti teorici superiori e inferiori reggano nella pratica.

Il seguente snippet di codice Python implementa questo concetto. Genera casualmente coppie di vettori in uno spazio ad alta dimensionalità e calcola la loro similarità del coseno. Poi, divide ogni vettore in due sottospazi, calcola la similarità del coseno all'interno di ogni sottospazio e valuta i limiti superiori e inferiori della similarità del coseno a dimensione piena basandosi sulle similarità dei sottospazi.

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

tagComprendere i Limiti

In breve, quando si confrontano due vettori ad alta dimensionalità, la similarità complessiva si trova tra le migliori e le peggiori similarità dei loro sottospazi, aggiustata per quanto grandi o importanti sono questi sottospazi nello schema generale. Questo è ciò che i limiti per la similarità del coseno in dimensioni superiori rappresentano intuitivamente: il bilanciamento tra le parti più e meno simili, pesate dalla loro dimensione o importanza relativa.

Immagina di dover confrontare due oggetti multi-parte (diciamo, due penne eleganti) basandoti sulla loro similarità complessiva. Ogni penna ha due componenti principali: il corpo e il cappuccio. La similarità dell'intera penna (sia corpo che cappuccio) è ciò che stiamo cercando di determinare:

tagLimite Superiore ($\gamma \cdot s$)

Pensa a $s$ come al miglior abbinamento tra le parti corrispondenti delle penne. Se i cappucci sono molto simili ma i corpi no, $s$ è la similarità dei cappucci.

Ora, $\gamma$ è come un fattore di scala basato sulla dimensione (o importanza) di ogni parte. Se una penna ha un corpo molto lungo e un cappuccio corto, mentre l'altra ha un corpo corto e un cappuccio lungo, $\gamma$ aggiusta la similarità complessiva per tenere conto di queste differenze nelle proporzioni.

Il limite superiore ci dice che, non importa quanto simili siano alcune parti, la similarità complessiva non può superare questa "similarità della parte migliore" scalata dal fattore di proporzione.

tagLimite Inferiore ($\gamma \cdot t$)

Qui, $t$ è la similarità delle parti che corrispondono meno. Se i corpi delle penne sono molto diversi ma i cappucci sono simili, $t$ riflette la similarità del corpo.

Ancora una volta, $\gamma$ scala questo basandosi sulla proporzione di ogni parte.

Il limite inferiore significa che la similarità complessiva non può essere peggiore di questa "similarità della parte peggiore" dopo aver tenuto conto della proporzione di ogni parte.

tagImplicazioni dei Limiti

Per gli ingegneri software che lavorano con embedding, ricerca vettoriale, recupero o database, comprendere questi limiti ha implicazioni pratiche, in particolare quando si ha a che fare con dati ad alta dimensionalità. La ricerca vettoriale spesso implica trovare i vettori più vicini (più simili) in un database rispetto a un vettore di query dato, tipicamente usando la similarità del coseno come misura di vicinanza. I limiti che abbiamo discusso possono fornire intuizioni sull'efficacia e le limitazioni dell'uso delle similarità dei sottospazi per tali compiti.

tagUso della Similarità dei Sottospazi per il Ranking

Sicurezza e Accuratezza: Usare la similarità dei sottospazi per il ranking e il recupero dei top-k risultati può essere efficace, ma con cautela. Il limite superiore indica che la similarità complessiva non può superare la massima similarità dei sottospazi. Quindi, se una coppia di vettori è altamente simile in un particolare sottospazio, è un forte candidato per essere simile nello spazio ad alta dimensionalità.

Potenziali Insidie: Tuttavia, il limite inferiore suggerisce che due vettori con bassa similarità in un sottospazio potrebbero ancora essere abbastanza simili nel complesso. Quindi, affidarsi solamente alla similarità dei sottospazi potrebbe far perdere alcuni risultati rilevanti.

tagConcezioni Errate e Precauzioni

Sovrastima dell'Importanza dei Sottospazi: Una concezione errata comune è sovrastimare l'importanza di un particolare sottospazio. Mentre un'alta similarità in un sottospazio è un buon indicatore, non garantisce un'alta similarità complessiva a causa dell'influenza degli altri sottospazi.

Ignorare le Similarità Negative: Nei casi in cui la similarità del coseno in un sottospazio è negativa, indica una relazione opposta in quella dimensione. Gli ingegneri dovrebbero fare attenzione a come queste similarità negative impattano sulla similarità complessiva.