View source for Part-of-speech tagging

==Parameter estimation==

===Maximum likelihood===

The easiest way to estimate the parameters<ref>By parameters, we mean the transmission, emission and initial probabilities</ref> of a hidden Markov model is to use maximum likelihood (ML). This method requires a pre-tagged corpus. We're going to make a very small training corpus so that we can train a model which can be used to disambiguate the example sentence above. The corpus is much smaller than would be normally used, but will let us demonstrate step-by-step how the model is constructed and used.

<div style="float: center;">
{|class="wikitable"
! Untagged             !! Analysed !! Tagged
|-
| Vino a la playa      || Vino{{fadetag|<noun>/<verb>}} a{{fadetag|<pr>}} la{{fadetag|<det>/<prn>}} playa{{fadetag|<noun>}} .{{fadetag|<sent>}}      || Vino{{fadetag|<verb>}} a{{fadetag|<pr>}} la{{fadetag|<det>}} playa{{fadetag|<noun>}} .{{fadetag|<sent>}}
|-
| Voy a la casa        || Voy{{fadetag|<verb>}} a{{fadetag|<pr>}} la{{fadetag|<det>/<prn>}} casa{{fadetag|<noun>/<verb>}} .{{fadetag|<sent>}}               || Voy{{fadetag|<verb>}} a{{fadetag|<pr>}} la{{fadetag|<det>}} casa{{fadetag|<noun>}} .{{fadetag|<sent>}}
|- 
| Bebe vino en casa    || Bebe{{fadetag|<verb>}} vino{{fadetag|<noun>/<verb>}} en{{fadetag|<pr>}} casa{{fadetag|<noun>/<verb>}} .{{fadetag|<sent>}}|| Bebe{{fadetag|<verb>}} vino{{fadetag|<noun>}} en{{fadetag|<pr>}} casa{{fadetag|<noun>}} .{{fadetag|<sent>}}
|-
| La casa es grande    || La{{fadetag|<det>/<prn>}} casa{{fadetag|<noun>/<verb>}} es{{fadetag|<verb>}} grande{{fadetag|<adj>}} .{{fadetag|<sent>}}   || La{{fadetag|<det>}} casa{{fadetag|<noun>}} es{{fadetag|<verb>}} grande{{fadetag|<adj>}} .{{fadetag|<sent>}}
|-
| Es una ciudad grande || Es{{fadetag|<verb>}} una{{fadetag|<det>/<prn>/<verb>}} ciudad{{fadetag|<noun>}} grande{{fadetag|<adj>}} .{{fadetag|<sent>}}|| Es{{fadetag|<verb>}} una{{fadetag|<det>}} ciudad{{fadetag|<noun>}} grande{{fadetag|<adj>}} .{{fadetag|<sent>}}
|}
</div>
In this corpus, the "untagged" text would come from anywhere, the "analysed" text would be the result after being passed through a [[morphological analyser]], and the "tagged" text would be manually disambiguated from the analysed text by one or more humans.
<div style="float:right; padding: 2px; font-size: 85%">
{|class=wikitable
!colspan=8|Matrix of transition counts
|-
! !!colspan=7|Second tag
|-
! First tag                !! verb !! noun !! det !! prn !! pr !! adj !! sent
|-
| '''verb'''               ||  0   ||  1   ||  1  ||  0  || 2  ||  1  ||  0
|-
| '''noun'''               ||  1   ||  0   ||  0  ||  0  || 1  ||  1  ||  3 
|-
| '''det'''                ||  0   ||  4   ||  0  ||  0  || 0  ||  0  ||  0 
|-
| '''prn'''                ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  0
|-
| '''pr'''                 ||  0   ||  1   ||  2  ||  0  || 0  ||  0  ||  0
|-
| '''adj'''                ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  2
|-
| '''sent'''               ||  3   ||  0   ||  1  ||  0  || 0  ||  0  ||  0
|-
|}
</div>
; Calculating the transition probabilities

The transition probabilities are basically the set of probabilities that a certain tag follows a certain other tag. We're training a bigram model, so we need to make a two-dimensional matrix. The axes of this matrix are the tag set. The first thing we do is sum up the transition counts. For example, if we see a determiner, then a noun four times in the course of the tagged corpus, then we put a four in the element (<code>det</code>, <code>noun</code>).

It should be possible to see from the counts in the table on the right that already this models some information about the corpus we have. We can see that determiners are followed by nouns and that verbs very often start a sentence. If the corpus were larger, there would be fewer zeroes. These counts are quite easy to calculate. 

The next thing to do is calculate the matrix of '''transition probabilities''', <math>A</math>. This is usually written as 

:<math>a_{ij} = p(\gamma_j | \gamma_i)~</math>

and means the element at <math>a_{ij}</math> is the probability of <math>\gamma_j</math> appearing given the previous tag <math>\gamma_i</math>. We can give the example for determiner followed by noun as:

