HMMs with PyMC3: Complexity and point estimates

I’ve been looking to expand on what other HMM libraries can do by having probabilistic estimates with PyMC3. I found some working code for this task here, which was quickly adapted to my data.

I have found runtime to be polynomial with respect to sample length:

This runtime is too slow for my project. Is there a way to adapt this code to make point estimates for each timestep’s hidden state, but estimate distributions for the initial, transition and emission matrices which parameterize an HMM? Would that make it asymptotically faster?

I appreciate your help - I’m not very experienced with probabilistic models, but I thought I’d try them on this problem to see if the distributions generated add useful information.

Aside #1: I’m not quite sure which part of the algorithm is pushing it past linear - It seems to be the CategoricalGibbsMetropolis step, is there any documentation on its time complexity?
Aside #2: I am a victim of this bug, is there any reliable fix?

That post you are looking at is pretty old and the implementation is not optimal. You should instead take a look at How to marginalized Markov Chain with categorical?