Spectral Learning of Mixture of Hidden Markov Models
In this paper, we propose a learning approach for the Mixture of Hidden Markov Models (MHMM) based on the Method of Moments (MoM). Computational advantages of MoM make MHMM learning amenable for large data sets. It is not possible to directly learn an MHMM with existing learning approaches, mainly due to a permutation ambiguity in the estimation process. We show that it is possible to resolve this ambiguity using the spectral properties of a global transition matrix even in the presence of estimation noise. We demonstrate the validity of our approach on synthetic and real data.
Summary: The authors consider the problem of learning a mixture of Hidden Markov Models. The authors first suggest using a spectral learning algorithm to learn a set of parameters for a hidden Markov model, and then provide a method for resolving the permutation ambiguity in the transition matrix to recover it’s underlying block-diagonal structure.Major Comments:1. I found this paper to be very well written for the most part. The experimental results section could be fleshed out a bit. In particular the 2. The authors rely on the fact that a mixture of Hidden Markov Models can be expressed as a single HMM. One of the main reasons, if not the primary reason, for learning a mixture of HMMs as opposed to a single HMM directly is that the block diagonal structure of the mixture of HMMs is sparse. This sparseness may be imposed on problems that are deemed to be too large to learn with a full model, especially if the problem is large and the amount of training data is small. However, in this paper, the author’s algorithm relies on *first* accurately estimating the full HMM parameters, then reversing the permutation in order to find the block diagonal structure. For most real-world problems this seems completely untenable. Do the author’s have suggestions for when their algorithm might be appropriate and when it might not be? 3. Again, in practice, the recovered transition matrix is not likely to be sparse. Is there any way to guarantee that the transition matrix learned by the spectral algorithms suggested in this paper will be (close to) sparse? I suspect that there may be many HMM models with full transition matrices that are close to the sparse model with block diagonal structure that the authors are looking for. It is not at all obvious that the matrix that is learned via [1,2] will be sparse with very small amounts of noise.4. I am really worried that the experimental results do not accurately reflect the reality of noise in the transition matrix. For example, in Section 4.1, the authors apply their algorithm to a transition matrix that has been permuted by noise sampled from a Dirichlet distribution… but this is a paper about learning mixtures of HMM parameters, not just depermuting matrices. Shouldn’t the authors have sampled observation data from a mixture of HMMs and then learned all of the parameters back from the *observed* data? This would give a much more accurate idea of how noise in observations and small quantities of data are actually reflected in the learned transition matrix, and how hard it is to depermute the matrix in the presence of this noise.5. The experiment in Section 4.2 is starting to get at what I was hoping for in the previous section, but there is nowhere near enough information to evaluate the quality of the experiment. In particular, I have no idea what the mixture of HMMs actually looked like. The actual parameters of the transition and observation matrix matter *a lot* for evaluating how easy or hard it is to learn the model from data. I would like to know more about the specifics of these parameters (the authors could put it in an appendix if they feel that space is at a premium).6. In table 1, why is EM initialized with spectral learning ever doing worse than spectral learning alone? Shouldn’t EM only improve the results?Minor Comments:1. I believe that the subscript of \Lambda in the bottom right corner of the first matrix in the proof in Section 3.2.1 should be K, not 2.2. Text and numbers are *way* too small in the figures.