EXPERIMENTE ZUR TEXTKOMPRESSION

Die von der künstlichen stochastischen Grammatik aus obigem Experiment erzeugten Zeichenreihen lassen sich mit wenig Aufwand stark komprimieren. Der Grund hierfür liegt in der Tatsache, daß die in den Zeichenreihen enthaltene (Shannon-) Information angesichts der Sequenzlängen als sehr niedrig zu bewerten ist.

Für auf natürlichem Wege (z.B. durch Zeitungsjournalisten) generierte Zeichenreihen trifft derartiges nicht (notwendigerweise) zu. Aus diesem Grunde eignen sich Experimente zur Kompression natürlichsprachlicher Texte mit relativ hohem Informationsgehalt auch zur Aufweisung der Schranken des in diesem Kapitel verfolgten Ansatzes.

In Zusammenarbeit mit Stefan Heil (Student an der TUM) wurden (und werden gegenwärtig) daher Versuche zur adaptiven Komprimierung deutscher Sprache durchgeführt. Der zugrundeliegende Datensatz bestand aus 25 Zeitungstexten aus der Zeitung `Frankenpost'. Ein Text verfügte über zwischen 3000 und 10000 Zeichen.

Zur Bewertung der Ergebnisse bedienen wir uns des Begriffs des durchschnittlichen Kompressionsfaktors eines Textkompressionsalgorithmus. Darunter versteht man das durchschnittliche Verhältnis zwischen den Längen von Originaltexten und den Längen der entsprechenden komprimierten Texte. Um eine Vorstellung davon zu bekommen, was ein `guter' Textkompressionsalgorithmus ist, sei ein Satz aus [34] zitiert:

`In general, good algorithms can be expected to achieve an average compression ratio of 1.5, while excellent algorithms based upon sophisticated processing techniques will achieve an average compression ratio exceeding 2.0.'

Der wohl am weitesten verbreitete Textkompressionsalgorithmus ist der Lempel-Ziv Algorithmus [158], welcher u.a. auch die Grundlage der compress-Funktion des Betriebssytems UNIX bildet. Der Lempel-Ziv Algorithmus ist in einem gewissen informationstheoretischen Sinne optimal [154]. Sein durchschnittlicher Kompressionsfaktor beträgt für englischen Text etwas mehr als 2.0.

In den Experimenten wurde wie folgt vorgegangen: Alle Kleinbuchstaben eines jeden Textes wurden in die entsprechenden Großbuchstaben umgewandelt. Als Prediktor $P_1$ der untersten (und bei diesem Experiment einzigen Stufe) wurde statt einem rekurrenten Netz der Einfachheit ein azyklisches BP-Netz und der `Zeitfensteransatz' verwendet. Dabei versucht $P_1$ aus je $n$ aufeinanderfolgenden Zeichen das $n+$erste vorherzusagen. 42 Zeichen eines jeden Textes (Buchstaben, Interpunktionszeichen und Ziffern) besaßen dabei jeweils eine eindeutige lokale Eingaberepräsentation als 43-dimensionale Binärvektoren, bei denen jeweils eine einzige Komponente gleich 1 und alle anderen Komponenten gleich 0 waren. Der dreiundvierzigste mögliche Binärvektor der Länge 1 diente zur Repräsentation aller anderen Zeichen. Der Nullvektor diente zur Repräsentation des `Defaultzeichens' - jedem Text wurden am Anfang $n$ derartige Defaultzeichen vorangestellt.

$P_1$ verfügte über $43n$ Eingabeknoten, $43n$ versteckte Knoten und 43 Ausgabeknoten. Die Eingabelage war vollständig mit der `versteckten Lage' vernetzt, die versteckte Lage war vollständig mit der Ausgabelage vernetzt. Zur Textverarbeitung wurde das Eingabefenster sequentiell über den Text geschoben - $P_1$ erhielt also zunächst die ersten $n$ Zeichen als Eingabe, daraufhin das zweite bis zum $n+$ersten Zeichen, und so fort bis zum Textende. Als deterministische Vorhersage des Prediktors galt jeweils dasjenige Zeichen, dessen Repräsentation den geringsten euklidischen Abstand zum rellwertigen Ausgabevektor von $P_1$ besaß. Während der Textverarbeitung wurde ein komprimiertes File erzeugt, in das nur die vom Prediktor nicht vorhergesagten Zeichen sowie eine Repräsentation der Zahl der Zeichen, die seit dem jeweils letzten unvorhersagbaren Zeichen aufgetreten waren, geschrieben wurden. Aus dem komprimierten File ließ sich das Originalfile mit Hilfe des Prediktors durch eine entsprechende inverse `uncompress'-Funktion also wieder vollständig rekonstruieren.

