Das nächste Token vorhersagen in Java

Problem

Ein Anfang, drei Antworten

Der Support-Bot soll Antworten fortsetzen. Ein Kollege startet denselben Anfang, „die bestellung“, dreimal mit einem anderen Seed für den Generator. Das sind die drei Antworten:

var table = countNext(TEXT);
for (int seed : new int[] {2026, 34567, 12345})
    System.out.println("Seed " + seed + ": " + generate(table, "die bestellung", 1, 100, new Rng(seed)));

Seed 2026: die bestellung trifft innerhalb von 14 tagen ein
Seed 34567: die bestellung ist ab 50 euro
Seed 12345: die bestellung trifft morgen zu spät

Die erste klingt vernünftig. Die zweite hört mitten im Satz auf: „ist ab 50 Euro“, und was dann? Die dritte widerspricht sich: Die Bestellung trifft „morgen“ ein, aber „zu spät“. Jeweils zwei benachbarte Wörter stammen in allen dreien aus dem Shop-Text. Und alle drei kommen aus demselben Programm, das nirgends eine Antwort nachschlägt: Es schreibt Wort für Wort.

Woher weiß es, welches Wort es setzen soll? Und warum ist es jedes Mal anders?

Die Idee

Die Wahrscheinlichkeit des nächsten Wortes

Ein Sprachmodell bekommt Text und liefert eine Wahrscheinlichkeit für jedes mögliche nächste Token. Mehr nicht: Es weiß nicht, was eine Bestellung ist, es weiß nur, was gewöhnlich worauf folgt.

Text entsteht in einer Schleife:

Das Modell liefert die Wahrscheinlichkeiten des nächsten Tokens.
Eines wird nach ihnen gewählt.
Es wird an den Text angehängt, und alles wiederholt sich, bis das Ende oder das Limit erreicht ist.

Die Wahl ist ein eigener Schritt und nicht Teil des Modells. Deshalb kann dasselbe Modell verschiedene Antworten geben.

Das Modell in dieser Lektion ist das kleinstmögliche: eine Tabelle, wie oft jedes Wort direkt nach jedem Wort kam. Es schaut nur auf das letzte Wort und zählt ganze Wörter, keine Tokens. Echte Modelle sind neuronale Netze, die den ganzen Text ansehen, aber sie liefern dasselbe: die Wahrscheinlichkeiten des nächsten Tokens.

Sieh es dir an

Die Tabelle: welches Wort nach welchem

Der Shop-Text ist derselbe wie in der Lektion über Tokens. Für jeden Satz zählen wir jedes Paar benachbarter Wörter. Der Punkt „.“ markiert das Satzende, damit das Modell weiß, wann es aufhören soll.

// ein mögliches nächstes Wort und seine Wahrscheinlichkeit
record Choice(String word, double p) {}

// wie oft jedes Wort direkt nach jedem Wort kommt; "." beendet einen Satz
static Map<String, Map<String, Integer>> countNext(String[] text) {
    Map<String, Map<String, Integer>> table = new LinkedHashMap<>();
    for (String line : text) {
        String[] w = (line + " .").split(" ");
        for (int i = 0; i + 1 < w.length; i++)
            table.computeIfAbsent(w[i], key -> new LinkedHashMap<>())
                 .merge(w[i + 1], 1, Integer::sum);
    }
    return table;
}

Die Wahrscheinlichkeit des nächsten Wortes ist seine Anzahl geteilt durch die Summe. Schau vorerst nur auf t = 1 und „alle Wörter“: Dann ist das Gewicht die Anzahl selbst. Die Temperatur t und k kommen weiter unten.

