Zum Inhalt
wannacode

Semantische Suche: die k nächsten

Kurz gesagt: Die semantische Suche vergleicht den Vektor der Frage mit den Vektoren der Texte und gibt die k nächsten per Kosinus zurück, auch ohne gemeinsames Wort.

Problem

Eine Antwort reicht nicht

Die Antwortbasis des Supports hat jetzt sechs Texte:

// ein Text aus der Antwortbasis: Thema und Text
record Doc(String topic, String text) {}


// ein gefundener Text und seine Ähnlichkeit zur Frage
record Hit(Doc doc, double score) {}


// ein Eintrag im Index: der Text und sein Vektor
record Entry(Doc doc, int[] vector) {}


// die Antwortbasis des Supports
static final List<Doc> DOCS = List.of(
    new Doc("lieferung", "die lieferung dauert bis zu zwei tagen"),
    new Doc("rückgabe", "gib die ware innerhalb von 14 tagen zurück und erhalte das geld"),
    new Doc("zahlung", "zahle mit karte oder per nachnahme"),
    new Doc("preis", "die lieferung an eine adresse kostet 5 euro und an eine filiale 3 euro"),
    new Doc("abgelehnt", "wenn die bank die zahlung ablehnt versuche eine andere karte oder zahle per nachnahme"),
    new Doc("garantie", "die garantie beträgt zwei jahre ab dem kauf"));


// die Fragen der Kunden
static final String[] QUESTIONS = {
    "wann kommt mein paket an",
    "ich will die bestellung zurückgeben",
    "was kostet die lieferung an eine filiale",
};

Der Bot aus der Lektion zu Vektoren macht aus jedem Text einen Vektor und gibt nur den zurück, der der Frage am nächsten ist:

Ausgabe
wann kommt mein paket an → lieferung: die lieferung dauert bis zu zwei tagen
ich will die bestellung zurückgeben → lieferung: die lieferung dauert bis zu zwei tagen
was kostet die lieferung an eine filiale → preis: die lieferung an eine adresse kostet 5 euro und an eine filiale 3 euro

Die erste und die dritte Frage sind in Ordnung. Der zweite Kunde will die Bestellung zurückgeben und bekommt die Lieferzeit. Der Text zur Rückgabe ist nicht weit weg: Er steht an zweiter Stelle, mit 0,573 gegen 0,775. Aber der Bot schaut nur auf den ersten.

Die Idee

Die k nächsten

Die Suche sollte nicht alles auf einen Text setzen. Sie soll die ersten k zurückgeben: sortiert vom nächsten, zusammen mit der Ähnlichkeit.

Das ist die semantische Suche:

  1. Jeder Text in der Basis wird zu einem Vektor. Die Vektoren werden einmal berechnet und neben den Texten aufbewahrt. Das ist der Index.
  2. Die Frage wird im selben Raum zu einem Vektor.
  3. Der Kosinus der Frage zu jedem Eintrag im Index.
  4. Sortieren vom größten Kosinus und die ersten k.

Das sind die nächsten Nachbarn aus der Lektion zu k-NN. Dort waren die Nachbarn vergangene Bestellungen, hier sind es Texte. Das Maß ist der Kosinus, nicht der Abstand.

Die k gefundenen Texte sind nicht die Antwort. Sie gehen an das Sprachmodell, das sie liest und aus ihnen antwortet. Das ist der nächste Schritt.

Sieh es dir an

Der Index

Die Vektoren kommen aus demselben Raum wie in der Lektion zu Vektoren: die acht häufigsten Wörter im Text des Shops. Der Index ist eine Liste von Einträgen: der Text und sein Vektor.

// der Index: der Vektor jedes Textes, einmal berechnet
static List<Entry> buildIndex(Space space) {
    List<Entry> index = new ArrayList<>();
    for (Doc d : DOCS)
        index.add(new Entry(d, space.ofText(d.text())));
    return index;
}
Space space = new Space(TEXT, STOP, 8);
List<Entry> index = buildIndex(space);
for (Entry e : index)
    System.out.printf("%-10s%s%n", e.doc().topic(), Arrays.toString(e.vector()));
