Eine kurze Einführung in die Vektorsuche

Von der Vektorsuche bis hin zu leistungsstarken REST-APIs bietet Elasticsearch Entwicklern das umfangreichste Such-Toolkit. Sehen Sie sich die Beispiel-Notebooks auf GitHub an, um etwas Neues testen. Sie können auch noch heute Ihre kostenlose Testversion starten oder Elasticsearch lokal ausführen.

Dieser Artikel ist der erste einer dreiteiligen Reihe, die sich mit den Feinheiten der Vektorsuche, auch semantische Suche genannt, und ihrer Implementierung in Elasticsearch befasst.

Dieser erste Teil konzentriert sich auf die allgemeine Einführung in die Grundlagen der Vektoreinbettung und die Funktionsweise der Vektorsuche im Detail.

Mit dem im ersten Artikel erworbenen Wissen ausgestattet, führt Sie der zweite Teil durch die verschlungenen Pfade der Einrichtung der Vektorsuche in Elasticsearch.

Im dritten Teil werden wir das in den ersten beiden Teilen Gelernte nutzen, darauf aufbauen und uns damit beschäftigen, wie man leistungsstarke hybride Suchanfragen in Elasticsearch erstellt.

Bevor wir uns dem eigentlichen Thema dieses Artikels zuwenden, werfen wir einen Blick zurück in die Geschichte der Vektoren, einem zentralen Konzept der semantischen Suche.

Vektoren sind nicht neu

Ich bin mir ziemlich sicher, dass jeder zustimmen würde, dass seit dem Aufkommen von ChatGPT im November 2022 kein einziger Tag vergeht, an dem man nicht von „Vektorsuche“ hört oder liest. Sie ist allgegenwärtig und so weit verbreitet, dass wir oft den Eindruck gewinnen, es handele sich um eine neue, hochmoderne Technologie, die gerade erst auf den Markt gekommen ist. Doch in Wahrheit gibt es diese Technologie schon seit mehr als sechs Jahrzehnten! Die Forschung zu diesem Thema begann Mitte der 1960er Jahre, und die ersten Forschungsarbeiten wurden 1978 von Gerard Salton, einem Experten für Informationswiedergewinnung, und seinen Kollegen an der Cornell University veröffentlicht. Saltons Arbeiten über dichte und dünnbesetzte Vektormodelle bilden die Grundlage der modernen Vektorsuchtechnologie.

In den letzten 20 Jahren wurden viele verschiedene Vektordatenbanksysteme auf der Grundlage seiner Forschung entwickelt und auf den Markt gebracht. Dazu gehört Elasticsearch, das auf dem Apache Lucene-Projekt basiert und seit 2019 an der Vektorsuche arbeitet .

Vektoren sind heutzutage allgegenwärtig und so durchdringend, dass es wichtig ist, zunächst ein gutes Verständnis ihrer zugrunde liegenden Theorie und Funktionsweise zu erlangen, bevor man mit ihnen arbeitet. Bevor wir darauf näher eingehen, wollen wir kurz die Unterschiede zwischen lexikalischer Suche und Vektorsuche wiederholen, um besser zu verstehen, wie sie sich unterscheiden und wie sie sich ergänzen können.

Vektorsuche vs. lexikalische Suche

Eine einfache Möglichkeit, die Vektorsuche einzuführen, besteht darin, sie mit der herkömmlichen lexikalischen Suche zu vergleichen, die Ihnen wahrscheinlich bekannt ist. Vektorsuche, auch bekannt als semantische Suche, und lexikalische Suche funktionieren sehr unterschiedlich. Die lexikalische Suche ist die Art von Suche, die wir alle schon seit Jahren in Elasticsearch verwenden. Zusammengefasst versucht es nicht, die eigentliche Bedeutung der indizierten und abgefragten Daten zu verstehen, sondern bemüht sich vielmehr, die Literale der vom Benutzer in einer Suchanfrage eingegebenen Wörter oder deren Varianten (z. B. Stemming, Synonyme usw.) mithilfe von Ähnlichkeitsalgorithmen wie TF-IDF lexikalisch mit allen zuvor in der Datenbank indizierten Literalen abzugleichen.

Wie wir sehen können, werden die drei Dokumente oben links tokenisiert und analysiert. Anschließend werden die resultierenden Begriffe in einem invertierten Index indexiert, der die analysierten Begriffe einfach den Dokument-IDs zuordnet, die sie enthalten. Beachten Sie, dass alle Begriffe nur einmal vorkommen und keiner von ihnen in mehreren Dokumenten verwendet wird. Die Suche nach „netter Deutschlehrer“ liefert alle drei Dokumente mit unterschiedlichen Trefferzahlen, obwohl keines von ihnen die eigentliche Bedeutung der Suchanfrage erfasst.

