Which sequential input problems are best suited for each? Does input dimensionality determine which is a better match? Are problems which require "longer memory" better suited for an LSTM RNN, while problems with cyclical input patterns (stock market, weather) more easily solved by an HMM?
It seems like there is a lot of overlap; Im curious what subtle differences exist between the two.
Hidden Markov Models (HMMs) are much simpler than Recurrent Neural Networks (RNNs), and rely on strong assumptions which may not always be true. If the assumptions are true then you may see better performance from an HMM since it is less finicky to get working.
An RNN may perform better if you have a very large dataset, since the extra complexity can take better advantage of the information in your data. This can be true even if the HMMs assumptions are true in your case.
Finally, don't be restricted to only these two models for your sequence task, sometimes simpler regressions (e.g. ARIMA) can win out, and sometimes other complicated approaches such as Convolutional Neural Networks might be the best. (Yes, CNNs can be applied to some kinds of sequence data just like RNNs.)
As always, the best way to know which model is best is to make the models and measure performance on a held out test set.
State transitions only depend on the current state, not on anything in the past.
This assumption does not hold in a lot of the areas I am familiar with. For example, pretend you are trying to predict for every minute of the day whether a person was awake or asleep from movement data. The chance of someone transitioning from asleep to awake increases the longer the person has been in the asleep state. An RNN could theoretically learn this relationship and exploit it for higher predictive accuracy.
You can try to get around this, for example by including the previous state as a feature, or defining composite states, but the added complexity does not always increase an HMM's predictive accuracy, and it definitely doesn't help computation times.
You must pre-define the total number of states.
Returning to the sleep example, it may appear as if there are only two states we care about. However, even if we only care about predicting awake vs. asleep, our model may benefit from figuring out extra states such as driving, showering, etc. (e.g. showering usually comes right before sleeping). Again, an RNN could theoretically learn such a relationship if showed enough examples of it.
It may seem from the above that RNNs are always superior. I should note, though, that RNNs can be difficult to get working, especially when your dataset is small or your sequences very long. I've personally had troubles getting RNNs to train on some of my data, and I have a suspicion that most published RNN methods/guidelines are tuned to text data. When trying to use RNNs on non-text data I have had to perform a wider hyperparameter search than I care to in order to get good results on my particular datasets.
In some cases, I've found the best model for sequential data is actually a UNet style (https://arxiv.org/pdf/1505.04597.pdf) Convolutional Neural Network model since it is easier and faster to train, and is able to take the full context of the signal into account.
Let's first see the differences between the HMM and RNN.
From this paper: A tutorial on hidden Markov models and selected applications in speech recognition we can learn that HMM should be characterized by the following three fundamental problems:
Problem 1 (Likelihood): Given an HMM λ = (A,B) and an observation sequence O, determine the likelihood P(O|λ).
Problem 2 (Decoding): Given an observation sequence O and an HMM λ = (A,B), discover the best hidden state sequence Q.
Problem 3 (Learning): Given an observation sequence O and the set of states in the HMM, learn the HMM parameters A and B.
We can compare the HMM with the RNN from that three perspectives.
Likelihood in HMM(Picture A.5)
Language model in RNN
In HMM we calculate the likelihood by $P(O)=\sum_Q P(O, Q) = \sum_Q P(O|Q)P(Q)$ where the $Q$ represents all the possible hidden state sequences, and the probability is the real probability in the graph. While in RNN the equivalent, as far as I know, is the inverse of the perplexity in language modeling where $\frac{1}{p(X)} = \sqrt[T]{\prod_{t=1}^T \frac{1}{p(x^t|x^{(t-1)},...,x^{(1)})}}$ and we don't sum over the hidden states and don't get the exact probability.
In HMM the decoding task is computing $v_t(j) = max_{i=1}^N v_{t-1}(i)a_{ij} b_(o_t)$ and determining which sequence of variables is the underlying source of some sequence of observations using the Viterbi algorithm and the length of the result is normally equal to the observation; while in RNN the decoding is computing $P(y_1, ..., y_O|x_1, ..., x_T) = \prod_{o=1}^OP(y_o|y_1, ..., y_{o-1}, c_o)$ and the length of $Y$ is usually not equal to the observation $X$.
Decoding in RNN
The learning in HMM is much more complicated than that in RNN. In HMM it usually utilized the Baum-Welch algorithm(a special case of Expectation-Maximization algorithm) while in RNN it is usually the gradient descent.
For your subquestions:
Which sequential input problems are best suited for each?
When you don't have enough data use the HMM, and when you need to calculate the exact probability HMM would also be a better suit(generative tasks modeling how the data are generated). Otherwise, you can use RNN.
Does input dimensionality determine which is a better match?
I don't think so, but it may take HMM more time to learn if hidden states is too big since the complexity of the algorithms (forward backward and Viterbi) is basically the square of the number of discrete states.
Are problems which require "longer memory" better suited for an LSTM RNN, while problems with cyclical input patterns (stock market, weather) more easily solved by an HMM?
In HMM the current state is also affected by the previous states and observations(by the parent states), and you can try Second-Order Hidden Markov Model for "longer memory".
I think you can use RNN to do almost
I found this question, because I was wondering about their similarities and differences too. I think it's very important to state that Hidden Markov Models (HMMs) do not have inputs and outputs in the strictest sense.
HMMs are so-called generative models, if you have an HMM, you can generate some observations from it as-is. This is fundamentally different from RNNs, as even if you have a trained RNN, you need input to it.
A practical example where this is important is speech synthesis. The underlying Hidden Markov states are phones and the emitted probability events are the acoustics. If you have a word model trained, you can generate as many different realisations of it as you want.
But with RNNs, you need to provide at least some input seed to get out your output. You could argue that in HMMs you also need to provide an initial distribution, so it's similar. But if we stick with the speech synthesis example,, it is not because the initial distribution will be fixed (starting always from first phones of the word).
With RNNs you get a deterministic output sequence for a trained model, if you are using the same input seed all the time. With HMM, you don't because the transitions and the emissions are always sampled from a probability distribution.