Ausgabe
lieferung [2, 2, 1, 1, 2, 0, 1, 0]
rückgabe  [1, 0, 5, 1, 3, 2, 1, 0]
zahlung   [0, 0, 0, 0, 0, 1, 0, 3]
preis     [12, 4, 0, 2, 1, 0, 0, 0]
abgelehnt [0, 0, 0, 0, 0, 6, 0, 6]
garantie  [0, 0, 0, 0, 0, 0, 0, 0]

„zahlung“ und „abgelehnt“ haben nur die Achsen „karte“ und „zahlung“. „garantie“ besteht nur aus Nullen: Ihre Wörter kommen im Text des Shops nicht vor (oder gelten als Füllwörter), und das kleine Modell weiß nicht, wovon sie handelt. Darauf kommen wir bei „Wann es wehtut“ zurück.

Sieh es dir an

Die ersten k

Die Suche nimmt den Vektor der Frage, berechnet den Kosinus zu jedem Eintrag, sortiert vom nächsten und gibt die ersten k zurück:

// die ersten k Texte, die dem Fragevektor am nächsten sind
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).reversed());
    return hits.subList(0, Math.min(k, hits.size()));
}
for (String q : QUESTIONS) {
    System.out.println(q);
    int[] v = space.ofText(q);
    for (Hit h : search(index, v, 3)) {
        String topic = h.doc().topic();
        System.out.printf("  %-10s%.3f%n", topic, h.score());
    }
}
Ausgabe
wann kommt mein paket an
  lieferung 0.738
  rückgabe  0.510
  preis     0.286
ich will die bestellung zurückgeben
  lieferung 0.775
  rückgabe  0.573
  preis     0.259
was kostet die lieferung an eine filiale
  preis     0.945
  lieferung 0.867
  rückgabe  0.282

Bei der Rückgabe ist der erste Text weiterhin „lieferung“, aber der zweite ist „rückgabe“. Mit k = 3 ist er unter den Treffern. Hier dasselbe als Bild. Die Vektoren haben 8 Dimensionen, darum behält das Bild nur, wie weit jeder Text von der Frage entfernt ist:

// die ersten k Texte, die dem Fragevektor am nächsten sind
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).reversed());
    return hits.subList(0, Math.min(k, hits.size()));
}


int[] v = space.ofText("ich will die bestellung zurückgeben");
for (Hit h : search(index, v, 3)) {
    String topic = h.doc().topic();
    System.out.printf("  %-10s%.3f%n", topic, h.score());
}
Schritt für Schritt, in Worten
  1. Die Frage „ich will die bestellung zurückgeben“ wird zu einem Vektor: [0, 2, 1, 0, 2, 0, 0, 0]. Sie ist der Punkt in der Mitte.
  2. Der Kosinus zu jedem Eintrag im Index. Je größer der Kosinus, desto näher der Punkt. Ein Text ohne gemeinsame Achse liegt auf dem äußeren Kreis.
  3. Vom nächsten aus sortiert: „lieferung“, „rückgabe“, „preis“…
  4. k = 1: nur „lieferung“ (0,775). Der Kunde will die Bestellung zurückgeben und bekommt die Lieferzeit.
  5. k = 2: „rückgabe“ (0,573) kommt dazu. Der richtige Text ist unter den Treffern.
  6. k = 3: auch „preis“ (0,259). Mehr Texte: größere Chance, dass der richtige dabei ist, aber auch mehr Rauschen.
  7. Die k = 3 nächsten: „lieferung“, „rückgabe“, „preis“. Der richtige Text, „rückgabe“, steht an zweiter Stelle, deshalb gibt die Suche k Texte zurück, nicht einen.

Probier es aus

Sag die Ausgabe voraus

