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

Solution 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

Solution 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.

Solution 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.

Classification of different Markov Models