Vector Search

Die Vektorsuche ruft Elemente ab, deren Embeddings einer Suchanfrage unter einem Ähnlichkeitsmaß wie Kosinusähnlichkeit, Skalarprodukt oder euklidischer Distanz am nächsten liegen. Ein Embedding-Modell ordnet Elemente mit ähnlicher Bedeutung oder ähnlichem Erscheinungsbild nahe beieinander an. Daher sind die nächsten Vektoren die ähnlichsten Dokumente, Bilder oder Produkte, auch wenn sie keine Keywords mit der Suchanfrage gemeinsam haben. Eine exakte Vektorsuche ist eine Suche nach den k nächsten Nachbarn (k-NN) unter allen gespeicherten Vektoren. Bei großen Datenmengen verwenden Systeme Indizes für ungefähre nächste Nachbarn (ANN), die die Suchanfrage mit einem kleinen Teil der Vektoren vergleichen und trotzdem nahezu alle tatsächlich nächsten Nachbarn zurückgeben.

So funktioniert Vektorsuche#

Die Suchanfrage und die gespeicherten Elemente werden mit demselben Modell oder mit einem gemeinsam trainierten Modellpaar in Embeddings umgewandelt: einem Satz-Encoder für Text, CLIP zum Abgleich von Text und Bildern oder einem Bildverarbeitungs-Backbone zum Abgleich von Bildern. Die Metrik sollte zur Trainingsmethode des Modells passen. Bei Einheitsvektoren entspricht die Kosinusähnlichkeit dem Skalarprodukt, und eine Rangfolge nach euklidischer Distanz ergibt dieselbe Reihenfolge. Eine exakte Suche erfordert für jede Suchanfrage einen Vergleich pro gespeichertem Vektor. Das ist bei Zehntausenden Vektoren schnell, bei Hunderten Millionen jedoch zu langsam. Deshalb verwenden große Systeme eine von vier Arten von ANN-Indizes:

• Graphindizes wie HNSW: Jeder Vektor wird in einem geschichteten Graphen mit seinen Nachbarn verknüpft. Eine Suchanfrage wird beantwortet, indem der Graph schrittweise auf sie zu durchlaufen wird.
• Clustering-Indizes (IVF): Gruppieren die Vektoren mit k-Means und durchsuchen nur die Cluster, deren Zentren der Suchanfrage am nächsten liegen.
• Vektorquantisierung: Komprimiert jeden Vektor wie bei der Produktquantisierung auf wenige Bytes, sodass Abstände anhand kompakter, im Arbeitsspeicher abgelegter Codes näherungsweise berechnet werden.
• Festplattenbasierte Graphen: Speichern einen Graphindex wie DiskANN auf einer SSD, um Milliarden von Vektoren auf einem einzelnen Rechner zu durchsuchen.

Die Grundidee eines IVF-Index lässt sich in einem kurzen Beispiel mit NumPy und scikit-learn darstellen, das ihn mit einer exakten Suche vergleicht:

import numpy as np
from sklearn.cluster import KMeans

# 20,000 embeddings grouped by topic, normalized so a dot product is cosine similarity
rng = np.random.default_rng(0)
topics = rng.normal(size=(200, 64))
vectors = topics[rng.integers(200, size=20000)] + 0.5 * rng.normal(size=(20000, 64))
vectors /= np.linalg.norm(vectors, axis=1, keepdims=True)
query = vectors[0] + 0.1 * rng.normal(size=64)

# Exact search: score every stored vector
exact = np.argsort(-(vectors @ query))[:10]

# IVF index: cluster the vectors, then scan only the lists of the 5 closest centroids
kmeans = KMeans(n_clusters=100, n_init=1, random_state=0).fit(vectors)
probed = np.argsort(-(kmeans.cluster_centers_ @ query))[:5]
candidates = np.flatnonzero(np.isin(kmeans.labels_, probed))
approx = candidates[np.argsort(-(vectors[candidates] @ query))[:10]]

print(f"scanned {len(candidates) / len(vectors):.1%} of vectors")
print(f"recall@10: {len(set(exact) & set(approx)) / 10:.0%}")

Beim Durchsuchen von 5 der 100 Cluster werden 5,1 % der Vektoren geprüft und trotzdem alle 10 tatsächlich nächsten Nachbarn gefunden. Die Trefferquote@10 liegt damit bei 100 %. Das Prüfen weiterer Cluster erhöht sowohl die Trefferquote als auch den Aufwand. Daher ist die Anzahl der Prüfungen die wichtigste abzustimmende Einstellung eines IVF-Index.

Vektorsuche im Vergleich zu verwandten Begriffen#

• Keyword-Suche: Sucht nach exakten Begriffen in einem invertierten Index und ordnet sie mit Formeln wie BM25. Sie eignet sich besonders für Namen, Codes und seltene Wörter, verpasst aber Synonyme.
• Semantische Suche: Sucht nach Bedeutung und ist das häufigste Ziel der Vektorsuche. Systeme für semantische Suche ergänzen sie oft um eine Umformulierung der Suchanfrage oder eine nachträgliche Rangordnung.
• Hybride Suche: Führt Keyword- und Vektorsuche gemeinsam aus und führt die beiden Ranglisten zusammen.
• Vektordatenbank: Das System, das Vektoren samt Metadaten speichert und Vektorsuche mit Filterung, Aktualisierungen und dauerhafter Speicherung ermöglicht.

Anwendungen in der Praxis#

• Retrieval-Augmented Generation (RAG): Findet die Textstellen in Dokumenten, die ein Sprachmodell zur Beantwortung einer Frage benötigt.
• Objekt-Re-Identifizierung: Gleicht das Erscheinungsbild-Embedding einer Person oder eines Fahrzeugs mit früheren Sichtungen ab, um dasselbe Objekt über mehrere Kameras hinweg zuzuordnen.
• Gesichtserkennung: Vergleicht ein Gesichts-Embedding mit registrierten Gesichtern und akzeptiert das ähnlichste, wenn es nahe genug liegt.
• Empfehlungssysteme: Empfehlen Produkte, Lieder oder Videos, deren Embeddings nahe bei den zuletzt ausgewählten Elementen liegen.

Die Ultralytics Platform nutzt Vektorsuche, um Trainingsdatensätze zu erweitern. Die Aktion Find Similar Images verwendet ein ausgewähltes Bild, durchsucht öffentliche Datensätze sowie die eigenen Datensätze und Teamdatensätze des Benutzers nach den anhand des Embeddings ähnlichsten Bildern und zeigt bis zu 24 Treffer samt Ähnlichkeitswerten an. Diese lassen sich dem Datensatz als unbeschriftete Trainingsbilder hinzufügen.