FAQ
T_LOGIN Log in

Don't have an account on our website?

T_REGISTER Register
logo of Jagiellonian University in Krakow

Markov State Space Aggregation via the Information Bottleneck Method

Publication date: 14.04.2015

Schedae Informaticae, 2014, Volume 23, pp. 45-56

https://doi.org/10.4467/20838476SI.14.004.3021

Authors

Bernhard C. Geiger
Institute for Communications Engineering TU Munich, Arcisstraße 21, D-80333 Munich
Contact with author
All publications →

Titles

Markov State Space Aggregation via the Information Bottleneck Method

Abstract

Consider the problem of approximating a Markov chain by another Markov chain with a smaller state space that is obtained by partitioning the original state space. An information-theoretic cost function is proposed that is based on the relative entropy rate between the original Markov chain and a Markov chain defined by the partition. The state space aggregation problem can be sub-optimally solved by using the information bottleneck method.

References

Download references

Cover T.M., Thomas J.A., Elements of Information Theory, Wiley Interscience, Hoboken, NJ, 2nd edition, 2006.

Deng K., Mehta P.G., Meyn S.P., Optimal Kullback-Leibler aggregation via spectral theory of Markov chains, IEEE Trans. Autom. Control 56 (12), Dec. 2011, pp. 2793–2808.

Dhillon I., Mallela S., Modha D., Information-theoretic co-clusterings, Proc. ACM Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD), Washington, D.C., Aug. 2003, pp. 89–98.

Friedman A., Goldberger J., Information theoretic pairwise clustering, E. Hancock and M. Pelillo (Eds.), Proc. Similarity-Based Pattern Recognition, Springer Berlin LNCS 7953, 2013, pp. 106–119.

Geiger B.C., Petrov T., Kubin G., Koeppl H., Optimal Kullback-Leibler aggregation via information bottleneck, Apr. 2013, Accepted for publication in IEEE Trans. Autom. Control; preprint available: arXiv:1304.6603 [cs.SY].

Geiger B.C., Temmel C., Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability, Dec. 2012. Accepted for publication in J. Appl. Prob., preprint available: arXiv:1212.4375 [cs.IT].

Goldberger J., Erez K., Abeles M., A Markov clustering method for analyzing movement trajectories, Proc. IEEE Int. Workshop on Machine Learning for Signal Processing (MLSP), Thessaloniki, Aug. 2007, pp. 211–216.

Gray R.M., Entropy and Information Theory, Springer, New York, NY, 1990.

Gurvits L., Ledoux J., Markov property for a function of a Markov chain: A linear algebra approach, Linear Algebra Appl. 404, 2005, pp. 85–117.

Hayes B., First links in the Markov chain, American Scientist 101, 2013,

Katsoulakis M.A., Trashorras J., Information loss in coarse-graining of stochastic particle dynamics, J. Stat. Phys., 122 (1), 2006, pp. 115–135.

Kemeny J.G., Snell J.L., Finite Markov Chains, Springer, 2nd edition, 1976.

Manning C.D., Sch¨utze H., Foundations of Statistical Natural Language Processing, MIT Press, Cambridge, MA, 2nd edition, 2000.

Petrov T., Formal reductions of stochastic rule-based models of biochemical systems, PhD thesis, ETH Z¨urich, 2013.

Rached Z., Alajaji F., Campbell L.L., The Kullback-Leibler divergence rate between Markov sources, IEEE Trans. Inf. Theory 50 (5), May 2004, pp. 917–921.

Raj A., Wiggins C.H., An information-theoretic derivation of min-cut-based clustering, IEEE Trans. Pattern Anal. Mach. Intell. 32 (6), June 2010, pp. 988–995.

Shannon C.E., A mathematical theory of communication, Bell Systems Technical Journal 27, Oct. 1948, pp. 379–423, 623–656.

Slonim N., Tishby N., Agglomerative information bottleneck, Advances in Neural Information Processing Systems (NIPS), Denver, CO, Nov. 1999, pp. 617–623.

Tishby N., Pereira F.C., Bialek W., The information bottleneck method, Proc. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Sept. 1999, pp. 368–377.

Tishby N., Slonim N., Data clustering by Markovian relaxation and the information bottleneck method, Advances in Neural Information Processing Systems (NIPS), Denver, CO, Nov. 2000.

Tzortzis I., Charalambous C.D., Charalambous T., Hadjicostis C.N., Johansson M., Approximation of Markov processes by lower dimensional processes via total variation metrics, Oct. 2014, arXiv:1410.3976 [math.OC].

Vedaldi A., Fulkerson B. VLFeat: An open and portable library of computer vision algorithms, 2008, http://www.vlfeat.org/

Vidyasagar M., Reduced-order modeling of Markov and hidden Markov processes via aggregation, Proc. IEEE Conf. on Decision and Control (CDC), Atlanta, GA, Dec. 2010, pp. 1810–1815.

White L.B., Mahony R., Brushe G.D., Lumpable hidden Markov models–model reduction and reduced complexity filtering, IEEE Trans. Autom. Control 45 (12), Dec. 2000, pp. 2297–2306.

Information

Information: Schedae Informaticae, 2014, Volume 23, pp. 45-56

Article type: Original scientific article

Authors

Institute for Communications Engineering TU Munich, Arcisstraße 21, D-80333 Munich

Published at: 14.04.2015

Article status: Open

Licence: None

Percentage share of authors:

Bernhard C. Geiger (Author) - 100%

Article corrections:

-

Publication languages:

English

4. Markov State Space Aggregation via the Information Bottleneck Method

quote

download files

RIS BIB ENDNOTE