Ein winziges Sprachmodell

1. Das nächste Wort

Tippst du auf dem Handy eine Nachricht, schlägt die Tastatur über den Buchstaben drei Wörter vor, die als Nächstes kommen könnten. Ein Chatbot macht im Grunde dasselbe, nur sehr viel besser: Er schreibt ein Wort, schaut, was bisher dasteht, schreibt das nächste Wort, und so weiter, bis die Antwort fertig ist. Ein Programm, das zu einem Text das nächste Wort vorhersagt, heißt Sprachmodell.

Du baust heute ein winziges Sprachmodell. Es lernt aus den Märchen der Brüder Grimm: 54 Märchen mit zusammen etwa 80 000 Wörtern, von »Marienkind« bis »Des Herrn und des Teufels Getier«. Lernen heißt hier: zählen, welches Wort wie oft auf welches folgt.

Was so ein Modell zählt, merkt es sich in einem Dictionary, genauer in einem Dictionary von Dictionaries. Wie Dictionaries gehen, übst du in den Katas: Dictionaries.

2. Einrichten

mkdir -p ~/sprachmodell
cd ~/sprachmodell
wget https://workspace.hackschule.de/sprachmodell/maerchen.txt
touch model.rb story.rb

irb -r ./model.rb

mkdir -p ~/sprachmodell
cd ~/sprachmodell
wget https://workspace.hackschule.de/sprachmodell/maerchen.txt
touch model.py story.py

python3 -i model.py

Die Märchen stehen in der Schreibweise eines Buchs von 1921: »daß« statt »dass«, »Türe« statt »Tür«. Der Text kommt von Project Gutenberg, wo Freiwillige alte Bücher abtippen, die niemandem mehr gehören; die vier Märchen auf Plattdeutsch sind herausgenommen, damit das Modell nur eine Sprache lernt.

3. Aus Text werden Wörter

Ein Modell zählt Wörter, also muss der Text zuerst in Wörter zerlegt werden. Satzzeichen zählen dabei als eigene Wörter: Wer weiß, dass nach »König« oft ein Komma kommt und nach einem Punkt ein neuer Satz, schreibt Sätze, die enden. Anführungszeichen lässt das Modell weg, denn es kann sich nicht merken, ob es gerade eines geöffnet hat.

# Der Text als Liste von Wörtern und Satzzeichen
def words(text)
  text.scan(/\p{L}+|[.,;:!?]/)
end

import random
import re


# Der Text als Liste von Wörtern und Satzzeichen
def words(text):
    return re.findall(r"[^\W\d_]+|[.,;:!?]", text)

4. Wer folgt auf wen

Das Modell soll sich für jedes Wort merken, welche Wörter danach kamen und wie oft. Für den kleinen Text »Der Wolf kam. Der Wolf fraß. Der Jäger kam.« sieht das so aus:

{
  "Der" => { "Wolf" => 2, "Jäger" => 1 },
  "Wolf" => { "kam" => 1, "fraß" => 1 },
  "kam" => { "." => 2 },
  "." => { "Der" => 2 },
  "fraß" => { "." => 1 },
  "Jäger" => { "kam" => 1 }
}

{
    "Der": {"Wolf": 2, "Jäger": 1},
    "Wolf": {"kam": 1, "fraß": 1},
    "kam": {".": 2},
    ".": {"Der": 2},
    "fraß": {".": 1},
    "Jäger": {"kam": 1},
}

Ein Dictionary, dessen Werte wieder Dictionaries sind: Unter jedem Wort steht, was darauf folgte, und unter jedem Nachfolger, wie oft. Nach dem letzten Punkt kommt nichts mehr, darum zählt er nicht mit.

def follow_counts(tokens)
  counts = {}
  (0...tokens.size - 1).each do |i|
    word = tokens[i]
    following = tokens[i + 1]
    # hier: das Dictionary für word anlegen, wenn es fehlt, und following zählen
  end
  counts
end

# Für jedes Wort: welche Wörter darauf folgen, und wie oft
def follow_counts(tokens)
  counts = {}
  (0...tokens.size - 1).each do |i|
    word = tokens[i]
    following = tokens[i + 1]
    counts[word] ||= {}
    counts[word][following] = (counts[word][following] || 0) + 1
  end
  counts
