5 ms·

Intro to Hidden Markov Models (2010) [pdf]

181 points by kercker 10y ago

graycat 10y ago
> A Markov chain is a sequence of random variables X1, X2, X3, . . . , Xt , . . . , such that the probability distribution of Xt+1 depends only on t and xt (Markov property), in other words: No. In a Markov process, the future does depend on the past, even all of the past. But what is special is that the past and the future are conditionally independent given the present. If we are not given the present, then all of the past can be relevant in predicting the future.
- btaitelb 10y ago
  Markov chains are much simpler than Markov models. The lecture starts off with the simpler idea to motivate the more complex one that you're describing.
  - graycat 10y ago
    Sorry. The statement I quoted is just flatly wrong. Okay?
    - evanpw 10y ago
      It's more reasonable to parse "depends only on" as expressing conditional independence than unconditional, and that parsing has the added bonus of making the original statement correct.
      - graycat 10y ago
        No. Again, once again, over again, one more time, in a Markov process, including a discrete time Markov chain, even one with a finite state space, the past can, and in practice usually does, provide a lot of powerful information to predict the future. The future really can depend on the past. Typically the past and the future are not independent -- not even close. But, the Markov assumption (property) says that GIVEN (excuse my emphasis -- it is just crucial here) the present, the past does not contribute more information for predicting the future. That is the past and the future may not be independent at all, but the past and the future are conditionally independent given the present. To discuss the Markov property, desperately need the concept of conditional independence -- there is no substitute, no easier terminology or description. Alas, conditional independence is not so easy to discuss, even in the simplest cases. And in the grown up cases, need the Radon-Nikodym theorem of measure theory and the associated machinery of conditional expectation. Tellingly, the part I quoted never mentioned conditional independence or even conditioning. Sorry, again, the quote was wrong. I tried to correct the quote and, thus, keep readers trying to learn from being misled. My sympathies are with the readers trying to learn. Early in my career, I read lots of such elementary, easy to understand introductions to lots of topics in applied math. The biggie problem was, as here, the content was from not very good down to actually wrong. Later I got a first class, rock solid foundation in grad school. In particular my background in Markov processes was from a star student of E. Cinlar, a world class expert long at Princeton. And my Ph.D. dissertation was in stochastic optimal control where the Markov assumption is just crucial -- indeed, stochastic optimal control is also commonly called Markov decision processes. In addition I've applied Markov processes in some serious work in US national security. What I'm saying here is on the center of the target. What I quoted no one should try to learn from -- it's wrong.
      - mturmon 10y ago
        This is quite correct.
- mturmon 10y ago
  Out of a pretty big slide deck, explicitly intended for a beginner audience, this is a weird thing to pick on. The following is "Proposition 1.1" from the relevant section of a standard text (Bhattacharya and Waymire): "A stochastic process X0, X1, X2, ... has the Markov property if and only if for each n the conditional distribution of Xn+1 given X0...Xn is a function only of Xn." The only difference between the above Prop. 1.1 and the statement in TFA is that TFA omits to specify it means a conditional distribution of Xt+1 given X1...Xt (as opposed to an unconditional distribution). But, in literally the following line, TFA goes on to clarify what it means by stating the equation that the words correspond to, and the equation has the correct conditional distribution. I don't see reason for alarm here.
