Textanalyse und Textgenerierung/Graphen von Textfragmenten

Einleitung

In dieser Lerneinheit geht es um die Erzeugung von mathematischen Graphen, bei denen Wörter in den Knoten stehen und Übergangswahrscheinlichkeiten an den Verbindungen die Wahrscheinlichkeit angeben, welches Wort als nächstes Wort bei der Bildung eines Satzes verwendet werden können. Die Übergangswahrscheinlichkeiten werden als eine stochastische Matrix dargestellt.

Beispiel

In diesem Beispiel verwenden wir die Wörter "Wie", "geht", "es", "Ihnen" und "Dir" als Knoten und setzen die Übergangswahrscheinlichkeiten so, dass sinnvolle Sätze in deutscher Sprache gebildet werden können.

Schritt 1: Definition der Knoten

Die Knoten des Graphen sind:

Knotentabelle
Knoten	Wort	Knoten	Wort
(K1)	"Wie"	(K4)	"Dir"
(K2)	"geht"	(K5)	"Ihnen"
(K3)	"es"	(K6)	"Euch"

Schritt 2: Definition der Übergangswahrscheinlichkeiten

Da die Lerneinheit auch dazu dient, in die Funktionsweise von stochastischen Modellen zu Textgenerierung einzuführen, wird eine einfach stochastische Matrix mit deterministischen und stochastischen Zustandsübergängen definiert. Insgesamt muss man die Übergangswahrscheinlichkeiten wegen der Normierung von Wahrscheinlichkeitsmaßen so festlegen, dass die Summe der ausgehenden Kantengewichte für jeden Knoten 1 ist. Dies entspricht der Spaltensummen in der stochastischen Matrix. Bei deterministischen Zustandsübergängen finden nur an einer Stelle in der Spalte eine 1 Dies entspricht den .

Schritt 3: Erstellung der stochastischen Matrix

Eine stochastische Matrix $P$ ist eine quadratische Matrix, bei der die Summe der Elemente jeder Spalte 1 ist. Die Elemente der Matrix geben die Übergangswahrscheinlichkeiten zwischen den Knoten an.

Angenommen, wir haben die folgenden Übergangswahrscheinlichkeiten:

Von "Wie" zu "geht": 1
Von "geht" zu "es": 1
Von "es" zu "Ihnen": ${\frac {1}{3}}$
Von "es" zu "Euch": ${\frac {1}{3}}$
Von "es" zu "Dir": ${\frac {1}{3}}$

Diese Übergangswahrscheinlichkeiten können in einer stochastischen Matrix $P$ dargestellt werden:

P={\begin{pmatrix}0&0&0&0&0\\1&0&0&0&0\\0&0.5&0&0&0\\0&0.5&0.5&0&0\\0&0&0.5&1&1\end{pmatrix}}

Schritt 4: Interpretation der Matrix

Die Matrix $P$ gibt die Übergangswahrscheinlichkeiten zwischen den Knoten an. Zum Beispiel:

- Die erste Zeile gibt die Übergangswahrscheinlichkeiten von "Wie" zu den anderen Knoten an. - Die zweite Zeile gibt die Übergangswahrscheinlichkeiten von "geht" zu den anderen Knoten an. - Die dritte Zeile gibt die Übergangswahrscheinlichkeiten von "es" zu den anderen Knoten an. - Die vierte Zeile gibt die Übergangswahrscheinlichkeiten von "Ihnen" zu den anderen Knoten an. - Die fünfte Zeile gibt die Übergangswahrscheinlichkeiten von "Dir" zu den anderen Knoten an.

Schritt 5: Beispiel für die Erzeugung eines Satzes

Um einen sinnvollen Satz zu erzeugen, können wir die Übergangswahrscheinlichkeiten verwenden, um von einem Knoten zum nächsten zu gehen. Zum Beispiel:

1. Beginne bei "Wie". 2. Gehe mit Wahrscheinlichkeit 1 zu "geht". 3. Gehe mit Wahrscheinlichkeit 0.5 zu "es" oder mit Wahrscheinlichkeit 0.5 zu "Ihnen". 4. Wenn du bei "es" bist, gehe mit Wahrscheinlichkeit 0.5 zu "Ihnen" oder mit Wahrscheinlichkeit 0.5 zu "Dir". 5. Wenn du bei "Ihnen" bist, gehe mit Wahrscheinlichkeit 1 zu "geht". 6. Wenn du bei "Dir" bist, gehe mit Wahrscheinlichkeit 1 zu "geht".

Ein möglicher Satz könnte also "Wie geht es Ihnen" oder "Wie geht es Dir" sein.

Zusammenfassung

Die Erzeugung von mathematischen Graphen mit Wörtern in den Knoten und Übergangswahrscheinlichkeiten an den Verbindungen kann durch eine stochastische Matrix dargestellt werden. In diesem Beispiel haben wir die Wörter "Wie", "geht", "es", "Ihnen" und "Dir" als Knoten verwendet und die Übergangswahrscheinlichkeiten so gesetzt, dass sinnvolle Sätze in deutscher Sprache gebildet werden können. Die stochastische Matrix gibt die Übergangswahrscheinlichkeiten zwischen den Knoten an und kann verwendet werden, um sinnvolle Sätze zu erzeugen.

