Generieren von Wortvorschlägen / Autovervollständigung

Für viele Leute ist es eine unverzichtbare Funktion des Smartphones: beim Schreiben von Nachrichten wird das nächste Wort vorhergesagt. Die Vorschläge sind oft richtig und erleichtern damit das Schreiben auf der Mini-tastatur.

Das Generieren von Vorschlägen hat viele weitere Anwendungen, zum Beispiel in der Spracherkennung (das Umsetzen eines akoustischen Signals in Schrift): ohne eine Erwartung über das nächste Wort, würden weder Mensch noch Computer viel verstehen.

Eine einfache Variante der Wortvorhersage kann man in Python leicht implementieren. Hierbei stoßen wir direkt auf ein zentrales Problem der statistischen Sprachverarbeitung: die Spärlichkeit (Engl.: sparseness) der Daten.

Worthäufigkeiten und Sprachmodelle

Die Wahrscheinlichkeit für das nächste Wort hängt von vielen Faktoren ab: dem Art des Dokumentes, dem persönlichen Schreibstil und Wortschatz, und vorallem von den vorangegangenen Wörtern. Diese Wahrscheinlicheiten können aus entsprechenden Texten vom richtigen Autor oder im gewünschten Stil berechnet werden. Die Voraussetzung ist, dass es genug Text gibt. Schwieriger ist es mit der Abhängigkeit der vorangegangenen Wörter. Die Abhängigkeit ist groß: auf dem Wort 'die' kann zum Beispiel ein weibliches Substantib aber kein männliches.

Die Wahrscheinlichkeit eines Wortes ist aber auch von weiter vorangegängenen Wörtern abhängig. Je mehr Wörter wir berücksichtigen wollen, desto schwieriger wird das natürlich. In der Sprachverarbeitung macht man oft die vereinfachende Annahme, dass nur eine begrenzte Zahl von Wörtern Einfluss auf das nächste Wort hat. Diese vereinfachende Annahme heißt die Markov-Annahme.

Im Extremfall gehen wir davon aus, dass die Wahl eines Wortes von keinem der vorangegangenen Wörter abhängt. Die Wahrscheinlichkeit lässt sich jetzt direkt aus der Häufigkeit des Wortes in eine Texttcorpus (Eine Sammlung von Texten) berechnen. Die Wörter und ihre Wahrscheinlichkeiten, nennen wir ein Unigramm-modell. In Python kann ein Unigramm-modell als ein Dictionary gespeichert werden.

Wir machen die Funktion auf den ersten Blick unnötig kompliziert: wir nutzen die erste 1000 Sätze aus dem Corpus nicht für unsere Statistik. Diese Sätze wollen wir später noch nutzen um unsere Funktionen zu testen. Wenn wir diese Sätze schon bei der Berechnung der Wahrscheinlichkeiten nutzen würden, würden wir unsere Ergebnisse verfälschen.

Ein Korpus der Größe des Tigercorpus enthält, nach dem Zipf'schen Gesetz sehr viele Wörter, die nur einmal vorkommen (die sogenannte hapax legomena). Diese Wörter werden wir bei unserer Zählung nicht berücksichtigen. Erstens wird unser Dictionary dadurch nicht unnötig groß. Zweitens gibt das einmalige Vorkommen eines Wortes zu wenig Evidenz dafür, dass das Wort wahrscheinlicher ist, als ein Wort, das ünerhaupt nicht vorkommt.

In [20]:
def unigram_model(corpus,start):
    counts = {}
    nrOfWords = 0
    # Zunächst zählen wir die Wörter
    for s in corpus.sents()[start:]:
        for w in s:
            w = w.lower()
            nrOfWords += 1
            f =  counts.get(w,0)
            counts[w] = f+1
    # Jetzt müssen wir die Häufigkeiten durch die Gesamtzahl der Wörter dividieren, um Wahrscheinlichkeiten zu bekommen
    # Bilde Liste von Paare bestehend aus Wort und Wahrscheinlichkeit.
    # Daraus kann ein Dictionary erzeugt werden.
    return dict([(wrd,float(frq)/float(nrOfWords)) for (wrd,frq) in counts.items() if frq > 1])

