3 ms·

-- vs kalman filters: "In both models, there's an unobserved state that changes over time according to relatively simple rules, and you get indirect informatio

by platz 10y ago

-- vs kalman filters: "In both models, there's an unobserved state that changes over time according to relatively simple rules, and you get indirect information about that state every so often. In Kalman filters, you assume the unobserved state is Gaussian-ish and it moves continuously according to linear-ish dynamics (depending on which flavor of Kalman filter is being used). In HMMs, you assume the hidden state is one of a few classes, and the movement among these states uses a discrete Markov chain. In my experience, the algorithms are often pretty different for these two cases, but the underlying idea is very similar." - THISISDAVE -- vs LSTM/RNN: "Some state-of-the-art industrial speech recognition [0] is transitioning from HMM-DNN systems to "CTC" (connectionist temporal classification), i.e., basically LSTMs. Kaldi is working on "nnet3" which moves to CTC, as well. Speech was one of the places where HMMs were _huge_, so that's kind of a big deal." -PRACCU "HMMs are only a small subset of generative models that offers quite little expressiveness in exchange for efficient learning and inference." - NEXTOS "IMO, anything that be done with an HMM can now be done with an RNN. The only advantage that an HMM might have is that training it might be faster using cheaper computational resources. But if you have the $$$ to get yourself a GPU or two, this computational advantage disappears for HMMs." - SHERJILOZAIR

supercarrot 10y ago
Interesting observation of computational complexity. HMMs require Viterbi algorithm to find the desirable sequence. The complexity of the algorithm depends on the number of previous decisions on which we condition the current one. Time complexity is O(n^(k+1) * S) where n is the length of the sequence, k is the number of previous decisions we condition on, and S is the number of possible decisions. Now, why does HMM require the Viterbi search procedure, and LSTM/RNN doesn't? Inference in LSTM is linear in the length of the sequence -- ignoring the classifier decision time. Why does this work without Viterbi? Given the fact that even Conditional Random Fields need dynamic programming, and that Maximum Entropy Markov Model suffers the inability to learn quickly without dynamic programming and make inference not suffer label bias. What is so special about LSTM that it doesn't need DP. RNN obviously learns a much better representation of features. Still, why then won't HMMs work with that same representation without the search part? Really baffles me. Although, there exists a process that doesn't use NN for sequence labeling and it is linear in the length of sequence and works well. Instead of using a simple classifier as is the case in MEMMs, one can use a cost-sensitive classifier and learn for each decision associated future loss and greedily avoid the loss. This allows the usage of a simple multiclass classifier, removes the search part and can work as well as NN given the right features.
- kastnerkyle 10y ago
  RNN for discrete structured prediction tasks often use a technique called beam search during decoding (see for example papers on neural MT), which is about as close as you can get to a true Viterbi when you don't have independence assumptions. The CTC mentioned above is also a special type of "reductionist" dynamic programming which uses some awesome and clever stuff to remain backproppable. It only works for monotonic alignments (input larger than desired output).
  - supercarrot 10y ago
    Still, beam search can be simulated and improved by running decision processes in parallel. For example, instead of learning the sequence labeling as a sequence of n decisions (where n is the length of the sequence) you can learn sequence labeling as a sequence of 3n+1 decisions where you make 3 decisions for each sequence element and after 3n decision pick one out of three decision streams that minimizes loss using an extra decision. (when inference is done then the classifier will, hopefully, pick the stream that minimizes test loss). This simulates a beam search and can be done during learning and inference and is probably more effective than picking confidence scores of particular decisions and keeping a beam of most confident partial sequences. Bean search is a heuristic thing that improves performance and is done mostly to allow you to correct mistakes you made at the beginning of the process. http://arxiv.org/abs/1603.06042 http://arxiv.org/abs/1603.06042 they illustrate the problem well (label bias). the question remains the same, for example, in the paper above they approximate the partition function of CRFs with a beam but get superior results to other structured prediction methods.
    - kastnerkyle 10y ago
      Sure, there are a lot of potential things to do - either by enumerating towards the full "brute force" loss partway as I think you are hinting toward, or treating as a subsequences, or something else [0, 1, 2]. The point is, IMO RNNs do need some kind of structured loss (more than per step likelihood) to be competitive with HMM approaches using Viterbi decoding, in addition to some sequence smarts (such as beam search) in decoding. At least in NMT, enumerating the possible decisions as 3n + 1 is almost impossible since the softmax size is generally the memory bottleneck in training - and a bigger vocabulary is typically a huge win. It is more feasible in speech, but often your labels are themselves triphones and you end up with a pretty large vocabulary too. Figuring out how to get RNNs closer to on par with DNN-HMMs with Viterbi decoding (or full on sequence training [3]) through something like "deep fusion" with a language model (or something else) is something I am very interested in. [0] http://arxiv.org/abs/1312.6082 http://arxiv.org/abs/1312.6082 [1] http://arxiv.org/abs/1511.06456 http://arxiv.org/abs/1511.06456 [2] https://arxiv.org/abs/1511.04868 https://arxiv.org/abs/1511.04868 [3] http://www.danielpovey.com/files/2013_interspeech_dnn.pdf http://www.danielpovey.com/files/2013_interspeech_dnn.pdf
