Introduction

A Hidden Markov Model (HMM) is a probability model for POS tagging. It finds the most likely sequence of tags for a sentence. It scores the tags of all the words together, so each tag also depends on the tag before it.

HMM sees a sentence as 2 layers:

LayerWhat it isIn "Will can spot Mary"
Hidden statesThe POS tags. We cannot see them in the textNoun, Modal, Verb, Noun
ObservationsThe words, because we can physically see themWill, can, spot, Mary

The job of HMM is to use the words that we can see to guess the tags that we cannot see.

Transition and Emission Probabilities

These are the 2 probabilities that HMM uses:

ProbabilityQuestion it answersExample
TransitionHow likely is one tag to come after another tag?
EmissionHow likely is a tag to produce this word?

"Emit" means "produce". asks: if the hidden tag is a Verb, how likely is the word to be "spot"? A high value makes Verb a good tag for "spot".

Both come from counts in the tagged training data:

Each word adds 1 transition and 1 emission to the score:

The score of a full tag path is all the step scores multiplied together, plus the last transition into the end tag <e>.

Remembering tip

  • Transition goes Tag to Tag
  • Emission goes tag to word, because a tag Emits a word

Example

We build a small HMM tagger with 3 tags: Noun, Modal and Verb. A modal is a helper verb such as "can" or "will". The tables below write it as "Model".

These are the 4 training sentences:

  1. Mary Jane can see Will
  2. Spot will see Mary
  3. Will Jane spot Mary
  4. Mary will pat Spot

We want to tag the new sentence Will can spot Mary. The correct tags are Noun, Modal, Verb, Noun.

Step 1: Count each word under each tag

Step 2: Calculate the emission probabilities

Divide each count by the total count of its tag (the column total). For example, Modal appears 4 times and "Will" is a Modal 3 times, so .

Step 3: Add the start and end tags

To calculate transitions, add <s> at the start and <e> at the end of each sentence. Now the first tag and the last tag also have a tag next to them.

Step 4: Calculate the transition probabilities

Count how often each tag is followed by each other tag. For example, <s> is followed by a Noun in 3 of the 4 sentences, so .

Each row is the previous tag and each column is the next tag, so each row adds up to 1.

Step 5: Score one tag path

Follow one tag path from <s> to <e> and multiply every transition and emission on it. A higher score means a more likely tag path.

Problem: too many paths

To find the best path, we would have to score every possible path. With 3 tags and 4 words there are paths. The number of paths is for words, so it grows very fast. The Viterbi Algorithm solves this problem.

The best tag sequence that HMM finds is the output of Part-of-Speech (POS) Tagging.