What is the difference between markov chains and hidden markov model?

Question

What is the difference between markov chain models and hidden markov model? I've read in Wikipedia, but couldn't understand the differences.

Answer 1

To explain by example, I'll use an example from natural language processing. Imagine you want to know the probability of this sentence:

I enjoy coffee

In a Markov model, you could estimate its probability by calculating:

P(WORD = I) x P(WORD = enjoy | PREVIOUS_WORD = I) x P(word = coffee| PREVIOUS_WORD = enjoy)

Now, imagine we wanted to know the parts-of-speech tags of this sentence, that is, if a word is a past tense verb, a noun, etc.

We did not observe any parts-of-speech tags in that sentence, but we assume they are there. Thus, we calculate what's the probability of the parts-of-speech tag sequence. In our case, the actual sequence is:

PRP-VBP-NN

(where PRP=“Personal Pronoun”, VBP=“Verb, non-3rd person singular present”, NN=“Noun, singular or mass”. See https://cs.nyu.edu/grishman/jet/guide/PennPOS.html for complete notation of Penn POS tagging)

But wait! This is a sequence that we can apply a Markov model to. But we call it hidden, since the parts-of-speech sequence is never directly observed. Of course in practice, we will calculate many such sequences and we'd like to find the hidden sequence that best explains our observation (e.g. we are more likely to see words such as 'the', 'this', generated from the determiner (DET) tag)

The best explanation I have ever encountered is in a paper from 1989 by Lawrence R. Rabiner: http://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf

Answer 2

Markov model is a state machine with the state changes being probabilities. In a hidden Markov model, you don't know the probabilities, but you know the outcomes.

For example, when you flip a coin, you can get the probabilities, but, if you couldn't see the flips and someone moves one of five fingers with each coin flip, you could take the finger movements and use a hidden Markov model to get the best guess of coin flips.

Answer 3

As I understand it, the question is: what is the difference between a Markov Process and a Hidden Markov Process?

A Markov Process (MP) is a stochastic Process with:

1. Finite number of states
2. Probabilistic transitions between these states
3. Next state determined only by the current state (Markov property)

A Hidden Markov Process (HMM) is also a stochastic Process with:

1. Finite number of states
2. Probabilistic transitions between these states
3. Next state determined only by the current state (Markov property) AND
4. We’re unsure which state we’re in: The current state emits an observation.

Example - (HMM) Stock Market:
In the Stock Market, people trade with the value of the firm. Let's assume that the real value of the share is $100 (this is unobservable, and in fact you never know it). What you really see is then the value it is traded with: let's assume in this case $90 (this is observable).

For people interested in Markov: The interesting part is when you start taking actions on these models (in the previous example, to gain money). This goes to Markov Decision Processes (MDP) and Partially Observable Markov Decision Processes (POMDPs). To assess a general classification of these models, I have summarized in the following picture the main characteristics of each Markov Model.

Answer 4

Since Matt used parts-of-speech tags as an HMM example, I could add one more example: Speech Recognition. Almost all large vocabulary continuous speech recognition (LVCSR) systems are based on HMMs.

"Matt's example": I enjoy coffee

In a Markov model, you could estimate its probability by calculating:

P(WORD = I) x P(WORD = enjoy | PREVIOUS_WORD = I) x P(word = coffee| PREVIOUS_WORD = enjoy)

In a Hidden Markov Model,

Let's say 30 different people read the sentence "I enjoy hugging" and we have to recognize it. Every person will pronounce this sentence differently. So we do NOT know whether or not the person meant "hugging" or "hogging". We will only have the probabilistic distribution of the actual word.

In short, a hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states.

Answer 5

A hidden Markov models is a double embedded stochastic process with two levels.

The upper level is a Markov process and the states are unobservable.

In fact, observation is a probabilistic function of the upper level Markov states.

Different Markov states will have different observation probabilistic functions.