to recover the latent structure of an HMM only from pairwise co-occurrence probabilities $\Pr[Y_t,Y_{t+1}]$, provided that the underlying emission probability $\Pr[Y_t|X_t]$ is *sufficiently scattered*. Compared to the existing NMF-based HMM learning approaches, our formulation employs a different (determinant-based) criterion to ensure identifiability of the HMM parameters. Our matrix factorization approach resolves cases that cannot be handled by tensor methods, namely when $T$ is insufficient to estimate third-order probabilities, under an additional condition that is quite mild: that the emission probability matrix ${\boldsymbol{M}}$ must be *sufficiently scattered*, rather than simply full column-rank.

We apply our method to hidden topic Markov modeling (HTMM) [@gruber2007hidden], in which case the number of hidden states (topics) is indeed much smaller than the number of ambient states (words). HTMM goes beyond the simple and widely used bag-of-words model by assuming that (ordered) words in a document are emitted from a hidden topic sequence that evolves according to a Markov model. We show improved performance on real data when using this simple and intuitive model to take word ordering into account when learning topics, which also benefits from our identifiability guaranteed matrix factorization method.

As an illustrative example, we showcase the inferred topic of each word in 