Markov Aggregation & Information Bottlenecks

Dipl.-Ing. Bernhard C. Geiger
Signal Processing and Speech Communication Laboratory of Graz University of Technology

Abstract:

We present a method for aggregating the state space of a regular, discrete-time Markov chain (DTMC). As a cost function we choose the Kullback-Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Since the Kullback-Leibler divergence rate between a stationary process and a Markov chain is difficult to compute, we relax the problem and propose an upper bound via the divergence rate between two Markov chains. This upper bound is easy to compute and it is tight in the case when the original chain is lumpable with respect to the partition. By further relaxing the problem, we show that it can be expressed in the formalism of the information bottleneck method, a standard method in machine learning. We discuss the properties of our aggregation method in the light of the related literature.

Biography:

Bernhard C. Geiger was born in Graz, Austria, in 1984. He attended the Higher Technical College (BULME) in Graz-Goesting and graduated in 2003. From 2004 to 2009 he studied Electrical Engineering with focus on Telecommunications at Graz University of Technology, where he received his Dipl.-Ing. (MSc degree) in November 2009. Between September 2009 and March 2010 he was a Research Assistant at the Signal Processing and Speech Communication Lab, where he analyzed acquisition probabilities for GNSS systems. He joined the lab in March 2010 as a Research and Teaching Associate (Universitaetsassistent). He is currently pursuing his PhD thesis in the intersection of information theory, system theory, and signal processing.