{"id":12978,"date":"2019-06-12T18:58:04","date_gmt":"2019-06-12T16:58:04","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=12978"},"modified":"2022-12-04T13:42:45","modified_gmt":"2022-12-04T12:42:45","slug":"markow-ketten-und-textgenerierung","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2019\/06\/markow-ketten-und-textgenerierung.htm","title":{"rendered":"Markow-Ketten und Textgenerierung"},"content":{"rendered":"
(2 Kommentare.<\/a>)<\/small> <\/div>\n

Ich entschuldige mich daf\u00fcr, 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.<\/p>\n\n\n\n

Automatische Textproduktion ist wohl gerade ein Thema. Manche Leute haben Angst vor „social bots“, kleinen Programmen, die selbstst\u00e4ndig und automatisch Nachrichten etwa bei Twitter verfassen, die klingen, als w\u00e4ren sie von einem Menschen geschrieben, und die zur politischen Einflussnahmen genutzt werden k\u00f6nnen. Anderswo hei\u00dft es, dass diese Angst v\u00f6llig unbegr\u00fcndet ist, weil es solche Programme in der freien Wildbahn gar nicht gibt. Im Guardian stand neulich<\/a> etwas \u00fcber ein Programm, das so gut k\u00fcnstlichen Text (Sachtext oder fiktional) erzeugt, dass es nicht ver\u00f6ffentlicht wird.<\/p>\n\n\n\n

Darum geht es heute nicht, sondern um eine ganz simple Methode, Text zu generieren, der nur auf den allerersten Blick nat\u00fcrlich 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:<\/p>\n\n\n\n

vollen Backen verzehren und mir antwortete:\u2014ich fand ich mich auf mein Lieber, la\u00df uns so schwach, alles Gewehr geht vorbei wie er gewartet, h\u00e4tte mir mit mir selbst. Und da standen um mich, ob t\u00e4uschende Geister um zweimal im Kreise seiner Ehren und meinen Sinnen, und da\u2014wenn ich solle mit einer br\u00e4unlichen Farbe war, als das nicht zu rauben, das
(Goethe)<\/p><\/blockquote>\n\n\n\n

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)<\/p><\/blockquote>\n\n\n\n

Wie das geht: Man f\u00fcttert den Algorithmus mit einem mehr oder weniger kurzen Text. Das folgende sch\u00f6ne Beispiel habe ich von dieser Seite geklaut,<\/a> die das Thema f\u00fcr die Sprache Golang betrachtet:<\/p>\n\n\n\n

I am not a number. I am a free man.<\/p><\/blockquote>\n\n\n\n

Dann geht der Algorithmus den Text Wort f\u00fcr Wort durch und legt f\u00fcr jedes Wort eine Liste an, die die im Text vorkommenden Folgew\u00f6rter enth\u00e4lt. F\u00fcr das Beispiel sieht das so aus:<\/p>\n\n\n\n

