  This paper proposes an information-theoretic cost function for aggregating a
Markov chain via a (possibly stochastic) mapping. The cost function is
motivated by two objectives: 1) The process obtained by observing the Markov
chain through the mapping should be close to a Markov chain, and 2) the
aggregated Markov chain should retain as much of the temporal dependence
structure of the original Markov chain as possible. We discuss properties of
this parameterized cost function and show that it contains the cost functions
previously proposed by Deng et al., Xu et al., and Geiger et al. as special
cases. We moreover discuss these special cases providing a better understanding
and highlighting potential shortcomings: For example, the cost function
proposed by Geiger et al. is tightly connected to approximate probabilistic
bisimulation, but leads to trivial solutions if optimized without
regularization. We furthermore propose a simple heuristic to optimize our cost
function for deterministic aggregations and illustrate its performance on a set
of synthetic examples.
