Approximative Suche nach nächsten Nachbarn in Empfehlungssystemen
Einführung
Im Februar 2024 hörten wir beim SF Unstructured Data Meetup von Yury Malkov über Approximate Nearest Neighbor (ANN) und seine Schlüsselrolle in Empfehlungssystemen. Die ANN-Suche ist bereits in die Produktions-Stacks der weltweit beliebtesten Tools integriert. Yury hilft uns, die Schlüsselkonzepte und den Hintergrund zu verstehen, die die Einführung von ANN in groß angelegten Empfehlungssystemen vorangetrieben haben.
Link zur YouTube-Aufzeichnung von Yury Malkovs Vortrag: Den Vortrag auf YouTube ansehen
Warum sollte dich ANN interessieren?
Yuri Malkov ist im wahrsten Sinne des Wortes ein Genie. Wenn du mir nicht glaubst, sieh dir seinen Google-Scholar-Eintrag an https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Physiker, Laserforscher und Erfinder von HNSW - einem graphbasierten Indexierungsalgorithmus, der inzwischen standardmäßig in alle großen Vektordatenbanken integriert ist. Heute arbeitet er für OpenAI als Research Scientist. Sag mir, dass das nicht wie eine plausible Tony-Stark-Bio im Jahr 2024 klingt.
Damit steigen wir in Yuris Vortrag über „Approximate Nearest Neighbor Search in Recommender Systems“ ein.
Was ist ANN Search?
Wir halten uns kurz, da wir die Grundlagen von ANN Search bereits kurz und ausführlich behandelt haben.
Nearest-Neighbor-Suchen sind eine Reihe statistischer Techniken, die wir verwenden können, um Ähnlichkeitssuchen in Anwendungen des maschinellen Lernens oder der Data Science durchzuführen. Im Gegensatz zu ihrem speziellen, nach K benannten Cousin KNN, der bei der Suche jeden Datenpunkt in einem System mit jedem anderen vergleicht, verwenden ANN-Suchalgorithmen verschiedene Indexierungstechniken, um approximative nächste Nachbarn zurückzugeben. ANN-Suchen sind für viele Anwendungen und Technologien, die heute kundenorientiert sind, zentral geworden. Von Suchmaschinen (wie Google, nicht Vektorsuche) bis hin zu Social-Media-Seiten sind ANN und Empfehlungssysteme bereits durch den gesamten Stack hindurch in der Produktion integriert.
ANN war nicht die einzige Lösung für Empfehlungssysteme. Wie sind wir also hier gelandet? Wir gehen auf ausgereifte ANN-Lösungen ein, die heute auf dem Markt sind, was Empfehlungssysteme zu einem schwierigen Problem für Nearest-Neighbor-Algorithmen macht, wie Entwickler Empfehlungssysteme strukturiert haben und wie Forscher ANN nutzen, um den Stack von Empfehlungssystemen neu zu schreiben. Yuri merkt in seinem Vortrag an, dass viele ausgereifte ANN-Lösungen existieren. Viele dieser Themen werden ausführlich in unserem Visual Guide to Choosing a Vector Index behandelt, aber ich habe eine Tabelle der in Yuris Präsentation aufgeführten Tools zusammengestellt.
Tabelle der erwähnten ANN-Indizes
| ANN Index | Klassifizierung | Szenario |
|---|---|---|
| LSH | Graphbasierter Index | - Große, hochkomplexe multidimensionale Datensätze - Verwendet euklidische Distanz, um Datenpunkte in Buckets einzuordnen - Gibt nur die nächstliegenden Ergebnisse zurück |
| HNSW | Graphbasierter Index | - Sehr schnelle Abfrage - Erfordert eine möglichst hohe Recall-Rate - Große Speicherressourcen |
| SCANN | Quantisierungsbasierter Index | - Sehr schnelle Abfrage - Erfordert eine möglichst hohe Recall-Rate - Große Speicherressourcen |
| IVF_PQ | Quantisierungsbasierter Index (invertiert) | - Invertierter Index - Sehr schnelle Abfrage - Begrenzte Speicherressourcen - Akzeptiert erhebliche Kompromisse bei der Recall-Rate |
| IVF_HSNW | Graphbasierter Index (invertiert) | - Invertierter Index - HSNW-basiert - Erfordert eine möglichst hohe Recall-Rate - Große Speicherressourcen |
| DiskANN | Mehrere Indizes für nächste Nachbarn | - ANN-Modifikationen und Toolkit für ANN-Suchen |
| ANNOY | Mehrere Indizes für nächste Nachbarn | - LSH- oder KDtrees-Implementierungen - Speichereffiziente und schnelle Suche in hochdimensionalen Räumen |
| Viele weitere | - | - FAISS, cuHNSW, ngt, song |
Über ANN-Benchmarks
Yuri huscht blitzschnell durch ANN-Benchmarking - mit Verweis auf ANNBenchmarks und dem Hinweis, dass das Benchmarking inverser ANN-Algorithmen knifflig werden kann. Verlangsamen wir das Ganze:
Was ist ANN-Benchmarks?
ANN-Benchmarks ist eine Benchmarking-Umgebung, die verschiedene Algorithmen für die approximative Suche nach nächsten Nachbarn bewertet und die Ergebnisse auf ihrer Website nach Distanzmaß und Datensatz aufschlüsselt. Die Benchmarks zeigen Leistungskennzahlen wie Recall-Rate und Abfragen pro Sekunde, und Nutzer können beitragen, indem sie ihren Code über GitHub Pull Requests einreichen.
Während du Benchmarking-Daten zu ANN-Algorithmen an vielen Stellen finden kannst (github, ANN-Benchmarks, sogar Produktdokumentation), wirst du immer Diagramme sehen, die QPS - Abfragen pro Sekunde darstellen. Mehr QPS, mehr besser! Brumm brumm!
Ein Hinweis zur Auswahl von ANN-Algorithmen (und anderen Vektorsuchalgorithmen)
Wenn dir beim Blick auf Algorithmus-Benchmarks die Nase blutet, bist du nicht allein. Deshalb hat das Milvus-Team Knowhere entwickelt. Knowhere ist die zentrale Open-Source-Vektorausführungs-Engine von Milvus, die mehrere Bibliotheken für Vektorähnlichkeitssuche integriert, darunter Faiss, Hnswlib und Annoy. Knowhere steuert, auf welcher Hardware (CPU oder GPU) Indexerstellung und Suchanfragen ausgeführt werden. So erhält Knowhere seinen Namen - es weiß, wo die Operationen auszuführen sind. Weitere Hardwaretypen, darunter DPU und TPU, werden in zukünftigen Versionen unterstützt.
Aufbauend auf Knowhere veröffentlichte das Zilliz Cloud-Team Cardinal, die zentrale Vektorsuchmaschine von Zilliz. Diese Suchmaschine hat bereits eine dreifache Leistungssteigerung im Vergleich zur vorherigen Version gezeigt und bietet eine Suchleistung (QPS), die das Zehnfache von Milvus erreicht. Die ANN-Suche ist seit Langem in Empfehlungssysteme integriert. Um herauszufinden, warum ANN-Suchalgorithmen in Empfehlungssystemen in der Produktion so beliebt geworden sind, müssen wir einen Schritt zurücktreten und die Motivationen, die Architektur und die neuartigen Lösungen betrachten, die ANN übertroffen hat.
Anwendungen von Empfehlungssystemen im großen Maßstab: Motivationen und Herausforderungen
Ziel: Das grundlegende Ziel aller Empfehlungssysteme besteht darin, ein Element (Video, Produkt, Dokument, Nachricht) zu einer Anfrage (Nutzer, Anwendung, Kontext) zurückzugeben. Merken Sie sich diese Element-Anfrage-Beziehung – sie ist wichtig, um Such- (Empfehlungs-)Algorithmen zu verstehen.
Markt: Empfehlungstechnologien haben angesichts ihrer Fähigkeit, Verbraucherverhalten zu erzeugen, einen großen Markt dargestellt und stellen ihn weiterhin dar.
Typische Herausforderungen im großen Maßstab:
Generalisierbarkeit:
- Traditionell hatten Empfehlungssysteme eine geringe Generalisierbarkeit – hauptsächlich aufgrund der Abhängigkeit von internen Daten, Modellen und Infrastruktur.
Riesige Korpora:
Große Datensätze (Millionen bis Billionen von Elementen, Anfragen) verursachen hohe Inferenzkosten.
Effizienz und die Begrenzung der Inferenzkosten sind sehr wichtig.
Aufwendige Video- und Bildverarbeitung erforderte dedizierte Ingenieure zur Wartung der Infrastruktur.
Lösungen, Reifegrad:
Eigenentwickelte Lösungen/Infrastruktur sind in der Regel selbst entwickelt (z. B. Google, Meta, X,)
Typischerweise ein mehrstufiger Empfehlungstrichter (siehe unten), um Inferenzkosten zu sparen
Gebrauchsfertige Tools haben mit dem Aufstieg von Vektordatenbanken und LLMs an Beliebtheit und Zugkraft gewonnen.
Typischer mehrstufiger Trichter
Yuri geht auf ein Diagramm eines typischen Empfehlungssystems in der Produktion ein. Im folgenden Beispiel für Videoempfehlungen erhält eine Anwendung Elemente und eine Anfrage und muss eine Videoempfehlungs-Pin zurückgeben. Diese Anwendungen sind mehrstufige Trichter, in denen Elementkandidaten erzeugt und durch aufeinanderfolgende Ranking-Modelle geleitet werden, um Suchergebnisse zu verfeinern.
Schritt 1: Kandidatengenerierung - ANN + Light Model
In dieser Anfangsphase nutzt das System Approximate Nearest Neighbors, um die riesige Videodatenbank schnell zu durchsuchen und eine vorläufige Liste von Kandidatenvideos zu identifizieren, die für die Anfrage des Nutzers relevant sind. Dieser Prozess ist darauf ausgelegt, schnell und effizient zu sein und potenziell Millionen von Elementen zu verarbeiten, indem er sich auf diejenigen konzentriert, die am wahrscheinlichsten den Anfrageeigenschaften entsprechen. Das in diesem Schritt verwendete „Light Model“ ist typischerweise ein einfacheres, weniger rechenintensives Modell, das hilft, den Kandidatenpool auf diejenigen einzugrenzen, die am besten mit den Interessen oder Suchbegriffen des Nutzers übereinstimmen.
Schritt 2: Leichtgewichtiges Ranking - Brute Force + Middle Model
Sobald eine Kandidatenmenge erzeugt wurde, umfasst der nächste Schritt eine detailliertere Untersuchung dieser Kandidaten. Dies geschieht mit einem „Brute Force“-Ansatz, bei dem jeder Kandidat gründlicher mithilfe eines „Middle Model“ bewertet wird, das komplexer ist als das im ersten Schritt verwendete Light Model. Dieses Modell berücksichtigt zusätzliche Merkmale wie Nutzerinteraktionsmetriken, kontextuelle Relevanz und Inhaltsqualität, um die Kandidaten so zu ordnen, dass die relevantesten Videos an die Spitze der Empfehlungsliste geschoben werden. Dieser Schritt schafft ein Gleichgewicht zwischen Leistung und Präzision und verfeinert die Auswahl, indem er sich stärker auf Qualität und Relevanz konzentriert.
Schritt 3: Vollständiges Ranking - Brute Force + Heavy Model
Der letzte Schritt im Empfehlungsprozess ist die Full-Ranking-Phase, die ein „Heavy Model“ einsetzt – das anspruchsvollste und ressourcenintensivste der verwendeten Modelle. Dieses Modell berücksichtigt eine breite Palette von Signalen und Datenpunkten, darunter eine tiefere Analyse des Nutzerprofils, langfristige Präferenzen, detaillierte Inhaltsanalysen und möglicherweise Echtzeitdaten wie aktuelle Betrachtungstrends. Die hier angewandte Brute-Force-Methode stellt sicher, dass jedes Video umfassend bewertet und eingestuft wird, sodass die endgültigen Empfehlungen hochgradig personalisiert und relevant sind. Dieser Schritt gewährleistet Empfehlungen von höchster Qualität, erfordert jedoch mehr Rechenleistung und Zeit, wodurch er sich für die abschließende Verfeinerung der Empfehlungsliste eignet.
Warum HSNW bei traditionellen Empfehlungssystemen ins Straucheln gerät und (unvollkommene) Lösungen In dem Wissen, dass groß angelegte Produktions-Empfehlungssysteme durch große Datensätze und die damit verbundenen Kosten eingeschränkt sind, stellt Yuri fest, dass Items und Queries auf zwei - inkompatiblen Ebenen liegen. Wenn Queries und Items in unterschiedlichen und inkompatiblen Räumen liegen, stehen traditionelle Ähnlichkeitssuchalgorithmen wie Hierarchical Navigable Small World (HNSW) vor Herausforderungen, da diese Algorithmen von einer messbaren Beziehung oder Distanzfunktion direkt zwischen der Query und den Items abhängen. Ohne eine klare Metrik zur Bewertung von Nähe kann HNSW seine Funktion nicht effektiv erfüllen, nämlich durch einen Graphen von Items zu navigieren, um die nächstliegenden Übereinstimmungen zu einer Query zu finden.****
Ein Überblick über neuartige Lösungen für Item-Query-Inkompatibilität
L2-Distanz auf Datenvektoren
So funktioniert es: Verwendet die L2-Distanz zwischen vektorisierten Dateneingaben, um eine Ersatz-Graphstruktur für Empfehlungssysteme zu erstellen.
Vorteile: Vereinfacht den Prozess durch die Verwendung einer unkomplizierten Distanzberechnung und bietet einen Geschwindigkeitsvorteil während der Phasen der Kandidatengenerierung und des Re-Rankings.
Nachteile: Erfasst komplexe Beziehungen oder Nuancen zwischen Items und Queries möglicherweise nicht so effektiv wie anspruchsvollere Modelle, was potenziell zu weniger personalisierten Empfehlungen führt.
Ranking mit bipartitem Graphen
So funktioniert es: Projiziert Items und Queries in einen bipartiten Graphen, in dem Items mit ihren nächstliegenden Nutzern oder Queries verknüpft werden, sodass Kanten auf Grundlage dieser Beziehungen erzeugt werden können.
Vorteile: Effektiv bei der Strukturierung relationaler Daten zwischen Nutzern und Items, obwohl direkte Vergleiche mit anderen Methoden begrenzt sind.
Nachteile: Aufbau und Pflege des bipartiten Graphen können ressourcenintensiv sein, und die Wirksamkeit kann je nach Dichte und Qualität der Graphverbindungen stark variieren.
Bildquelle: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Graph-Re-Ranking (textfokussiert)
So funktioniert es: Nutzt einen aus Vektoren erstellten Graphen zur Kandidatengenerierung und wendet einen Heavy Ranker direkt auf den Graphen für den Textabruf an, wodurch die Ergebnisqualität verbessert wird.
Vorteile: Beseitigt den traditionellen mehrstufigen Funnel und ermöglicht die Korrektur von Fehlern, die in früheren Phasen der Kandidatenfilterung gemacht wurden.
Nachteile: Vorwiegend effektiv für textbasierten Abruf; in anderen Kontexten, in denen nicht-textuelle Merkmale dominieren, möglicherweise weniger effektiv, was seine Anwendbarkeit einschränkt.
Bildquelle: https://arxiv.org/pdf/2208.08942
Kaskadierte Graphsuche
So funktioniert es: Beginnt mit einer leichten Distanzfunktion für die anfängliche Suche und geht während des Suchprozesses nahtlos zu einer aufwendigeren Distanzfunktion über.
Vorteile: Bietet Flexibilität, indem die Distanzfunktion in Echtzeit angepasst wird, und optimiert so während des gesamten Suchprozesses sowohl Geschwindigkeit als auch Genauigkeit.
Nachteile: Die Komplexität der Verwaltung und Optimierung zweier Distanzfunktionen kann den Rechenaufwand und die Komplexität des Systems erhöhen und potenziell die Skalierbarkeit beeinträchtigen.
Bildquelle: https://arxiv.org/pdf/2202.10226
Warum ist ANN Search so beliebt?
Alles zusammen betrachtet – Yuri hat ein gutes Bild davon gezeichnet, warum ANN-Algorithmen so umfassend implementiert wurden, insbesondere in Anwendungen (wie groß angelegten Empfehlungssystemen), die mit hochdimensionalen Datensätzen arbeiten.
Gut genuges (oder besseres) Matching - Wenn Sie keine perfekte Übereinstimmung benötigen, ist eine ANN-Variante fast immer eine bessere Lösung als andere NN-Algorithmen.
Flexibilität - mit einer breiten Palette von Implementierungen kann ein Entwickler Kosten auswählen
Reife - ANN wurden in allen wichtigen Programmiersprachen implementiert, und es gibt mehrere beliebte Frameworks zur Auswahl und Ausführung von ANN-Suchen.
Weitere Ressourcen
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Link zur YouTube-Aufzeichnung von Yury Malkovs Vortrag: Vortrag auf YouTube ansehen
Weiterlesen
Introducing Customer-Managed Encryption Keys (CMEK) on Zilliz Cloud
We're announcing the general availability of Customer-Managed Encryption Keys (CMEK) on Zilliz Cloud.
Top 10 Context Engineering Techniques You Should Know for Production RAG
A practical guide to context engineering for production LLM systems, covering RAG, context processing, memory, agents, and multimodal context.
Legal Document Analysis: Harnessing Zilliz Cloud's Semantic Search and RAG for Legal Insights
Enhance legal document analysis with Zilliz Cloud’s Semantic Search and RAG. Improve accuracy, efficiency, and scalability for contracts, case law, and compliance.