Wie aus Abbildung 2 unten ersichtlich, wird es noch komplizierter bei Polysemie oder Homographen, d. h. Wörtern, die gleich geschrieben werden, aber unterschiedliche Bedeutungen haben (rechts, Palme, Fledermaus, gemein usw.). Nehmen wir das Wort „rechts“, das drei verschiedene Bedeutungen haben kann, und sehen wir, was passiert.

Die Suche nach „Ich habe nicht Recht“ liefert ein Dokument, das genau die gegenteilige Bedeutung des ersten Suchergebnisses hat. Wenn Sie nach genau denselben Begriffen suchen, diese aber in einer anderen Reihenfolge eingeben, um eine andere Bedeutung zu erhalten, z. B. „rechts abbiegen“ und „rechts abbiegen“, erhalten Sie genau dasselbe Ergebnis (d. h. das dritte Dokument „Take a right turn“). Zugegeben, unsere Suchanfragen sind stark vereinfacht und nutzen keine fortgeschritteneren Suchmethoden wie die Phrasensuche, aber dies verdeutlicht, dass die lexikalische Suche die wahre Bedeutung hinter dem, was indexiert und was gesucht wird, nicht versteht. Falls das noch nicht klar ist, keine Sorge, wir werden dieses Beispiel im dritten Artikel noch einmal aufgreifen, um zu sehen, wie die Vektorsuche in diesem Fall helfen kann.

Um der lexikalischen Suche gerecht zu werden: Wenn man die Kontrolle darüber hat, wie man seine strukturierten Daten indexiert (z. B. Mappings, Textanalyse, Datenaufnahmepipelines usw.) und wie man seine Abfragen gestaltet (z. B. geschickt formulierte DSL-Abfragen, Abfragetermanalyse usw.), kann man mit lexikalischen Suchmaschinen wahre Wunder vollbringen, daran besteht kein Zweifel! Die Erfolgsbilanz von Elasticsearch hinsichtlich seiner lexikalischen Suchfunktionen ist einfach erstaunlich. Was es erreicht hat und wie sehr es das Gebiet der lexikalischen Suche in den letzten Jahren popularisiert und verbessert hat, ist wirklich bemerkenswert.

Wenn es jedoch darum geht, Unterstützung für die Abfrage unstrukturierter Daten (z. B. Bilder, Videos, Audiodateien, Rohtexte usw.) für Benutzer bereitzustellen, die Freitextfragen stellen müssen, stößt die lexikalische Suche an ihre Grenzen. Darüber hinaus besteht die Suchanfrage manchmal nicht einmal aus Text, sondern kann beispielsweise ein Bild sein, wie wir gleich sehen werden. Der Hauptgrund, warum die lexikalische Suche in solchen Situationen unzureichend ist, liegt darin, dass unstrukturierte Daten weder indiziert noch auf die gleiche Weise abgefragt werden können wie strukturierte Daten. Bei der Verarbeitung unstrukturierter Daten kommt die Semantik ins Spiel. Was bedeutet Semantik? Ganz einfach, die Bedeutung!

Nehmen wir das einfache Beispiel einer Bildsuchmaschine (z. B. Google Bildersuche oder Lens). Sie ziehen ein Bild per Drag & Drop in das Fenster, und die semantische Suchmaschine von Google findet und liefert die ähnlichsten Bilder zu Ihrer Suchanfrage. In Abbildung 3 unten sehen wir auf der linken Seite das Bild eines Deutschen Schäferhundes und auf der rechten Seite alle ähnlichen Bilder, die abgerufen wurden, wobei das erste Ergebnis das gleiche Bild wie das bereitgestellte ist (d. h. das ähnlichste).

Auch wenn das für uns Menschen einfach und logisch klingt, ist es für Computer eine ganz andere Geschichte. Genau das ermöglicht und trägt die Vektorsuche dazu bei, es zu erreichen. Die durch die Vektorsuche freigesetzten Möglichkeiten sind enorm, wie die Welt in jüngster Zeit erfahren musste. Nun wollen wir die Motorhaube öffnen und entdecken, was sich darunter verbirgt.

Einbettungsvektoren