melling 10y ago
Markov Chains Explained Visually http://setosa.io/ev/markov-chains/ http://setosa.io/ev/markov-chains/
- GnarlyWhale 10y ago
  The interactive nature of those visualisations do a great job of increasing ones' grasp of the concept.
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.
platz 10y ago
link to MIT course: http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-410-principles-of-autonomy-and-decision-making-fall-2010/ http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-4...
gallamine 10y ago
Are there an open tools for solving HMMs for large datasets? i.e. if I have millions of observations from millions of users and want to learn a HMM from the data, what are my options?
- fizzbitch 10y ago
  mlpack (http://www.mlpack.org/ http://www.mlpack.org/) has a nice implementation of HMMs. The library provides a few command-line programs you can use to work with HMMs: http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_generate.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_generate.... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_train.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_train.htm... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_loglik.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_loglik.ht... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_viterbi.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_viterbi.h... There is also the HTK toolkit, but last I used that, years ago, I was pretty disappointed; it did not compile on a 64-bit system. Both of these are single-machine toolkits, so there is a limit to how much you can scale, but I think you may be able to deal with a million or so points with mlpack. There's also MATLAB's implementation, but that is not very fast.
mjt0229 10y ago
A coworker of mine used to ask job candidates (usually folks with PhDs) with HMMs on their CV "what's hidden in a hidden markov model". Lots of people couldn't answer that question.

181 points by kercker 10y ago

> A Markov chain is a sequence of random variables X1, X2, X3, . . . , Xt , . . . , such that the probability distribution of Xt+1 depends only on t and xt (Markov property), in other words: No. In a Markov process, the future does depend on the past, even all of the past. But what is special is that the past and the future are conditionally independent given the present. If we are not given the present, then all of the past can be relevant in predicting the future.

btaitelb 10y ago
Markov chains are much simpler than Markov models. The lecture starts off with the simpler idea to motivate the more complex one that you're describing.
- graycat 10y ago
  Sorry. The statement I quoted is just flatly wrong. Okay?
  - evanpw 10y ago
    It's more reasonable to parse "depends only on" as expressing conditional independence than unconditional, and that parsing has the added bonus of making the original statement correct.
    - graycat 10y ago
      No. Again, once again, over again, one more time, in a Markov process, including a discrete time Markov chain, even one with a finite state space, the past can, and in practice usually does, provide a lot of powerful information to predict the future. The future really can depend on the past. Typically the past and the future are not independent -- not even close. But, the Markov assumption (property) says that GIVEN (excuse my emphasis -- it is just crucial here) the present, the past does not contribute more information for predicting the future. That is the past and the future may not be independent at all, but the past and the future are conditionally independent given the present. To discuss the Markov property, desperately need the concept of conditional independence -- there is no substitute, no easier terminology or description. Alas, conditional independence is not so easy to discuss, even in the simplest cases. And in the grown up cases, need the Radon-Nikodym theorem of measure theory and the associated machinery of conditional expectation. Tellingly, the part I quoted never mentioned conditional independence or even conditioning. Sorry, again, the quote was wrong. I tried to correct the quote and, thus, keep readers trying to learn from being misled. My sympathies are with the readers trying to learn. Early in my career, I read lots of such elementary, easy to understand introductions to lots of topics in applied math. The biggie problem was, as here, the content was from not very good down to actually wrong. Later I got a first class, rock solid foundation in grad school. In particular my background in Markov processes was from a star student of E. Cinlar, a world class expert long at Princeton. And my Ph.D. dissertation was in stochastic optimal control where the Markov assumption is just crucial -- indeed, stochastic optimal control is also commonly called Markov decision processes. In addition I've applied Markov processes in some serious work in US national security. What I'm saying here is on the center of the target. What I quoted no one should try to learn from -- it's wrong.
    - mturmon 10y ago
      This is quite correct.
mturmon 10y ago
Out of a pretty big slide deck, explicitly intended for a beginner audience, this is a weird thing to pick on. The following is "Proposition 1.1" from the relevant section of a standard text (Bhattacharya and Waymire): "A stochastic process X0, X1, X2, ... has the Markov property if and only if for each n the conditional distribution of Xn+1 given X0...Xn is a function only of Xn." The only difference between the above Prop. 1.1 and the statement in TFA is that TFA omits to specify it means a conditional distribution of Xt+1 given X1...Xt (as opposed to an unconditional distribution). But, in literally the following line, TFA goes on to clarify what it means by stating the equation that the words correspond to, and the equation has the correct conditional distribution. I don't see reason for alarm here.

melling 10y ago

Markov Chains Explained Visually http://setosa.io/ev/markov-chains/ http://setosa.io/ev/markov-chains/

GnarlyWhale 10y ago
The interactive nature of those visualisations do a great job of increasing ones' grasp of the concept.

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.

platz 10y ago

link to MIT course: http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-410-principles-of-autonomy-and-decision-making-fall-2010/ http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-4...

gallamine 10y ago

Are there an open tools for solving HMMs for large datasets? i.e. if I have millions of observations from millions of users and want to learn a HMM from the data, what are my options?

fizzbitch 10y ago
mlpack (http://www.mlpack.org/ http://www.mlpack.org/) has a nice implementation of HMMs. The library provides a few command-line programs you can use to work with HMMs: http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_generate.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_generate.... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_train.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_train.htm... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_loglik.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_loglik.ht... http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_viterbi.html http://mlpack.org/docs/mlpack-2.0.1/man/mlpack_hmm_viterbi.h... There is also the HTK toolkit, but last I used that, years ago, I was pretty disappointed; it did not compile on a 64-bit system. Both of these are single-machine toolkits, so there is a limit to how much you can scale, but I think you may be able to deal with a million or so points with mlpack. There's also MATLAB's implementation, but that is not very fast.

mjt0229 10y ago

A coworker of mine used to ask job candidates (usually folks with PhDs) with HMMs on their CV "what's hidden in a hidden markov model". Lots of people couldn't answer that question.