// die k häufigsten, Gewicht Anzahl^(1/t) / Summe
static List<Choice> nextWords(Map<String, Integer> counts,
                              double t, int k) {
    List<String> words = new ArrayList<>(counts.keySet());
    words.sort((a, b) -> counts.get(b) - counts.get(a));
    List<String> top =
        words.subList(0, Math.min(k, words.size()));
    double total = 0;
    for (String w : top)
        total += Math.pow(counts.get(w), 1 / t);
    List<Choice> choices = new ArrayList<>();
    for (String w : top) {
        double weight = Math.pow(counts.get(w), 1 / t);
        choices.add(new Choice(w, weight / total));
    }
    return choices;
}

var table = countNext(TEXT);
Map<String, Integer> counts = table.get("die");
System.out.println("nach \"die\":");
for (Choice c : nextWords(counts, 1, 100))
    System.out.printf("%-11s%2d  %5.1f%%%n", c.word(), counts.get(c.word()), c.p() * 100);

nach "die":
lieferung   6   35.3%
ware        4   23.5%
zahlung     3   17.6%
bestellung  2   11.8%
rückgabe    1    5.9%
bank        1    5.9%

Nach „die“ kommen im Text sechs verschiedene Wörter vor, insgesamt 17 Mal. „lieferung“ ist 6 davon: 35,3 %. Das ist das Sprachmodell: Für „die“ sagt es „lieferung“ mit 35,3 %, „ware“ mit 23,5 %, „zahlung“ mit 17,6 %, „bestellung“ mit 11,8 % und je 5,9 % für „rückgabe“ und „bank“.

Sieh es dir an

Die Wahl: eine Zahl von 0 bis 1

Wie wählt man ein Wort mit der Wahrscheinlichkeit 35,3 %? Der Generator mit Seed liefert eine Zahl r von 0 bis 1. Die Balken der Wörter stehen nebeneinander: „lieferung“ von 0 bis etwa 0,35, „ware“ von 0,35 bis etwa 0,59 und so weiter. Das Wort, in dessen Balken r fällt, ist das gewählte.

class Rng {
    private long state;

    Rng(long seed) {
        state = seed;
    }

    // die nächste Zahl zwischen 0 und 1; derselbe Seed liefert dieselben Zahlen
    double next() {
        state = state * 48271 % 2147483647;
        return (double) state / 2147483647;
    }
}

// eine Zahl von 0 bis 1 fällt in einen der Balken
static String pick(List<Choice> choices, Rng rng) {
    double r = rng.next();
    double sum = 0;
    for (Choice c : choices) {
        sum += c.p();
        if (r < sum)
            return c.word();
    }
    return choices.get(choices.size() - 1).word();
}

Die Generierung wiederholt das Wort für Wort vom Anfang an, bis „.“ kommt oder 12 Wörter erreicht sind:

// setze den Text Wort für Wort fort bis "." oder 12 Wörter
static String generate(Map<String, Map<String, Integer>> table,
                       String start, double t, int k, Rng rng) {
    List<String> text = new ArrayList<>(List.of(start.split(" ")));
    String word = text.get(text.size() - 1);
    while (text.size() < 12) {
        word = pick(nextWords(table.get(word), t, k), rng);
        if (word.equals("."))
            break;
        text.add(word);
    }
    return String.join(" ", text);
}

Nimmst du immer das wahrscheinlichste Wort (k = 1), hat der Generator nichts zu wählen, und die Antwort ist bei jedem Seed dieselbe:

var table = countNext(TEXT);
for (int seed : new int[] {2026, 34567, 12345})
    System.out.println("Seed " + seed + ": " + generate(table, "die bestellung", 1, 1, new Rng(seed)));

Seed 2026: die bestellung trifft innerhalb von drei tagen ein
Seed 34567: die bestellung trifft innerhalb von drei tagen ein
Seed 12345: die bestellung trifft innerhalb von drei tagen ein

Bei zufälliger Wahl hängt die Antwort vom Seed ab. Derselbe Seed liefert aber dieselben Zahlen, also auch dieselbe Antwort:

var table = countNext(TEXT);
for (int seed : new int[] {2026, 2026, 34567})
    System.out.println("Seed " + seed + ": " + generate(table, "die bestellung", 1, 100, new Rng(seed)));