kastnerkyle 10y ago
Hybrid DNN-HMM type systems (or CNN-HMM) still roundly beat purely RNN based systems on public benchmarks (~5% across tasks such as Switchboard, WSJ, even a bit behind on TIMIT) and most of the best internal systems at the companies I know (barring Baidu) are still using this DNN-HMM scheme, though RNN+CTC or CNN+CTC is not far behind performance wise these days. RNN or CNN+CTC is tantalizing because it is conceptually simple, should "scale with data", and you can build a toy version in a few hundred lines of code! Which is a far cry from the massive complexity of most speech systems in use today. I think we are still a ways off from replacing all HMMs with RNNs, but with tighter integration of the language model into the speech system and training the whole shebang end-to-end there will be some interesting results. There are a few ares of machine translation where people have tried this "deep fusion" with promising improvements.
the_decider 10y ago
An RNN can be trained to a) Simulate the random output behavior of the sequence b) Predict the categorial hidden states at any given sequence location from supervised training data. A HMM is able to carry out both a and b. It also has the capacity to do: c) Predict the categorical hidden states any sequence location with reliance on supervised training data. Effectively, an HMM can identify/reveal hidden categorical states directly from unsupervised learning. To my knowledge, unsupervised labeling of hidden states is not a trivial task for RNNs.
- howlin 10y ago
  HMMs are a good model if you know what the categorical states are before you start modeling. If you let the HMM learn the hidden states (e.g. with expectation maximization), there is no good reason to believe they will have obvious semantic value to you. For RNNs, you can get very similar info. If you do have meaningful hidden state, you can treat a few labeled examples as training data for a supervised learning procedure. The RNN winds up predicting the state variable along with the future of the sequence. If you want something exploratory, you can use the RNN's hidden state activation over the course of a sequence as a general real valued vector that is amenable to cluster analysis. If the RNN state vectors segment well, it's likely these segmentations will have at least as much meaning as learned HMM states.

by platz 10y ago

supercarrot 10y ago

Interesting observation of computational complexity. HMMs require Viterbi algorithm to find the desirable sequence. The complexity of the algorithm depends on the number of previous decisions on which we condition the current one. Time complexity is O(n^(k+1) * S) where n is the length of the sequence, k is the number of previous decisions we condition on, and S is the number of possible decisions. Now, why does HMM require the Viterbi search procedure, and LSTM/RNN doesn't? Inference in LSTM is linear in the length of the sequence -- ignoring the classifier decision time. Why does this work without Viterbi? Given the fact that even Conditional Random Fields need dynamic programming, and that Maximum Entropy Markov Model suffers the inability to learn quickly without dynamic programming and make inference not suffer label bias. What is so special about LSTM that it doesn't need DP. RNN obviously learns a much better representation of features. Still, why then won't HMMs work with that same representation without the search part? Really baffles me. Although, there exists a process that doesn't use NN for sequence labeling and it is linear in the length of sequence and works well. Instead of using a simple classifier as is the case in MEMMs, one can use a cost-sensitive classifier and learn for each decision associated future loss and greedily avoid the loss. This allows the usage of a simple multiclass classifier, removes the search part and can work as well as NN given the right features.