:<math>a[det][noun] = \frac{N(det, noun)}{N(det, \{verb,det,prn,pr,adj,sent,noun\})} = \frac{4}{4} = 1</math>
<div style="float:right; padding: 2px; font-size: 85%">
{|class=wikitable
!colspan=8|Matrix of transition probabilities (<math>A</math>)
|-
! !!colspan=7|Second tag (<math>\gamma_j</math>)
|-
! First tag (<math>\gamma_i</math>)               !! verb !! noun !! det !! prn !! pr !! adj !! sent
|-
| '''verb'''               ||  0     ||  0.2   ||  0.2  ||  0  || 0.4   ||  0.2     ||  0
|-
| '''noun'''               ||  0.16  ||  0      ||  0     ||  0  || 0.16  ||  0.16  ||  0.5 
|-
| '''det'''                ||  0   ||  1   ||  0  ||  0  || 0  ||  0  ||  0 
|-
| '''prn'''                ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  0
|-
| '''pr'''                 ||  0   ||  0.3   ||  0.6  ||  0  || 0  ||  0  ||  0
|-
| '''adj'''                ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  1
|-
|style="background-color: #bbbbff"| '''sent'''<ref>This row represents the initial probabilities, <math>~\pi</math> of the model.</ref>               ||style="background-color: #bbbbff"|  0.75   ||style="background-color: #bbbbff"|  0   ||style="background-color: #bbbbff"|  0.25  ||style="background-color: #bbbbff"|  0  ||style="background-color: #bbbbff"| 0  ||style="background-color: #bbbbff"|  0  ||style="background-color: #bbbbff"|  0
|-
|}
</div>
Or for a more ambiguous example:

:<math>a[pr][noun] = \frac{N(pr, noun)}{N(pr, \{verb,det,prn,pr,adj,sent,noun\})} = \frac{1}{3} \approx 0.33</math>

Where <math>N(x)</math> stands for the number of time that <math>x</math> is seen in the training set.

;Calculating the emission probabilities

We follow a similar process for calculating the emission probabilities of the model, only this time, we're counting the number of times that an ambiguity class is seen in the untagged corpus given a tag in the tagged corpus over the number of times all the other ambiguity classes have been seen. This is expressed as:

:<math>b_i(\sigma_k) = p(\sigma_k|\gamma_i)~</math>

Here, <math>\sigma_k</math> is the given ambiguity class, and <math>p(\sigma_k|\gamma_i)</math> is the probability of seeing the the ambiguity class <math>\sigma_k</math> given the tag <math>\gamma_i</math>. So, to continue the example, in the above tagged corpus we see the tag "verb" five times, and the ambiguity class "verb|noun" once.
<div style="float:right; padding: 2px; font-size: 85%">
{|class=wikitable
!colspan=8|Matrix of emission probabilities (<math>B</math>)
|-
! !!colspan=7|Second tag (<math>\gamma_j</math>)
|-
! First tag (<math>\sigma_k</math>)  !! verb !! noun !! det !! prn !! pr !! adj !! sent
|-
| '''det/prn/verb'''                 ||  0     ||  0   ||  0.25  ||  0  || 0   ||  0     ||  0
|-
| '''det/prn'''                      ||  0     ||  0   ||  0.75  ||  0  || 0   ||  0     ||  0
|-
| '''noun/verb'''                    ||  0.2     ||  0.67   ||  0  ||  0  || 0   ||  0     ||  0
|-
| '''verb'''                         ||  1     ||  0   ||  0  ||  0  || 0   ||  0     ||  0
|-
| '''noun'''                         ||  0   || 1      ||  0     ||  0  || 0  ||  0  ||  0 
|-
| '''det'''                          ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  0 
|-
| '''prn'''                          ||  0   ||  0   ||  0  ||  0 || 0  ||  0  ||  0
|-
| '''pr'''                           ||  0   ||  0   ||  0  ||  0  || 1  ||  0  ||  0
|-
| '''adj'''                          ||  0   ||  0   ||  0  ||  0  || 0  ||  1  ||  0
|-
| '''sent'''                         ||  0   ||  0   ||  0  ||  0  || 0  ||  0  ||  1
|-
|}
</div>

:<math>b_{verb}((verb|noun)) = \frac{N((verb|noun))}{N(verb)} = \frac{1}{5} = 0.2</math>

And given the tag "noun" which we see six times, we see the ambiguity class "verb|noun" four times,

:<math>b_{noun}((verb|noun)) = \frac{N((verb|noun))}{N(noun)} = \frac{4}{6} = 0.67</math>

;Calculating the initial probabilities

The vector for the initial probabilities of the model is just the row from the transition probability matrix which corresponds to the end of sentence marker tag <code><sent></code> (in the equations marked as <code>#</code>), that is:

:<math>\pi_i = p(\gamma_i|\#)</math>

So given our above data set:

:<math>\pi_{verb} = \frac{N(sent, verb)}{N(\{det,prn,pr,adj,verb,sent,noun\}, verb)} = \frac{3}{4} = 0.75</math>

===Expectation maximisation===