end

def follow_counts(tokens):
    counts = {}
    for i in range(len(tokens) - 1):
        word = tokens[i]
        following = tokens[i + 1]
        # hier: das Dictionary für word anlegen, wenn es fehlt, und following zählen
    return counts

# Für jedes Wort: welche Wörter darauf folgen, und wie oft
def follow_counts(tokens):
    counts = {}
    for i in range(len(tokens) - 1):
        word = tokens[i]
        following = tokens[i + 1]
        if word not in counts:
            counts[word] = {}
        counts[word][following] = counts[word].get(following, 0) + 1
    return counts

In die Märchen schauen

Jetzt zählt dein Modell die ganzen Märchen. Damit du nachsehen kannst, was auf ein Wort folgt, schreib noch diese Funktion dazu; sie gibt die n häufigsten Nachfolger mit ihrer Anzahl zurück:

# Die n häufigsten Nachfolger von word, mit ihrer Anzahl
def top(counts, word, n)
  (counts[word] || {}).sort_by { |following, count| -count }.first(n)
end

counts = follow_counts(words(File.read("maerchen.txt")))
top(counts, "Es", 5)

# Die n häufigsten Nachfolger von word, mit ihrer Anzahl
def top(counts, word, n):
    followers = counts.get(word, {})
    return sorted(followers.items(), key=lambda pair: -pair[1])[:n]

counts = follow_counts(words(open("maerchen.txt").read()))
top(counts, "Es", 5)

5. Ein Märchen schreiben

Ein Modell, das zu jedem Wort seine Nachfolger kennt, kann schreiben: Es beginnt mit einem Wort, nimmt einen Nachfolger, dann dessen Nachfolger, und so weiter. Am einfachsten nimmt es jedes Mal den häufigsten.

# Der häufigste Nachfolger von word, nil für ein unbekanntes Wort
def most_likely(counts, word)
  return nil unless counts.key?(word)

  counts[word].max_by { |following, count| count }[0]
end

# Der häufigste Nachfolger von word, None für ein unbekanntes Wort
def most_likely(counts, word):
    if word not in counts:
        return None
    return max(counts[word], key=counts[word].get)

Zum Schreiben noch eine Funktion, die eine Liste von Wörtern wieder als Text ausgibt, ohne Leerzeichen vor einem Satzzeichen:

# Wörter als Text, ohne Leerzeichen vor einem Satzzeichen
def text(tokens)
  tokens.join(" ").gsub(/ ([.,;:!?])/, '\1')
end

# Wörter als Text, ohne Leerzeichen vor einem Satzzeichen
def text(tokens):
    return re.sub(r" ([.,;:!?])", r"\1", " ".join(tokens))

require_relative "model"

counts = follow_counts(words(File.read("maerchen.txt")))
tokens = ["Es"]
30.times do
  tokens << most_likely(counts, tokens.last)
end
puts text(tokens)

ruby story.rb

from model import *

counts = follow_counts(words(open("maerchen.txt").read()))
tokens = ["Es"]
for _ in range(30):
    tokens.append(most_likely(counts, tokens[-1]))
print(text(tokens))

python3 story.py

6. Würfeln statt immer das Häufigste

Ein Modell, das nur das häufigste Wort nimmt, schreibt immer dasselbe. Besser: Es würfelt, aber so, dass ein häufiger Nachfolger öfter drankommt. Auf »Es« folgt 41-mal »war« und 21-mal »ist«; dann soll »war« ungefähr doppelt so oft gewählt werden wie »ist«.

Das geht mit einer Zufallszahl. Folgte auf ein Wort sechsmal »war«, dreimal »ist« und einmal »trug«, zusammen zehnmal, zieht das Modell eine Zahl von 0 bis 9 und geht die Nachfolger der Reihe nach durch:

Ist die Zahl kleiner als die Anzahl des ersten Nachfolgers, nimmt das Modell diesen Nachfolger. Sonst zieht es dessen Anzahl von der Zahl ab und vergleicht mit der Anzahl des nächsten Nachfolgers.

def next_word(counts, word)
  return nil unless counts.key?(word)

  r = rand(counts[word].values.sum)
  counts[word].each do |following, count|
    # hier: following zurückgeben, wenn r kleiner als count ist,
    # sonst count von r abziehen
  end