20 der 25 Textfiles dienten zum Training, 5 ausschließlich zum Testen der Performanz. In andauernden Versuchen sollen verschiedene Zeitfensterbreiten $n$ getestet werden. Signifikante Resultate existieren wegen der zeitaufwendigen Trainingsphase bisher erst für $n=5$: Bei einer Lernrate von 0.2 sowie bei 50 Durchgängen durch die Trainingsfiles lernte $P_1$, 60 Prozent der Buchstaben der Trainingstexte und 47 Prozent der Buchstaben der Testtexte korrekt vorherzusagen (interessant ist natürlich vor allem der Wert für die unbekannten Testtexte). Aufgrund des zusätzlichen Speicheraufwands für die Repräsentationen der Zahl der Zeichen, die seit dem jeweils letzten unvorhersagbaren Zeichen aufgetreten waren, entsprach dies allerdings nicht einer Kompression auf 53 Prozent der Originaltextlänge, sondern lediglich einer Verkürzung auf 64 Prozent. Durch anschließendes einfaches `Huffman-Coding' (siehe z.B. [34]) des komprimierten Files mit Hilfe der UNIX Funktion pack konnte jedoch für unbekannte Texte ein Kompressionsfaktor von insgesamt über 2 erreicht werden.

Schon für $n=5$ schnitt dieses hybride Verfahren damit so gut oder gar besser ab als der Lempel-Ziv Algorithmus, welcher bei den Zeitungstexten auf einen Kompressionsfaktor von durchschnittlich nur knapp 2.0 kam.

Die durch das Netzwerk erzielten Resultate wurde auch verglichen mit durch Stefan Heil als menschlichem Testsubjekt erhaltenen Werten. Heil versuchte sich darin, aus $n$ aufeinanderfolgenden zufällig aus dem Datensatz ausgewählten Buchstaben den $n+$ersten zu prophezeihen. Er erhielt die folgenden Resultate: Für $n=5$ 50 Prozent korrekte Vorhersagen, für $n=10$ 60 Prozent korrekte Vorhersagen, für $n=15$ 68 Prozent korrekte Vorhersagen.

Für $n=5$ erreichte das adaptive Netzwerk also nicht ganz die Performanz des menschlichen Testers, die Ergebnisse waren jedoch zumindest vergleichbar. Es besteht die Hoffnung, daß KNN für $n>5$ ähnlich gut mit der menschlichen Performanz mithalten können, was als Nebenprodukt dieser Untersuchungen ein neuartiges, für praktische Anwendungen interessantes Textkompressionsverfahren zur Folge hätte, welches manche Texte wesentlich besser komprimieren könnte als der Lempel-Ziv Algorithmus.

Obige Experimente zeigen, daß natürlichsprachliche deutsche Texte zwar einen bedeutenden Teil lokal entdeckbarer Redundanz aufweisen, daß die durch Entfernung lokal entdeckbarer Redundanz gewonnenen Kompressionserfolge jedoch erheblich hinter denen mit gewissen einfacheren künstlichen Satzgeneratoren zu erzielenden Resultaten (siehe den vorangegangenen Abschnitt) zurückstehen können. Dieses Ergebnis war zu erwarten: Je mehr algorithmische Information (siehe e.g. [17]) in gewissen Zeichenreihen enthalten ist, desto weniger lassen sie sich durch Geschichtskompression oder irgendein anderes Kompressionsverfahren komprimieren. Das Extrem ist natürlich durch auf rein zufälligem Wege generierte Zeichenreihen gegeben: In diesem Falle lassen sich auf Grund der maximalen algorithmischen Information i.a. überhaupt keine Kompressionserfolge erzielen.

Es bleibt zu untersuchen, welche Domänen der `Echtwelt' sich besonders zur Redundanzreduzierung durch Geschichtskompression eignen. Ein hohes Maß an Redundanz ist beispielsweise in Schwarzweißbildern typischer visueller Szenen (und erst recht in typischen Sequenzen aufeinanderfolgender derartiger Schwarzweißbilder) enthalten. Nach kleineren, auf die Zweidimensionalität von Bilddaten zugeschnittenen Modifikationen des Prinzips der Geschichtskompression könnten sich hier vielversprechende Möglichkeiten ergeben.

Related links in English: Recurrent networks - Fast weights - Subgoal learning - Reinforcement learning and POMDPs - Unsupervised learning and ICA - Metalearning and learning to learn
Deutsche Heimseite