Seed 2026: die bestellung trifft innerhalb von 14 tagen ein
Seed 2026: die bestellung trifft innerhalb von 14 tagen ein
Seed 34567: die bestellung ist ab 50 euro

Deshalb waren die drei Antworten am Anfang verschieden: Jeder Seed liefert andere Zahlen und damit andere Wörter.

Probier es aus

Sag die Ausgabe voraus

Nach „lieferung“ hat der Text fünf Fortsetzungen. Was gibt das Programm mit k = 1 aus?

var table = countNext(TEXT);
for (Choice c : nextWords(table.get("lieferung"), 1, 1))
    System.out.printf("%s %.1f%%%n", c.word(), c.p() * 100);

Antwort

an 42.9%
ist 14.3%
dauert 14.3%
kam 14.3%
war 14.3%

an 100.0%

an 42.9%

Die Idee

Temperatur und Top-k

Die Wahl hat zwei Regler, die auch echte Modelle haben:

Temperatur t: Das Gewicht ist Anzahl^(1/t). Bei t unter 1 werden die häufigen Wörter noch wahrscheinlicher, und die Antwort ist vorhersagbarer. Bei t über 1 gleichen sich die Wahrscheinlichkeiten an, und seltene Wörter kommen öfter vor.
Top-k: Nur die k häufigsten Wörter bleiben, die anderen können nicht gewählt werden. Die Summe wird nur über sie gebildet, also ist sie wieder 100 %.

var table = countNext(TEXT);
Map<String, Integer> counts = table.get("die");
double[] temps = {0.5, 1.0, 2.0};
List<List<Choice>> rows = new ArrayList<>();
StringBuilder head = new StringBuilder(" ".repeat(11));
for (double t : temps) {
    rows.add(nextWords(counts, t, 100));
    head.append(String.format("%7s", "t=" + (t == (int) t ? String.valueOf((int) t) : String.valueOf(t))));
}
System.out.println(head);
for (int i = 0; i < counts.size(); i++) {
    StringBuilder line = new StringBuilder(String.format("%-11s", rows.get(0).get(i).word()));
    for (List<Choice> row : rows)
        line.append(String.format("%6.1f%%", row.get(i).p() * 100));
    System.out.println(line);
}

             t=0.5    t=1    t=2
lieferung    53.7%  35.3%  25.5%
ware         23.9%  23.5%  20.8%
zahlung      13.4%  17.6%  18.1%
bestellung    6.0%  11.8%  14.7%
rückgabe      1.5%   5.9%  10.4%
bank          1.5%   5.9%  10.4%

Bei t = 0,5 ist „lieferung“ 53,7 %, bei t = 2 nur 25,5 %. Die Wörter, die nur einmal vorkommen („rückgabe“ und „bank“), haben 1,5 %, 5,9 % und 10,4 %: Je höher die Temperatur, desto öfter wählt das Modell sie.

Hier sind die Balken nach „die“ bei den drei Temperaturen, dann mit k = 3 und die Wahl mit einer Zahl vom Generator:

// die k häufigsten, Gewicht Anzahl^(1/t) / Summe
static List<Choice> nextWords(Map<String, Integer> counts,
                              double t, int k) {
    List<String> words = new ArrayList<>(counts.keySet());
    words.sort((a, b) -> counts.get(b) - counts.get(a));
    List<String> top =
        words.subList(0, Math.min(k, words.size()));
    double total = 0;
    for (String w : top)
        total += Math.pow(counts.get(w), 1 / t);
    List<Choice> choices = new ArrayList<>();
    for (String w : top) {
        double weight = Math.pow(counts.get(w), 1 / t);
        choices.add(new Choice(w, weight / total));
    }
    return choices;
}

// eine Zahl von 0 bis 1 fällt in einen der Balken
static String pick(List<Choice> choices, Rng rng) {
    double r = rng.next();
    double sum = 0;
    for (Choice c : choices) {
        sum += c.p();
        if (r < sum)
            return c.word();
    }
    return choices.get(choices.size() - 1).word();
}