end

# Ein Nachfolger von word, gezogen nach seiner Anzahl; nil für ein unbekanntes Wort
def next_word(counts, word)
  return nil unless counts.key?(word)

  r = rand(counts[word].values.sum)
  counts[word].each do |following, count|
    return following if r < count

    r -= count
  end
end

def next_word(counts, word):
    if word not in counts:
        return None
    r = random.randrange(sum(counts[word].values()))
    for following, count in counts[word].items():
        # hier: following zurückgeben, wenn r kleiner als count ist,
        # sonst count von r abziehen
        ...

# Ein Nachfolger von word, gezogen nach seiner Anzahl; None für ein unbekanntes Wort
def next_word(counts, word):
    if word not in counts:
        return None
    r = random.randrange(sum(counts[word].values()))
    for following, count in counts[word].items():
        if r < count:
            return following
        r -= count

# start und bis zu n gezogene Wörter danach
def generate(counts, start, n)
  tokens = [start]
  n.times do
    following = next_word(counts, tokens.last)
    break if following.nil?

    tokens << following
  end
  tokens
end

# start und bis zu n gezogene Wörter danach
def generate(counts, start, n):
    tokens = [start]
    for _ in range(n):
        following = next_word(counts, tokens[-1])
        if following is None:
            break
        tokens.append(following)
    return tokens

counts = follow_counts(words(File.read("maerchen.txt")))3.times do  puts text(generate(counts, "Es", 30))  putsend

counts = follow_counts(words(open("maerchen.txt").read()))for _ in range(3):    print(text(generate(counts, "Es", 30)))    print()

Zum Beispiel:

Es trug sich um zu dem Richter, dann wollen wir uns doch der König in solche Blume, in einer kurzen Marsch haben will gleich nicht zu den sieben Zwerge

Der Mathematiker Claude Shannon hat 1948 genau solche Texte erzeugt, ohne Computer: Er schlug ein Buch an einer zufälligen Stelle auf, las bis zu dem Wort, das er zuletzt aufgeschrieben hatte, und schrieb das Wort dahinter auf. Dann blätterte er weiter zu einer anderen Stelle, suchte dort dieses Wort, und so weiter. Ein Buch würfelt so von selbst nach der Häufigkeit: Ein Wort, das oft folgt, findet man oft.

Mehr dazu

• MacTutor: Shannon
• people.math.harvard.edu (PDF)
• news.mit.edu
• Wikipedia: Shannon–Fano coding
• MIT Technology Review: mighty mouse

Claude Shannon (1916–2001). Wie viele Bits eine Nachricht mindestens braucht, rechnete er 1948 aus und gründete damit die Informationstheorie; das Wort Bit machte er bekannt. Er fuhr Einrad, jonglierte und baute die Maus Theseus, die selbst lernte, durch ein Labyrinth zu finden.

Einen Code mit so wenigen Bits wie möglich suchten er und Robert Fano fast gleichzeitig, jeder für sich. Der Shannon-Fano-Code kam nah heran, aber nicht immer ganz.

In derselben Arbeit von 1948 ließ er englische Texte Wort für Wort entstehen, jedes Wort nach dem vorigen aus einem Buch gezogen: ein winziges Sprachmodell, von Hand.

Foto: Tekniska museet, CC BY 2.0, zugeschnitten (Wikimedia Commons)

Gezählt hatte vor ihm schon Andrei Markow: 1913 ging er die ersten 20 000 Buchstaben von Puschkins Versroman »Eugen Onegin« durch und zählte, wie oft auf einen Vokal ein Vokal folgt und wie oft ein Konsonant. Eine Kette, in der jedes Glied nur vom vorigen abhängt, heißt seitdem Markow-Kette, und dein Modell ist eine Markow-Kette: Welches Wort es zieht, hängt nur vom Wort davor ab.

Andrei Markow (1856–1922), russischer Mathematiker in Sankt Petersburg. 1913 ging er die ersten 20 000 Buchstaben von Puschkins »Eugen Onegin« durch und zählte, wie oft auf einen Vokal ein Vokal folgt und wie oft ein Konsonant: Der nächste Buchstabe hängt vom vorigen ab, und mit dieser Abhängigkeit kann man rechnen.

