# \[ANN\] HiddenMarkovModels.jl: when did HMMs get so fast?

**URL:** <https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191>\
**Category:** Package Announcements\
**Tags:** statistics, hmm\
**Created:** [June 11, 2023, 4:43pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191 "2023-06-11T16:43:43Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [June 11, 2023, 4:43pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/1 "2023-06-11T16:43:43Z")

</div>

> **[GitHub - gdalle/HiddenMarkovModels.jl: A Julia package for simulation, inference and...](https://github.com/gdalle/HiddenMarkovModels.jl)**
>
> A Julia package for simulation, inference and learning of Hidden Markov Models.

# What the \*\*\*\* is an HMM?

> Skip to the good bits below if you’re in a rush

[Hidden Markov Models](https://en.wikipedia.org/wiki/Hidden_Markov_model) (HMMs for short) are a statistical modeling framework that is ubiquitous in signal processing, bioinformatics and plenty of other fields. They capture the distribution of an observation sequence (Y\_t) by assuming the existence of a latent state sequence (X\_t) such that:

- (X\_t) follows a (discrete time, discrete space) Markov chain
- for each t, the distribution of Y\_t is entirely determined by the value of X\_t

Imagine we are given an observation sequence (Y\_t) and a parametric family of HMMs \{p\_\theta\}. Following this famous [tutorial](https://ieeexplore.ieee.org/document/18626), we can list three fundamental problems, each of which has a solution that relies on dynamic programming:

| Problem | Description | Solution |
| --- | --- | --- |
| Evaluation | Compute the likelihood of the observation sequence p\_\theta(Y) for a fixed \theta | Forward algorithm |
| Decoding | Compute the most likely state sequence \arg\max\_X p\_\theta(X \mid Y) for a fixed \theta | Viterbi algorithm |
| Learning | Find the best parameter \arg\max\_\theta p\_\theta(Y) | Baum-Welch (EM) algorithm |

# Who are the competitors?

Of course, you saw me coming a mile away: there are already some Python packages that provide HMM functionalities. The main two are:

- [hmmlearn](https://github.com/hmmlearn/hmmlearn) – this one seems dormant
- [pomegranate](https://github.com/jmschrei/pomegranate) – this one does plenty of other things, it truly is an amazing toolkit, and its maintainer was very friendly when I asked for help

There is also a Julia package called [HMMBase.jl](https://github.com/maxmouchet/HMMBase.jl), developed by @maxmouchet a while ago. But for my PhD research, I found myself wanting things that none of these implementations provided. So I rolled up my sleeves and created [HiddenMarkovModels.jl](https://github.com/gdalle/HiddenMarkovModels.jl).

What follows is _not_ a criticism of past efforts: if anything, it is an hommage. HMMBase.jl in particular was my main source of inspiration, and much of my code comes from it. I have discussed it with @maxmouchet, and we agreed to declare my package the official successor to HMMBase.jl. Since the interface is very similar, users shouldn’t struggle too much with the transition.

As a side note, one can always rephrase an HMM as a probabilistic program and throw some MCMC or variational inference at it. But at least in the basic case I describe, it will be much slower than dedicated routines. That is why I don’t include packages such as [Turing.jl](https://github.com/TuringLang/Turing.jl) in the comparison.

# What can the package do?

To get a feel for the package, check out its documentation at [https://gdalle.github.io/HiddenMarkovModels.jl/](https://gdalle.github.io/HiddenMarkovModels.jl/). Here is a feature comparison between HMMBase.jl and HiddenMarkovModels.jl:

| Feature | HMMBase.jl | HiddenMarkovModels.jl |
| --- | --- | --- |
| Number types | `Float64` | anything |
| Observation types | `Number` or `Vector` | anything |
| Observation distributions | from [Distributions.jl](https://github.com/JuliaStats/Distributions.jl) | satisfying [DensityInterface.jl](https://github.com/JuliaMath/DensityInterface.jl) |
| Priors / structures | no | customizable |
| Autodiff | no | forward mode (for now) |
| Multiple sequences | no | parallelized |

Reaching this level of generality was my main motivation. Indeed, my doctoral research involved differentiating the likelihood of HMMs with multiple sequences of Poisson process observations. This kind of funky combination is now possible with very little additional work from the user.

# How reliable is it?

The package follows all the best practices that I’m aware of:

- quality checks with [Aqua.jl](https://github.com/JuliaTesting/Aqua.jl)
- correctness _and_ type stability checks with [JET.jl](https://github.com/aviatesk/JET.jl) (shoutout to @aviatesk as always)
- coherence checks against HMMBase.jl
- integration checks with third-party packages like [SparseArrays](https://github.com/JuliaSparse/SparseArrays.jl), [StaticArrays.jl](https://github.com/JuliaArrays/StaticArrays.jl) and [ForwardDiff.jl](https://github.com/JuliaDiff/ForwardDiff.jl)
- documentation with [Documenter.jl](https://github.com/JuliaDocs/Documenter.jl)
- benchmarks compatible with [PkgBenchmark.jl](https://github.com/JuliaCI/PkgBenchmark.jl)

# Does it run fast?

In addition to the features, there is a number of tricks that I used to speed up the code: avoiding allocations, calling linear algebra subroutines, multithreading across sequences, etc.  
The results are pretty amazing on small- to medium-scale problems. HiddenMarkovModels.jl blows HMMBase.jl out of the water, and compares quite favorably to hmmlearn (which has a NumPy backend) and pomegranate (which has a PyTorch backend), even though I ran it on a single thread.  
Complete reproducible benchmarks with their explanations can be found at [https://gdalle.github.io/HiddenMarkovModels.jl/dev/benchmarks/](https://gdalle.github.io/HiddenMarkovModels.jl/dev/benchmarks/), they’re run automatically before each docs build.

 ![benchmark_single_sequence_baum_welch](https://global.discourse-cdn.com/julialang/original/3X/6/5/6553084fbb9b3d727375a5874c5d88e2778b1762.png)

 ![benchmark_multiple_sequences_baum_welch](https://global.discourse-cdn.com/julialang/original/3X/7/e/7e9b862f8c10762530907252a959806b667b7ec9.png)

# Where will it go next?

The package is currently awaiting registration (see [this PR](https://github.com/JuliaRegistries/General/pull/85313) to the general registry).

Here are some of the things that I would like to work on soon-ish:

- specification and testing for an `AbstractHMM` interface, perhaps with [Interfaces.jl](https://github.com/rafaqz/Interfaces.jl)
- numerical stability in large-dimensional settings with sparse transitions
- reverse mode autodiff with [ChainRules.jl](https://github.com/JuliaDiff/ChainRules.jl)
- SIMD optimization with [LoopVectorization.jl](https://github.com/JuliaSIMD/LoopVectorization.jl) or [Tullio.jl](https://github.com/mcabbott/Tullio.jl)
- [spectral estimation methods](https://arxiv.org/abs/0811.4413)
- [input-output HMMs](https://pubmed.ncbi.nlm.nih.gov/18263517/) in my other package [ControlledMarkovModels.jl](https://github.com/gdalle/ControlledHiddenMarkovModels.jl) (don’t look at it yet, it’s ugly and unmaintained!)

Contributors are welcome!  
In the long run, I will probably transfer this package to [JuliaStats](https://github.com/JuliaStats), but for now I’d like to keep control until things are stabilized.

# I’ve read everything, what now?

If you’ve made it this far, congrats. Take a break. Treat yourself to a fruit juice. Chill.

And whenever you’re ready, you can run the command below, then look at the tutorial to start playing around: [https://gdalle.github.io/HiddenMarkovModels.jl/dev/tutorial/](https://gdalle.github.io/HiddenMarkovModels.jl/dev/tutorial/).

```julia
pkg> add https://github.com/gdalle/HiddenMarkovModels.jl

```

If you have any suggestions or run into trouble, feel free to [open an issue](https://github.com/gdalle/HiddenMarkovModels.jl/issues) or use this thread! Also, a little star on the repo is always appreciated if you find it useful 😇

---

<div class="post-metadata">

**Author:** ![camilogarciabotero](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/camilogarciabotero/32/35000_2.png) [@camilogarciabotero](https://discourse.julialang.org/u/camilogarciabotero)\
**Post date:** [June 14, 2023, 3:59pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/2 "2023-06-14T15:59:58Z")

</div>

This is so amazing. Thanks for working on this and creating an excellent framework for working with HMMs. I just wanted to point out that there is another package called [MarkovModels.jl](https://github.com/FAST-ASR/MarkovModels.jl) that seems to have neat implementations of some of the algorithms (e.g. Viterbi) that apparently scales well.

---

<div class="post-metadata">

**Author:** ![jacobusmmsmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jacobusmmsmit/32/217669_2.png) [@jacobusmmsmit](https://discourse.julialang.org/u/jacobusmmsmit)\
**Post date:** [June 14, 2023, 6:31pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/3 "2023-06-14T18:31:41Z")

</div>

Are you gonna add the Aqua badge to the repo?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [June 15, 2023, 7:02am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/4 "2023-06-15T07:02:41Z")

</div>

Wow, I missed that one in my SoTA review. Might add it to the benchmarks sometime! And I should specify that my package is mostly geared towards middle-scale uses on the CPU, I made absolutely zero effort to be GPU-friendly

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [June 15, 2023, 7:02am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/5 "2023-06-15T07:02:57Z")

</div>

I didn’t even remember there was such a badge! Is there a JET badge?

---

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [June 15, 2023, 7:15am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/6 "2023-06-15T07:15:21Z")

</div>

[![JET QA](https://img.shields.io/badge/JET.jl-%E2%9C%88%EF%B8%8F-%23aa4444)](https://github.com/aviatesk/JET.jl) Works (from [Logo or Readme badge similar to Aqua's · Issue #375 · aviatesk/JET.jl · GitHub](https://github.com/aviatesk/JET.jl/issues/375))

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 22, 2024, 8:19pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/7 "2024-02-22T20:19:58Z")

</div>

> [@gdalle](#):
>
> Here are some of the things that I would like to work on soon-ish:
> 
> - specification and testing for an `AbstractHMM` interface, perhaps with [Interfaces.jl](https://github.com/rafaqz/Interfaces.jl)
> - numerical stability in large-dimensional settings with sparse transitions
> - reverse mode autodiff with [ChainRules.jl](https://github.com/JuliaDiff/ChainRules.jl)
> - SIMD optimization with [LoopVectorization.jl](https://github.com/JuliaSIMD/LoopVectorization.jl) or [Tullio.jl](https://github.com/mcabbott/Tullio.jl)
> - [spectral estimation methods](https://arxiv.org/abs/0811.4413)
> - [input-output HMMs](https://pubmed.ncbi.nlm.nih.gov/18263517/) in my other package [ControlledMarkovModels.jl](https://github.com/gdalle/ControlledHiddenMarkovModels.jl) (don’t look at it yet, it’s ugly and unmaintained!)

There is now a new version v0.4.1 which supports most of the stuff listed here! Go try it out 🙂

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 5, 2024, 8:47pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/9 "2024-04-05T20:47:46Z")

</div>

Update: version 0.5 is registered and has been turned into a JOSS paper!

> **[HiddenMarkovModels.jl: generic, fast and reliable state space modeling](https://joss.theoj.org/papers/10.21105/joss.06436)**
>
> Dalle, G., (2024). HiddenMarkovModels.jl: generic, fast and reliable state space modeling. Journal of Open Source Software, 9(96), 6436, https://doi.org/10.21105/joss.06436

---

<div class="post-metadata">

**Author:** ![NeroBlackstone](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/neroblackstone/32/208679_2.png) [@NeroBlackstone](https://discourse.julialang.org/u/NeroBlackstone)\
**Post date:** [May 2, 2024, 6:29pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/10 "2024-05-02T18:29:09Z")

</div>

Amazing! 😊😊😊  
Do you have plan to support High-Order HMM?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 2, 2024, 7:01pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/11 "2024-05-02T19:01:17Z")

</div>

Do you mean HMMs where the dependency is on the previous k states? If so, no, but you can probably trick the package into doing what you want by encoding k states into a single integer and using a sparse transition matrix.  
Some discussion of this workaround can be found in [this issue](https://github.com/gdalle/HiddenMarkovModels.jl/issues/12), and I can also help you if you’re stuck

---

<div class="post-metadata">

**Author:** ![MikeAinOz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikeainoz/32/202188_2.png) [@MikeAinOz](https://discourse.julialang.org/u/MikeAinOz)\
**Post date:** [May 4, 2024, 9:18pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/12 "2024-05-04T21:18:09Z")

</div>

This looks like great work, congratulations, I did notice that the tutorial link ending “/dev/tutorial” above doesn’t work and gives a 404​:+1:😁

---

<div class="post-metadata">

**Author:** ![apo383](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/apo383/32/11272_2.png) [@apo383](https://discourse.julialang.org/u/apo383)\
**Post date:** [May 5, 2024, 3:50am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/13 "2024-05-05T03:50:28Z")

</div>

> [@gdalle](#):
>
> HMMs where the dependency is on the previous kkk states

Doesn’t that violate the Markov property? I thought Markov models were defined as dependent on previous state alone.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 5, 2024, 5:13am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/14 "2024-05-05T05:13:03Z")

</div>

> [@MikeAinOz](#):
>
> I did notice that the tutorial link ending “/dev/tutorial” above doesn’t work and gives a 404​

The first message was written with a previous version of the package, where the documentation was structured differently. Now there is more than one tutorial, hence the broken link 😉 Here’s the first one:

> **[Basics · HiddenMarkovModels.jl](https://gdalle.github.io/HiddenMarkovModels.jl/stable/examples/basics/)**
>
> Documentation for HiddenMarkovModels.jl.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 5, 2024, 5:13am UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/15 "2024-05-05T05:13:55Z")

</div>

> [@apo383](#):
>
> Doesn’t that violate the Markov property? I thought Markov models were defined as dependent on previous state alone.

It is indeed a generalization of the Markov property to depend on the past k states, but as I have hinted before, you can reformulate such models to depend only on the last state by changing what you put in the state. So it’s not really more generic

---

<div class="post-metadata">

**Author:** ![adannenberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adannenberg/32/7869_2.png) [@adannenberg](https://discourse.julialang.org/u/adannenberg)\
**Post date:** [October 6, 2024, 4:32pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/16 "2024-10-06T16:32:05Z")

</div>

Question: Does the package support continuous-valued state variables in addition to discrete-valued state variables? The examples and documentation seem limited to discrete-valued state variables (finite-size vector of probabilities for initial values of state variable, evolution in terms of a set of transition probabilities rather than a transition matrix and noise covariance matrix).

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 6, 2024, 5:55pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/17 "2024-10-06T17:55:05Z")

</div>

No, if you’re thinking SSMs and things like Kalman filter, that’s not supported by HiddenMarkovModels.jl. But there are other packages in Julia to do that, although I’m not familiar with them.

---

<div class="post-metadata">

**Author:** ![adannenberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adannenberg/32/7869_2.png) [@adannenberg](https://discourse.julialang.org/u/adannenberg)\
**Post date:** [October 6, 2024, 6:07pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/18 "2024-10-06T18:07:53Z")

</div>

Quel dommage! But thank you for the rapid response. Maybe the package should be renamed DiscreteHiddenMarkovModels or, less jokingly, the documentation should make more explicit the fact that the package is for HMMs in which the state variable is discrete. I’ll keep browsing… Thanks again.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 6, 2024, 7:39pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/19 "2024-10-06T19:39:59Z")

</div>

Sounds like a good idea! Do you want to open a docs PR?

---

<div class="post-metadata">

**Author:** ![adannenberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adannenberg/32/7869_2.png) [@adannenberg](https://discourse.julialang.org/u/adannenberg)\
**Post date:** [October 6, 2024, 9:30pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/20 "2024-10-06T21:30:05Z")

</div>

Sure, if you’d like. I haven’t done that before, though, so just let me know the steps please. Also, just out of curiosity, since you’re the package author and we’ve already communicated what will be the benefit?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 6, 2024, 10:17pm UTC](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191/21 "2024-10-06T22:17:12Z")

</div>

Of course I can do the docs PR myself, so don’t stress about it. But putting myself in the shoes of someone who has never contributed to a package before (as seems to be your case?), I think it’s nice to be encouraged to do it, especially for something low-stakes like updating documentation. It was meant as an invitation and an offer to guide you through it, not an obligation.

[Next page](https://discourse.julialang.org/t/ann-hiddenmarkovmodels-jl-when-did-hmms-get-so-fast/100191.md?page=2)