HMM structure, characterized by the transition matrix $\Pr[X_{t+1}|X_{t}]$ and the emission probability $\Pr[Y_t|X_t]$ from the set of observations $\{Y_t\}_{t=0}^T$.

Related work {#sec:related}
------------

The traditional way of learning a HMM from $\{Y_t\}_{t=0}^T$ is via expectation-maximization (EM) [@rabiner1986introduction], in which the expectation step is performed by calling the forward-backward algorithm. This specific instance of EM is also called the Baum-Welch algorithm [@baum1970maximization; @Ghahramani2001]. However, the complexity of Baum-Welch is prohibitive when $T$ is relatively large—the complexity of the forward-backward algorithm is ${\mathcal{O}}(K^2T)$, but EM converges slowly, so the forward-backward algorithm must be called many times. This is a critical issue, because a HMM can only be learned with high accuracy when the number of observation samples $T$ is large enough.

One way of designing scalable algorithms for learning HMMs is to work with sufficient statistics—a summary of the given observation sequence, whose size does not grow with $T$. Throughout this paper we assume that the HMM process is stationary (time-invariant), which is true almost surely if the underlying Markov process is ergodic and the process has been going on for a reasonable amount of time. With $T$ large enough, we can accurately estimate the co-occurrence probability between two consecutive emissions $\Pr[Y_t,Y_{t+1}]$. 