Schritt für Schritt, in Worten

Nach „die“ stehen im Text 6 Wörter. Ein Balken ist die Anzahl geteilt durch alle 17: „lieferung“ ist 6 von 17, 35,3 %.
t = 0,5: Das Gewicht ist Anzahl². Das häufige Wort wird noch wahrscheinlicher: „lieferung“ 53,7 %.
t = 2: Das Gewicht ist √Anzahl. Die Balken gleichen sich an: „lieferung“ 25,5 %, „bank“ 10,4 %.
t = 1, k = 3: Nur die drei häufigsten bleiben, und zusammen sind sie wieder 100 %: 46,2 %, 30,8 %, 23,1 %.
Die drei Balken stehen nebeneinander von 0 bis 1. Der Generator mit dem Seed 31337 liefert 0,7044.
0,7044 fällt in den Balken von „ware“ (von 46,2 % bis 76,9 %): Das nächste Wort ist „ware“, nicht das häufigste.

var table = countNext(TEXT);
List<Choice> choices = nextWords(table.get("die"), 1, 3);
System.out.println("k=3:");
for (Choice c : choices)
    System.out.printf("%-11s%5.1f%%%n", c.word(), c.p() * 100);
Rng rng = new Rng(31337);
Rng copy = new Rng(31337);
System.out.printf("Zahl vom Generator: %.4f%n", copy.next());
System.out.println("gewählt: " + pick(choices, rng));

k=3:
lieferung   46.2%
ware        30.8%
zahlung     23.1%
Zahl vom Generator: 0.7044
gewählt: ware

Mit k = 3 bleiben „lieferung“, „ware“ und „zahlung“, und ihre Häufigkeiten sind 6, 4 und 3 von 13. Der Generator mit Seed 31337 liefert 0,7044, und das fällt in den Balken von „ware“, von 46,2 % bis 76,9 %. Die Wahl folgt den Wahrscheinlichkeiten, aber es ist nicht immer das wahrscheinlichste Wort.

Probier es aus

Ergänze

Was steht anstelle von ___ im Gewicht eines Wortes?

for (String w : top)
    total += Math.pow(counts.get(w), 1 / );

Probier es aus

Finde den Fehler

Ein Kollege will Top-k mit den drei wahrscheinlichsten Wörtern, aber sein Modell schreibt nur seltene Wörter. In welcher Zeile liegt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann es wehtut

Wahrscheinlich ist nicht wahr. Das Modell schreibt „innerhalb von drei tagen“ so leicht wie „bis zu zwei tagen“: Beides steht im Text. Es weiß nicht, wann genau diese Bestellung ankommt. Glatter Text klingt selbstsicher, auch wenn er falsch ist. Darum geht es in der Lektion über die Grenzen des Modells.
Jedes Paar stimmt, der Satz nicht. „die bestellung trifft morgen zu spät“ besteht aus benachbarten Wörtern, die es im Text gibt. Unser Modell schaut nur ein Wort zurück. Echte Modelle sehen den ganzen Text und schreiben viel besser, können aber trotzdem etwas Glattes und Sinnloses zusammenkleben.
Höhere Temperatur, mehr Fehler. Seltene Fortsetzungen kommen öfter vor. Für Antworten an Kunden, wo es auf Genauigkeit ankommt, ist die Temperatur niedrig. Für Ideen und Varianten darf sie höher sein.
Ein Seed ist kein Versprechen. In der Lektion liefert ein Seed eine Antwort. Bei einem echten Modell hinter einer API gibt dieselbe Anfrage manchmal auch mit denselben Einstellungen eine andere Antwort, verlass dich also nicht auf genau denselben Text, sondern prüfe die Antwort.

Genauer, für Neugierige