Eine Kette, in der jedes Glied nur vom vorigen abhängt, heißt nach ihm Markow-Kette. Auch ein Sprachmodell aus Wortpaaren ist eine Markow-Kette.

Foto: unbekannt, 1886, gemeinfrei, zugeschnitten (Wikimedia Commons)

7. Mehr Kontext: zwei Wörter

Dein Modell schaut nur auf das letzte Wort. Was vorher stand, hat es vergessen. Schaut es auf die letzten zwei, weiß es mehr: Nach »sprach der« kommt ein anderes Wort als nach »Da sprach«. Der Kontext ist jetzt ein Paar von Wörtern, und als Schlüssel nimmt das Modell beide zusammen, mit einem Leerzeichen dazwischen: Unter "sprach der" steht, was nach »sprach der« kam.

# Für jedes Paar von Wörtern: welche Wörter darauf folgen, und wie oft
def pair_counts(tokens)
  counts = {}
  (0...tokens.size - 2).each do |i|
    pair = "#{tokens[i]} #{tokens[i + 1]}"
    following = tokens[i + 2]
    counts[pair] ||= {}
    counts[pair][following] = (counts[pair][following] || 0) + 1
  end
  counts
end

# Für jedes Paar von Wörtern: welche Wörter darauf folgen, und wie oft
def pair_counts(tokens):
    counts = {}
    for i in range(len(tokens) - 2):
        pair = tokens[i] + " " + tokens[i + 1]
        following = tokens[i + 2]
        if pair not in counts:
            counts[pair] = {}
        counts[pair][following] = counts[pair].get(following, 0) + 1
    return counts

Zum Schreiben braucht das Modell eine zweite Fassung von generate, die mit zwei Wörtern beginnt und jedes Mal die letzten beiden als Schlüssel nimmt:

# first, second und bis zu n gezogene Wörter danach, mit zwei Wörtern Kontext
def generate_pairs(counts, first, second, n)
  tokens = [first, second]
  n.times do
    following = next_word(counts, tokens.last(2).join(" "))
    break if following.nil?

    tokens << following
  end
  tokens
end

pairs = pair_counts(words(File.read("maerchen.txt")))
3.times do
  puts text(generate_pairs(pairs, "Es", "war", 30))
  puts
end

# first, second und bis zu n gezogene Wörter danach, mit zwei Wörtern Kontext
def generate_pairs(counts, first, second, n):
    tokens = [first, second]
    for _ in range(n):
        following = next_word(counts, " ".join(tokens[-2:]))
        if following is None:
            break
        tokens.append(following)
    return tokens

pairs = pair_counts(words(open("maerchen.txt").read()))
for _ in range(3):
    print(text(generate_pairs(pairs, "Es", "war", 30)))
    print()

Abgeschrieben?

Klingt der Text besser, weil das Modell mehr verstanden hat? Schau nach, wie viel Auswahl es noch hat. Hat ein Paar von Wörtern in den Märchen nur einen einzigen Nachfolger, kann das Modell nach diesem Paar nur genau das Wort schreiben, das im Märchen steht: Es schreibt ab.

8. Was das Modell aus seinem Text lernt

Dein Modell kennt nur die Märchen. Was dort oft steht, schreibt es oft; was dort nie steht, schreibt es nie. Es hat keine Meinung, aber es gibt die Meinungen seines Textes weiter.

9. Was ein großes Sprachmodell anders macht

Ein Chatbot rechnet auch nur aus, welches Wort als Nächstes kommt, und würfelt dann. Aber fast alles andere ist größer:

Die Tabelle deines Modells kann für einen Kontext, der nie vorkam, nichts sagen. Ein neuronales Netz kann es, weil es nicht jeden Kontext einzeln speichert, sondern lernt, welche Kontexte einander ähneln. Gleich bleibt die Idee: aus vielen Texten lernen, wie es weitergeht, und dann Wort für Wort ziehen.

11. Zum Nachschlagen

• Katas: Dictionaries: Dictionaries anlegen, zählen, nachsehen
• Reguläre Ausdrücke im Handbuch: Muster wie das in words
• Project Gutenberg: die Märchen, aus denen dein Modell lernt