Der Kunde schreibt „kann ich eine andere farbe haben“. Kein Wort davon steht im Text des Shops. Was gibt das Programm aus?

int[] v = space.ofText("kann ich eine andere farbe haben");
for (Hit h : search(index, v, 3))
    System.out.printf("%s %.3f%n", h.doc().topic(), h.score());
Antwort

Probier es aus

Ergänze

Die Suche muss von der größten Ähnlichkeit zur kleinsten sortieren. Was gehört an die Stelle von ___?

// die ersten k Texte, die dem Fragevektor am nächsten sind
static List<Hit> search(List<Entry> index, int[] v, int k) {
    List<Hit> hits = new ArrayList<>();
    for (Entry e : index)
        hits.add(new Hit(e.doc(), cosine(v, e.vector())));
    hits.sort(Comparator.comparing(Hit::score).());
    return hits.subList(0, Math.min(k, hits.size()));
}

Probier es aus

Finde den Fehler

Ein Kollege schreibt die Suche und bekommt für „ich will die bestellung zurückgeben“ „zahlung“, „abgelehnt“ und „garantie“: alles Texte mit der Ähnlichkeit 0,000. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wie groß soll k sein

Mit k = 1 verpasst der Bot die Rückgabe. Mit k = 3 ist der richtige Text dabei, aber es kommen auch andere: Bei „wann kommt mein paket an“ sind auch „rückgabe“ (0,510) und „preis“ (0,286) dabei, die die Frage nicht beantworten.

  • Ein kleines k verpasst den richtigen Text, wenn er nicht der erste ist.
  • Ein großes k bringt Rauschen. Jeder Text kommt in den Prompt: Das sind Tokens, die Geld kosten und Platz im Kontextfenster. Und das Modell kann sich an den falschen Text halten.
  • Eine Schwelle. Ein Text unter einer festgelegten Ähnlichkeit wird gar nicht zurückgegeben. So bekommt eine Frage wie „kann ich eine andere farbe haben“ nicht drei zufällige Texte, sondern „nicht sicher“.

Echte Systeme nehmen meist zwischen 3 und 10 Texte, aber das ist nur ein Beispiel. Wie viele genau, misst du mit einem Testset aus Fragen, bei denen du den richtigen Text kennst. Das ist das Bewerten der Suche.

Die Idee

Wann es wehtut

  • Exakte Dinge. „wo ist bestellung 10234“: Die Nummer ist ein unbekanntes Wort, und ihr Vektor besteht aus Nullen. Vektoren fangen Bedeutung ein, keine exakten Zeichenketten. Eine Bestellnummer, ein Produktcode oder eine E-Mail wird in der Datenbank per Gleichheit gesucht. Für Namen und seltene Wörter hilft eine Suche nach Wörtern, und echte Systeme mischen oft beides. Suchmaschinen über Wörter findest du in der Lektion zur Textsuche.
  • Wörter, die das Modell nicht kennt. „garantie“ hat zu jeder Frage die Ähnlichkeit 0,000 und wird nie gefunden. Ein echtes Modell kennt viel mehr Wörter, aber dasselbe passiert mit dem Jargon einer Firma und mit neuen Produktnamen.
  • Jede Frage geht durch den ganzen Index. Bei sechs Texten sind das sechs Kosinus. Bei einer Million Texten mit Vektoren aus je 1.024 Zahlen sind es etwa eine Milliarde Multiplikationen pro Frage (eine Beispielzahl). Darum suchen Vektordatenbanken näherungsweise: Sie prüfen einen kleinen Teil der Einträge und finden fast immer dieselben k. Du findest sie in der Lektion zu Vektordatenbanken. Eine solche Datenbank zu betreiben und zu pflegen ist eine Aufgabe für ZeroToOps.
  • Der Index wird alt. Änderst du einen Text, wird sein Vektor neu berechnet. Wechselst du das Modell für Vektoren, wird der ganze Index neu berechnet: Vektoren aus zwei Modellen lassen sich nicht miteinander vergleichen.
  • Ein langes Dokument, ein Vektor. Der Vektor einer ganzen Seite ist eine Mischung aus allen ihren Themen. Wie ein Dokument in Abschnitte geschnitten wird, steht in der nächsten Lektion.