Wenn es um Autocompletion geht, ist ein Unigramm-Modell nicht besonders spannend: das Modell wird immer das gleiche, nämlich das häufigste Wort, vorschlagen. Interessanter wird es, wenn wir wenigstens ein vorangeganges Wort berücksichtigen. Wir brauchen dazu also ein Statistik über Wortpaare, und nennen das ganze dann ein Bigramm-modell.

In Python können wir ein Bigramm-modell als ein Dictionary mit Wörtern als Schlüssel und Unigramm-Modelle als Werte darstellen: Für jedes Wort müssen wir die Wahrscheinlichkeiten aller Wörter in der nachfolgende Position speichern.

In [21]:
def bigram_model(corpus,start):
    counts = {}
    for s in corpus.sents()[start:]:
        s.insert(0,u'@s')
        for i in range(len(s)-1):
            w1 = s[i].lower()
            w2 = s[i+1].lower()
            cnt_w1 = counts.get(w1,{})
            f = cnt_w1.get(w2,0)
            cnt_w1[w2] = f+1
            counts[w1] = cnt_w1
            
    freqs = {}
    for w in counts:
        cnts_w = counts[w]
        nr_of_w = sum(cnts_w.values())
        model_w = dict([(wrd,float(frq)/float(nr_of_w)) for (wrd,frq) in cnts_w.items() if frq > 1])
        if len(model_w) > 0:
            freqs[w] = model_w

    return freqs 

Wir können ein Bigramm-modell jetzt nutzen, um das nächste Wort vorauszusagen:

In [22]:
def predict(bgmodel,words):
    w = words[-1]
    maxprob = 0
    bestword = ""
    
    if w in bgmodel:
        model = bgmodel.get(w)
        for pred, prob in model.items():
            if prob > maxprob:
                maxprob = prob
                bestword = pred
    return bestword

Anwendung und Test

Wenn wir jetzt eine Menge Text haben, können wir ein Modell tranieren und anschließend anwenden. Für ein gutes Modell brauchen wir Texte, die ähnlich zu den Texten in der Anwendungsdomäne sind. Vorallem brauchen wir aber viele Texte, damit wir zuverlässige Statistiken für möglichst viele Wörter bekommen.

Um unser Modell zu Trainieren können wir einfach Texte aus dem Internet sammeln. In diesem Beispiel nutzen wir eine Textsammlung, die von der Universttät Stuttgart gesammelt wurde und für Forschungszwecke frei verfügbar ist: das Tigercorpus. Dieses Corpus enthält (ältere) Texte aus dem Frankfurter Rundschau mit insgesamt knapp eine Million Wörter. Das Corpus können Sie von der Seite http://www.ims.uni-stuttgart.de/forschung/ressourcen/korpora/tiger.html herunterladen nachdem Sie die Lizenzbedingunegn zugestimmt haben. Von der download Seite laden Sie dann die Datei tigercorpus-2.2.conll09.tar.gz herunter und entpacken diese in dem Verzeichnis Corpora.

Mit dem folgenden Programmzeilen, können Sie das Corpus jetzt aus dem Verzeichnis Corpora einlesen:

In [23]:
import nltk

root = 'Corpora'
fileid = 'tiger.16012013.conll09'
columntypes = ['ignore','words','ignore','ignore','pos']

tiger_corpus = nltk.corpus.ConllCorpusReader(root,fileid,columntypes,encoding='utf8')

Jetzt können wir aus dem Corpus ein Bigramm-Modell ableiten:

In [24]:
ugmodel = unigram_model(tiger_corpus,1000)
bgmodel = bigram_model(tiger_corpus,1000)

Schließlich testen wir unser Modell mit einigen willkürlichen Wörtern:

In [25]:
print(predict(bgmodel,['gegen']))
print(predict(bgmodel,['mit']))
print(predict(bgmodel,['sanktionen']))
print(predict(bgmodel,['helmut']))
print(predict(bgmodel,['gewerkschaft']))
print(predict(bgmodel,['vorsitzender']))
die
der
gegen
kohl
handel
der

Autovervollständigung

