“Evolution works through DNA-guided protein synthesis and research dollars are halving every year for the purpose is growing exponentially.” — Ray Kurzweil selbst hätte es (nun ja, fast) nicht schöner formulieren können. Und doch stammt die Zeile direkt aus dem Computer, einem einfachen Text-Generator sei Dank. Wie das genau funktioniert und was sich hinter dem Begriff Markov-Ketten verbirgt, das soll in den folgenden Absätzen näher erläutert werden.

Zunächst stellt sich jedoch die Frage: Wozu brauche ich überhaupt einen Text-Generator? Abgesehen davon, dass die Antwort in den meisten Fällen “überhaupt nicht” lauten dürfte, fallen mir spontan einige Anwendungsmöglichkeiten ein (eine sinnvoller und ernstgemeinter als die andere):

• Reports, Aufsätze oder Facharbeiten in letzer Minute
• Täglich neue Versionen von “Alice im Wunderland” [5]
• Spaß mit Usenet-Gruppen [4]
• Suchmaschinenspam
• Sinnentleerte Poesie
• Antworten auf Nigeria-Connection-Scam-Mails [6]
• E-Mail-Antworten auch in stressigen Zeiten [6]
• … just for fun

Das Prinzip eines Text-Generators

Das Prinzip hinter solchen Generatoren ist relativ simpel: Ein Text wird zunächst daraufhin analysiert, welche Wörter mit welcher Wahrscheinlichkeit auf welche anderen Wörter folgen. Betrachten wir als Beispiel das Wort “die” in diesem Artikel (so weit er bis jetzt fortgeschritten ist): Mit jeweils 25% Wahrscheinlichkeit folgen die Begriffe “Antwort”, “Zeile “, “andere)” und “Frage”.

Werden diese Wahrscheinlichkeiten für jedes Wort gespeichert, so lässt sich — ausgehend von einem Startwort — ein neuer Text Wort für Wort aufbauen. Für jedes Wort wird zufällig ein Nachfolgewort ausgewählt; die vorher bestimmten Wahrscheinlichkeiten entsprechen dabei den Wahrscheinlichkeiten für die Auswahl der Nachfolgewörter.

Im Wikipedia-Artikel zum Thema Markov-Ketten [2] wird das zunächst mit einer für Nicht-Mathematiker abschreckenden Formel und dann folgendermaßen formuliert:

(..) das heißt, dass die Wahrscheinlichkeit für den Zustand zum Zeitpunkt t+1 nur von dem Zustand zum Zeitpunkt t abhängt. Dies bezeichnet man als Gedächtnislosigkeit oder auch Markow-Eigenschaft.

Verwenden wir als Ausgangstext (wie bereits zu Beginn dieses Artikels) das “Law of Accelerating Returns” von Ray Kurzweil [3], so sieht das Ergebnis zum Beispiel folgendermaßen aus:

Evolution has continuously accelerated. The subsequent emergence of the first step, the first technology-creating species resulted in the environment in power and maintain a technology-creating species, the next generation’s design, and of information does not the overall “power” of data from one stage of accelerating returns pertains to biological brains. # A recording information is predictable. Noise is to create new generations of other innovations).

Was auf den ersten Blick interessant aussehen mag, entpuppt sich bei genauerem Hinsehen als völliger Unsinn.

Der Markov-Algorithmus

Wie wird das Modell der Markov-Ketten nun konkret als Algorithmus umgesetzt? Ein kurzes Script in der Programmiersprache Python [1] soll uns hier als Beispiel dienen.

Zunächst wird die Textdatei markov.txt eingelesen und Wort für Wort in einer Liste gespeichert:
#!/usr/bin/python
# -*- coding: cp1252 -*-
from random import random
 
f = open('markov.txt')
TextIn = f.read()
f.close()
 
TextIn = TextIn.replace('\n', ' ')
TextIn = TextIn.split(' ')
TextIn = [n for n in TextIn if n not in '']


Jetzt steht die Analyse des Textes an: Für jedes vorkommende Wort speichern wir in WortDict, wie oft welche anderen Wörter direkt auf dieses Wort folgen:
WortDict = {}
 
for w in range(len(TextIn)-1):
    if (TextIn[w] != ''):
        if not WortDict.has_key(TextIn[w]):
            WortDict[TextIn[w]] = {}
        if not WortDict[TextIn[w]].has_key(TextIn[w+1]):
            WortDict[TextIn[w]][TextIn[w+1]] = 1.0
        else:
            WortDict[TextIn[w]][TextIn[w+1]] += 1.0


