Algorithmen
20.02.2019, 10:52 Uhr
Mit Schach zum besseren Autocomplete
Wie wahrscheinlich folgt bei einem Schachspiel ein bestimmter Zug auf eine Konstellation? Markov-Ketten können darüber Auskunft geben. Analog lässt sich mit Markov-Ketten auch das Autocomplete verbessern.
(Quelle: https://chess-db.com/)
Kleine Tastaturen wie auf Smartphones unterstützen nicht gerade das schnelle Schreiben von Mengentext. Hier kann eine Funktion helfen, die versucht, das nächste Wort zu erraten und anzuzeigen. Passt es, muss der Anwender anstelle vieler Buchstaben nur auf das Wort tippen.
Mit Markov-Ketten lässt sich so eine Funktion implementieren. Dazu wird die Funktion zuerst mit passenden Texten trainiert. Anschließend weiß sie um die Wahrscheinlichkeit, nach einem Wort ein bestimmtes nächstes zu finden. Die Wörter mit der höchsten Wahrscheinlichkeit schlägt sie dann vor.
Dieses einfach Vorgehen ist eine Markov-Kette erster Ordnung: Es wird nur die Wahrscheinlichkeit des Übergangs von einem Wort auf das nächste berücksichtigt. Ketten zweiter Ordnung berücksichtigen dementsprechend zwei Wörter als Vorgänger und informieren dann über die Wahrscheinlichkeit des Übergangs auf das dritte Wort.
Anschaulich erklärt wird die Verwendung im Blogpost https://yurichev.com/blog/markov/. Der Autor zeigt das ganze anhand von Python-Code. Als Trainingslektüre verwendete er Sherlock-Holmes-Geschichten von der Gutenberg-Bibliothek.
Als Ergebnis kommt dann beispielsweise heraus, dass nach dem Wort "return" 28 mal das Wort "to" folgt. Oder bei Markov-Ketten dritter Ordnung: nach "the return of" folgt sechsmal das Wort "sherlock".
Abschließend erklärt der Autor noch den Einsatz für die Autocomplete-Funktion und welche der Markov-Ketten sich wohl eher dafür eignet.