Das Wort, das von unserem Model vorgeschlagen wird, wird selten das richtige sein. Wenn wir die erste paar Buchstaben des Wortes geschrieben haben, erwarten wir aber den richtigen Vorschlag. Wir brauchen also eine Funktion, die nicht nur das vorangegange Wort berücksichtigt, sondern auch die bereits geschriebenen Anfangsbuchstaben.

In [26]:
def predict_bg(bgmodel,words,beginning):
    w = words[-1]
    maxprob = 0
    bestword = ""
    
    if w in bgmodel:
        model = bgmodel.get(w)
        for pred, prob in model.items():
            if prob > maxprob and pred.startswith(beginning):
                maxprob = prob
                bestword = pred
    return bestword

Wir testen die Funktion 0 unf mit 1 Anfangsbuchstaben, und sehen, dass jetzt tatsächlich ein anderes Wort vorgeschlagen wird.

In [27]:
print(predict_bg(bgmodel,['maßnahmen'],''))
print(predict_bg(bgmodel,['maßnahmen'],'e'))
zur
ergriffen

Wir können jetzt auch sehr schön sehen, dass der Vorschag besser wird, je mehr Anfangsbuchstaben geschrieben wurden:

In [28]:
satz = ['den']
test = 'vorsitzenden'
for i in range(len(test)+1):
    print(str(i)+' '+satz[0]+' '+test[:i]+'\t'+predict_bg(bgmodel,satz,test[:i]))
0 den 	usa
1 den v	vergangenen
2 den vo	von
3 den vor	vorwurf
4 den vors	vorschlag
5 den vorsi	vorsitz
6 den vorsit	vorsitz
7 den vorsitz	vorsitz
8 den vorsitze	vorsitzenden
9 den vorsitzen	vorsitzenden
10 den vorsitzend	vorsitzenden
11 den vorsitzende	vorsitzenden
12 den vorsitzenden	vorsitzenden

Spärlichkeit

Leider reicht ein Korpus von 900 000 Wörter überhaupt nicht aus, um für jedes Wort gute Vorschläge machen zu können. Viele Wortkombinationen kommen in dem Korpus nie vor:

In [29]:
satz = ['klavier']
test = 'spielen'
for i in range(len(test)+1):
    print(str(i)+' '+satz[0]+' '+test[:i]+'\t'+predict_bg(bgmodel,satz,test[:i]))
0 klavier 	
1 klavier s	
2 klavier sp	
3 klavier spi	
4 klavier spie	
5 klavier spiel	
6 klavier spiele	
7 klavier spielen	

Größere Textmengen lösen diese Problem nicht wirklich. Natürlich helfen mehr Texte, bessere Vorschläge zu generieren, aber es gibt so viele mögliche Kombinationen von Wörtern, dass das Problem immer wieder auftauchen wird. Hier stoßen wir auf ein zentrales Problem der statistischen Sprachverarbeitung: wir haben meistens nicht ausreichend Daten, um gute Modelle zu erstellen.

