You will learn to build Hidden Markov Model using the Viterbi algorithm and apply it to the

task of POS tagging. Complete each of the following tasks.

Load NLTK Treebank tagged sentences using nltk$.$corpus.treebank.tagged$\_$sents$().$

Use first $80\%$ of sentences for training and the remaining $20\%$ for testing.

Extract the word and the tag from each of the sentences and create a vocabulary of all

the words and a set of all tags.

To implement the Viterbi algorithm, you need $2$ components,

Tag transition probability matrix A: It represents the probability of a tag

occurring given the previous tag or $p(t_i|t_{i-1}).$ We compute the maximum likelihood

estimate $($MLE$)$ of the probability by counting the occurrences of the tag $t_{i-1}$ followed

by $tag{t}_i.$

$p(t_i|t_{i-1})=\frac{\text{c}\text{o}\text{u}\text{n}\text{t}(t_{i-1},t_i)}{\text{c}\text{o}\text{u}\text{n}\text{t}(t_{i-1})}$

Emission probability matrix B: It represents the probability of a tag $t_i$ being

associated with a given word $w_i$ or $p(w_i|t_i).$ MLE estimate is:

$p(w_i|t_i)=\frac{\text{c}\text{o}\text{u}\text{n}\text{t}(t_i,w_i)}{\text{c}\text{o}\text{u}\text{n}\text{t}(t_i)}$

Since the number of tags is smaller, creating matrix $A$ is time efficient whereas generation

of matrix B will be very expensive due to vocabulary size.

Implement a method compute$\_$tag$\_$trans$\_$probs $()$ to calculate matrix $A$ by parsing the

sentences in the training set and counting the occurrences of the tag $t_{i-1}$ followed by $t_i.$

Implement a method emission$\_$probs $()$ to calculate emission probability of a given word

$w_i$ having a tag $t_i.$

Next step in HMM is decoding which entails determining the hidden variable sequence of

observations. In POS tagging, decoding is to choose the sequence of tags most probable

to the sequence of words. We compute this using the following equation,

hat$(t{)}_{1\text{:}n}=argma{x}_{t_{1}dots{t}_n}pro{d}_i=1^{n}p(w_i|t_i)p(t_i|t_{i-1})$

The optimal solution for HMM decoding is given by the Viterbi algorithm, a dynamic

approach to the computation of the decoded tags. Implement the algorithm using the

two methods, compute$\_$tag$\_$trans$\_$probs$()$ and emission$\_$probs$()$ implemented above

and return the sequence of tags corresponding to the given sequence of words. Refer to

section $8\mathrm{.}4\mathrm{.}5,$ Fig. $8\mathrm{.}10$ of Speech and Language Processing book ${?}^5.$

Evaluate the performance of the model in terms of accuracy on the test set.