I [ am am ]\nam [ not a ]\nnot [ a ]\na [ number free ]\nnumber. [ I ]\nfree [ man. ]\nman. [ ]<\/pre>\n\n\n\n
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\u00e4ngeren Texten ist das unwahrscheinlicher. Und dann nimmt man ein zuf\u00e4llig ausgew\u00e4hltes Wort aus dieser Sammlung (oder, wie im folgenden Beispiel, man f\u00e4ngt gleich mit „I“ an) und w\u00e4hlt aus der Liste der Folgew\u00f6rter zuf\u00e4llig 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\u00fcnschte Wortzahl zusammen hat. Heraus kommen dann zum Beispiel solche Texte:<\/p>\n\n\n\n
I am a free man.\nI am a number. I am not a free man.\nI am a number. I am a free man.\nI am not a free man.\nI am not a number. I am a number. I am not a number. I am a free man.\nI am not a number. I am not a free man.\nI am not a number. I am a free man.\nI am a number. I am a number. I am a free man.\nI am a number. I am a number. I am not a free man.\nI am not a number. I am not a number. I am not a free man.<\/pre>\n\n\n\n
Nach „man.“ h\u00f6ren 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\u00e4chlich w\u00e4re es vielleicht sauber, jede Instanz eines Folgewort nur einmal in einer Liste zu speichern, zusammen mit der relativen Wahrscheinlichkeit, wobei die Wahrscheinlichkeiten aller W\u00f6rter sich dabei zu 1 summieren m\u00fcssten. Aber bei relativ kleinen Texten ist das so einfacher.)<\/p>\n\n\n\n
F\u00fcr Hemingways „A clean, well-lighted place“ sieht ein Teil des W\u00f6rterbuchs \u00fcbrigens so aus:<\/p>\n\n\n\n
Hail [ nothing ]\nHe [ would disliked smiled was was did can has drinks might sat put should ]\nI [ am am have have.\" am wish have never should know.\" never ]\nI'm [ not ]\nIn [ the ]\nIt [ was was was was was is is was ]\nLook [ at ]\nMany [ must ]\nNor [ can ]\nNow, [ without ]\nOur [ nada ]<\/pre>\n\n\n\n
Weil das so viele W\u00f6rter sind, gehen wir erst einmal zur\u00fcck zu unserem kurzen Ausgangstext. Man kann die Information in dem W\u00f6rterbuch auch als Graph angeben:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Dabei ist jedes Wort, jeder Lexikoneintrag, ein Zustand des Systems, dargestellt als ein Knoten, verbunden mit den m\u00f6glichen Folgew\u00f6rtern durch gerichtete Kanten, die durch eine Gewichtung ausgezeichnet sind, die die Wahrscheinlichkeit des \u00dcbergangs angibt – es muss lediglich gelten, dass die Summe aller Kantengewichte, die von einem Knoten ausgehen, 1 ist. <\/p>\n\n\n\n
Klar, sch\u00f6ner w\u00e4re es, wenn man von „free“ auch noch mit einer gewissen Wahrscheinlichkeit zu „number“ k\u00e4me. Aber das kommt im – zugegeben sehr kurzen – Ausgangstext nun mal nicht vor. Eine Markow-Kette w\u00e4re das dann trotzdem.<\/p>\n\n\n\n
Man kann die \u00dcbergangswahrscheinlichkeiten der Zust\u00e4nde auch als Tabelle angeben:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Was eine Markow-Kette nun genau ist, muss ein Mathematiker erkl\u00e4ren. Hier geht es nur um die einfachen F\u00e4lle, mit endlich vielen Zust\u00e4nden, und \u00dcbergangswahrscheinlichkeiten, die nur vom letzten Zustand abh\u00e4ngen. Man k\u00f6nnte ja auch die zwei<\/em> vorhergehenden W\u00f6rter heranziehen, um das Folgewort zu ermitteln.<\/p>\n\n\n\n
Markow-Ketten eignen sich wohl zur Simulation von Systemen, die sich damit gut simulieren lassen. :-)  Wenn man f\u00fcr ein Computerspiel zum Beispiel zuf\u00e4lliges Wetter braucht, kann man entweder jeden Tag neues Wetter ausw\u00fcrfeln mit 50% Chance f\u00fcr Sonne oder Regen, oder man erstellt eine Markow-Kette, wo man vom Zustand Sonne aus am n\u00e4chsten Tag mit 80% Wahrscheinlichkeit wieder im Sonnenzustand landet, aber mit 20% bei Regen – und der Zustand Regen funktioniert \u00e4hnlich. Dann \u00e4ndert sich das Wetter auch ab und zu, und es gibt eben so viele Sommer- wie Regentage, aber es gibt l\u00e4ngere Folgen und seltenere Wechsel.<\/p>\n\n\n\n
Zum Schluss noch ein Auszug aus der modifizierten Schulordnung f\u00fcr Gymnasien in Bayern:<\/p>\n\n\n\n
zugelassener Hilfsmittel bei ausreichendem Leistungsstand in Latein mindestens zwei Ausbildungsabschnitten 12\/1 ist, abgesehen vom Kurzreferat; 2. Nach Beginn der Gesamtnote \u201eausreichend\u201c oder staatlich genehmigten Ersatzschule abzunehmen, wenn nicht auf dem Abschlusszeugnis die Fortsetzung eines schul\u00e4rztlichen Zeugnisses eine mindestens 1 und Sch\u00fcler, die nach \u00a7 2 Satz 2 Satz 2, der m\u00fcndlichen Pr\u00fcfungen abgelegt und Gesellschaft. (3) F\u00fcr Schulaufgaben in eine \u00c4nderung der Nachpr\u00fcfung erfolgreich unterzogen haben, erhalten sie oder des Ausbildungsabschnitts 12\/1 oder dem doppelt gewichteten Durchschnitt der Schulleiter kann f\u00fcr den F\u00e4chern Deutsch, Mathematik (Abiturpr\u00fcfungsf\u00e4cher 1 und 3. am Kolleg kann bei der Jahrgangsstufe mit der \u00dcbertritt in einem vom Staatsministerium gesondert fest. 2Sch\u00fclerinnen und das Vorr\u00fccken gef\u00e4hrdet, so bem\u00fchen sich auf Ausschluss von Leistungsnachweisen und Recht sowie in der Hauptpr\u00fcfung dauern in Anlage 9 nach dem gew\u00e4hlten Ausbildungsrichtung hat die zweite Fremdsprache 1 Punkt bewertet. 8. \u00fcber das Ziel der Schulleiter festzusetzenden Frist, die sich auf einem Sch\u00fcler w\u00e4hrend der Realschule, die Belegung und Worten) ausgedr\u00fcckt, die Punktzahl der f\u00fcnf Abiturpr\u00fcfungsf\u00e4chern wird ermittelt, indem die ihnen die Schule wird in Satz 1 genannte Zeitpunkt. (4) W\u00e4hrend des Gymnasiums sind ferner am Musischen Gymnasien als Abiturpr\u00fcfungsf\u00e4cher ist und welche beiden F\u00e4cher (Abiturpr\u00fcfungsf\u00e4cher 4 erreicht haben sich die auch darauf<\/p><\/blockquote>\n\n\n\n
Links:<\/p>\n\n\n\n