Es gibt nun verschiedene Möglichkeiten, die Wahrscheinlichkeit eines Wortpaares zu schätzen, wenn der Wert nicht direkt aus den Daten berechnet werden kann. Eine schöne Übersicht über die Methiden hierfür bietet zum Beispiel das Buch Speech and Language Processing von Jurafsky und Martin (https://web.stanford.edu/~jurafsky/slp3/4.pdf)). Wir nutzen hier nur zwei ganz einfache Möglichkeiten.

Wir können zum Beispiel ein Unigramm-Model nutzen, wenn das Bigramm-Model keine Vorschläge gibt. Anders gesagt, wenn wir keine Idee haben, welches Wort dem vorangegangenen Wort folgen kann, schlagen wir einfach das global wahrscheinlichste Wort vor. Wir nennen dieses Verfahren backoff.

In [30]:
def predict_backoff(bgmodel,ugmodel,words,beginning):
    w = words[-1]
    
    maxprob = 0
    bestword = ""
    #Vorhersage mit Bigramm-model
    if w in bgmodel:
        model = bgmodel.get(w)
        for pred, prob in model.items():
            if prob > maxprob and pred.startswith(beginning):
                maxprob = prob
                bestword = pred
    if maxprob == 0:
        #Dann machen wir eine Vorhesage mit dem Unigramm modell
        for pred, prob in ugmodel.items():
            if prob > maxprob and pred.startswith(beginning):
                maxprob = prob
                bestword = pred
    return bestword

Wir testen mit der inzwischen bekannten Schleife:

In [31]:
satz = ['klavier']
test = 'spielen'
for i in range(len(test)+1):
    print(str(i)+' '+satz[0]+' '+test[:i]+'\t'+predict_backoff(bgmodel,ugmodel,satz,test[:i]))
0 klavier 	,
1 klavier s	sich
2 klavier sp	spd
3 klavier spi	spitze
4 klavier spie	spielen
5 klavier spiel	spielen
6 klavier spiele	spielen
7 klavier spielen	spielen

Da die Bigrammwahrscheinlichkeiten oft auf sehr wenigen Daten beruhen, ist zu befürchten, dass diese of nicht zuverlässig sind. Wir können daher immer einen Mittelwert der Bigramm- und der Unigrammwahrscheinlichkeit nutzen. Dabei können die beiden Modelle mit einem unterschiedlichen Gewicht im Mittel berücksichtigt werden. Wir nenen dieses Verfahren (lineare) Interpolation.

In [32]:
def predict_interpol(bgmodel,ugmodel,ugweight,words,beginning):
    w = words[-1]
    model = bgmodel.get(w)
    maxprob = 0
    bestword = ""
    #Vorhersage mit Bigramm-model
    for pred, ugprob in ugmodel.items():
        if w in bgmodel:
            prob = ugweight * ugprob +  (1.0 - ugweight) * bgmodel[w].get(pred,0.0)
        else:
            prob = ugweight * ugprob 
        if prob > maxprob and pred.startswith(beginning):
            maxprob = prob
            bestword = pred

    return bestword

Wir testen auch dies Funktion.

In [33]:
satz = ['klavier']
test = 'spielen'
for i in range(len(test)+1):
    print(str(i)+' '+satz[0]+' '+test[:i]+'\t'+predict_interpol(bgmodel,ugmodel,0.4,satz,test[:i]))
 
print()

satz = ['den']
test = 'vorsitzenden'
for i in range(len(test)+1):
    print(str(i)+' '+satz[0]+' '+test[:i]+'\t'+predict_interpol(bgmodel,ugmodel,0.4,satz,test[:i]))
0 klavier 	,
1 klavier s	sich
2 klavier sp	spd
3 klavier spi	spitze
4 klavier spie	spielen
5 klavier spiel	spielen
6 klavier spiele	spielen
7 klavier spielen	spielen

0 den 	,
1 den v	von
2 den vo	von
3 den vor	vor
4 den vors	vorschlag
5 den vorsi	vorsitz
6 den vorsit	vorsitz
7 den vorsitz	vorsitz
8 den vorsitze	vorsitzenden
9 den vorsitzen	vorsitzenden
10 den vorsitzend	vorsitzenden
11 den vorsitzende	vorsitzenden
12 den vorsitzenden	vorsitzenden

Vollständigkeitshalber schreiben wir jetzt auch noch die Funktion für die Vorhersage mit einem Unigramm-Modell:

In [34]:
def predict_ug(model,beginning):
    maxprob = 0
    bestword = ""
    for pred, prob in model.items():
        if prob > maxprob and pred.startswith(beginning):
            maxprob = prob
            bestword = pred
    return bestword

Evaluierung

Wir haben nun drei Funktionen für die Vorhesage: das Unigramm, das Backoff und das Interpolationsmodell. Bei dem Interpolationsmodell können wir außerdem noch verschiedene Gewichte für die Berechnung des Mittelwertes nutzen. Welche Möglichkeit ist nun die beste?

Das Ziel der Autovervollständigung ist es, Arbeit beim Schreiben einzusparen. Je schneller ein Modell das richtige Wort vorhersagen kann, desto besser ist es. Wir brauchen also eine Funktion, die uns sagt, wie weit vor dem Wortende, die richtige Vorhersage gemacht wird. Da der Gewinn in den meisten Fällen nicht sehr groß ist, fangen wir mit dem größten Wortanfang an, und versuchen immer wieder, ob es mit einem Buchstaben weniger auch klappt.

In [35]:
def test_pred(pred_function,word,prevwords):
    saving = 0
    for i in range(len(word)-1,-1,-1):
        if pred_function(word[:i],prevwords) == word:
            saving = len(word) - i
        else:
            break
    return saving    
In [36]:
satz = ['am']
wort = 'dienstag'
ip = test_pred(lambda word, sent: predict_interpol(bgmodel,ugmodel,0.4,sent,word),wort,satz)
bo = test_pred(lambda word, sent: predict_backoff(bgmodel,ugmodel,sent,word),wort,satz)
ug = test_pred(lambda word, sent: predict_ug(ugmodel,word),wort,satz)

print('Ergebnis Interpolation:',ip)
print('Ergebnis Backoff:',bo)
print('Ergebnis Unigramm:',ug)
Ergebnis Interpolation: 7
Ergebnis Backoff: 7
Ergebnis Unigramm: 4

Mit den ersten 500 Sätzen aus dem Korpus können wir jetzt testen, welches Gewicht für die Interpolation die besten Ergebnisse liefert.

In [37]:
def eval(corpus,start,end,pred_func):
    count = 0
    saving = 0
    for s in corpus.sents()[start:end]:
        s.insert(0,u'@s')
        for i in range(1,len(s)-1):
            prec = s[i-1].lower()
            word = s[i].lower()
            count += 1
            saving += test_pred(pred_func,word,[prec])
    return float(saving)/float(count)

Bei der Implementierung haben wir nicht auf Effizienz geachtet. Das rächt sich jetzt ein wenig. Das Testen von mehreren tausenden Wortpaaren dauert sehr lang.

In [38]:
%matplotlib inline
import matplotlib.pyplot as plt


weigths = [0.01*x for x in range(0,80,5)]
results = [eval(tiger_corpus,0,500,lambda word, sent: predict_interpol(bgmodel,ugmodel,w,sent,word)) for w in weigths]

plt.plot(weigths, results, 'r')
Out[38]:
[<matplotlib.lines.Line2D at 0x1ba4cc65f28>]

Jetzt können wir mit den verbliebenen 500 Sätzen testen, welches Verfahren die beste Ergebnisse liefert.

In [39]:
ip = eval(tiger_corpus,500,1000,lambda word, sent: predict_interpol(bgmodel,ugmodel,0.2,sent,word))
bo = eval(tiger_corpus,500,1000,lambda word, sent: predict_backoff(bgmodel,ugmodel,sent,word))
ug = eval(tiger_corpus,500,1000,lambda word, sent: predict_ug(ugmodel,word))

print('Ergebnis Interpolation:',ip)
print('Ergebnis Backoff:',bo)
print('Ergebnis Unigramm:',ug)
Ergebnis Interpolation: 1.9288385511272572
Ergebnis Backoff: 1.9317234747302061
Ergebnis Unigramm: 1.5797627951704243

Wir sparen im Schnitt also etwa zwei Buchstaben pro Wort. Es gibt noch viele Möglichkeiten, dieses Ergebnis zu verbessern. Erstens können wir mehr Text zum Berechnen der Wahrscheinlichkeiten nutzen. Zweitens können wir statt Bigrammmodelle auch Trigrammodelle nutzen. Es gibt viele Konstruktionen wie "Er las einen Text". Die Abhängigkeit zwischen las und Text wird mit einem Bigrammmodell nicht erfasst, aber mit einem Trigrammmodell. Schließlich gibt es noch weitaus bessere (und kompliziertere) Verfahren als die hier benutzte, einfache Interpolation und das Backoff.

Das benutzte Testverfahren eignet sich zum Evaluieren der Modelle. Um die Usability einer Anwendung und die Qualität der Modelle für eine Anwendung zu testen, bräuchten wir noch andere Tests. Zum Beispiel bringt das Vorhersagen des letzten Buchstaben nichts beim Schreiben, hilft aber gut in unserer Statistik. Der Durchschnittswert ist als kein gutes Maß. Außerdem machen die meisten Anwendungen mehrere Vorschläge, und nicht nur einen.