Wie wir bereits gesehen haben, können mit lexikalischen Suchmaschinen strukturierte Daten wie Texte leicht in Begriffe tokenisiert werden, die zum Zeitpunkt der Suche gefunden werden können, unabhängig von der wahren Bedeutung der Begriffe. Unstrukturierte Daten können jedoch verschiedene Formen annehmen, wie zum Beispiel große Binärobjekte (Bilder, Videos, Audiodateien usw.), und eignen sich überhaupt nicht für den gleichen Tokenisierungsprozess. Darüber hinaus besteht der gesamte Zweck der semantischen Suche darin, Daten so zu indexieren, dass sie anhand der Bedeutung, die sie repräsentieren, durchsucht werden können. Wie erreichen wir das? Die Antwort liegt in zwei Worten: Maschinelles Lernen! Oder genauer gesagt: Deep Learning!

Deep Learning ist ein spezielles Gebiet des maschinellen Lernens, das auf Modellen basiert, die auf künstlichen neuronalen Netzen mit mehreren Verarbeitungsschichten beruhen und schrittweise die wahre Bedeutung der Daten extrahieren können. Die Funktionsweise dieser neuronalen Netzwerkmodelle ist stark vom menschlichen Gehirn inspiriert. Abbildung 4 unten zeigt, wie ein neuronales Netzwerk mit seinen Eingabe- und Ausgabeschichten sowie mehreren verborgenen Schichten aussieht:

Die eigentliche Leistung neuronaler Netze besteht darin, dass sie in der Lage sind, ein einzelnes Stück unstrukturierter Daten in eine Folge von Gleitkommawerten umzuwandeln, die als Einbettungsvektoren oder einfach Einbettungen bekannt sind. Als Menschen können wir Vektoren recht gut verstehen, solange wir sie uns in einem zwei- oder dreidimensionalen Raum vorstellen. Jede Komponente des Vektors repräsentiert eine Koordinate in einer 2D xy-Ebene oder einem 3D xyz-Raum.

Allerdings können die Einbettungsvektoren, auf denen neuronale Netzwerkmodelle basieren, mehrere hundert oder sogar tausende Dimensionen aufweisen und lediglich einen Punkt in einem mehrdimensionalen Raum darstellen. Jede Vektordimension repräsentiert ein Merkmal oder eine Charakteristik der unstrukturierten Daten. Lassen Sie uns dies anhand eines Deep-Learning-Modells veranschaulichen, das Bilder in Einbettungsvektoren mit 2048 Dimensionen umwandelt. Dieses Modell würde das in Abbildung 3 verwendete Bild des Deutschen Schäferhundes in den in der folgenden Tabelle dargestellten Einbettungsvektor umwandeln. Beachten Sie, dass wir nur die ersten und letzten drei Elemente anzeigen, die Tabelle aber noch 2.042 weitere Spalten/Dimensionen enthalten würde.

Jede Spalte stellt eine Dimension des Modells dar und repräsentiert ein Merkmal oder eine Eigenschaft, die das zugrunde liegende neuronale Netzwerk zu modellieren versucht. Jeder dem Modell zugeführte Input wird danach charakterisiert, wie ähnlich dieser Input jeder der 2048 Dimensionen ist. Daher gibt der Wert jedes Elements im Einbettungsvektor die Ähnlichkeit des jeweiligen Eingangs mit einer bestimmten Dimension an. In diesem Beispiel können wir sehen, dass das Modell eine hohe Ähnlichkeit zwischen Hunden und Deutschen Schäferhunden sowie das Vorhandensein von blauem Himmel festgestellt hat.

Im Gegensatz zur lexikalischen Suche, bei der ein Begriff entweder gefunden wird oder nicht, ermöglicht die Vektorsuche eine viel bessere Einschätzung darüber, wie ähnlich ein unstrukturiertes Datenelement den einzelnen Dimensionen des Modells ist. Als solche dienen Einbettungsvektoren als hervorragende semantische Repräsentation unstrukturierter Daten.

Die geheime Soße

Nachdem wir nun wissen, wie unstrukturierte Daten von neuronalen Netzen des Deep Learning in Einbettungsvektoren zerlegt werden, die die Ähnlichkeit der Daten über eine hohe Anzahl von Dimensionen erfassen, müssen wir verstehen, wie der Abgleich dieser Vektoren funktioniert. Es stellt sich heraus, dass die Antwort ziemlich einfach ist. Nahe beieinander liegende Einbettungsvektoren repräsentieren semantisch ähnliche Datenteile. Wenn wir also eine Vektordatenbank abfragen, wird die Suchanfrage (Bild, Text usw.) zunächst mithilfe desselben Modells, das zur Indizierung aller unstrukturierten Daten verwendet wurde, in einen Einbettungsvektor umgewandelt. Das letztendliche Ziel ist es, die nächstgelegenen Nachbarvektoren zu diesem Anfragevektor zu finden. Daher müssen wir lediglich herausfinden, wie wir die „Distanz“ oder „Ähnlichkeit“ zwischen dem Abfragevektor und allen in der Datenbank indizierten Vektoren messen können, das ist im Prinzip alles.

Distanz und Ähnlichkeit

Zum Glück für uns ist die Messung des Abstands zwischen zwei Vektoren dank der Vektorarithmetik ein leicht zu lösendes Problem. Schauen wir uns also die gängigsten Distanz- und Ähnlichkeitsfunktionen an, die von modernen Vektorsuchdatenbanken wie Elasticsearch unterstützt werden. Achtung, es folgen mathematische Berechnungen!

L1-Distanz

Die L1-Distanz, auch Manhattan-Distanz genannt, zweier Vektoren x und y wird gemessen, indem die paarweise absolute Differenz aller ihrer Elemente summiert wird. Offensichtlich gilt: Je kleiner der Abstand d, desto näher liegen die beiden Vektoren beieinander. Die Formel ist recht einfach, wie unten ersichtlich:

Visuell lässt sich der L1-Abstand wie in Abbildung 5 unten dargestellt veranschaulichen:

Nehmen wir zwei Vektoren x und y, etwa x = (1, 2) und y = (4, 3), dann wäre der L1-Abstand beider Vektoren | 1 - 4 | + | 2 - 3 | = 4.

L2-Abstand

Die L2-Distanz, auch euklidische Distanz genannt, zweier Vektoren x und y wird gemessen, indem man zuerst die Quadrate der paarweisen Differenzen aller ihrer Elemente aufsummiert und dann die Quadratwurzel des Ergebnisses zieht. Es handelt sich im Grunde um den kürzesten Weg zwischen zwei Punkten (auch Hypotenuse genannt). Ähnlich wie bei L1 gilt: Je kleiner der Abstand d, desto näher liegen die beiden Vektoren beieinander.

Der Abstand L2 ist in Abbildung 6 unten dargestellt:

Wir verwenden dieselben beiden Beispielvektoren x und y, die wir bereits für die L1-Distanz verwendet haben, und können nun die L2-Distanz wie folgt berechnen $: (1 - 4)^2 + (2 - 3)^2 = 10$. Die Quadratwurzel aus 10 ergibt 3,16.

Linf-Distanz

Der Linf-Abstand (für L unendlich), auch Tschebyscheff- oder Schachbrettabstand genannt, zweier Vektoren x und y ist einfach definiert als der größte Abstand zwischen je zwei ihrer Elemente oder der größte Abstand, gemessen entlang einer der Achsen/Dimensionen. Die Formel ist sehr einfach und wird unten dargestellt:

Eine Darstellung der Linf-Distanz ist in Abbildung 7 unten zu sehen:

Nimmt man erneut die gleichen beiden Beispielvektoren x und y, so kann man den Abstand L unendlich berechnen als max ( | 1 - 4 | , | 2 - 3 | ) = max (3, 1) = 3.

Kosinusähnlichkeit

Im Gegensatz zu L1, L2 und Linf misst die Kosinusähnlichkeit nicht den Abstand zwischen zwei Vektoren x und y, sondern ihren relativen Winkel, d. h. ob sie beide ungefähr in die gleiche Richtung zeigen. Je höher die Ähnlichkeit s, desto „näher“ sind die beiden Vektoren beieinander. Die Formel ist wiederum sehr einfach und wird im Folgenden dargestellt:

Eine Möglichkeit zur Darstellung der Kosinusähnlichkeit zwischen zwei Vektoren ist in Abbildung 8 unten dargestellt:

Da Kosinuswerte immer im Intervall [-1, 1] liegen, bedeutet -1 entgegengesetzte Ähnlichkeit (d. h. ein Winkel von 180° zwischen den beiden Vektoren), 0 bedeutet unverwandte Ähnlichkeit (d. h. ein Winkel von 90°) und 1 bedeutet identisch (d. h. ein Winkel von 0°), wie in Abbildung 9 unten dargestellt:

Nehmen wir noch einmal die gleichen Beispielvektoren x und y und berechnen die Kosinusähnlichkeit mit der obigen Formel. Zunächst können wir das Skalarprodukt beider Vektoren berechnen: $(1 · 4) + (2 · 3) = 10$. Dann multiplizieren wir die Länge (auch Betrag genannt) beider Vektoren: $(1^2 + 2^2)^{1/2}+ (4^2 + 3^2)^{1/2} = 11.18034.$ Schließlich dividieren wir das Skalarprodukt durch die multiplizierte Länge 10 / 11,18034 = 0,894427 (d. h. ein Winkel von 26°), was recht nahe an 1 liegt, sodass beide Vektoren als ziemlich ähnlich betrachtet werden können.

Ähnlichkeit des Skalarprodukts

Ein Nachteil der Kosinusähnlichkeit besteht darin, dass sie nur den Winkel zwischen zwei Vektoren berücksichtigt, nicht aber deren Betrag (d. h. Länge). Das bedeutet, dass, wenn zwei Vektoren ungefähr in die gleiche Richtung zeigen, einer aber viel länger ist als der andere, beide trotzdem als ähnlich gelten. Die Ähnlichkeit mittels des Punktprodukts, auch Skalarprodukt oder inneres Produkt genannt, verbessert dies, indem sie sowohl den Winkel als auch die Länge der Vektoren berücksichtigt, was zu einer wesentlich genaueren Ähnlichkeitsmetrik führt.

Zur Berechnung der Ähnlichkeit des Skalarprodukts werden zwei äquivalente Formeln verwendet. Der erste ist derselbe, den wir bereits im Zähler der Kosinusähnlichkeit gesehen haben:

Die zweite Formel multipliziert einfach die Länge beider Vektoren mit dem Kosinus des Winkels zwischen ihnen:

Die Ähnlichkeit des Skalarprodukts wird in Abbildung 10 unten visualisiert:

Zum letzten Mal nehmen wir die Beispielvektoren x und y und berechnen ihre Skalarproduktähnlichkeit mit der ersten Formel, wie wir es zuvor für die Kosinusähnlichkeit getan haben, als (1 $·$4) + (2 $·$3) = 10.

Mit der zweiten Formel multiplizieren wir die Längen beider Vektoren: $(1^2 + 2^2)^{1/2}+ (4^2 + 3^2)^{1/2} = 11,18034$ und multiplizieren das mit dem Kosinus des 26°-Winkels zwischen den beiden Vektoren, und wir erhalten 11,18034 $·$cos(26°) = 10.

Eine wichtige Anmerkung: Wenn alle Vektoren vorher normalisiert werden (d. h. ihre Länge 1 beträgt), dann ist die Ähnlichkeit des Skalarprodukts genau gleich der Ähnlichkeit des Kosinus (weil |x| |y| = 1), d. h. dem Kosinus des Winkels zwischen den beiden Vektoren. Wie wir später sehen werden, ist die Normalisierung von Vektoren eine gute Vorgehensweise, um die Länge des Vektors irrelevant zu machen, sodass sich die Ähnlichkeit nur noch auf den Winkel konzentriert. Außerdem beschleunigt es die Distanzberechnung bei der Indizierung und Abfrage, was bei der Verarbeitung von Milliarden von Vektoren ein großes Problem darstellen kann.

Kurze Zusammenfassung

Wow, wir haben bisher eine Menge Informationen durchgearbeitet, also lasst uns kurz innehalten und eine kurze Zusammenfassung des aktuellen Stands geben. Wir haben gelernt, dass…

• Die semantische Suche basiert auf Deep-Learning-Neuronalnetzwerkmodellen, die sich durch ihre Fähigkeit auszeichnen, unstrukturierte Daten in mehrdimensionale Einbettungsvektoren umzuwandeln.
• …jede Dimension des Modells repräsentiert ein Merkmal oder eine Eigenschaft der unstrukturierten Daten.
• …ein Einbettungsvektor ist eine Sequenz von Ähnlichkeitswerten (einer für jede Dimension), die darstellen, wie ähnlich ein gegebenes Stück unstrukturierter Daten zu jeder Dimension ist.
• Je „näher“ zwei Vektoren beieinander liegen (d. h. je näher sie beieinander liegen), desto mehr repräsentieren sie semantisch ähnliche Konzepte.
• …Distanzfunktionen (L1, L2, Linf) ermöglichen es uns, zu messen, wie nahe zwei Vektoren beieinander liegen.
• …Ähnlichkeitsfunktionen (Kosinus und Skalarprodukt) ermöglichen es uns zu messen, wie stark zwei Vektoren in die gleiche Richtung zeigen.