Aufgabe für Studierende (Stochastik auf Texten - N-Gramme)

Teil 1: Der Text

Gegeben ist ein einfacher Satz (dieser ist nicht zufällig gewählt):

„Das ist ein einfacher Satz.“

Teil 2: Monogramme (1-Gramme) – Was ist am häufigsten?

Zähle die Häufigkeit der Buchstaben in den ersten 15 Buchstaben:

Das ist ein einfac

Die einzelnen Buchstaben sind Fragmente des Textes, sogenannte N-Gramme. Hier, da das Fragment aus einem Objekt besteht, eben ein 1-Gramm oder Monogramm. Die untenstehende Tabelle gibt die Häufigkeit eines jeden 1-Gramm an.

Häufigkeit der Buchstaben (Monogramme)- ’LZ’ steht für Leerzeichen
Buchstabe	Häufigkeit
D	1
a	2
s	2
i	3
t	1
e	2
n	2
f	1
c	1
LZ	3

Teil 3: Bigramme (2-Gramme) – Was kommt nach „e“?

Ein Bi-Gramm ist ein Paar aufeinanderfolgender Buchstaben.

Aus den 15 Buchstaben lassen sich insgesamt 17 verschiedene Bi-Gramme finden. So beispielsweise ’DA’, ’AS’ und ’S LZ’ (LZ steht nach wie vor für das Leerzeichen).

Zählt man wieder die Häufigkeiten so ergibt sich:
Die Bigramme ei, LZ e und in kommen je 2-mal vor, alle anderen nur 1 mal!
Nun soll aufgrund dieser Analyse der Satzanfang ”EineLZ” vervollständigt werden. Dazu wird gemäß der ausgezählten Häufigkeiten ein Wahrscheinlichkeitsmaß erfast (frequentistisches W-Maß, definiert durch die relativen Häufigkeiten) und ein Folgezeichen abhängig von dem ersten Zeichen im 2-Gramm ’ausgewürfelt’. Welche folgenden zwei Zeichen erwartet man am häufigsten für den obigen Satzanfang nach sehr vielen Simulationen für die Vorhersage?

Teil 4: Verallgemeinerung

Das ist die Grundidee von N-Grammen die zur Vorhersage von Sprache verwendet werden. Natürlich wird im Allgemeinen ein N betrachtet das deutlich größer als 2 ist, damit so der Kontext von vorangehenden Wörtern erfasst werden kann.
Trotzdem lassen sich bereits aus 2-Grammen zwei fundamentale Regeln ableiten:. Nach einem beliebigen Training mit 2-Grammen wird:

ein Großbuchstabe immer nur nach einem Leerzeichen kommen
nach einem Punkt kommt immer ein Großbuchstabe

Teil 5: Erweiterung

Wir kommen zurück zu unserem Satzbeginn oben. Betrachten wir nun die bedingte Wahrscheinlichkeit:
$P('as'|'{\text{erster Buchstabe des 2-Gramms ist ein a}}')$ (also die Wahrscheinlichkeit das, ausgehend von einem a das 2-Gramm as gewählt wird)
Es kann gefolgert werden, dass diese Wahrscheinlichkeit ${\textstyle {\frac {1}{2}}}$ betragen muss. Warum?

Analog kann folgende Tabelle gefolgert werden, wobei der Ausgangszustand (erste Zeile) in der Kopfzeile und der Folgezustand (zweiter Buchstabe) in der ersten Spalte angegeben ist:

**stochastische Übergangsmatrix:** Wahrscheinlichkeiten für Bigramme (2-Gramme)
Ausgangszustand	a	D	e	f	i	LZ	n	s	t
a	0	1	0	1	0	0	0	0	0
c	0,500	0	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0	0	0
e	0	0	0	0	0	0.666	0	0	0
f	0	0	0	0	0	0	0,500	0	0
i	0	0	1	0	0	0.333	0	0	0
LZ	0	0	0	0	0	0	0,500	0,500	1
n	0	0	0	0	0,500	0	0	0	0
s	0,500	0	0	0	0,500	0	0	0	0
t	0	0	0	0	0	0	0	0,500	0

Erstelle nun einen neuen Satz. Beginne mit einem ’D’. Sollten mehrere Möglichkeiten für einen Buchstaben möglich sein, simuliere ein passendes, beliebiges Zufallsexperiment zur Auswahl. Simuliere mehrmals!
Warum erhält man mit größer werdenen N-Grammen und mehr Trainingssätzen bessere Wortvorhersagen?
Begründe die folgende Formel für die Wahrscheinlichkeit der Vorhersage von ${\textstyle w_{n}}$ nach dem ein N-Gramm die ersten N-1 Zeichen ${\textstyle (w_{n-N+1},\dots ,w_{n-1})}$ hat. $P(w_{n}\mid w_{n-N+1},\dots ,w_{n-1})={\frac {{\text{Häufigkeit von }}(w_{n-N+1},\dots ,w_{n})}{{\text{Häufigkeit von }}(w_{n-N+1},\dots ,w_{n-1})}}$