Given an HMM, it is easy to compute the best approximating $n$-gram model over the observations. For example, for $N=1$, we have $p(w_i|w_{i-1}) = \sum_{s_i,s_{i-1}}p(w_i,s_i|w_{i-1},s_{i-1})=\sum_{s_i,s_{i-1}}p(w_i|s_i)p(s_i|s_{i-1}) p(s_{i-1} | w_{i-1})$.

This can be computed given the parameters of the HMM (and its stationary distribution).

It seems natural to say the HMM is "difficult" if the entropy of its observations under the true model (computed with the forward-backward algorithm) is significantly lower than the entropy of the best approximating $n$-gram model. If they are close, it means that the latents do not play an important role, and you can do as well by just calculating counts over the observations.

Is there a principled way to sample "difficult" HMMs, e.g., HMMs where there is a difference of at least $d$ between their entropy and the entropy of the best approximating $n$-gram model?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.