kastnerkyle 10y ago
RNN for discrete structured prediction tasks often use a technique called beam search during decoding (see for example papers on neural MT), which is about as close as you can get to a true Viterbi when you don't have independence assumptions. The CTC mentioned above is also a special type of "reductionist" dynamic programming which uses some awesome and clever stuff to remain backproppable. It only works for monotonic alignments (input larger than desired output).
- supercarrot 10y ago
  Still, beam search can be simulated and improved by running decision processes in parallel. For example, instead of learning the sequence labeling as a sequence of n decisions (where n is the length of the sequence) you can learn sequence labeling as a sequence of 3n+1 decisions where you make 3 decisions for each sequence element and after 3n decision pick one out of three decision streams that minimizes loss using an extra decision. (when inference is done then the classifier will, hopefully, pick the stream that minimizes test loss). This simulates a beam search and can be done during learning and inference and is probably more effective than picking confidence scores of particular decisions and keeping a beam of most confident partial sequences. Bean search is a heuristic thing that improves performance and is done mostly to allow you to correct mistakes you made at the beginning of the process. http://arxiv.org/abs/1603.06042 http://arxiv.org/abs/1603.06042 they illustrate the problem well (label bias). the question remains the same, for example, in the paper above they approximate the partition function of CRFs with a beam but get superior results to other structured prediction methods.
  - kastnerkyle 10y ago
    Sure, there are a lot of potential things to do - either by enumerating towards the full "brute force" loss partway as I think you are hinting toward, or treating as a subsequences, or something else [0, 1, 2]. The point is, IMO RNNs do need some kind of structured loss (more than per step likelihood) to be competitive with HMM approaches using Viterbi decoding, in addition to some sequence smarts (such as beam search) in decoding. At least in NMT, enumerating the possible decisions as 3n + 1 is almost impossible since the softmax size is generally the memory bottleneck in training - and a bigger vocabulary is typically a huge win. It is more feasible in speech, but often your labels are themselves triphones and you end up with a pretty large vocabulary too. Figuring out how to get RNNs closer to on par with DNN-HMMs with Viterbi decoding (or full on sequence training [3]) through something like "deep fusion" with a language model (or something else) is something I am very interested in. [0] http://arxiv.org/abs/1312.6082 http://arxiv.org/abs/1312.6082 [1] http://arxiv.org/abs/1511.06456 http://arxiv.org/abs/1511.06456 [2] https://arxiv.org/abs/1511.04868 https://arxiv.org/abs/1511.04868 [3] http://www.danielpovey.com/files/2013_interspeech_dnn.pdf http://www.danielpovey.com/files/2013_interspeech_dnn.pdf

kastnerkyle 10y ago

Hybrid DNN-HMM type systems (or CNN-HMM) still roundly beat purely RNN based systems on public benchmarks (~5% across tasks such as Switchboard, WSJ, even a bit behind on TIMIT) and most of the best internal systems at the companies I know (barring Baidu) are still using this DNN-HMM scheme, though RNN+CTC or CNN+CTC is not far behind performance wise these days. RNN or CNN+CTC is tantalizing because it is conceptually simple, should "scale with data", and you can build a toy version in a few hundred lines of code! Which is a far cry from the massive complexity of most speech systems in use today. I think we are still a ways off from replacing all HMMs with RNNs, but with tighter integration of the language model into the speech system and training the whole shebang end-to-end there will be some interesting results. There are a few ares of machine translation where people have tried this "deep fusion" with promising improvements.

the_decider 10y ago

An RNN can be trained to a) Simulate the random output behavior of the sequence b) Predict the categorial hidden states at any given sequence location from supervised training data. A HMM is able to carry out both a and b. It also has the capacity to do: c) Predict the categorical hidden states any sequence location with reliance on supervised training data. Effectively, an HMM can identify/reveal hidden categorical states directly from unsupervised learning. To my knowledge, unsupervised labeling of hidden states is not a trivial task for RNNs.

howlin 10y ago
HMMs are a good model if you know what the categorical states are before you start modeling. If you let the HMM learn the hidden states (e.g. with expectation maximization), there is no good reason to believe they will have obvious semantic value to you. For RNNs, you can get very similar info. If you do have meaningful hidden state, you can treat a few labeled examples as training data for a supervised learning procedure. The RNN winds up predicting the state variable along with the future of the sequence. If you want something exploratory, you can use the RNN's hidden state activation over the course of a sequence as a general real valued vector that is amenable to cluster analysis. If the RNN state vectors segment well, it's likely these segmentations will have at least as much meaning as learned HMM states.