Nun müssen wir uns als letztes noch mit der Vektorsuchmaschine selbst befassen. Wenn eine Anfrage eingeht, wird diese zunächst vektorisiert, und anschließend findet die Vektorsuchmaschine die nächstgelegenen Nachbarvektoren zu diesem Anfragevektor. Der Ansatz, bei dem man die Distanz oder Ähnlichkeit zwischen dem Abfragevektor und allen Vektoren in der Datenbank misst, funktioniert zwar bei kleinen Datensätzen, stößt aber schnell an seine Grenzen, wenn die Anzahl der Vektoren zunimmt. Anders formuliert: Wie können wir Millionen, Milliarden oder sogar Billionen von Vektoren indizieren und die nächsten Nachbarn des Anfragevektors in angemessener Zeit finden? Hier müssen wir clever vorgehen und optimale Wege finden, Vektoren zu indizieren, damit wir die nächsten Nachbarn so schnell wie möglich finden können, ohne die Genauigkeit zu sehr zu beeinträchtigen.

Vektorsuchalgorithmen und -techniken

Über die Jahre haben viele verschiedene Forschungsteams viel Mühe in die Entwicklung sehr ausgeklügelter Vektorsuchalgorithmen investiert. Hier werden wir die wichtigsten kurz vorstellen. Je nach Anwendungsfall eignen sich manche besser als andere.

Lineare Suche

Wir haben die lineare Suche bzw. die flache Indizierung bereits kurz angesprochen, als wir den Brute-Force-Ansatz erwähnten, bei dem der Abfragevektor mit allen in der Datenbank vorhandenen Vektoren verglichen wird. Während es bei kleinen Datensätzen gut funktionieren mag, nimmt die Leistung rapide ab, wenn die Anzahl der Vektoren und Dimensionen zunimmt (O(n)-Komplexität).

Zum Glück gibt es effizientere Ansätze, die als approximative Nächste-Nachbarn-Verfahren (ANN) bezeichnet werden. Dabei werden die Distanzen zwischen den Einbettungsvektoren vorab berechnet und ähnliche Vektoren so gespeichert und organisiert, dass sie nahe beieinander liegen, beispielsweise mithilfe von Clustern, Bäumen, Hashes oder Graphen. Solche Ansätze werden als „approximativ“ bezeichnet, weil sie in der Regel keine hundertprozentige Genauigkeit garantieren. Das ultimative Ziel ist es, entweder den Suchbereich so weit und so schnell wie möglich zu reduzieren , um sich nur auf Bereiche zu konzentrieren, die mit hoher Wahrscheinlichkeit ähnliche Vektoren enthalten, oder die Dimensionalität der Vektoren zu reduzieren.

K-dimensionale Bäume

Ein K-dimensionaler Baum, oder KD-Baum, ist eine Verallgemeinerung eines binären Suchbaums, der Punkte in einem k-dimensionalen Raum speichert und durch kontinuierliche Halbierung des Suchraums in kleinere linke und rechte Bäume funktioniert, in denen die Vektoren indiziert sind. Zum Zeitpunkt der Suche muss der Algorithmus lediglich einige Zweige des Baums um den Anfragevektor (den roten Punkt in Abbildung 11) besuchen, um den nächsten Nachbarn (den grünen Punkt in Abbildung 11) zu finden. Werden mehr als k Nachbarn angefordert, wird der gelbe Bereich so lange erweitert, bis der Algorithmus weitere Nachbarn findet.

Der größte Vorteil des KD-Baum-Algorithmus besteht darin, dass er es uns ermöglicht, uns schnell nur auf einige lokalisierte Zweige des Baums zu konzentrieren und somit die meisten Vektoren aus der Betrachtung auszuschließen. Allerdings nimmt die Effizienz dieses Algorithmus mit zunehmender Dimensionalität ab, da im Vergleich zu niedrigerdimensionalen Räumen viel mehr Zweige besucht werden müssen.

Invertierter Dateiindex

Der Ansatz des invertierten Dateiindex (IVF) ist ebenfalls ein Algorithmus zur Raumpartitionierung , der Vektoren, die nahe beieinander liegen, ihrem gemeinsamen Schwerpunkt zuordnet. Im zweidimensionalen Raum lässt sich dies am besten mit einem Voronoi-Diagramm veranschaulichen, wie in Abbildung 12 dargestellt:

