Solving inverse problem of Markov chain with partial observations
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.
The paper proposes an estimation strategy for 
      recovering the parameters of a finite state Markov chain given observed 
      stationary frequencies of some states. (The paper also considers using 
      additional hitting frequencies for a few state pairs, but this is not used 
      in the final evaluation.) Although the problem proposed is 
      potentially very interesting, the paper does not appear to be in a mature 
      state. Some fundamental issues are not adequately addressed, while the 
      evaluation is limited, and the writing quality is not strong. Note 
      that there is an uncountable set of ergodic transition models that can 
      exactly match a given subset of stationary frequencies when the number of 
      observed stationary state frequencies is small relative to the total 
      number of states. In short, the problem is ill posed. This means that 
      additional prior knowledge is required to recover a unique transition 
      model, whether via regularization or imposing a compact parametric form. 
      Unfortunately, the paper does not even discuss the necessity of 
      imposing prior knowledge to achieve non-vacuous results in this setting. 
      That is, even though the paper proposes a parametric representation and 
      considers regularization, it does not observe that the problem is ill 
      posed, hence that *zero* loss is obtainable for an uncountable set of 
      transition models. Instead, the paper merely proposes a few heuristic loss 
      functions and an arbitrary regularizer. This seems to be a somewhat 
      superficial approach to the issue. Even the paper's main motivating 
      example of a traffic network possesses clear prior structure: the 
      transition probability must be zero between unconnected links. There will 
      be some subsets of stationary state probabilities that can identify the 
      transition model in such a structured setting, but this possibility is not 
      even discussed. The proposed loss functions (8) and (9) are 
      clearly heuristic, and I found the attempted justification below (8) to be 
      unconvincing. A distributional assumption can always be reverse engineered 
      from a loss formulation like (8), but that does not mean the 
      log-frequencies will have this distributional form. The discussion 
      of "bias" in Section 3.2 appears to be too informal: on the context of 
      estimation, unbiasedness normally refers to a property that the expected 
      value of an estimator is the true value of the underlying parameter. 
      Although the loss formulation (8) is claimed to be "unbiased", no argument 
      is given that the expected value of the minimizer of (8) has the correct 
      value. If one accepts the regularized loss formulation, the 
      natural gradient approach developed in Section 4 appears to be reasonable. 
      The technical development in this section is sound. The 
      experimental evaluation appears to be limited. One synthetic and one 
      "real" experiment are conducted. In the synthetic experiment, the 
      model exactly matches that used by the paper's proposed estimator, which 
      is an ideal scenario that cannot be guaranteed in practice. Here the 
      proposed method's results are compared to a baseline estimator (NWKR) that 
      does not exploit the fact that the target stationary frequencies are 
      associated with a Markov chain. This seems to be a weak straw-man 
      competitor, and it is not too surprising that it performs poorly by 
      comparison. In the real experiment, it is somewhat disappointing 
      that hitting rate observations are not included in the observations, which 
      means that the initial distribution is irrelevant to the estimation 
      problem (since only stationary frequencies are being used). Nevertheless, 
      this is an interesting experimental domain. The results look reasonable, 
      although again, the baseline competitor is too weak to take very 
      seriously. A more credible competitor would identify a transition model 
      that exactly matches the observed stationary frequencies (and the sparsity 
      pattern implied by the road network) while maximizing entropy. The 
      experimental evaluation would also be more convincing if results could be 
      obtained for a larger number of synthetic and real 
      domains.