Bedeutet die Kosinus-Ähnlichkeit im Unterraum auch Kosinus-Ähnlichkeit in höheren Dimensionen?

Betrachten Sie dies: Wenn man die Kosinus-Ähnlichkeit von Embedding-Vektoren in hochdimensionalen Räumen misst, wie impliziert ihre Ähnlichkeit in niedrigdimensionalen Teilräumen die Gesamtähnlichkeit? Gibt es eine direkte, proportionale Beziehung, oder ist die Realität bei hochdimensionalen Daten komplexer?

Konkreter ausgedrückt: Garantiert eine hohe Ähnlichkeit zwischen Vektoren in ihren ersten 256 Dimensionen auch eine hohe Ähnlichkeit in ihren vollen 768 Dimensionen? Andersherum gefragt: Wenn sich Vektoren in einigen Dimensionen deutlich unterscheiden, bedeutet dies eine niedrige Gesamtähnlichkeit? Dies sind keine rein theoretischen Überlegungen; sie sind entscheidende Aspekte für effizientes Vector Retrieval, Database Indexing und die Leistung von RAG-Systemen.

Entwickler verlassen sich oft auf Heuristiken und nehmen an, dass eine hohe Teilraum-Ähnlichkeit einer hohen Gesamtähnlichkeit entspricht oder dass bemerkenswerte Unterschiede in einer Dimension die Gesamtähnlichkeit signifikant beeinflussen. Die Frage ist: Basieren diese heuristischen Methoden auf einer soliden theoretischen Grundlage, oder sind es lediglich pragmatische Annahmen?

Dieser Beitrag geht diesen Fragen nach und untersucht die Theorie und praktischen Implikationen der Teilraum-Ähnlichkeit in Bezug auf die Gesamtvektor-Ähnlichkeit.

tagBegrenzung der Kosinus-Ähnlichkeit

Gegeben seien Vektoren $\mathbf{A}, \mathbf{B}\in \mathbb{R}^d$, die wir in $\mathbf{A}=[\mathbf{A}_1, \mathbf{A}_2]$ und $\mathbf{B}=[\mathbf{B}_1, \mathbf{B}_2]$ zerlegen, wobei $\mathbf{A}_1,\mathbf{B}_1\in\mathbb{R}^m$ und $\mathbf{A}_2,\mathbf{B}_2\in\mathbb{R}^n$, mit $m+n=d$.

Die Kosinus-Ähnlichkeit im Teilraum $\mathbb{R}^m$ ist gegeben durch $\cos(\mathbf{A}_1, \mathbf{B}_1)=\frac{\mathbf{A}_1\cdot\mathbf{B}_1}{\|\mathbf{A}_1\|\|\mathbf{B}_1\|}$; entsprechend ist die Ähnlichkeit im Teilraum $\mathbb{R}^n$ gleich $\cos(\mathbf{A}_2, \mathbf{B}_2)=\frac{\mathbf{A}_2\cdot\mathbf{B}_2}{\|\mathbf{A}_2\|\|\mathbf{B}_2\|}$.

Im ursprünglichen Raum $\mathbb{R}^d$ ist die Kosinus-Ähnlichkeit definiert als:$$\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*}$$

Sei nun $s := \max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2))$. Dann gilt:$$\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*}$$

Ende des Beweises.

Beachten Sie, dass wir im letzten Schritt des Beweises ausnutzen, dass die Kosinus-Ähnlichkeit immer kleiner oder gleich 1 ist. Dies bildet unsere obere Schranke. Analog können wir zeigen, dass die untere Schranke von $\cos(\mathbf{A},\mathbf{B})$ gegeben ist durch:

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

Beachten Sie, dass wir für die untere Schranke nicht vorschnell schließen können, dass $\cos(\mathbf{A},\mathbf{B}) \geq t$. Dies liegt am Wertebereich der Kosinus-Funktion, der zwischen $[-1, 1]$ liegt. Aufgrund dieses Bereichs ist es unmöglich, eine engere untere Schranke als den trivialen Wert von -1 festzulegen.