Genauer, für Neugierige

Die echten Werkzeuge. Die Vektoren kommen aus einem Modell für Vektoren: Es wird wie die anderen Modelle über eine API aufgerufen oder lokal betrieben, meist aus Python. Sie liegen in einer Vektordatenbank (zum Beispiel pgvector in PostgreSQL), die einen Index für die näherungsweise Suche hat. In Python rechnet man mit Vektoren meist mit NumPy. Die ML-Praxis läuft überwiegend in Python, aber die Suche wird aus jeder Sprache aufgerufen: Die Anfrage an die Datenbank ist dieselbe. Hier ist alles von Hand gemacht, damit jede Zahl sichtbar ist.

Alles sortieren oder nur die ersten k. Das Sortieren von n Einträgen kostet O(n log n). Wenn k klein ist, reicht ein Heap aus k Elementen: Jeder Eintrag wird mit dem schwächsten darin verglichen, und das sind O(n log k) Schritte. Den Heap findest du in der Lektion zur Prioritätswarteschlange.

Gleiche Ähnlichkeiten. Die Sortierung ist in allen vier Sprachen stabil: Gleiche Werte bleiben in der Reihenfolge, die sie in der Basis haben. Darum gibt „Sag die Ausgabe voraus“ die ersten drei Texte aus. Verlass dich nicht auf diese Reihenfolge für die Bedeutung: Gleiche Ähnlichkeiten heißen, dass das Modell die Texte nicht unterscheiden kann.

Der Abstand im Bild. Der Punkt jedes Textes ist √(2 − 2·cos) von der Frage entfernt. Das ist der Abstand zwischen den Spitzen der beiden Vektoren, wenn beide die Länge 1 haben. Nach ihm zu sortieren ergibt dieselbe Reihenfolge wie nach dem Kosinus.

Übung

Höchstens k, aber nur die nahen

Löse die Aufgabe in deinem Editor.

Schreibe eine Funktion, die höchstens k Texte zurückgibt, aber nur die mit der Ähnlichkeit von mindestens 0,5. Bleibt keiner übrig, gibt sie „nicht sicher, ich gebe an einen Kollegen weiter“ zurück. Probiere sie mit k = 3 für „wann kommt mein paket an“, „ich will die bestellung zurückgeben“ und „kann ich eine andere farbe haben“.

Ausgabe
wann kommt mein paket an: lieferung 0.738, rückgabe 0.510
ich will die bestellung zurückgeben: lieferung 0.775, rückgabe 0.573
kann ich eine andere farbe haben: nicht sicher, ich gebe an einen Kollegen weiter

Die erste Frage behält „lieferung“ und „rückgabe“, die Rückgabe mit 0,510 nur knapp über der Schwelle. Die zweite behält ebenfalls „lieferung“ und „rückgabe“, und die dritte behält nichts und geht an einen Menschen.

Weitere Aufgaben

  • Ein Heap statt einer Sortierung. Baue die Suche mit einem Heap aus k Elementen. Die Ausgabe muss dieselbe sein.
  • Der Abstand zwischen dem ersten und dem zweiten. Gib den Unterschied der Ähnlichkeit zwischen dem ersten und dem zweiten Text aus. Ein kleiner Abstand heißt, dass die Suche nicht sicher ist.

Test

Teste dich

1. Warum gibt die Suche k Texte zurück und nicht nur den nächsten?
2. Was hält der Index?
3. In der Frage steht kein einziges Wort, das das Modell kennt. Was gibt die Suche mit k = 3 zurück?
4. Der Kunde schreibt „wo ist bestellung 10234“. Warum hilft die semantische Suche hier nicht?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·