Ene Mene Muh (Linux-Magazin, September 2017)

Nachdem diese Kolumne einerseits mit dieser Ausgabe sage und schreibe zwanzig Jahre voll hat (die erste Folge erschien im September 1997), und andererseits künstliche Intelligenz immer mehr Arbeitsplätze verdrängt, stellt sich die Frage, ob es irgendwann einmal ein KI-System schaffen könnte, das Manuskript zum bassen Staunen der sonst zum Unzeitpunkt Redaktionsschluss! rufenden Redakteure fürderhin pünktlich abzuliefern, und es dem Autor statt dessen erlaubte, dauerhaft seinem Surfhobby an diversen Pazifikstränden nachzugehen (Abbildung 1).

Abbildung 1: Der urlaubshungrige Autor auf Hawaii, während ein KI-System seine Kolumne schreibt.

Launisch wie das Wetter

Als Algorithmus böte sich eine sogenannte Markow-Kette an, benannt nach dem russischen Mathematiker Andrei Markow (englisch übrigens: Markov). Hierbei handelt es sich um stochastische Prozesse mit verschiedenen Zuständen, die entsprechend vorgegebener Wahrscheinlichkeiten wechseln. Das in Abbildung 2 dargestellte Modell zur Wettervorhersage besagt zum Beispiel, dass auf den Zustand "Sonne" mit 65-prozentiger Wahrscheinlichkeit wieder ein Sonnentag folgt. Zu 30% wechselt das Wetter hingegen zu "Bewölkt", und zu 5% sogar direkt zu "Regen". Die angegebenen Wahrscheinlichkeiten beziehen sich also nur auf den aktuellen Zustand, ein Wechsel in den nächsten Zustand erfordert keinerlei Kenntnis der vorherigen Zustände, ist also höchst einfach und blitzschnell auszurechnen.

Abbildung 2: Markow-Diagramm zur Wettervorhersage

In einer Übergangsmatrix wie in Abbildung X muss der Rechner nur die Reihe mit dem aktuellen Zustand heraussuchen, zum Beispiel Reihe 3 für den Zustand bewölkt (B), um dann herauszufinden, dass das Wetter zu 25% sonnig bleibt, zu weiteren 25% in Regen und zu 50% in Regen umschlägt. Mit ensprechenden Zufallsgeneratoren ausgestattet springt das Modell dann zwischen den Zuständen hin und her, und die spätere Auswertung des Monte-Carlo-Verfahrens erlaubt dann Rückschlüsse auf das wahrscheinlichste zukünftige Wetter.

Abbildung 3: Übergangsmatrix des Wettermodells

Sätze vom Automaten

Mittels solcher "Random Walks" lassen sich auch Sätze mit einer fein dosierten Portion Zufall generieren. Hierzu analysiert ein Programm zunächst die Wortfolgen in einem umfangreichen Korpustext. Es merkt sich, welche Worte in einem Satz aufeinander folgen, und stückelt aus gelernten Satzteilen einen neuen Text zusammen. Merkt es zum Beispiel, dass nach drei bestimmten Worten als viertes irgendwo im Korpus WortA und einmal WortB steht, wird es im generierten Text jedes Mal einen imaginären Würfel entscheiden lassen, welches zum jeweiligen Zeitpunkt zum Einsatz kommt.

Es zerlegt den Korpustext in Wörter (Tokens) und analysiert ihn schrittweise mit einem rollenden Fenster von N Wörtern. Die ersten N-1 Wörter des Fensters bestimmen den Zustand des Automaten an diesem Zeitpunkt und das letzte Wort ist der Wert, den der Automat beim Übergang in den nächsten Zustand annimmt.

Rollendes Fenster