Wir können sehen, dass der obige 2D-Raum in 20 Cluster unterteilt ist, deren Schwerpunkte jeweils als schwarze Punkte dargestellt sind. Alle Einbettungsvektoren im Raum werden dem Cluster zugeordnet, dessen Schwerpunkt ihnen am nächsten liegt. Bei der Suche ermittelt der Algorithmus zunächst den Cluster, auf den er sich konzentrieren soll, indem er den Schwerpunkt findet, der dem Abfragevektor am nächsten liegt. Anschließend kann er sich einfach auf diesen Bereich und gegebenenfalls auch auf die umliegenden Bereiche konzentrieren, um die nächsten Nachbarn zu finden.

Dieser Algorithmus leidet unter dem gleichen Problem wie KD-Bäume, wenn er in hochdimensionalen Räumen verwendet wird. Dies wird als Fluch der Dimensionalität bezeichnet und tritt auf, wenn das Volumen des Raums so stark zunimmt, dass alle Daten spärlich erscheinen und die Datenmenge, die für genauere Ergebnisse erforderlich wäre, exponentiell wächst. Bei spärlichen Daten wird es für diese Raumpartitionierungsalgorithmen schwieriger, die Daten in Cluster zu organisieren. Zum Glück gibt es andere Algorithmen und Techniken, die dieses Problem mindern, wie im Folgenden detailliert beschrieben.

Quantisierung

Bei der Quantisierung handelt es sich um einen kompressionsbasiertenAnsatz, der es uns ermöglicht, die Gesamtgröße der Datenbank zu reduzieren, indem die Präzision der Einbettungsvektoren verringert wird. Dies kann durch Skalarquantisierung (SQ) erreicht werden, indem die Gleitkomma-Vektorwerte in Ganzzahlwerte umgewandelt werden. Dadurch wird nicht nur die Größe der Datenbank um den Faktor 8 reduziert, sondern auch der Speicherverbrauch verringert und die Distanzberechnung zwischen Vektoren zur Suchzeit beschleunigt.

Eine weitere Technik ist die sogenannte Produktquantisierung (PQ). Dabei wird der Raum zunächst in niedrigdimensionale Unterräume unterteilt, und anschließend werden in jedem Unterraum Vektoren, die nahe beieinander liegen, mithilfe eines Clustering-Algorithmus (ähnlich wie bei k-Means) gruppiert.

Beachten Sie, dass sich die Quantisierung von der Dimensionsreduktion unterscheidet, bei der die Anzahl der Dimensionen reduziert wird, d. h. die Vektoren einfach kürzer werden.

Hierarchische navigierbare kleine Welten (HNSW)

Wenn es schon beim Lesen des Namens kompliziert aussieht, keine Sorge, es ist gar nicht so kompliziert! Kurz gesagt, Hierarchical Navigable Small Worlds ist ein mehrschichtiger, graphenbasierter Algorithmus, der sehr beliebt und effizient ist. Es wird von vielen verschiedenen Vektordatenbanken verwendet, darunter Apache Lucene. Eine konzeptionelle Darstellung von HNSW ist in Abbildung 13 unten zu sehen.

Auf der obersten Ebene sehen wir einen Graphen von sehr wenigen Vektoren, die die längsten Verbindungen untereinander aufweisen, d. h. einen Graphen von verbundenen Vektoren mit der geringsten Ähnlichkeit. Je tiefer wir in die unteren Schichten vordringen, desto mehr Vektoren finden wir und desto dichter wird der Graph, mit immer mehr Vektoren, die näher beieinander liegen. In der untersten Schicht können wir alle Vektoren finden, wobei die ähnlichsten Vektoren am nächsten beieinander liegen.

Bei der Suche beginnt der Algorithmus in der obersten Ebene an einem beliebigen Einstiegspunkt und findet den Vektor, der dem Abfragevektor (dargestellt durch den grauen Punkt) am nächsten liegt. Dann geht es eine Ebene tiefer und wiederholt den gleichen Vorgang, ausgehend vom gleichen Vektor, den es in der darüber liegenden Ebene hinterlassen hat, und so weiter, Ebene für Ebene, bis es die unterste Ebene erreicht und den nächsten Nachbarn zum Anfragevektor findet.

Locality-Sensitive Hashing (LSH)

