nips nips2013 nips2013-299 nips2013-299-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tetsuro Morimura, Takayuki Osogami, Tsuyoshi Ide
Abstract: The Markov chain is a convenient tool to represent the dynamics of complex systems such as traffic and social systems, where probabilistic transition takes place between internal states. A Markov chain is characterized by initial-state probabilities and a state-transition probability matrix. In the traditional setting, a major goal is to study properties of a Markov chain when those probabilities are known. This paper tackles an inverse version of the problem: we find those probabilities from partial observations at a limited number of states. The observations include the frequency of visiting a state and the rate of reaching a state from another. Practical examples of this task include traffic monitoring systems in cities, where we need to infer the traffic volume on single link on a road network from a limited number of observation points. We formulate this task as a regularized optimization problem, which is efficiently solved using the notion of natural gradient. Using synthetic and real-world data sets including city traffic monitoring data, we demonstrate the effectiveness of our method.
[1] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proc. of International Conference on Machine learning, 2004.
[2] AccessKenya.com. http://traffic.accesskenya.com/.
[3] S. Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2):251–276, 1998.
[4] S. Amari and H. Nagaoka. Method of Information Geometry. Oxford University Press, 2000.
[5] S. Amari, H. Park, and K. Fukumizu. Adaptive method of realizing natural gradient learning for multilayer perceptrons. Neural Computation, 12(6):1399–1409, 2000.
[6] H. Balzter. Markov chain models for vegetation dynamics. Ecological Modelling, 126(2-3):139–154, 2000.
[7] J. Baxter and P. L. Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319–350, 2001.
[8] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[9] H. H. Bui, S. Venkatesh, and G. West. On the recognition of abstract Markov policies. In Proc. of AAAI Conference on Artificial Intelligence, pages 524–530, 2000.
[10] S. L. Chang, L. S. Chen, Y. C. Chung, and S. W. Chen. Automatic license plate recognition. In Proc. of IEEE Transactions on Intelligent Transportation Systems, pages 42–53, 2004.
[11] E. Crisostomi, S. Kirkland, and R. Shorten. A Google-like model of road network dynamics and its application to regulation and control. International Journal of Control, 84(3):633–651, 1995.
[12] M. Gamon and A. C. K¨ nig. Navigation patterns from and to social media. In Proc. of AAAI Conference o on Weblogs and Social Media, 2009.
[13] J. E. Gonzales, C. C. Chavis, Y. Li, and C. F. Daganzo. Multimodal transport in Nairobi, Kenya: Insights and recommendations with a macroscopic evidence-based model. In Proc. of Transportation Research Board 90th Annual Meeting, 2011.
[14] T. Id´ and M. Sugiyama. Trajectory regression on road networks. In Proc. of AAAI Conference on e Artificial Intelligence, pages 203–208, 2011.
[15] T. Katasuki, T. Morimura, and T. Id´ . Bayesian unsupervised vehicle counting. In Technical Report. IBM e Research, RT0951, 2013.
[16] D. Levin, Y. Peres, and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
[17] D. MacKay. Information theory, inference, and learning algorithms. Cambridge University Press, 2003.
[18] T. Morimura and S. Kato. Statistical origin-destination generation with multiple sources. In Proc. of International Conference on Pattern Recognition, pages 283–290, 2012.
[19] T. Morimura, E. Uchibe, J. Yoshimoto, and K. Doya. A generalized natural actor-critic algorithm. In Proc. of Advances in Neural Information Processing Systems, volume 22, 2009.
[20] A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. In Proc. of International Conference on Machine Learning, 2000.
[21] J. R. Norris. Markov Chains. Cambridge University Press, 1998.
[22] OpenStreetMap. http://wiki.openstreetmap.org/.
[23] C. C. Pegels and A. E. Jelmert. An evaluation of blood-inventory policies: A Markov chain application. Operations Research, 18(6):1087–1098, 1970.
[24] J.A. Quinn and R. Nakibuule. Traffic flow monitoring in crowded cities. In Proc. of AAAI Spring Symposium on Artificial Intelligence for Development, 2010.
[25] C. M. Roberts. Radio frequency identification (RFID). Computers & Security, 25(1):18–26, 2006.
[26] S. M. Ross. Stochastic processes. John Wiley & Sons Inc, 1996.
[27] S. Santini. Analysis of traffic flow in urban areas using web cameras. In Proc. of IEEE Workshop on Applications of Computer Vision, pages 140–145, 2000.
[28] R. R. Sarukkai. Link prediction and path analysis using Markov chains. Computer Networks, 33(16):377–386, 2000.
[29] G. Tauchen. Finite state Markov-chain approximations to univariate and vector autoregressions. Economics Letters, 20(2):177–181, 1986.
[30] Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An information-theoretic approach to traffic matrix estimation. In Proc. of Conference on Applications, technologies, architectures, and protocols for computer communications, pages 301–312. ACM, 2003.
[31] J. Zhu, J. Hong, and J. G. Hughes. Using Markov chains for link prediction in adaptive Web sites. In Proc. of Soft-Ware 2002: Computing in an Imperfect World, volume 2311, pages 60–73. Springer, 2002.
[32] B. D. Ziebart, A. L. Maas, and A. K. Dey J. A. Bagnell. Maximum entropy inverse reinforcement learning. In Proc. of AAAI Conference on Artificial Intelligence, pages 1433–1438, 2008. 9