Bei einer Fenstergröße von N=3 extrahiert der Algorithmus aus "Ene mene muh und raus bist du." zum Beispiel die Fenster "Ene mene muh", "mene muh und", "muh und raus", und so weiter. Die ersten zwei Worte bestimmen jeweils den Zustand des Automaten ("bist du"), und das folgende Wort (oder im vorliegenden Fall das Sonderzeichen ".") ist der Folgezustand. Stolpert der Algorithmus im zweiten Teil des Abzählreims ("raus bist du noch lange nicht") ebenfalls wieder auf den Zustand "bist du", dann folgt auf diesen aber kein Punkt, sondern das Wort "noch". Jetzt hat der Algorithmus beim späteren Erstellen des Zufallstexts zwei Möglichkeiten: Er kann auf "bist du" entweder einen Punkt folgen lassen oder das Wort "noch", und wird dies auch entsprechend kalkulierter Zufallswerte tun. Das Ergebnis ist ein Text, der leicht menschliche Qualitäten aufweist, weil er Wortfolgen kopiert, aber doch hin und wieder in völlig andere Zusammenhänge springt, was entweder konfus oder lustig klingt.

Listing 1: randomtext.py

    01 #!/usr/bin/python3
    02 from nltk.tokenize import word_tokenize
    03 from collections import deque
    04 import re
    05 import random
    06 
    07 re_special=re.compile("^[,.:]$")
    08 re_word=re.compile("^\w+$")
    09 
    10 def token_feed(file):
    11     string  = open(file, 'r').read()
    12 
    13     for i in word_tokenize(string):
    14         if re_special.match(i) or \
    15            re_word.match(i):
    16             yield(i)
    17 
    18 def tokens_to_text(tokens):
    19     out=""
    20     for word in tokens:
    21         if(not re_special.match(word)):
    22             out += " "
    23         out += word
    24     return out
    25 
    26 def window(seq, n):
    27     it = iter(seq)
    28     win = deque(
    29       (next(it, None) for _ in range(n)),
    30       maxlen=n)
    31     yield win
    32     append = win.append
    33     for e in it:
    34         append(e)
    35         yield win
    36 
    37 def statemap_gen(file):
    38     statemap={}
    39     tokens=token_feed(file)
    40     for state in window(tokens,4):
    41         key   = list(state)
    42         value = key.pop()
    43         key   = tuple(key)
    44     
    45         if key in statemap:
    46             statemap[key].append(value)
    47         else:
    48             statemap[key] = [value]
    49     return statemap
    50 
    51 def generate_from(file):
    52     statemap=statemap_gen(file)
    53     key=list(
    54       random.choice(list(statemap.keys())))
    55     words_new=list(key)
    56 
    57     for i in range(200):
    58         if not tuple(key) in statemap:
    59             continue
    60         next_token = random.choice(
    61           statemap[tuple(key)])
    62         words_new.append(next_token)
    63         key.append(next_token)
    64         key.pop(0)
    65     
    66     return tokens_to_text(words_new)
    67 
    68 print(generate_from('test.txt'))

Listing 1 schnappt sich den Source-Code aller bisher erschienenen Programmiersnapshots seit 1997 und übergibt den Namen der sie enthaltenden Datei an die Funktion generate_from() in Zeile 68. Die Funktion statemap_gen ab Zeiel 37 unterteilt die Datei mit token_feed() in Tokens und übergibt die daraus resultierende Liste der Funktion window() ab Zeile 26, die als Fensterbreite n=4 entgegen nimmt. Der Status der Markow-Kette besteht also den drei zuletzt letzten Worten, das vierte ist Teil des Folgezustands.

Abbildung 4: Herunterladen der Daten für den nltk-Tokenizer

Damit der Tokenizer aus dem Paket nltk auch funktioniert, muss der Admin letzteres mittels pip3 install nltk installieren und auch nach Abbildung 4 noch den Tokenizer-Datensatz "punkt" herunterladen. Satzzeichen wie Kommas oder Doppelpunkte (der reguläre Ausdruck in Zeile 7 definiert sie alle) interpretiert der Tokenizer als eigene Tokens, das erhöht später erfahrungsgemäß die Lesbarkeit und den fast menschlichen Klang des generierten Zufallstextes.

