Textanalyse und Textgenerierung/Wege in Graphen

Gewichteter Graph und absolute Häufigkeit - Knoten entsprechen Wörtern und die Gewichtung drückt aus, dass z.B. in einem Datensatz das Wort A 10x nach dem Wort B aufgetreten ist.

Einführung

In dieser Lerneinheit werden Wege in Graphen betrachtet und an einen kurzen Satz in deutscher Sprache als Beispiel der Weg in einem Graph als einen Wort-zu-Wort-Übergang beschrieben. Dabei werden grundlegende Kenntnisse in der Graphentheorie verwendet und der Wort-zu-Wort-Weg über stochastischen Übergangsmatrizen formalisieren.

Lernvoraussetzungen

Grundlegende Kenntnisse in Graphentheorie
Grundlegende Kenntnisse in stochastischen Prozessen und Übergangsmatrizen

Schritte zur Formalisierung

Der Lerneinheit gliedert sich in die folgenden Teile:

Definition des Graphen
Formalisierung eines Satzes als Weg
Stochastische Übergangsmatrizen
Matrixmultiplikation für Wortassoziationen

Schritt 1 - Definition des Graphen

Ein gewichteter Graph $G=(V,E,w)$ besteht aus einer Menge von Knoten $V$ und einer Menge von Kanten $E$ .
Jeder Knoten $v\in V$ repräsentiert ein Wort
Jede Kante $(u,v)\in E$ repräsentiert einen Übergang von einem Wort $u$ zu einem Wort $v$ .

Schritt 2 - Formalisierung eines Satzes als Weg

Ein Satz kann als ein Weg im Graphen $G$ betrachtet werden.
Ein Weg ist eine Folge von Knoten $(v_{1},v_{2},\ldots ,v_{n})$ , wobei $(v_{i},v_{i+1})\in E$ für alle $i$ .

Schritt 3 - Stochastische Übergangsmatrizen

Eine stochastische Übergangsmatrix $P$ gibt die Wahrscheinlichkeit des Übergangs von einem Knoten zu einem anderen an.
Die Matrix $P$ hat die Dimension $|V|\times |V|$ , wobei $P_{ij}$ die Wahrscheinlichkeit des Übergangs von Knoten $j$ zu Knoten $i$ ist.
Die Summe der Wahrscheinlichkeiten in jeder Spalte von $P$ ist 1: $\sum _{i=1}^{|V|}P_{ij}=1$ für alle $j\in \{1,\ldots ,|V|\}$ .

Schritt 4 - Beispielsatz

Betrachten wir den Satz "Der Hund jagt die Katze".
Der Graph $G$ hat die Knoten $V=\{{\text{Der}},{\text{Hund}},{\text{jagt}},{\text{die}},{\text{Katze}}\}$ .
Die Kanten $E$ sind $\{({\text{Der}},{\text{Hund}}),({\text{Hund}},{\text{jagt}}),({\text{jagt}},{\text{die}}),({\text{die}},{\text{Katze}})\}$ .
Die Übergangsmatrix $P$ könnte wie folgt aussehen, wobei $x_{1}$ "Der" entspricht und $x_{2}$ "Hund":

$P={\begin{pmatrix}0&0&0&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\end{pmatrix}}\,\,\,\,\,\,\,\,P\cdot x_{1}=P\cdot {\begin{pmatrix}1\\0\\0\\0\\0\\\end{pmatrix}}={\begin{pmatrix}0\\1\\0\\0\\0\\\end{pmatrix}}=:x_{2}$

Schritt 5 - Matrixmultiplikation für Wortfolgen

Der Startvektor $x_{1}:=(1,0,0,0,0)\in \mathbb {R} ^{5}$ besagt, dass der Satz mit dem ersten Wort "Der" der Wortmenge mit einer Wahrscheinlichkeit 1 beginnt. Die Matrixmultiplikation $x_{2}:=P\cdot x_{1}=(0,1,0,0,0)\in \mathbb {R} ^{5}$ assoziiert das Wort "Der" ( $x_{1}$ ) mit dem nächsten Wort "Hund" mit einer Wahrscheinlichkeit 1. Analog erhält man $x_{3}:=P\cdot x_{2}=(0,0,1,0,0)\in \mathbb {R} ^{5}$ nicht nächste Wort-zu-Wort-Verbindung von Wort "Hund" zu dem Wort "jagt". Mit $x_{4}:=P\cdot x_{3}=(0,0,0,1,0)\in \mathbb {R} ^{5}$ wird die Wortverbindung $(jagt,die)$ repräsentiert und mit $x_{5}:=P\cdot x_{4}=(0,0,0,0,1)\in \mathbb {R} ^{5}$ .

