Informationstheoretische Aggregation von Markov-Ketten

Markov-Modelle sind wichtige mathematische Modelle für Zufallsprozesse und werden in vielen Wissenschaftsdisziplinen eingesetzt. Sie dienen als Werkzeuge in der Nachrichtentechnik, der Genetik und der Systembiologie, in der Sprachverarbeitung und im maschinellen Lernen. In einigen dieser Anwendungsgebiete sind die Modelle allerdings zu groß, um sinnvoll eingesetzt werden zu können. Einerseits kann es unmöglich werden, ein gegebenes Markov-Modell zu simulieren, andererseits reichen oft die vorhandenen Daten nicht aus um die Parameter des Modells zu bestimmen. Es ist daher in diesen Wissenschaftsdisziplinen erforderlich, die vorhandenen Modelle zu vereinfachen. Das Ziel des Forschungsaufenthalts ist, Markov-Modelle mithilfe informationstheoretischer Methoden zu aggregieren. Aggregation bedeutet in diesem Zusammenhang dass einzelne Zustände des ursprünglichen Modells zu einem einzigen Zustand zusammengefasst werden in der Sprachverarbeitung würde man z.B. die Wörter forschen, beantragen und hoffen zu Verben zusammenfassen. Die Vereinfachung von Markov- Modellen wurde in den letzten Jahren zwar immer populärer, doch werden informationstheoretische Methoden immer noch zögerlich eingesetzt. Aber was sind informationstheoretische Methoden? Die Informationstheorie beschäftigt sich mit der Übertragung von Information und deren mathematischer Grundlage. Markov-Modelle mithilfe informationstheoretischer Methoden zu aggregieren bedeutet also, salopp ausgedrückt, das Modell zu vereinfachen und dabei so wenig Information wie möglich zu zerstören. Während des Forschungsaufenthalts werden wir nicht nur theoretische Resultate erarbeiten, sondern auch Algorithmen entwerfen, die ein gegebenes Markov-Modell vereinfachen. Die Anwendungsmöglichkeiten solcher Algorithmen sind enorm: Konkret hoffen wir, den Viterbi-Algorithmus, einen wichtigen Algorithmus in der Nachrichtentechnik, zu vereinfachen. Außerdem wollen wir, vor allem während der Rückkehrphase in Österreich, unsere Ergebnisse und Methoden in der Sprachverarbeitung einsetzen. Wer weiß, vielleicht finden einige der Resultate sogar ihren Weg in den Programmcode von Siri, Google Now oder Microsoft Cortana!

Wie lässt sich ein komplexes mathematisches Modell vereinfachen ohne dabei viel Information zu verlieren? Genau mit dieser Frage beschäftigte sich dieses Erwin-Schrödinger-Auslandsstipendium. Der Fokus lag dabei auf Markov-Modellen. Diese populären Modelle für Zufallsfolgen finden Anwendung in der automatisierten Textverarbeitung, der Biologie und im maschinellen Lernen. Konkretes Ziel des Projekts war die Entwicklung von informationstheoretischen Methoden zur Aggregation solcher Markov-Modelle. Aggregation bedeutet in diesem Zusammenhang die Gruppierung von Objekten zu Clustern - in der Textverarbeitung würden zum Beispiel die Objekte forschen, anwenden und hoffen zum Cluster Verben zusammengefasst werden. Während Aggregation ein bekanntes Verfahren ist, wurde ihre Kombination mit informationstheoretischen Methoden erst in den letzten Jahren populär. Doch was sind informationstheoretischen Methoden? Die Informationstheorie beschäftigt sich mit den Grenzen der Übertragung von Information. Ein Markov-Modell mit informationstheoretischen Methoden zu aggregieren bedeutet - grob gesagt - das mathematische Modell zu vereinfachen und dabei soviel Information wie möglich zu bewahren. Der Name ist Programm: Der Großteil der Projektarbeit war theoretischer Natur. Dennoch fanden wir viele interessante praktische Anwendungen der entwickelten Theorie und der implementierten Algorithmen. Zum Beispiel lassen sich die Methoden zur Markov-Aggregation einsetzen, um Textdokumente zu gruppieren. Diese Gruppierungen geben nicht nur Auskunft über die in den Dokumenten behandelten Themen, sondern auch über Wortgruppen welche diese Themen definieren. Ein weiteres Anwendungsbeispiel ist das Gruppieren von Kinofilmen basierend auf Bewertungen. Außerdem kann man mittels Markov-Aggregation eng zusammengehörende Personengruppen in Theaterstücken entdecken - die Brücke zu den digitalen Geisteswissenschaften ist geschlagen. Und wer weiß, vielleicht sind es gerade diese Methoden die Auskunft geben ob Romeo und Julias Ehe bestand gehabt hätte, wäre ihre Geschichte ein wenig anders ausgegangen.