Zusammenfassend haben wir also die folgende lockere Schranke: $$-1\leq\cos(\mathbf{A},\mathbf{B})\leq\max(\cos(\mathbf{A}_1, \mathbf{B}_1), \cos(\mathbf{A}_2, \mathbf{B}_2)).$$ und eine engere Schranke $$\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*}$$, wobei $\gamma = \cos([\|\mathbf{A}_1\|, \|\mathbf{A}_2\|], [\|\mathbf{B}_1\|, \|\mathbf{B}_2\|])$.

tagVerbindung zum Johnson–Lindenstrauss-Lemma

Das JL-Lemma besagt, dass für jedes $0 < \epsilon < 1$ und jede endliche Menge von Punkten $S$ in $\mathbb{R}^d$ eine Abbildung $f: \mathbb{R}^d \rightarrow \mathbb{R}^k$ (mit $k = O(\epsilon^{-2} \log |S|)$) existiert, sodass für alle $\mathbf{u}, \mathbf{v} \in S$ die euklidischen Abstände annähernd erhalten bleiben:

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

Um $f$ wie eine Teilraumauswahl arbeiten zu lassen, können wir eine Diagonalmatrix zur Projektion verwenden, wie zum Beispiel eine $5 \times 3$ Matrix $f$, wenn auch nicht zufällig (beachten Sie, die typische Formulierung des JL-Lemmas beinhaltet lineare Transformationen, die oft zufällige Matrizen aus einer Gauß-Verteilung verwenden). Wenn wir beispielsweise die 1., 3. und 5. Dimension aus einem 5-dimensionalen Vektorraum beibehalten wollen, könnte die Matrix $f$ wie folgt gestaltet werden: $$f = \begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\0 & 0 & 1\end{bmatrix}$$
Indem wir $f$ jedoch als diagonal festlegen, schränken wir die Klasse der Funktionen ein, die für die Projektion verwendet werden können. Das JL-Lemma garantiert die Existenz eines geeigneten $f$ innerhalb der breiteren Klasse linearer Transformationen, aber wenn wir $f$ auf Diagonalmatrizen beschränken, existiert möglicherweise kein geeignetes $f$ innerhalb dieser eingeschränkten Klasse für die Anwendung der JL-Lemma-Grenzen.

tagValidierung der Grenzen

Um die theoretischen Grenzen der Kosinus-Ähnlichkeit in hochdimensionalen Vektorräumen empirisch zu untersuchen, können wir eine Monte-Carlo-Simulation verwenden. Diese Methode ermöglicht es uns, eine große Anzahl zufälliger Vektorpaare zu generieren, ihre Ähnlichkeiten sowohl im ursprünglichen Raum als auch in Teilräumen zu berechnen und dann zu bewerten, wie gut die theoretischen oberen und unteren Grenzen in der Praxis gelten.

Der folgende Python-Code-Ausschnitt implementiert dieses Konzept. Er generiert zufällig Vektorpaare in einem hochdimensionalen Raum und berechnet ihre Kosinus-Ähnlichkeit. Dann teilt er jeden Vektor in zwei Teilräume auf, berechnet die Kosinus-Ähnlichkeit innerhalb jedes Teilraums und evaluiert die oberen und unteren Grenzen der vollständig-dimensionalen Kosinus-Ähnlichkeit basierend auf den Teilraum-Ähnlichkeiten.

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

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

tagVerständnis der Grenzen

Kurz gesagt: Beim Vergleich zweier hochdimensionaler Vektoren liegt die Gesamtähnlichkeit zwischen den besten und schlechtesten Ähnlichkeiten ihrer Teilräume, angepasst an die Größe oder Bedeutung dieser Teilräume im Gesamtkontext. Dies ist es, was die Grenzen für die Cosinus-Ähnlichkeit in höheren Dimensionen intuitiv darstellen: die Balance zwischen den ähnlichsten und unähnlichsten Teilen, gewichtet nach ihrer relativen Größe oder Bedeutung.

Stellen Sie sich vor, Sie versuchen, zwei mehrteilige Objekte (sagen wir, zwei edle Stifte) basierend auf ihrer Gesamtähnlichkeit zu vergleichen. Jeder Stift hat zwei Hauptkomponenten: den Körper und die Kappe. Die Ähnlichkeit des gesamten Stifts (sowohl Körper als auch Kappe) ist das, was wir bestimmen möchten:

