Information-Theoretic Markov Aggregation

Markov models are important mathematical models for random processes and are used in many scientific disciplines. They act as tools in communications, genetics, systems biology, speech communication, and machine learning. In some of these application areas, however, the resulting models are too large to be useful. On the one hand it might become impossible to simulate a given model efficiently, on the other hand the available data might not suffice to determine the model parameters. Hence, in these scientific disciplines it is necessary to simplify the mathematical models. The goal of this research stay is to aggregate Markov models with information-theoretic methods. Aggregation means that states of the original model are grouped together to a single state in speech communication, for example, the words research, apply, and hope could be grouped together to verbs. While the simplification of Markov models became increasingly popular in the last few years, information-theoretic methods are still used sparingly. But what are information-theoretic methods? Information theory deals with the transmission of information and its mathematical fundamentals. To aggregate Markov models with information-theoretic methods means, loosely speaking, to simplify the model while preserving as much information as possible. We will not only develop theoretical results during the research stay, but we will also design algorithms which simplify a given Markov model. The application areas of such algorithms are manifold: In concrete terms, we hope to find a way to simplify the Viterbi algorithm, an important algorithm in communications. Aside from that we will apply our methods in speech communication (especially during the return phase in Austria). Who knows, maybe some of our results will even find their way into the source code of Siri, Google Now, or Microsoft Cortana!

How can you simplify a complex mathematical model without losing too much information? This is precisely the question that was addressed during this Schroedinger Fellowship. We placed our focus on Markov models, which are popular models for sequences of random objects in fields as diverse as language, biology, speech communication, and machine learning. Specifically, the goal of this Schroedinger Fellowship was to aggregate Markov models with information- theoretic methods. Aggregation in this context means that objects are grouped together to clusters - in natural language processing, for example, the objects ro research, to apply, and to hope would be grouped together to the cluster verbs. While aggregation is an old idea, combining it with information- theoretic methods has become popular only recently. But what are information-theoretic methods? Information theory deals with the transmission of information and its fundamental limits. To aggregate a Markov model with information-theoretic methods means, loosely speaking, to simplify the mathematical model while preserving as much information as possible. Although the project - the name says it all - was of a mainly theoretical nature, we have found several interesting practical applications of the developed theory and algorithms. For example, Markov aggregation techniques can be used to cluster documents, thus revealing topics and groups of words that indicate them. Another application is the grouping of movies based on user ratings. The results of this grouping can subsequently be used to recommend movies to users based on the ratings of other users with similar interests. Finally, Markov aggregation can be used to detect communities in dramatic plays, connecting this Schroedinger Fellowship to literary network analysis, an exciting field of research in the digital humanities. Who knows? Perhaps it is such methods that will tell whether Romeo and Juliet`s marriage would have lasted, had their story ended differently.