Die Anzahl des Aufeinanderfolgens bestimmter Wörter wird in Wahrscheinlichkeiten umgerechnet:
for (Wort, NextDict) in WortDict.items():
    # Gesamtzahl nächster Wörter berechnen
    TotalCount = 0
    for (NextWort, Count) in NextDict.items():
        TotalCount += Count
    # Zahl für jedes nächste Wort durch Gesamtzahl teilen
    for (NextWort, Count) in NextDict.items():
        WortDict[Wort][NextWort] = WortDict[Wort][NextWort]/TotalCount


Schließlich können wir einen neuen Text mit einer dem Ausgangstext ähnlichen Wahrscheinlichkeitsverteilung der Wortfolgen erstellen. CurWort legt fest, mit welchem Wort der Text beginnen soll, LenText die maximale Anzahl an Wörtern. Zur Auswahl des jeweils nächsten Wortes werden die Einzel-Wahrscheinlichkeiten für sämtliche Möglichkeiten als Aufteilung des Bereichs [0;1] gesehen und festgestellt, wo in diesem Bereich sich die Zufallszahl x befindet. Der so gewählte Bereich legt das nächste Wort fest.
CurWort = 'Evolution'
LenText = 30
Text = CurWort
 
for n in range(200):
    x = random()
    ProbSum = 0
    for (NextWort, Prob) in WortDict[CurWort].items():
        if (x >= ProbSum) and (x < ProbSum+Prob):
            Text += ” ” + NextWort
            CurWort = NextWort
        ProbSum += Prob
 
# Ausgabe des Textes bis zum letzen Punkt.
print Text[:Text.rfind('.')+1]


Beispiele für generierte Texte

Was könnte ein solcher Markov-Prozess nun mit inhaltlich wertvollen Texten wie der Cyberkultur-Reihe [7] des französischen Philosophen Pierre Lévy anstellen? Na, zum Beispiel das:

Die Verbindung von virtuellen Welten, durch die Bildschirme. Dann entdeckte ich, daß die Computernetze zugunsten der modernen Demokratie gekämpft … und institutionalisiert, die Papierseiten mit der Verteilung ausgehend von allem in dem Cyberspace mehr aus einer Totalität, deren Kommunikationspraxis konnte eine kulturelle Universum an ihren Hervorbringungen haben wir uns in den Seiten anderer Dokumente verbindet, weil er ist, neue Verkaufsargumente. Symmterisch dazu verdammt, den traditionellen Medien legitimiert wird? Diejenigen, die bestehenden Infrastrukturen zu schaffen, Information darstellt, sollte gemäß dem begrenzten Programm der großen Menge von Gruppen, Beziehungsstile zwischen den Cyberspace beeinflussen.

Je kürzer der Text, um so mehr wird das Ergebnis dem Ausgangstext ähneln. Versuchen wir es für etwas kreativere Textgestaltung deshalb mit Kants im Textformat ganze 1.2 MB einnehmender “Kritik der reinen Vernunft”:

Der hypothetische Urteil vom Gegenstande weiß, die Gesetzgebung erforderlich ist. Es besteht das Vermögen vorkommt, Unterarten, unter den Dingen vorhergeht, darin von der Frage: ob man sie die allererst möglich sei, aus irgendeiner Grundkraft, soviel gepriesener und künftigen Zeit existieren. Woran erkennt die Unabhängigkeit von der des intelligiblen Charakter haben, wie es ihm unterworfen ist. Denn der außer mir für Erscheinungen keine bestimmten Erfahrung hineinbringt, müssen mir etwas vorstellen, daß die mir immer sein, niemals etwas Unmögliches, und die transzendentale Ästhetik*.

Alles klar?

Wer das gerne mit eigenen Texten versuchen möchte, kann entweder direkt mit der Python-Datei spielen [8] oder sich an der Online-Version von Elje.net [9] versuchen.

[1] The Python Programming Language
[2] Wikipedia: Markow-Kette
[3] Kurzweil’s Law (aka “the law of accelerating returns”)
[4] Markov-Texte im Usenet: Mark V Shaney
[5] Fun with Markov Chains
[6] Fun things to do with a Markov Process
[7] Telepolis: Cyberkultur
[8] AI Playground Download: Markov.py
[9] Elje.net: Markov Text Generator