Schritt 6 - Matrixmultiplikation und Satzende

Wenn man den repräsentierenden Vektor $x_{5}=(0,0,0,0,1)\in \mathbb {R} ^{5}$ für "Katze" wiederum in die Assoziationsmatrix $P$ einsetzt, erhält man den Nullvektor über $P\cdot x_{5}=(0,0,0,0,0)\in \mathbb {R} ^{5}$ . Damit ist "Katze" mit keinem anderen Wort aus dem kleinen Wortschatz mit 5 Wörtern assoziiert.

Schritt 7 - Weg in einem Wortgraphen

In dem obigen Beispiel wird eine Weg in einem Wortschatz über eine Assoziation zwischen Wörtern generiert. Es entsteht der Satz "Der Hund jagt die Katze" repräsentiert durch einen Wort-zu-Wort-Weg, der über die Sequenz von Vektoren $(x_{1},x_{2},x_{3},x_{4},x_{5})$ bestimmt wurde.

Aufgaben für Studierende

Stochastische Wort-zu-Wort-Übergänge
Absolute und relative Häufigkeiten
$N$ -Gramme

Aufgabe 1 - Stochastische Wort-zu-Wort-Übergänge

Erzeugen Sie ein kleine Übergangsmatrix für die Sätze "Wie geht es Ihnen", "Wie geht es Dir", "Wie geht es Euch". Legen Sie die Wahrscheinlichkeiten bei einer stochastischen Matrix verteilt. Dies Beispiel soll das obige Beispiel etwas verallgemeinern, wobei stochastische Wortfolgen durch eine Matrix $P$ repräsentiert werden.

Aufgabe 2 - Absolute und relative Häufigkeiten

Betrachten Sie einen Ausgangstext, den man als Trainingstext für eine stochastische Matrix auffassen kann. Wie kann man aus der absoluten Häufigkeiten $(Wort1,Wort2)$ -Übergängen die Wahrscheinlichkeiten der Stochastischen Matrix gewinnen.

Aufgabe 3 - N-Gramme

Der Begriff $N$ -Gramm wird bei Texten verwendet, wenn man diesen in jeweils $N$ aufeinanderfolgende Fragmente (z.B. Wörter) zerlegt wird. Werden $N$ -Gramme verwendet, ist nicht nur das vorherige Wort für die Wahrscheinlichkeitsverteilung des Folgewortes verantwortlich, sondern die letzten $N$ Wörter bestimmen das Folgewort. Erläutern Sie den Begriff $N$ -Gramm am Beispiel der Trigamme $({\mbox{''Wie''}},{\mbox{''geht''}},{\mbox{''es''}})$ und $({\mbox{''Wo''}},{\mbox{''gibt''}},{\mbox{''es''}})$ und suchen Sie für beide $N$ -Gramme geeignete Folgewörter nach dem "es"!

Welchen Vorteil haben $N$ -Gramme im Vergleich zu einer reinen Wort-zu-Wort-Assoziationsmatrix $P$ ?
Welche Dimension hat eine assoziative stochastische Matrix ${\widehat {P}}$ , wenn der Wortschatz $k$ Wörter enthält und statt der Wort-zu-Wort-Assoziation Trigramme mit einzelnen Wörter aus dem Wortschatz assoziiert wird (siehe Kombinatorik)?

Fazit

Die Formalisierung von Sätzen als Wege in einem Graphen und die Verwendung von stochastischen Übergangsmatrizen bietet eine strukturierte Methode zur Analyse und Modellierung von Sprache. Diese Techniken sind grundlegend für viele Anwendungen in der Sprachverarbeitung und der Informatik.

Siehe auch