Are HMMs still used for unsupervised tasks? [D]

[u/fullgoopy_alchemist]

I'm exploring Hidden Markov Models (HMMs) as a baseline method for "dataset exploration/discovery" where I have a bunch of unstructured data with no annotations, and wish to gain insights about the structure and semantics of the data within. I was wondering if there are more modern (deep learning based or otherwise) approaches which have completely superseded HMMs for such tasks.

[u/eonu]

In practice I've found that it is quite challenging to get HMMs to perform well for unsupervised/supervised tasks if multivariate sequences are involved.

They might work okay for low dimensional problems like positional data, but otherwise you might struggle. Also depending on your data, choosing the emission distributions and number of states isn't always straightforward.

Also while they are more interpretable than deep learning methods, often the hidden states derived from EM aren't super intuitive, and usually don't translate to the regimes that you're expecting the HMM to capture in the data. If you truly have no expectations on what these regimes are, then a HMM may be suitable.

That said, it's one of the best starting points for the kind of task you are describing. Some deep learning architectures for this kind of stuff can be overly complex.

[u/s-jb-s]

Hard to say anything concrete without knowing more about the data and what you mean by structure (which could refer to quite a few things, particularly wrt HMMs*). A lot of choices will depend on e.g. dimensionality/dynamics/emission model & so forth.

There's been a tonne of interesting work over the past couple of decades building on HMMs, particularly in Bayesian nonparametrics if that's something of interest. Useful keywords include sticky HDP-HMMs, HDP-HSMMs, VAR/AR-HMMs, and switching linear dynamical systems (SLDSs).

Picking up on what the other commenter mentioned -- choosing the number of states is less of a fixed modelling choice in some of these approaches (e.g. HDP-HMMs), since you instead place a prior over an effectively unbounded state space (more generally there are some super interesting approaches if this is specifically a problem of interest). High dimensionality is a somewhat separate problem, but can often be handled through the model specification, dimensionality reduction, structured emissions, learned representations, etc.

I wouldn't really say HMMs have been superseded so much as they've been generalised & built on by other approaches. If you're specifically after (interpretable) latent regimes in sequential data, HMM/HSMM/state-space models are still pretty reasonable in some fields.

* If by structure you mean something broader in high-dimensional unstructured data, rather than latent dynamics in sequential data, then representation learning w/ clustering/segmentation is probably the more modern approach?

[u/waslous → u/s-jb-s]

Could you point me in the direction of the papers you mentioned regarding the state number selection? Sounds really interesting

[u/s-jb-s → u/waslous]

I'll give some pointers towards the Bayesian side of this problem as that's what i'm most familiar with (very nostalgic looking some of these papers up again!)

For finite HMMs, a classic is Robert, Rydén & Titterington (2000), which applies Green's (1995) RJMCMC approach to infer the number of states K directly. RJMCMC is a fun one, but it can be a bit of a pita. If you don't need to update K within a single chain, a lot of methods will just fit a bunch of fixed-K models and compare their marginal likelihoods, with the problem essentially reducing to that computation (e.g., Chib's estimator/bridge sampling/<insert other sampling method>/power posteriors/...). Friel & Pettitt (2008) is a good intro to power posteriors, it's very readable. The '90s and early '00s were a bit of a gold rush for these marginal-likelihood estimator methods. Honourable mention: The Worst Monte Carlo Method Ever.

There's some label-switching/identifiability caveats when applying these to HMM-type models, which is a whole can of worms itself. Another approach if you're explicitly dealing with finite-state HMMs is to overfit a HMM then use sparse priors & other such techniques. Gassiat & Rousseau (2014) & van Havre et al. (2016) are good references for this sort of idea.

On the non-parametric side, I’d look at Teh et al. (2006) for the HDPs, Fox et al. (2011) for sticky HDP-HMMs. Though, these don't quite infer a finite K in the same sense as RJMCMC. For inference wrt iHMMs/HDP-HMMs, Van Gael et al. (2008) is the classic beam-sampling paper, and if state-duration modelling is of interest, there's Johnson & Willsky (2013) for HDP-HSMMs.

They're all slightly different answers to the same general problem depending on what you're working with, and the assumptions & tradeoffs you're willing to make. I'd start with Robert, Rydén & Titterington (2000), Gassiat & Rousseau (2014)/van Havre et al. (2016), and Fox et al. (2011) since they're quite different approaches. But it depends on your familiarity with Bayesian approaches, I suppose.

Informal bibliography of sorts:

RJMCMC

• Green (1995), Reversible Jump Markov Chain Monte Carlo Computation and Bayesian Model Determination - DOI
• Robert, Rydén & Titterington (2000), Bayesian Inference in Hidden Markov Models Through the Reversible Jump Markov Chain Monte Carlo Method - DOI

Marginal likelihood

• Chib (1995), Marginal Likelihood from the Gibbs Output - DOI
• Frühwirth-Schnatter (2004), Estimating Marginal Likelihoods for Mixture and Markov Switching Models Using Bridge Sampling Techniques - DOI
• Friel & Pettitt (2008), Marginal Likelihood Estimation via Power Posteriors - DOI

Overfitting

• Gassiat & Rousseau (2014), About the Posterior Distribution in Hidden Markov Models with Unknown Number of States - DOI
• van Havre et al. (2016), Overfitting Hidden Markov Models with an Unknown Number of States - arXiv

Nonparametrics

• Teh et al. (2006), Hierarchical Dirichlet Processes - DOI
• Van Gael et al. (2008), Beam Sampling for the Infinite Hidden Markov Model - DOI
• Fox et al. (2011), A Sticky HDP-HMM with Application to Speaker Diarization - DOI
• Johnson & Willsky (2013), Bayesian Nonparametric Hidden Semi-Markov Models - JMLR

Frühwirth-Schnatter also has a whole bunch of papers from the early/mid '00's that are very very readable relating to this stuff (and a very good book!).

(this is a very limited & poorly mixed sample from memory)