tagObere Grenze ($\gamma \cdot s$)

Betrachten Sie $s$ als die beste Übereinstimmung zwischen entsprechenden Teilen der Stifte. Wenn die Kappen sehr ähnlich sind, aber die Körper nicht, ist $s$ die Ähnlichkeit der Kappen.

$\gamma$ ist dabei wie ein Skalierungsfaktor basierend auf der Größe (oder Bedeutung) jedes Teils. Wenn ein Stift einen sehr langen Körper und eine kurze Kappe hat, während der andere einen kurzen Körper und eine lange Kappe hat, passt $\gamma$ die Gesamtähnlichkeit an diese Proportionsunterschiede an.

Die obere Grenze sagt uns, dass die Gesamtähnlichkeit unabhängig davon, wie ähnlich einige Teile sind, diese "beste Teilähnlichkeit" skaliert mit dem Proportionsfaktor nicht überschreiten kann.

tagUntere Grenze ($\gamma \cdot t$)

Hier ist $t$ die Ähnlichkeit der am wenigsten übereinstimmenden Teile. Wenn sich die Körper der Stifte stark unterscheiden, aber die Kappen ähnlich sind, spiegelt $t$ die Ähnlichkeit der Körper wider.

Auch hier skaliert $\gamma$ dies basierend auf dem Anteil jedes Teils.

Die untere Grenze bedeutet, dass die Gesamtähnlichkeit nicht schlechter sein kann als diese "schlechteste Teilähnlichkeit" nach Berücksichtigung des Anteils jedes Teils.

tagImplikationen der Grenzen

Für Softwareentwickler, die mit Embeddings, Vektorsuche, Retrieval oder Datenbanken arbeiten, hat das Verständnis dieser Grenzen praktische Auswirkungen, besonders beim Umgang mit hochdimensionalen Daten. Die Vektorsuche beinhaltet oft das Finden der nächstgelegenen (ähnlichsten) Vektoren in einer Datenbank zu einem gegebenen Abfragevektor, typischerweise unter Verwendung der Cosinus-Ähnlichkeit als Maß für die Nähe. Die besprochenen Grenzen können Einblicke in die Effektivität und Grenzen der Verwendung von Teilraumähnlichkeiten für solche Aufgaben geben.

tagVerwendung der Teilraumähnlichkeit für das Ranking

Sicherheit und Genauigkeit: Die Verwendung der Teilraumähnlichkeit für das Ranking und Abrufen von Top-k-Ergebnissen kann effektiv sein, erfordert aber Vorsicht. Die obere Grenze zeigt, dass die Gesamtähnlichkeit die maximale Ähnlichkeit der Teilräume nicht überschreiten kann. Wenn also ein Vektorpaar in einem bestimmten Teilraum sehr ähnlich ist, ist es ein starker Kandidat für Ähnlichkeit im hochdimensionalen Raum.

Mögliche Fallstricke: Die untere Grenze deutet jedoch darauf hin, dass zwei Vektoren mit geringer Ähnlichkeit in einem Teilraum insgesamt noch recht ähnlich sein könnten. Daher könnte das ausschließliche Vertrauen auf die Teilraumähnlichkeit einige relevante Ergebnisse übersehen.

tagMissverständnisse und Vorsichtsmaßnahmen

Überschätzung der Teilraumbedeutung: Ein häufiges Missverständnis ist die Überschätzung der Bedeutung eines bestimmten Teilraums. Während hohe Ähnlichkeit in einem Teilraum ein guter Indikator ist, garantiert sie aufgrund des Einflusses anderer Teilräume keine hohe Gesamtähnlichkeit.

Ignorieren negativer Ähnlichkeiten: In Fällen, in denen die Cosinus-Ähnlichkeit in einem Teilraum negativ ist, zeigt dies eine gegensätzliche Beziehung in dieser Dimension an. Entwickler sollten vorsichtig sein, wie sich diese negativen Ähnlichkeiten auf die Gesamtähnlichkeit auswirken.