Softmax und Temperatur. Ein echtes Modell ist ein neuronales Netz: Für jedes Token des Vokabulars liefert es eine Zahl (einen Logit), und Softmax macht daraus Wahrscheinlichkeiten. Die Temperatur teilt die Zahlen vor Softmax durch t. Das Gewicht Anzahl^(1/t) aus der Lektion ist genau das: Softmax von log(Anzahl) / t.

Top-p. Neben Top-k gibt es Top-p: Die häufigsten Tokens bleiben, bis ihre Summe p erreicht (zum Beispiel 0,9). Ist sich das Modell sicher, bleiben also wenige Tokens, ist es unsicher, mehr.

Tokens, nicht Wörter. Ein echtes Modell wählt Tokens aus seinem Vokabular, und ein Wort entsteht aus mehreren Wahlen hintereinander. Temperatur, Top-k und Seed werden in der Anfrage an das Modell gesetzt (die Lektion über den Aufruf).

Wie weit es zurückschaut. Unser Modell merkt sich ein Wort. Ein echtes sieht das ganze Gespräch bis zu seinem Limit, und das ist das Kontextfenster.

Übung

Wie wahrscheinlich ist der Satz

Löse die Aufgabe in deinem Editor.

Die Wahrscheinlichkeit eines ganzen Satzes ist das Produkt der Wahrscheinlichkeiten jedes nächsten Wortes, einschließlich des „.“ am Ende. Schreibe eine Funktion, die sie mit der Tabelle aus der Lektion berechnet, und gib sie für drei Sätze in Prozent aus. Wurde ein Wortpaar nie gesehen, ist seine Wahrscheinlichkeit 0.

das paket trifft innerhalb von zwei tagen ein: 0.40%
das paket ist in der originalverpackung an: 0.05%
das paket kam morgen an: 0.00%

Der erste Satz hat 0,40 %, obwohl er im Text Wort für Wort steht: An fast jeder Stelle hätte das Modell auch ein anderes Wort wählen können. Der zweite hat 0,05 %, steht nicht im Text, aber alle Paare darin wurden gesehen. Der dritte hat 0,00 %: „paket“ und „kam“ stehen beide im Text, aber nie direkt hintereinander. So sagt das Modell, wie „natürlich“ ihm ein Text vorkommt.

Weitere Aufgaben

Der wahrscheinlichste Satz. Beginne bei „das paket“ und nimm immer das wahrscheinlichste Wort. Wie hoch ist die Wahrscheinlichkeit des Satzes, der dabei entsteht?
Zwei Wörter zurück. Zähle, welches Wort nach einem Wortpaar kommt, nicht nach einem Wort. Wie ändern sich die Antworten vom Anfang der Lektion?

Test

Teste dich

1. Was liefert ein Sprachmodell, wenn du ihm Text gibst?Nur ein Wort: das wahrscheinlichsteEine Wahrscheinlichkeit für jedes mögliche nächste Wort (Token)Die fertige Antwort, gefunden im Text, aus dem es gelernt hat

2. Du startest die Generierung zweimal mit Seed 2026. Was siehst du?Denselben Text: ein Seed liefert dieselben ZahlenEinen Fehler: ein Seed kann nur einmal benutzt werdenZwei verschiedene Texte, weil die Wahl zufällig ist

3. Wie verändert die Temperatur t = 0,5 die Wahrscheinlichkeiten nach „die“?Alle Wörter werden gleich wahrscheinlichNichts ändert sich, nur die GeschwindigkeitDas häufige Wort wird noch wahrscheinlicher, die seltenen noch unwahrscheinlicher

4. Der Bot schreibt „die Bestellung trifft innerhalb von drei Tagen ein“, aber die Lieferung dauert in Wirklichkeit bis zu zwei Tage. Warum?Das Modell schreibt eine wahrscheinliche Fortsetzung, keine geprüfte TatsacheDer Generator ist kaputtDie Temperatur ist zu niedrig

Das nächste Token vorhersagen

Cookies