3. Die Anwendungsbeispiele
Durch ihre sehr einfache Definition ist das Anwendungsfeld der Markov-Ketten sehr breit gefächert. Gerade im Bereich Informatik stößt man sehr häufig auf Markov-Ketten, selbst beim einfachen Surfen im Internet ist man in ständiger Begleitung dieser Systeme.
In diesem Kapitel werden zwei Einsatzgebiete für Markov-Ketten näher behandelt.
3.1 Textgenerierung mit Makov
3.1.1 Einführung Textgenerierung
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).
(1)
Dieser, bereits aus der Einleitung bekannte Text, sieht optisch gut aus, nicht wahr? Sicherlich aus einem Referat oder einem Vortrag! Unglaublich viel Information auf sehr engen Raum komprimiert. Wenn das kein Trugschluss ist! Dieser Text wurde mithilfe eines simplen Algorithmus auf der Basis von Markov-Ketten erstellt!
3.1.2 Der Algorithmus
Die Funktionsweise dieser Technik ist sehr simpel: Zunächst nimmt man einen Text, der möglichst lang sein sollte. Jetzt merkt man sich alle Wörter dieses Textes und berechnet, welche Worte wie oft aufeinander folgen. Anhand dieser Daten wird nun errechnet, mit welcher Wahrscheinlichkeit jedes Wort auf ein anderes Wort folgt.
Nun wird anhand dieser Markov-Kette ein neuer Text erstellt, indem für jedes Wort zufällig ein Nachfolgewort ausgewählt wird.
Je länger der Text ist, den der Algorithmus zur Berechnung erhält, desto genauer werden die Wahrscheinlichkeiten und desto besser werden die Ergebnisse. Schon bei geringer Länge des Eingabetextes erhält man ein Ergebnis, das zumindest optisch nach einem korrekten Satz aussieht und einen nicht künstlichen Eindruck macht, da es dem eingegebenen Text noch sehr ähnlich ist.
3.1.3 Anwendungsbereiche
Diese Technik wird häufig von Leuten genutzt, die Platzhalter- oder Spamwebseiten betreiben. Die mit solchen Texten gefüllten Webseiten werden von Algorithmen, die diese aufspüren sollen, nicht erkannt und selbst wenn ein menschlicher Benutzer einen flüchtigen Blick darüber wirft, ohne sich mit dem Inhalt zu beschäftigen, fällt der Betrug nicht auf.
Ansatzweise findet man diese Vorgehensweise bei Chat-Programmen, die menschliche Sprache und Spontanität simulieren sollen.
Dieses Vorgehen ist ebenfalls in der algorithmischen Musik zu finden, bei dem im ähnlichen Verfahren mit Noten vorgegangen wird.
Markov-Ketten können jedoch auch bei ganz anders gelagerten Problemen hilfreich sein. So werden sie erfolgreich im Google PageRank System (2)verwendet. Mehr dazu gibt es im folgenden Abschnitt.
[Die Grundlagen 3/3] | [PageRank]