Timezone: »
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 initialstate probabilities and a statetransition probability matrix. In the traditional setting, a major goal is to figure out 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 every single link on a road network from a very limited number of observation points. We formulate this task as a regularized optimization problem for probability functions, which is efficiently solved using the notion of natural gradient. Using synthetic and realworld data sets including city traffic monitoring data, we demonstrate the effectiveness of our method.
Author Information
Tetsuro Morimura (IBM)
Takayuki Osogami (IBM Research  Tokyo)
Tsuyoshi Ide (IBM Research)
More from the Same Authors

2021 : MeanVariance Efficient Reinforcement Learning by Expected Quadratic Utility Maximization »
Masahiro Kato · Kei Nakagawa · Kenshi Abe · Tetsuro Morimura 
2021 Poster: CardinalityRegularized HawkesGranger Model »
Tsuyoshi Ide · Georgios Kollias · Dzung Phan · Naoki Abe 
2018 : Live competition Pommerman: Competition battles projected in the room »
Robin Chauhan twitter.com/TalkRLPodcast · Takayuki Osogami 
2014 Poster: Restricted Boltzmann machines modeling human choice »
Takayuki Osogami · Makoto Otsuka 
2012 Poster: Robustness and risksensitivity in Markov decision processes »
Takayuki Osogami 
2009 Poster: A Generalized Natural ActorCritic Algorithm »
Tetsuro Morimura · Eiji Uchibe · Junichiro Yoshimoto · Kenji Doya