Each word has several possible tags, with different probabilities.

• in principle, if we had perfect knowledge of English
• as seen in our training set

For example, "can" appears using in several roles:

• Monica can swim. (modal verb)
• A can of beans. (noun)
• I will can the beans. (verb)

Some other words with multiple uses

• cover: noun, verb, adjective (cover crop)
• over: preposition, noun (e.g. cricket)
• pot: noun, verb

Consider the sentence "Heat oil in a large pot." The correct tag sequence is "verb noun prep det adj noun". Here's the tags seen when training on the Brown corpus.

(from Mitch Marcus)

Notice that

• An individual word may have more than one plausible tag
• The most commonly seen tag may not be correct choice for analyzing any particular input.
• A word may have possible tags that weren't seen in our training input.

An example of that last would be "over" used as a noun (e.g. in cricket). That is fairly common in British text but might never occur in a training corpus from the US.

Baseline algorithm

Most testing starts with a "baseline" algorithm, i.e. a simple method that does do the job, but typically not very well. In this case, our baseline algorithm might pick the most common tag for each word, ignoring context. In the table above, the most common tag for each word is shown in bold: it made one error out of six words.

The test/development data will typically contain some words that weren't seen in the training data. The baseline algorithm guesses that these are nouns, since that's the most common tag for infrequent words. An algorithm can figure this out by examining new words that appear in the development set, or by examining the set of words that occur only once in the training data ("hapax") words.

On larger tests, this baseline algorithm has an accuracy around 91%. It's essential for a proposed new algorithm to beat the baseline. In this case, that's not so easy because the baseline performance is unusually high.

Formulating the estimation problem

Suppose that W is our input word sequence (e.g. a sentence) and T is an input tag sequence. That is

\(W = w_1, w_2, \ldots w_n \)
\(T = t_1, t_2, \ldots t_n \)

Our goal is to find a tag sequence T that maximizes P(T | W). Using Bayes rule, this is equivalent to maximizing \( P(W \mid T) * P(T)/P(W) \) And this is equivalent to maximizing \( P(W \mid T) * P(T) \) because P(W) doesn't depend on T.

So we need to estimate P(W | T) and P(T) for one fixed word sequence W but for all choices for the tag sequenceT.

What can we realistically estimate?

Obviously we can't directly measure the probability of an entire sentence given a similarly long tag sequence. Using (say) the Brown corpus, we can get reasonable estimates for

• individual word frequencies
• tag usage for each word
• tag bigrams

If we have enough tagged data, we can also estimate tag trigrams. Tagged data is hard to get in quantity, because human intervention is needed for checking and correction.

Markov assumptions

To simplify the problem, we make "Markov assumptions." A Markov assumption is that the value of interest depends only on a short window of context. For example, we might assume that the probability of the next word depends only on the two previous words. You'll often see "Markov assumption" defined to allow only a single item of context. However, short finite contexts can easily be simulated using one-item contexts.

For POS tagging, we make two Markov assumptions. For each position k:

\(P(w_k)\) depends only on \(P(t_k)\)
\(P(t_k) \) depends only on \(P(t_{k-1}) \)

Like Bayes nets, HMMs are a type of graphical model and so we can use similar pictures to visualize the statistical dependencies:

In this case, we have a sequence of tags at the top. Each tag depends only on the previous tag. Each word (bottom row) depends only on the corresonding tag.

The equations

Therefore

\( P(W \mid T) = \prod_{i=1}^n P(w_i \mid t_i)\)
\( P(T) = P(t_1 | START) * \prod_{i=1}^n P(t_k \mid t_{k-1}) \)

where \( P(t_1 | START) \) is the probability of tag \(t_1\) at the start of a sentence.

Folding this all together, we're finding the T that maximizes

\( P (T \mid W)\)
\(\propto P(W \mid T) * P(T) \)
\( = \prod_{i=1}^n P(w_i \mid t_i)\ \ * \ \ P(t_1 \mid \text{START})\ \ *\ \ \prod_{k=2}^n P(t_k \mid t_{k-1}) \)

Let's label our probabilities as \(P_S\), \(P_E\), and \(P_T\) to make their roles more explicit. Using this notation, we're trying to maximize

