Niemand hat die Absicht, eine …

Lieber Leser, haben Sie den Satz in der Überschrift gerade gedanklich vervollständigt? Falls ja, dann haben Sie bereits, ohne es zu ahnen, den Gegenstand dieses Artikels als Grundlage für Ihre Entscheidung herangezogen. Im Folgenden geht es nämlich um statistische Sprachmodelle und deren Anwendungsfälle.

Es gibt natürlich viele Möglichkeiten, wie dieser Satz ergänzt werden kann:

  1. … Idee zu sabotieren.
  2. … Mauer zu errichten.
  3. … Demonstration zu verhindern.

Vielleicht fragen Sie sich nun, warum Sie spontan an Option 2), nämlich Walter Ulbrichts berühmtes Zitat gedacht haben. Dies mag daran liegen, dass Sie es im Fernsehen oder Radio gehört, im Museum oder Geschichtsunterricht gelesen haben. Da es sich hierbei um einen historisch relevanten Ausspruch handelt, haben Sie ihn vermutlich häufiger verwendet als die Optionen 1) und 3). Sie merken also, dass Häufigkeiten (in diesem Fall von Wortsequenzen) eine zentrale Rolle für unser Thema spielen.

Schon ist es nur noch ein kleiner gedanklicher Schritt zum Konzept der Wahrscheinlichkeit, das innerhalb der Computerlinguistik neben den regelbasierten Lösungsansätzen die zweite zentrale Säule bildet. Suchmaschinen wie Google etwa erstellen Statistiken über die Häufigkeiten der an sie gestellten Suchanfragen und berechnen hieraus Wahrscheinlichkeiten, die Ihnen dabei helfen sollen, schneller das zu finden, was Sie suchen. Füttern wir Google mit der Wortfolge aus unserer Überschrift, so ist sie davon überzeugt, dass wir Informationen über Walter Ulbricht oder Tondokumente seines Zitats finden wollen. Auch schlägt die Suchmaschine bereits beim Tippen vor, die Suchanfrage mit dem kompletten Zitat zu vervollständigen. Natürlich kann es aber trotzdem vorkommen, dass Google falsch liegt und Sie in Wahrheit nach etwas ganz anderem suchen. Deshalb werden nach den ersten Suchergebnissen verwandte Suchanfragen aufgelistet, die weniger wahrscheinlich, d.h. seltener gestellt worden sind. Das Vorhersagen des nächsten Wortes ist somit eine essentielle Teilaufgabe, auch für andere Anwendungsfälle wie Rechtschreibkorrektur, Textklassifikation oder Spracherkennung. Mit letzterem werden wir uns in diesem Artikel noch etwas genauer beschäftigen.

Aber wie lassen sich Wahrscheinlichkeiten für bestimmte Wortsequenzen nun konkret berechnen? Intuitiv wird man zunächst etwa von folgender Annahme ausgehen (der Buchstabe P steht im Folgenden für engl. probability):

(1)   \begin{equation*} P(niemand\ hat\ die\ Absicht\ eine\ Mauer\ zu\ errichten) > P(errichten\ Absicht\ niemand\ Mauer\ eine\ zu\ die\ hat) \end{equation*}

Die genaue Reihenfolge der geäußerten Wörter spielt eine entscheidende Rolle, denn es ist naheliegend, dass die dem Deutschen entsprechend ungrammatische Wortfolge auf der rechten Seite der Gleichung eine deutlich kleinere Wahrscheinlichkeit haben muss (die obendrein gegen null tendieren wird) als die Wortfolge aus Ulbrichts Zitat. Es bleibt also festzustellen, dass wir es hier mit bedingten Wahrscheinlichkeiten zu tun haben. Allgemein ausgedrückt berechnen wir die Wahrscheinlichkeit P(A|B), dass ein Ereignis A eintreten wird, unter der Bedingung, dass ein anderes Ereignis B vorher bereits eingetreten ist. Übertragen wir diese Annahme auf unser konkretes Beispiel, so berechnet sich theoretisch die Wahrscheinlichkeit für unser Zitat P(Z) aus dem Produkt der einzelnen bedingten Teilwahrscheinlichkeiten:

(2)   \begin{equation*} P(Z) = P(niemand) P(hat|niemand) P(die|niemand\ hat) \dotso P(errichten|niemand\ hat\ die\ Absicht\ eine\ Mauer\ zu) \end{equation*}

Formal betrachtet lässt sich die Wahrscheinlichkeit für eine Wortsequenz P(w_1,w_2,\dotsc,w_n), abgekürzt P(w_1^n), also wie folgt darstellen:

(3)   \begin{align*} P(w_1^n) &= P(w_1) P(w_2|w_1) P(w_3|w_1^2) \dotso P(w_n|w_1^{n-1})\\ \ &= \prod_{k=1}^{n} P(w_k|w_1^{k-1}) \end{align*}

Wer das zur Veranschaulichung statistischer Problemstellungen häufig verwendete Urnenmodell kennt, der weiß, dass exakte Wahrscheinlichkeiten sich nur dann berechnen lassen, wenn die Gesamtzahl aller möglichen unterschiedlichen Ergebnismengen bekannt ist. Für das Urnenmodell bedeutet das, dass man die Wahrscheinlichkeit für das Ziehen einer spezifischen Kugel nur dann genau bestimmen kann, wenn man weiß, wie viele Kugeln sich insgesamt in der Urne befinden. Für natürliche Sprachen wie das Deutsche lässt sich die Gesamtzahl aller möglichen Wörter und grammatischer Wortsequenzen aber nicht im Voraus festlegen. Denn Sprache ist kreativ. In aller Regelmäßigkeit werden neue Wörter erfunden und Sätze gebildet, die es vorher noch nicht gegeben hat. Wie finden wir nun eine Lösung für dieses Dilemma? Indem wir einen Kompromiss schließen und die Wahrscheinlichkeiten lediglich schätzen werden.

Eine Möglichkeit, solch eine Schätzung vorzunehmen, ist das Berechnen von relativen Häufigkeiten der Wortsequenzen in einem möglichst umfangreichen Textkorpus. Ein Beispiel für eine der Teilwahrscheinlichkeiten (der Buchstabe C steht im Folgenden für engl. count):

(4)   \begin{equation*} P(errichten|niemand\ hat\ die\ Absicht\ eine\ Mauer\ zu) = \frac{C(niemand\ hat\ die\ Absicht\ eine\ Mauer\ zu\ errichten)}{C(niemand\ hat\ die\ Absicht\ eine\ Mauer\ zu)} \end{equation*}

Diese Berechnungsmethode beantwortet also die Frage: Von all den Vorkommen der Wortsequenz niemand hat die Absicht eine Mauer zu, wie oft folgte danach das Wort errichten? An dieser Stelle gibt es nun ein weiteres Problem. Selbst wenn wir das gesamte Internet als Textkorpus heranziehen, sind die berechneten Schätzungen in den meisten Fällen nicht gut genug. Für unser Zitat mag dies noch funktionieren, aber für sehr konstruiert erscheinende Sätze wie etwa Kruzifix nochamol, ich hab den Klarspüler im dm vergessen ist es sehr unwahrscheinlich, dass diese überhaupt im World Wide Web existieren, so dass wir hier mit unserer Zählung nicht weiterkommen.

Um wiederum dieses Problem zu lösen, werden wir nun eine Annahme treffen, die aus sprachwissenschaftlicher Sicht unlogisch oder gar falsch erscheinen mag, sich in der praktischen Anwendung dennoch häufig bewährt. Wir gehen im Folgenden davon aus, dass einzelne Teilsequenzen unseres Zitats statistisch unabhängig voneinander sind. Das bedeutet, wir beschränken den vorhergehenden Kontext eines Wortes auf z.B. nur zwei oder drei Wörter, anstatt den gesamten Kontext zu betrachten. Diese Idee geht auf den russischen Mathematiker Andrei Markov zurück. Seine Annahme, deren Nutzen er für die Betrachtung bestimmter stochastischer Prozesse aufzeigte, ist unter den Begriffen Markov-Prozess bzw. Markov-Kette oder schlicht Markov-Annahme bekannt (engl. Markov assumption bzw. Markov property). Die dementsprechend überarbeitete Version der Gleichung (3) lautet deshalb:

