Higher-Order Kullback-Leibler Aggregation of Markov Chains
Conference: SCC 2017 - 11th International ITG Conference on Systems, Communications and Coding
02/06/2017 - 02/09/2017 at Hamburg, Germany
Proceedings: ITG-Fb. 268: SCC 2017
Pages: 6Language: englishTyp: PDFPersonal VDE Members are entitled to a 10% discount on this title
Geiger, Bernhard C.; Wu, Yuchen (Institute for Communications Engineering, Technical University of Munich, Germany)
We consider the problem of reducing a first-order Markov chain on a large alphabet to a higher-order Markov chain on a small alphabet. We present information-theoretic cost functions that are related to predictability and lumpability, show relations between these cost functions, and discuss heuristics to minimize them. Our experiments suggest that the generalization to higher orders is useful for model reduction in reliability analysis and natural language processing.