\( \prod_{i=1}^n P_E(w_i \mid t_i)\ \ * \ \ P_S(t_1)\ \ *\ \ \prod_{k=2}^n P_T(t_k \mid t_{k-1}) \)

So we need to estimate three types of parameters:

• \( P_S(t_1) \) initial probabilities
• \( P_T(t_k | t_{k-1}) \) transition probabilities
• \( P_E(w_i | t_i) \) emission probabilities

Toy model

For simplicity, let's assume that we have only three tags: Noun, Verb, and Determiner (Det). Our input will contain sentences that use only those types of words, e.g.

    Det Noun     Verb    Det Noun   Noun
    The student  ate     the ramen  noodles

    Det Noun   Noun  Verb    Det Noun
    The maniac rider crashed his bike.

We can look up our initial probabilities, i.e. the probability of various values for \(P_S(t_1)\) in a table like this.

tag	\(P_S(tag)\)
Verb	0.01
Noun	0.18
Det	0.81

We can estimate these by counting how often each tag occurs at the start of a sentence in our training data.

Transition probabilities

In the (correct) tag sequence for this sentence, the tags \(t_1\) and \(t_5\) have the same value Det. So the possibilities for the following tags (\(t_2\) and \(t_6\)) should be similar. In POS tagging, we assume that \(P_T(t_{k+1} \mid t_k)\) depends only on the identities of \(t_{k+1}\) and \( t_k\), not on their time position k. (This is a common assumption for Markov models.)

This is not an entirely safe assumption. Noun phrases early in a sentence are systematically different from those toward the end. The early ones are more likely to be pronouns or short noun phrases (e.g. "the bike"). The later ones more likely to contain nouns that are new to the conversation and, thus, tend to be more elaborate (e.g. "John's fancy new racing bike"). However, abstracting away from time position is a very useful simplifying assumption which allows us to estimate parameters with realistic amounts of training data.

So, suppose we need to find a transition probability \( P_T(t_k | t_{k-1}) \) for two tags \(t_{k-1} \) and \(t_k \) in our tag sequence. We consider only the identities of the two tags, e.g. \(t_{k-1} \) might be DET and \(t_k \) might be NOUN. And we look up the pair of tags in a table like this

	Next Tag
Previous tag	Verb	Noun	Det
Verb	0.02	0.21	0.77
Noun	0.51	0.44	0.05
Det	\(\approx 0 \)	0.99	0.01

We can estimate these by counting how often a 2-tag sequence (e.g. Det Noun) occurs and dividing by how often the first tag (e.g. Det) occurs.

Notice the near-zero probability of a transition from Det to Verb. If this is actually zero in our training data, do we want to use smoothing to fill in a non-zero number? Yes, because even "impossible" transitions may occur in real data due to typos or (with larger tagsets) very rare tags. Laplace smoothing should work well.

Finite-state automaton

We can view the transitions between tags as a finite-state automaton (FSA). The numbers on each arc is the probability of that transition happening.

These are conceptually the same as the FSA's found in CS theory courses. But beware of small differences in conventions.

• You can start in any state (probability given by the initial probability table).
• A transition always exists between every pair of states, but each transition has an associated probability of happening.
• Output (words) is generated when you enter a state, not on the transition between states.

Emission probabilities

Our final set of parameters are the emission probabilities, i.e. \(P_E(w_k | t_k)\) for each position k in our tag sequence. Suppose we have a very small vocabulary of nouns and verbs to go with our toy model. Then we might have probabilities like

   Verb   played 0.01
          ate   0.05
          wrote 0.05
          saw   0.03
          said  0.03
          tree  0.001
      
   Noun  boy   0.01
         girl  0.01
         cat   0.02
         ball  0.01
         tree  0.01
         saw   0.01

   Det  a    0.4
        the  0.4
        some 0.02
        many 0.02

Because real vocabularies are very large, it's common to see new words in test data. So it's essential to smooth, i.e. reserve some of each tag's probability for

• new words
• familiar words seen with a new tag

New tags for a familiar word are quite common in English, because most nouns can be used as verbs, and vice versa.

However, the details may need to depend on the type of tag. Tags divide (approximately) into two types

• open class, aka content words (e.g. verbs, nouns, adjectives)
• closed class, aka function words (e.g. prepositions, determiners)