(5)   \begin{equation*} P(w_1^n) \approx \prod_{k=1}^{n} P(w_k|w_{k-N+1}^{k-1}) \ mit \ 1 < N \le k \end{equation*}

Der Parameter N beschränkt also die Länge der Teilwortsequenzen, deren Wahrscheinlichkeiten wir mittels relativer Häufigkeiten schätzen werden. Deshalb werden diese Teilwortsequenzen auch N-Gramme (engl. N-gram) genannt. Wird N=2 gewählt, so hat man es mit Bigrammen zu tun, wohingegen man von Trigrammen spricht, wenn man sich für N=3 entscheidet. Welche Zahl man für N einsetzt, hängt sowohl von dem konkreten Anwendungsfall als auch von der Größe des zur Verfügung stehenden Textkorpus ab. Als Richtwert lässt sich sagen, je größer das zur Verfügung stehende Textkorpus ist, desto größer sollte auch N gewählt werden, um verlässliche Wahrscheinlichkeitswerte zu erhalten. Der Nutzen dieses Verfahrens erscheint plausibel, wenn man bedenkt, dass sich Wahrscheinlichkeiten für häufig vorkommende Trigramme wie etwa P(ich\ hab\ den) wesentlich verlässlicher schätzen lassen als für seltene Hexagramme wie P(ich\ hab\ den\ Klarsp\"uler\ im\ dm). Die Tatsache, dass benachbarte Wörter eines Satzes eigentlich syntaktisch und semantisch abhängig voneinander sind, wird an dieser Stelle also ausgeblendet. Formel (4) zur Berechnung der relativen Häufigkeiten lässt sich demnach wie folgt generalisieren:

(6)   \begin{equation*} P(w_n|w_{n-N+1}^{n-1}) = \frac{C(w_{n-N+1}^{n-1} w_n)}{C(w_{n-N+1}^{n-1})} \ mit \ 1 < N \le n \end{equation*}

Bevor wir uns in einem späteren Artikel mit weiteren Einsatzgebieten und Problemen von N-Gramm-Modellen beschäftigen werden, sei im Folgenden ein konkreter Anwendungsfall beschrieben, der in dieser oder in einer abgewandelten Form von Google, Facebook und anderen Diensten verwendet wird, um automatisiert entscheiden zu können, in welcher natürlichen Sprache ein beliebiger Text verfasst ist. Wer etwa bei Facebook einen Beitrag liest, der nicht in der im sozialen Netzwerk eingestellten Sprache erstellt worden ist, wird sicherlich bereits festgestellt haben, dass eine Option zum Übersetzen des Beitrags angeboten wird. Beim Klick auf den entsprechenden Link wird automatisch eine Übersetzung durchgeführt, allerdings wird der Nutzer vorher nicht gefragt, in welcher Sprache der Beitrag überhaupt geschrieben worden ist. Facebook versucht dies also automatisch zu erkennen. Doch wie funktioniert das? Natürlich lässt sich das Unternehmen nicht in die Karten schauen, aber es liegt nahe, dass sie den folgenden einfachen aber effizienten Weg zumindest als Grundlage heranziehen.

Fremdsprachliche Facebook-Beiträge können automatisch vom sozialen Netzwerk übersetzt werden lassen
Fremdsprachige Facebook-Beiträge können automatisch übersetzt werden lassen.

Die Aufgabe der automatischen Spracherkennung lässt sich mit der Berechnung relativer Häufigkeiten von N-Grammen durchführen. Jedoch werden hierbei nicht Wörter als Einheiten betrachtet, sondern Buchstaben. Die Häufigkeitsverteilung von Buchstabenkombinationen ist also der Schlüssel zur korrekten Identifikation der verwendeten Sprache. Wie funktioniert dies nun konkret? Im Folgenden werden wir ein kleines Python-Programm schreiben, das in der Lage ist zu entscheiden, ob ein beliebiger eingegebener Text in Englisch oder Deutsch verfasst ist. Für jede der beiden Sprachen benötigen wir jeweils einen Text von etwa 500 Wörtern als Grundlage für den Entscheidungsprozess. Im Allgemeinen spricht man hierbei auch von sog. Trainingsdaten, für welche im Vorfeld also die Sprache bereits bekannt ist. Hierfür nehmen wir willkürlich gewählte SPIEGEL Online-Artikel, einmal für das Deutsche und einmal für das Englische.

Sollte Facebook die Sprache nicht korrekt erkannt haben, kann der User dies melden.
Facebook-Nutzer können eine falsch erkannte Sprache selbst korrigieren.

Nun schreiben wir eine Funktion, die alle Buchstaben-N-Gramme aus den Texten ausliest und in einer Liste speichert. Hierfür normalisieren wir zunächst die Groß- und Kleinschreibung und entfernen sämtliche Interpunktions-, Leer- und Sonderzeichen, weil diese für die Sprachidentifikation keine signifikante Rolle spielen. Zusätzlich fügen wir am Anfang und Ende jedes Wortes sog. Dummy-Zeichen in Form eines Rautensymbols (#) an, um diejenigen N-Gramme zu kennzeichnen, die sich am Wortanfang bzw. -ende befinden. Der Code sieht dementsprechend wie folgt aus:

from collections import Counter
from re import findall

def create_character_ngrams(text, n):
    # 1. Text in Kleinbuchstaben umwandeln
    # 2. Text in Liste von einzelnen Wörtern zerlegen
    # 3. Interpunktions-, Leer- und Sonderzeichen herausfiltern
    words = findall(r'\w+', text.lower())
    
    # 4. Dummy-Zeichen '#' vorne und hinten an jedes Wort anfügen
    words = [
        '{dummy}{word}{dummy}'.format(dummy=(n-1)*'#', word=word) 
        for word in words
    ]
    
    # 5. N-Gramme erstellen und in Liste ablegen
    ngram_list = []
    for word in words:
        for i in range(len(word)-n+1):
            ngram = word[i:i+n]
            ngram_list.append(ngram)
    
    return ngram_list

Die Artikeltexte haben wir zuvor händisch von den entsprechenden Webseiten in jeweils eine Textdatei kopiert und mit der Kodierung UTF-8 abgespeichert. Mittels der folgenden Python-Funktion werden die Texte eingelesen und als Zeichenkette (engl. string) zurückgegeben. Anschließend werden gemäß Formel (6) sowohl Trigramme als auch Bigramme gebildet, da beide N-Gramm-Typen zum Berechnen der bedingten Trigramm-Wahrscheinlichkeiten benötigt werden:

# 1. Definieren der Funktion
def read_training_data_file(file_path, encoding='utf-8'):
    with open(file_path, encoding=encoding) as training_data_file:
        return training_data_file.read()

# 2. Einlesen der Texte
german_text = read_training_data_file('german_training_data.txt')
english_text = read_training_data_file('english_training_data.txt')

# 3. Erstellen der Trigramm-Liste für jede Sprache
german_trigrams = create_character_ngrams(text=german_text, n=3)
english_trigrams = create_character_ngrams(text=english_text, n=3)

# 4. Erstellen der Bigramm-Liste für jede Sprache
german_bigrams = create_character_ngrams(text=german_text, n=2)
english_bigrams = create_character_ngrams(text=english_text, n=2)

# 5. Zählen der Trigramm-Vorkommen für jede Sprache
german_trigram_counts = Counter(german_trigrams)
english_trigram_counts = Counter(english_trigrams)

# 6. Zählen der Bigramm-Vorkommen für jede Sprache
german_bigram_counts = Counter(german_bigrams)
english_bigram_counts = Counter(english_bigrams)

# 7. Beispielhaftes Ausgeben der 3 häufigsten Trigramme des deutschen Textes
for trigram, count in german_trigram_counts.most_common(3):
    print(trigram, ':', count)

# n## : 229
# t## : 153
# en# : 150

Wir verwenden für unser konkretes Sprachmodell Trigramme, da für N=3 bereits gute Ergebnisse möglich sind. Schauen wir uns nun für die erwähnten SPIEGEL Online-Artikel die jeweils zehn häufigsten Trigramme an, so lassen sich hieraus schon aufschlussreiche Unterschiede zwischen beiden Sprachen ausmachen:

HäufigkeitsrangDeutschEnglisch
TrigrammAnzahl der VorkommenTrigrammAnzahl der Vorkommen
1n##229e##206
2t##153##t183
3en#150#th134
4##d133t##128
5##s126s##124
6r##123the112
7e##117##a111
8er#92##s97
9s##71he#94
10##e68n##92

Grundsätzlich sind die häufigsten Trigramme in beiden Sprachen Präfixe und Suffixe, die an die Wortstämme angefügt werden, um korrekte Flexionsformen zu bilden. So kommt etwa das Trigramm en# im Deutschen sehr häufig vor, weil mit dem Suffix -en viele Pluralformen von Substantiven gebildet werden (z.B. Tisch-en), aber auch pluralisierte Verbformen (z.B. wir schreib-en). Im Englischen hingegen ist besonders die Buchstabenkombination th sehr oft anzutreffen, denn viele Wörter beginnen damit (z.B. this, that, thorough, …). Der bestimmte Artikel the taucht sogar als sechsthäufigstes Trigramm auf. Im Deutschen gibt es ebenfalls charakteristische Trigramme, die im Englischen selten bis gar nicht anzutreffen sind. So zählen wir für das Trigramm sch in unserem deutschen Trainingskorpus 42 Vorkommen, im englischen aber nur ein einziges. Umgekehrt zählen wir für das bereits erwähnte im Englischen häufige Trigramm #th auch nur ein Vorkommen im deutschen Artikel. Sie merken also, dass die Auswahl der einzelnen Texte, die als Trainingsdaten verwendet werden sollen, relativ beliebig erfolgen kann, solange sie wenig bis keine gemischtsprachigen Informationen enthalten, welche die Statistiken verfälschen könnten. Denn selbst so eng verwandte Sprachen wie Deutsch und Englisch unterscheiden sich signifikant in den Häufigkeitsverteilungen ihrer Buchstaben.

Um nun ein vollwertiges Spracherkennungsprogramm zu erstellen, benötigen wir eine Eingabemaske für einen beliebigen Text, dessen Sprache erkannt werden soll. Der eingegebene Text wird dann in seine Tri- und Bigramme zerlegt. Für jedes einzelne dieser N-Gramme wird dann überprüft, ob es in den Trainingsdaten der jeweiligen Sprachen vorkommt. Falls ja, werden die entsprechenden Häufigkeitswerte der Tri- und Bigramme für jede Sprache jeweils getrennt voneinander multipliziert und abschließend der Quotient aus Trigramm- und Bigramm-Produkt gebildet (siehe wieder Formel (6)). Der resultierende Wert pro Sprache ist eine Zahl zwischen 0 und 1 und drückt die geschätzte Wahrscheinlichkeit aus. Kommt ein N-Gramm des Eingabetextes nicht in den Trainingsdaten vor, wird es ignoriert. Hier der entsprechende Code:

def guess_language():
    while True:
        # 1. Variable 'text' speichert eingegebenen Text
        text = input('Bitte Text eingeben (oder \'EXIT\' zum Beenden):\n')
        if text == 'EXIT':
            print('Programm beendet')
            break
        
        # 2. Erstellen der Tri- und Bigramme des Eingabetextes
        trigrams = create_character_ngrams(text=text, n=3)
        bigrams = create_character_ngrams(text=text, n=2)
        
        # 3. Initialisieren der Ergebnisvariablen
        german_trigram_count_product = 1
        english_trigram_count_product = 1
        
        german_bigram_count_product = 1
        english_bigram_count_product = 1
        
        # 4. Multiplizieren der Häufigkeitswerte
        for trigram in trigrams:
            if trigram in german_trigram_counts:
                german_trigram_count_product *= german_trigram_counts[trigram]
            if trigram in english_trigram_counts:
                english_trigram_count_product *= english_trigram_counts[trigram]
                
        for bigram in bigrams:
            if bigram in german_bigram_counts:
                german_bigram_count_product *= german_bigram_counts[bigram]
            if bigram in english_bigram_counts:
                english_bigram_count_product *= english_bigram_counts[bigram]
        
        # 5. Berechnen der finalen Wahrscheinlichkeiten        
        german_estimated_probability = german_trigram_count_product / german_bigram_count_product
        english_estimated_probability = english_trigram_count_product / english_bigram_count_product
        
        # 6. Ausgabe
        print('Wahrscheinlichkeit für Deutsch:', '{:.20%}'.format(german_estimated_probability))
        print('Wahrscheinlichkeit für Englisch:', '{:.20%}'.format(english_estimated_probability))
        
        if german_estimated_probability == 0 and english_estimated_probability == 0:
            print('>>> Weder deutscher noch englischer Text <<<', end='\n\n')
        elif german_estimated_probability == english_estimated_probability:
            print('>>> Keine exakte Entscheidung möglich <<<', end='\n\n')
        elif german_estimated_probability > english_estimated_probability:
            print('>>> Deutscher Text <<<', end='\n\n')
        elif german_estimated_probability < english_estimated_probability:
            print('>>> Englischer Text <<<', end='\n\n')

guess_language()

Führen wir unser Programm aus, so wird die verwendete Sprache für unsere beispielhaften Eingaben stets korrekt geschätzt:

Bitte Text eingeben (oder 'EXIT' zum Beenden):
niemand hat die Absicht eine Mauer zu errichten
Wahrscheinlichkeit für Deutsch: 0.00000007251907691745%
Wahrscheinlichkeit für Englisch: 0.00000000000000000001%
>>> Deutscher Text <<<

Wahrscheinlichkeit
Wahrscheinlichkeit für Deutsch: 0.00000000892309618041%
Wahrscheinlichkeit für Englisch: 0.00000000000094755424%
>>> Deutscher Text <<<

probability
Wahrscheinlichkeit für Deutsch: 0.00000323016196032069%
Wahrscheinlichkeit für Englisch: 0.00072495287806292592%
>>> Englischer Text <<<

I hope the weather will be fine tomorrow
Wahrscheinlichkeit für Deutsch: 0.00000000000255736900%
Wahrscheinlichkeit für Englisch: 0.00000000016474070119%
>>> Englischer Text <<<

Kruzifix nochamol, ich hab den Klarspüler im dm vergessen
Wahrscheinlichkeit für Deutsch: 0.00000000000000871666%
Wahrscheinlichkeit für Englisch: 0.00000000000000000000%
>>> Deutscher Text <<<

computational linguistics is an awesome field
Wahrscheinlichkeit für Deutsch: 0.00000000000000000000%
Wahrscheinlichkeit für Englisch: 0.00000000000000000195%
>>> Englischer Text <<<

Sie sehen also, lieber Leser, dass es möglich ist, mit einem einfachen statistischen Modell, geringen Trainingsdaten und relativ wenig Programmieraufwand einen mächtigen Spracherkenner in kurzer Zeit nachzubauen. Facebook kocht eben auch nur mit Wasser.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.