Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition
Learning dynamic models from observed data has been a central issue in many scientific studies or engineering tasks. The usual setting is that data are collected sequentially from trajectories of some dynamical system operation. In quite a few modern scientific modeling tasks, however, it turns out that reliable sequential data are rather difficult to gather, whereas out-of-order snapshots are much easier to obtain. Examples include the modeling of galaxies, chronic diseases such Alzheimer's, or certain biological processes. Existing methods for learning dynamic model from non-sequence data are mostly based on Expectation-Maximization, which involves non-convex optimization and is thus hard to analyze. Inspired by recent advances in spectral learning methods, we propose to study this problem from a different perspective: moment matching and spectral decomposition. Under that framework, we identify reasonable assumptions on the generative process of non-sequence data, and propose learning algorithms based on the tensor decomposition method [2] to provably recover firstorder Markov models and hidden Markov models. To the best of our knowledge, this is the first formal guarantee on learning from non-sequence data. Preliminary simulation results confirm our theoretical findings.
- In this paper, a spectral learning based algorithm 
      for learning Markov Model and HMM in a non-sequential setting is derived. 
      The paper deals with learning Markov models and hidden Markov models from 
      sparse realizations obtained at random times. Proper proofs for 
      empirical moments are given. Also, a sample complexity bound has been 
      provided. The paper is generally well-written and understandable. The 
      comments are as follows: -Learning a sequential model in a 
      non-sequential setting is not a concept that everybody is familiar of. It 
      may be beneficial to briefly review the existing methods (possibly maximum 
      likelihood based). Author(s) may argue that this can’t be done because of 
      space constraints. However, I believe that, it would be better to motivate 
      the non-sequential sequential model learning rather than to reproduce the 
      tensor decomposition algorithm of Anandkumar et al. I think that the 
      tensor algorithm can be introduced only by giving the general idea of 
      expressing the parameters as symmetric observable tensors. (equation 2) 
      That is, author(s) can exclude the algorithm 2 and theorem 1. -The 
      proper moment equations for learning a Markov model in a non-sequential 
      setting are defined in page 5. Using these moment equations, it possible 
      to recover the expected transition probability matrix T, and parameters 
      \pi. of the Dirichlet prior, using the symmetric orthogonal tensor 
      decomposition algorithm of Anandkumar et al. from 2012. However, in order 
      to recover the transition matrix itself (P), author(s) propose a search 
      heuristic. In my opinion, this search algorithm can be made clearer to the 
      reader by writing it as a pseudo-code. The assumption of presence of a 
      zero entry in P makes sense if the number of states in the Markov chain is 
      large, which may induce sparsity. Minor comment: isn’t \pi = \alpha / 
      \alpha_0? Instead of using the proportional (at the beggining of page 5), 
      it is better to give the exact equality to make the reader understand the 
      moment equation proofs more easily. -Experimental results are 
      limited to synthetic data. Since learning a sequential model in a 
      non-sequential setting is the primal motivation of this paper, I think it 
      is essential to validate the algorithm on a real life data. Moreover, a 
      performance comparison with a more conventional learning algorithm is 
      vital for the justification of the algorithm. -In section 4, it is 
      indicated that as the number of data items N increases, the take off point 
      in Figure1(a) gets closer to the true value r=0.3. I personally can not 
      understand why the projection error is not zero when r is less than 0.3 
      and it is zero when r is larger. Shouldn’t it be different from zero 
      whenever r is not equal to 0.3? A comment on this issue would be helpful. 
      Minor comment: On legend of figure 1, shouldn’t the logarithms be of 
      base 10, instead of 2? -The general motivation behind choosing 
      spectral learning algorithms for learning latent variable models over ML 
      based approaches is also due to their speed. There is no mention regarding 
      the proposed algorithm on this aspect. A speed comparison with a ML based 
      approach (possibly EM) would be beneficial. It is also possible to use 
      matrix eigendecomposition based algorithm of Anandkumar et al. (A method 
      of moments for mixture models and HMMs, 2012) which would be 
      computationally cheaper than the tensor decomposition approach.