Abbildung 5 zeigt im Detail, wie der Algorithmus aus einer Testdatei mit dem bekannten Abzählreim und der Fensterlänge N=3 eine Zustandsdatei der Markow-Kette erzeugt. Der Eintrag

    ('bist', 'du'): ['.', 'noch']

gibt als mögliche Folge der Wortkette "best du" die Alternativen "." und "noch" vor.

Abbildung 5: Zerteilen eines Textes in Tokens und Erstellen des Markow-Modells.

Der Python-Code zeigt einige Schmankerln der Sprache, wie zum Beispiel den yield()-Operator in der Funktion token_feed() in Zeile 16: Damit Python mittels einer For-Schleife über die Komponenten eines Objekts iterieren kann, muss selbiges vom Typ "Iterable" sein. Letztere spucken ihre Komponenten nicht in einem Rutsch aus sondern reichen sie scheibchenweise bei jedem Aufruf durch. Das hat den Vorteil, dass das Skript nicht die Gesamtheit der in einem Konstrukt enthaltenen Daten im Arbeitsspeicher vorhalten muss, sondern sie erst "lazy" bei Bedarf ausrechnen darf. So kann ein Objekt durchaus unendlich viele Komponenten enthalten, wenn sie niemals alle gebraucht werden, bleibt die Illusion trotz natürlich begrenztem Arbeitsspeicher erhalten.

Abbildung 6: Das KI-System schreibt den Snapshot aller Snapshots.

Python bietet auch eine Vielzahl von Datenstrukturen, die sogenannten "Double Ended Queues", genannt deque in der Funktion window() ab Zeile 26 lassen sich besonders performant umwandeln, in dem Elemente zum Kopf oder Schwanz der Schlange hinzugefügt oder entfernt werden. Der einzige Schönheitsfehler ist, dass der Aufrufer der Funktion window() die von ihr zurückgegebene Deque nicht manipulieren darf, sonst gerät der Algorithmus durcheinander. Aus diesem Grund kopiert Zeile 41 mit key=list(state) die Elemente des Deque-Objekts in eine Python-Liste, auf der die Funktion statemap_gen() nach nach Herzenslust herumorgeln darf. Sie interpretiert die ersten N-1 Elemente als Markow-Status, und das letzte Element als möglichen Folgewert. In key liegt nach Zeile 43 ein nicht mehr modifizierbarer Python-Tupel, der dem Eintrag unter dem Schlüssel in einem mehrdimensionalen Dictionary statemap den Folgewert zuweist. Später kann der Algorithmus also blitzschnell nachsehen, ob zu einer Folge von N-1 Worten schon ein oder mehrere Folgewerte existieren und davon mittels random.choice() in Zeile 60 einen zufälligen auswählen. Das lenkt den Text in unberechenbare Bahnen und macht den Reiz des Verfahrens aus.

Das Ergebnis in Abbildung 6 zeigt, dass das Markow-Ketten-Verfahren nicht automatisch spannende neue Artikel liefert. Auch bei der Grammatik des erzeugten Zufallstext hapert es noch gewaltig, die Redakteure würden sich vermutlich am Abgabetermin ihre restlichen verbliebenen Haare raufen. Der Programmier-Snapshot wird also wohl auf absehbare Zeit noch von Hand erstellt und von der Redaktion auf Hochglanz getrimmt werden. Ganz altmodisch, aber die Leserschaft ist auch verdammt anspruchsvoll.

Infos

[1]

Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2017/09/snapshot/

[2]

Thoughtful Machine Learning with Python: A Test-Driven Approach", Matthew Kirk, O'Reilly 2017

[3]

"Generating pseudo random text with Markov chains using Python", Shabda Raaj, 2009, http://agiliq.com/blog/2009/06/generating-pseudo-random-text-with-markov-chains-u

Michael Schilli

arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen.