Markow-Ketten und Textgenerierung

Ich entschuldige mich dafür, dass ich das hier schreibe, weil es dazu so viel schon im Web gibt, und ich alles, was ich dazu wissen muss, in wenigen Minuten gefunden habe. Aber mein Blog ist ja auch Archiv.

Automatische Textproduktion ist wohl gerade ein Thema. Manche Leute haben Angst vor „social bots“, kleinen Programmen, die selbstständig und automatisch Nachrichten etwa bei Twitter verfassen, die klingen, als wären sie von einem Menschen geschrieben, und die zur politischen Einflussnahmen genutzt werden können. Anderswo heißt es, dass diese Angst völlig unbegründet ist, weil es solche Programme in der freien Wildbahn gar nicht gibt. Im Guardian stand neulich etwas über ein Programm, das so gut künstlichen Text (Sachtext oder fiktional) erzeugt, dass es nicht veröffentlicht wird.

Darum geht es heute nicht, sondern um eine ganz simple Methode, Text zu generieren, der nur auf den allerersten Blick natürlich wirkt, und auf schon auf den zweiten hofft man, dass vielleicht irgendwas ein bisschen Sinn macht, und beim dritten gibt man auf. Hier zwei Beispiele:

vollen Backen verzehren und mir antwortete:—ich fand ich mich auf mein Lieber, laß uns so schwach, alles Gewehr geht vorbei wie er gewartet, hätte mir mit mir selbst. Und da standen um mich, ob täuschende Geister um zweimal im Kreise seiner Ehren und meinen Sinnen, und da—wenn ich solle mit einer bräunlichen Farbe war, als das nicht zu rauben, das
(Goethe)

asked. They sat in the shadow the leaves.“ „Good night,“ the same.“ „You do not wish he likes it.“ „He’s lonely. I know.“ „I want to be unjust. He should have everything I have everything I have killed himself last week,“ he continued the wind. A clean, well-lighted cafe was not lonely. I’m not wish he said. Turning off the
(Hemingway)

Wie das geht: Man füttert den Algorithmus mit einem mehr oder weniger kurzen Text. Das folgende schöne Beispiel habe ich von dieser Seite geklaut, die das Thema für die Sprache Golang betrachtet:

I am not a number. I am a free man.

Dann geht der Algorithmus den Text Wort für Wort durch und legt für jedes Wort eine Liste an, die die im Text vorkommenden Folgewörter enthält. Für das Beispiel sieht das so aus:

I [ am am ]
am [ not a ]
not [ a ]
a [ number free ]
number. [ I ]
free [ man. ]
man. [ ]

Nach dem „I“ steht zweimal „am“, weil das Wort „I“ zweimal von „am“ gefolgt wird und sonst von nichts. Nach „man.“ steht nichts, weil im Ausgangstext nach diesem Wort nichts anderes mehr kommt. Bei längeren Texten ist das unwahrscheinlicher. Und dann nimmt man ein zufällig ausgewähltes Wort aus dieser Sammlung (oder, wie im folgenden Beispiel, man fängt gleich mit „I“ an) und wählt aus der Liste der Folgewörter zufällig eines aus. Und dann macht man mit diesem Folgewort weiter, sucht sich einen von dessen Nachfolgern aus, und so weiter, bis entweder ein Wort kommt, das keinen Nachfolger hat (selten, eher bei kurzen Eingabetexten) oder bis man die gewünschte Wortzahl zusammen hat. Heraus kommen dann zum Beispiel solche Texte:

I am a free man.
I am a number. I am not a free man.
I am a number. I am a free man.
I am not a free man.
I am not a number. I am a number. I am not a number. I am a free man.
I am not a number. I am not a free man.
I am not a number. I am a free man.
I am a number. I am a number. I am a free man.
I am a number. I am a number. I am not a free man.
I am not a number. I am not a number. I am not a free man.

Nach „man.“ hören die Texte jeweils auf – klar, da geht es nicht weiter. Nach „a“ kommt mit gleicher Wahrscheinlichkeit entweder „number“ oder „free“. Nach „I“ kommt mit einer Wahrscheinlichkeit von 1 „am“. (Tatsächlich wäre es vielleicht sauber, jede Instanz eines Folgewort nur einmal in einer Liste zu speichern, zusammen mit der relativen Wahrscheinlichkeit, wobei die Wahrscheinlichkeiten aller Wörter sich dabei zu 1 summieren müssten. Aber bei relativ kleinen Texten ist das so einfacher.)

Für Hemingways „A clean, well-lighted place“ sieht ein Teil des Wörterbuchs übrigens so aus:

Hail [ nothing ]
He [ would disliked smiled was was did can has drinks might sat put should ]
I [ am am have have." am wish have never should know." never ]
I'm [ not ]
In [ the ]
It [ was was was was was is is was ]
Look [ at ]
Many [ must ]
Nor [ can ]
Now, [ without ]
Our [ nada ]

Weil das so viele Wörter sind, gehen wir erst einmal zurück zu unserem kurzen Ausgangstext. Man kann die Information in dem Wörterbuch auch als Graph angeben:

Dabei ist jedes Wort, jeder Lexikoneintrag, ein Zustand des Systems, dargestellt als ein Knoten, verbunden mit den möglichen Folgewörtern durch gerichtete Kanten, die durch eine Gewichtung ausgezeichnet sind, die die Wahrscheinlichkeit des Übergangs angibt – es muss lediglich gelten, dass die Summe aller Kantengewichte, die von einem Knoten ausgehen, 1 ist.

Klar, schöner wäre es, wenn man von „free“ auch noch mit einer gewissen Wahrscheinlichkeit zu „number“ käme. Aber das kommt im – zugegeben sehr kurzen – Ausgangstext nun mal nicht vor. Eine Markow-Kette wäre das dann trotzdem.

Man kann die Übergangswahrscheinlichkeiten der Zustände auch als Tabelle angeben:

Was eine Markow-Kette nun genau ist, muss ein Mathematiker erklären. Hier geht es nur um die einfachen Fälle, mit endlich vielen Zuständen, und Übergangswahrscheinlichkeiten, die nur vom letzten Zustand abhängen. Man könnte ja auch die zwei vorhergehenden Wörter heranziehen, um das Folgewort zu ermitteln.

Markow-Ketten eignen sich wohl zur Simulation von Systemen, die sich damit gut simulieren lassen. :-) Wenn man für ein Computerspiel zum Beispiel zufälliges Wetter braucht, kann man entweder jeden Tag neues Wetter auswürfeln mit 50% Chance für Sonne oder Regen, oder man erstellt eine Markow-Kette, wo man vom Zustand Sonne aus am nächsten Tag mit 80% Wahrscheinlichkeit wieder im Sonnenzustand landet, aber mit 20% bei Regen – und der Zustand Regen funktioniert ähnlich. Dann ändert sich das Wetter auch ab und zu, und es gibt eben so viele Sommer- wie Regentage, aber es gibt längere Folgen und seltenere Wechsel.

Zum Schluss noch ein Auszug aus der modifizierten Schulordnung für Gymnasien in Bayern:

zugelassener Hilfsmittel bei ausreichendem Leistungsstand in Latein mindestens zwei Ausbildungsabschnitten 12/1 ist, abgesehen vom Kurzreferat; 2. Nach Beginn der Gesamtnote „ausreichend“ oder staatlich genehmigten Ersatzschule abzunehmen, wenn nicht auf dem Abschlusszeugnis die Fortsetzung eines schulärztlichen Zeugnisses eine mindestens 1 und Schüler, die nach § 2 Satz 2 Satz 2, der mündlichen Prüfungen abgelegt und Gesellschaft. (3) Für Schulaufgaben in eine Änderung der Nachprüfung erfolgreich unterzogen haben, erhalten sie oder des Ausbildungsabschnitts 12/1 oder dem doppelt gewichteten Durchschnitt der Schulleiter kann für den Fächern Deutsch, Mathematik (Abiturprüfungsfächer 1 und 3. am Kolleg kann bei der Jahrgangsstufe mit der Übertritt in einem vom Staatsministerium gesondert fest. 2Schülerinnen und das Vorrücken gefährdet, so bemühen sich auf Ausschluss von Leistungsnachweisen und Recht sowie in der Hauptprüfung dauern in Anlage 9 nach dem gewählten Ausbildungsrichtung hat die zweite Fremdsprache 1 Punkt bewertet. 8. über das Ziel der Schulleiter festzusetzenden Frist, die sich auf einem Schüler während der Realschule, die Belegung und Worten) ausgedrückt, die Punktzahl der fünf Abiturprüfungsfächern wird ermittelt, indem die ihnen die Schule wird in Satz 1 genannte Zeitpunkt. (4) Während des Gymnasiums sind ferner am Musischen Gymnasien als Abiturprüfungsfächer ist und welche beiden Fächer (Abiturprüfungsfächer 4 erreicht haben sich die auch darauf

Links:

Eine Antwort auf „Markow-Ketten und Textgenerierung“

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.