In ähnlicher Weise wie alle anderen bisher vorgestellten Ansätze zielt das lokalitätssensitive Hashing darauf ab, den Suchraum drastisch zu reduzieren, um die Abrufgeschwindigkeit zu erhöhen. Bei dieser Technik werden Einbettungsvektoren in Hashwerte umgewandelt, wobei die Ähnlichkeitsinformationen erhalten bleiben, sodass der Suchraum letztendlich zu einer einfachen Hashtabelle wird, die nachgeschlagen werden kann, anstatt zu einem Graphen oder Baum, der durchlaufen werden muss. Der Hauptvorteil von Hash-basierten Methoden besteht darin, dass Vektoren mit einer beliebigen (großen) Anzahl von Dimensionen auf Hashes fester Größe abgebildet werden können, was die Abrufzeit enorm beschleunigt, ohne dabei zu viel Genauigkeit einzubüßen.

Es gibt viele verschiedene Möglichkeiten, Daten im Allgemeinen und Vektoren im Besonderen zu hashen, aber dieser Artikel wird nicht auf die Details jeder einzelnen eingehen. Konventionelle Hash-Methoden erzeugen üblicherweise sehr unterschiedliche Hashwerte für Daten, die sich sehr ähnlich erscheinen. Da Einbettungsvektoren aus Gleitkommazahlen bestehen, nehmen wir zwei Gleitkommazahlen als Beispiel, die in der Vektorarithmetik als sehr nahe beieinander liegen (z. B. 0,73 und 0,74), und wenden einige gängige Hash-Funktionen darauf an. Anhand der unten stehenden Ergebnisse wird deutlich, dass gängige Hash-Funktionen die Ähnlichkeit zwischen den Eingaben nicht erhalten.

Während herkömmliche Hash-Methoden versuchen, Hash-Kollisionen zwischen ähnlichen Datenteilen zu minimieren , ist das Hauptziel des lokalitätssensitiven Hashings genau das Gegenteil, d. h. Hash-Kollisionen zu maximieren, damit ähnliche Daten mit hoher Wahrscheinlichkeit im selben Bucket landen. Dadurch werden Einbettungsvektoren, die in einem mehrdimensionalen Raum nahe beieinander liegen, zu einem Wert fester Größe gehasht, der in denselben Bucket fällt. Da LSH es ermöglicht, dass die gehashten Vektoren ihre Nähe zueinander beibehalten, ist diese Technik sehr nützlich für Datenclustering und Nächste-Nachbar-Suchen.

Die eigentliche Arbeit findet beim Indizieren statt, wenn die Hashwerte berechnet werden müssen. Bei der Suche hingegen müssen wir nur den Abfragevektor hashen, um den Bucket zu finden, der die nächstgelegenen Einbettungsvektoren enthält. Sobald der geeignete Kandidaten-Bucket gefunden ist, findet üblicherweise eine zweite Runde statt, um die nächstgelegenen Nachbarvektoren zum Anfragevektor zu ermitteln.

Lasst uns abschließen

Um die Vektorsuche einzuführen, mussten wir in diesem Artikel einiges an Stoff behandeln. Nach dem Vergleich der Unterschiede zwischen lexikalischer Suche und Vektorsuche haben wir gelernt, wie neuronale Netzwerkmodelle des Deep Learning die Semantik unstrukturierter Daten erfassen und deren Bedeutung in hochdimensionale Einbettungsvektoren transkodieren, eine Folge von Gleitkommazahlen, die die Ähnlichkeit der Daten entlang jeder Dimension des Modells darstellen. Es ist außerdem erwähnenswert, dass Vektorsuche und lexikalische Suche keine konkurrierenden, sondern sich ergänzende Information-Retrieval-Techniken sind (wie wir im dritten Teil dieser Reihe sehen werden, wenn wir uns mit der hybriden Suche befassen).

Anschließend stellten wir einen grundlegenden Baustein der Vektorsuche vor, nämlich die Distanz- (und Ähnlichkeits-) Funktionen, die es uns ermöglichen, die Nähe zweier Vektoren zu messen und die Ähnlichkeit der von ihnen repräsentierten Konzepte zu beurteilen.

Abschließend haben wir verschiedene Varianten der beliebtesten Vektorsuchalgorithmen und -techniken betrachtet, die auf Bäumen, Graphen, Clustern oder Hashes basieren und deren Ziel es ist, schnell einen bestimmten Bereich des mehrdimensionalen Raums einzugrenzen, um die nächsten Nachbarn zu finden, ohne den gesamten Raum durchsuchen zu müssen, wie es bei einer linearen Brute-Force-Suche der Fall wäre.

Wenn Ihnen gefällt, was Sie lesen, sollten Sie unbedingt auch die anderen Teile dieser Serie lesen:

• Teil 2: So richten Sie die Vektorsuche in Elasticsearch ein
• Teil 3: Hybride Suche mit Elasticsearch

Häufige Fragen