<jupyter_start><jupyter_text>POS Tagging Using Modified Viterbi   Problem StatementThe problem aims at building a HMM-based POS tagger with implementation of the Viterbi algorithm using the Penn Treebank training corpus. The task is to write the vanilla Viterbi algorithm for assigning POS tags (i.e. without dealing with unknown words). Once this baseline model is achieved the model has to be evaluated on the validation set and POS tagging check has to be performed on the sample test sentences set.    Approach:(i) Solving the problem of unknown words using at least two techniques. These techniques can use any of the approaches - lexicon, rule-based, probabilistic etc. (ii) Compare the tagging accuracy after making these modifications with the vanilla Viterbi algorithm. (iii) List down at least three cases from the sample test file (i.e. unknown word-tag pairs) which were incorrectly tagged by the original Viterbi POS tagger and got corrected after modifications.  Step 1: Data Preparation<jupyter_code>##Ignore Warnings
import warnings
warnings.filterwarnings('ignore')
##Importing all the necessary libraries
from collections import Counter
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import nltk, re, pprint
import random
from sklearn.model_selection import train_test_split
import time, pprint
from nltk.tokenize import word_tokenize
from nltk.tokenize import sent_tokenize
##Reading the tagged sentences in Penn Treebank training corpus 
nltk_data = list(nltk.corpus.treebank.tagged_sents(tagset='universal'))
##Checking first few tagged sentences 
nltk_data[:20]<jupyter_output><empty_output><jupyter_text>Train Test Split   Note: The term 'test_set' here refers to the validation set. The actual test set corresponds to the corpus within the Sample Test Sentences text file.<jupyter_code>##Splitting into train and test sets (using the pre-mentioned sample size of 95:5 for train and test sets respectively)
random.seed(42)
train_set, test_set = train_test_split(nltk_data, test_size= 0.05, random_state= 42)

print("Sentences in Train Set:", len(train_set))
print("Sentences in Test Set:", len(test_set)); print()
##Checking the few tagged sentences in train_set after train_test_split
print(train_set[:10])  ##Top 10 tagged sentences
## Getting list of tagged words
train_set_tagged_words = [tup for sent in train_set for tup in sent]
print(train_set_tagged_words[:10])  ##First 10 train_set_tagged_words
len(train_set_tagged_words)
##Finding tokens from tagged words in the train_set 
tokens = [pair[0] for pair in train_set_tagged_words]

##Create a copy for later use
tokens_copy= tokens.copy()

print(tokens[:10])  ##First 10 tokens listed
##Vocabulary
V = set(tokens) ##Unique tokens for vocabulary
print(len(V))
##Checking few(first 10) words from vocabulary
print(list(V)[:10])
##Number of POS tags in the corpus
T = sorted(set([pair[1] for pair in train_set_tagged_words]))  ##sorted POS tags within the corpus
print("POS Tags:", T)
len(T)<jupyter_output>POS Tags: ['.', 'ADJ', 'ADP', 'ADV', 'CONJ', 'DET', 'NOUN', 'NUM', 'PRON', 'PRT', 'VERB', 'X']<jupyter_text>The Universal tagset of `NLTK comprises only 12 coarse tag classes` as follows: `Verb, Noun, Pronouns, Adjectives, Adverbs, Adpositions, Conjunctions, Determiners, Cardinal Numbers, Particles, Other/ Foreign words, Punctuations.` Therefore, `using only 12 coarse classes` (compared to the 46 fine classes such as NNP, VBD etc.); this will `make the Viterbi algorithm faster` as well.  Step 2: Build the vanilla Viterbi algorithm based POS tagger  (i.e. without dealing with unknown words)  Emission Probabilities (word| given tag) Instances<jupyter_code>##Computing P(w/t) and storing in T x V matrix (Note: w: word and t:tag)
t = len(T)
v = len(V)
w_given_t = np.zeros((t, v))
##Define a function to compute instances of a word given tag (i.e. for Emission Probability)
def word_given_tag(word, tag, my_train_bag = train_set_tagged_words):
    tag_list = [pair for pair in my_train_bag if pair[1]== tag]           ##Storing pairs with matching POS tags
    count_tag = len(tag_list)                                             ##Total matched tagged pairs
    word_given_tag_list = [pair[0] for pair in tag_list if pair[0]== word]   ##List of pairs with matching word in the given tag list
    count_word_given_tag = len(word_given_tag_list)                             ##Count of word given tag
    
    return (count_word_given_tag, count_tag)
##Checking out Emission Probability function for an example.
print("Checking for word:", "\'management\'")
print(word_given_tag('management', 'NOUN'))
print(word_given_tag('management', 'PRON'))
print(word_given_tag('management', 'VERB'))<jupyter_output>Checking for word: 'management'
(21, 27423)
(0, 2618)
(0, 12885)<jupyter_text>The `Emission Probability (word| given tag) Instances` function works pretty well as we see that the emission probability for the word `'management'` aligns more towards `NOUN` as we do have matching instances of the same.  Transition Probabilities (tag t2| given tag t1) Instances<jupyter_code>##Define a function to compute tag given tag instances: tag2(t2) given tag1 (t1), [i.e. for Transition Probability]

def t2_given_t1(t2, t1, my_train_bag = train_set_tagged_words):   
    tags_list = [pair[1] for pair in my_train_bag]
    tags_match_t1= [t for t in tags_list if t== t1]
    count_t1 = len(tags_match_t1)
    count_t2_t1 = 0
    for index in range(len(tags_list)-1):
        if tags_list[index]== t1 and tags_list[index+1] == t2:  ##when tag(t1) followed by tag(t2)
            count_t2_t1 += 1
    return (count_t2_t1, count_t1)
##Checking out Transition Probability Instances function with an example.
print(t2_given_t1(t2='NOUN', t1='ADJ'))   ##transition probability instances where an 'ADJ'(t1) followed by a 'NOUN'(t2)<jupyter_output>(4234, 6077)<jupyter_text>Transition Probabilities Matrix Creating a `t x t transition matrix` of tags where each column is t2 and each row is t1. Thus, M(i, j) represents P(tj given ti).<jupyter_code>##Transition Probability Matrix
tags_matrix = np.zeros((len(T), len(T)), dtype='float32')
for i, t1 in enumerate(T):     ##T is sorted POS Tag list 
    for j, t2 in enumerate(T): 
        tags_matrix[i, j] = t2_given_t1(t2, t1)[0]/t2_given_t1(t2, t1)[1]  ##transition probabilities within the matrix
tags_matrix
##Creating a dataframe to store the transition probabilities of the 12 tags (coarse classes) from the Universal tagset_nltk
tags_df = pd.DataFrame(tags_matrix, columns = T, index= T)
tags_df
##Plot a heatmap of the tags_df matrix (transition probabilities)
plt.figure(figsize=(18, 12), dpi=100)
sns.heatmap(tags_df, cmap= "YlGnBu", annot= True)
plt.show()
##Let's check transition probabilities greater than 50% (filter the df to get P(t2, t1) >50%)

tags_trans_p_50_plus = tags_df[tags_df>0.5]
plt.figure(figsize=(18, 12))
sns.heatmap(tags_trans_p_50_plus, cmap= "YlGnBu", annot= True)
plt.show()<jupyter_output><empty_output><jupyter_text>1. Unmodified Viterbi POS Tagger (vanilla version)  Function (1)<jupyter_code>## Viterbi Algorithm (vanilla version)
def Viterbi(words, my_train_bag = train_set_tagged_words):
    state = []
    T = sorted(list(set([pair[1] for pair in my_train_bag])))  ##List of all unique tags within train_set_tagged_words
    
    for key, word in enumerate(words):
        #initialise list of probability column for a given observation
        p = [] 
        for tag in T:
            if key == 0:
                transition_p = tags_df.loc['.', tag]
            else:
                transition_p = tags_df.loc[state[-1], tag]
                
            # compute emission and state probabilities
            emission_p_instances= word_given_tag(words[key], tag)
            emission_p = emission_p_instances[0]/emission_p_instances[1]
            state_probability = emission_p * transition_p    
            p.append(state_probability)
            
        pmax = max(p)
        # getting state for which probability is maximum
        state_max = T[p.index(pmax)] 
        state.append(state_max)
    return list(zip(words, state))<jupyter_output><empty_output><jupyter_text>Evaluating Tagging Accuracy (Validation Set): Viterbi (Vanilla)<jupyter_code>##Let's test our Viterbi algorithm on our validation set (referred as test_set)
random.seed(42)

# list of all sentences selected
test_run = [sent for sent in test_set] 
test_run
# list of tagged words (tuples from the validation set)
test_run_base = [tup for sent in test_run for tup in sent]

# list of untagged words
test_set_untagged_words = [tup[0] for sent in test_run for tup in sent]
print(test_set_untagged_words[:50])  ##print first 50
##Tagging the test sentences
start = time.time()
tagged_sequence = Viterbi(test_set_untagged_words)
end = time.time()
difference = end-start
print("Time taken to tag the test sentences (in seconds): ", difference)
##Display comparison of first 50 (word,tag) pairs of tagged sequence vs actual test_run_base 
print("Tagged Sequence using vanilla Viterbi Algorithm:\n\n", tagged_sequence[:50], "\n\n\n")
print("Actual Test Set:\n\n", test_run_base[:50])
##Finding the number of correct (word, tag) pairs
correct_matches = [i for i, j in zip(tagged_sequence, test_run_base) if i == j] 

##Computing the tagging accuracy (of Vanilla Viterbi POS tagger on validation set)
accuracy_score= len(correct_matches)/len(tagged_sequence)

print("Viterbi Algorithm (vanilla) Accuracy: ", accuracy_score)
##Few correctly tagged words pairs by Vanilla Viterbi 
print(correct_matches[:10])  ##first 10
##Incorrect tagged cases (format: [(previous_word, tag),(tag_seq_word, tag_seq_tag), (actual_word, actual_tag)])
incorrect_cases = [[test_run_base[i-1],j] for i, j in enumerate(zip(tagged_sequence, test_run_base)) if j[0]!=j[1]]
incorrect_cases[:20]  ##First 20 incorrectly tagged cases
##Incorrect tagged words with tags
incorrect_tagged_words =  [j[0] for i, j in enumerate(zip(tagged_sequence, test_run_base)) if j[0]!=j[1]]
incorrect_tagged_words[:20]  ##First 20<jupyter_output><empty_output><jupyter_text>**Checking the `"Test_sentences.txt"` file to find out unknown words in the file(unknown words imply the words that are not present in the Universal NLTK corpus but might be present in the Test_sentences.txt file)**<jupyter_code>##Read 'Test_sentences.txt' file
with open("Test_sentences.txt", "r") as file:
    file_read= file.readlines()

file_read  ##Still contains '\n' and we can't use the sentence tokenizer directly as some lines don't end with a full-stop
##Defining a function to eliminate the new lines '\n' from the sentences
def without_spaces_lines(my_list):
    list_lines=[]
    for item in file_read:
        item = re.sub("\n$","", item)
        list_lines.append(item)
    list_lines = [item for item in list_lines if item!='']
    return list_lines

text_lines = without_spaces_lines(file_read)  ##List of lines in the text file
text_lines
##Entire Text
text_ = " ".join(text_lines)
##Tokenizing
test_tokens= nltk.tokenize.word_tokenize(text_)

#Copy of test_tokens
test_tokens_copy= test_tokens.copy()

print(test_tokens);print()  
print("Total Test Tokens:", len(test_tokens))
##Words not in corpus (Unknown Words)
tokens= tokens_copy
words_not_in_corpus = list(set(test_tokens).difference(set(tokens)))  ##unknown_words: difference between unique test_tokens and unique tokens from the training corpus
print("Unknown words in corpus:\n", words_not_in_corpus);print()
print("Number of Unknown words:",len(words_not_in_corpus))
##Applying Vanilla Viterbi Algorithm (that was created without dealing with these unknown words)
test_file_words_tagged= Viterbi(test_tokens)
test_file_words_tagged
##Unknown words and their respective wrong POS tags checking using Vanilla Viterbi (not designed using these unknown words)
unknown_words_tags_van_vit= [tup for tup in test_file_words_tagged for word in words_not_in_corpus if tup[0]==word]
print(unknown_words_tags_van_vit)
##Unique set of unknown words and wrong POS tags assigned by vanilla Viterbi
unknown_words_tags_van_vit_uniq = sorted(list(set(unknown_words_tags_van_vit)))
print(unknown_words_tags_van_vit_uniq)<jupyter_output>[('2011', '.'), ('2013', '.'), ('2015', '.'), ('2018', '.'), ('21st', '.'), ('Android', '.'), ('Cup', '.'), ('FIFA', '.'), ('Google', '.'), ('ICESAT-2', '.'), ('NASA', '.'), ('OS', '.'), ('Satellite', '.'), ('Twitter', '.'), ('arriving', '.'), ('contested', '.'), ('domineering', '.'), ('firehose', '.'), ('interact', '.'), ('invited', '.'), ('messages', '.'), ('online', '.'), ('personality', '.'), ('smartphones', '.'), ('tournament', '.'), ('trips', '.'), ('tweets', '.'), ('worldwide', '.')]<jupyter_text>**Observation:** All the unknown words in the sample sentences test file were naively tagged the first POS tag from the sorted POS tag list of Universal NLTK corpus i.e. `'.'`**(Punctuations)** was assigned to all unknown words by the vanilla Viterbi Algorithm. This can be improved by making certain modifications to the vanilla Viterbi Algorithm.  Solving the problem of unknown words Let's modify the Viterbi Algorithm to handle the unknown words. We shall be using two techniques.  2. Viterbi Modification-Technique I: *(Viterbi_Modified_Technique_1)* Method incorporated in `Viterbi_Modified_Technique_1`:(i) `Probabilitisc approach` (ii) `For words within the corpus`, computing the `state probability as (emission_probability)\*(transition probability)`(iii) `For words not in the corpus`, computing the `state probability as (weight of tag)*(transition probability)`. Note: We'll also be applying weights (for unknown words) based on the probability of tag occurance to the transition probabilities of tags and then use the resulting probability for predicting unknown words. This scheme will also take into account some POS tags that are more likely to occur as compared to others.<jupyter_code>##lets create a list containing tuples of POS tags and POS tag occurance probability, based on training data
tag_prob = []
total_tag_occ = len([tag for (word,tag) in train_set_tagged_words])  ##Total occurrences of all POS tags in the corpus

for t in T:  ##T is the unique set of POS Tags
    each_tag_occ = [tag for (word,tag) in train_set_tagged_words if tag==t]  ##Occurrence of each tag in the corpus
    tag_prob.append((t,len(each_tag_occ)/total_tag_occ))

##(tag, weight_based _on_occurrences)
tag_prob<jupyter_output><empty_output><jupyter_text>Function (2)<jupyter_code>##Defining a function for Modified Viterbi 
def Viterbi_Modified_Technique_1(words, my_train_bag = train_set_tagged_words):
    state = []
    T = sorted(list(set([pair[1] for pair in my_train_bag])))
    
    for key, word in enumerate(words):
        #initialise list of probability column for a given observation
        p = [] 
        p_transition =[] # list for storing transition probabilities
        for tag in T:
            if key == 0:
                transition_p = tags_df.loc['.', tag]
            else:
                transition_p = tags_df.loc[state[-1], tag] 
                
            # compute emission and state probabilities
            emission_p_instances= word_given_tag(words[key], tag)
            emission_p = emission_p_instances[0]/emission_p_instances[1]
            state_probability = emission_p * transition_p    
            p.append(state_probability)   
            
            # find POS tag occurance probability
            tag_p = [pair[1] for pair in tag_prob if pair[0]==tag ]
            
            # calculate the transition prob weighted by tag occurance probability.
            transition_p = tag_p[0]*transition_p   ##(weight based on occurrences)*(transition_p)
            
            p_transition.append(transition_p)
            
            
        pmax = max(p)
    
        if(pmax == 0): ##if state probability is zero (because of zero emission probability for unknown word) 
            pmax = max(p_transition)  ##Use transition probability
            state_max = T[p_transition.index(pmax)]
        else:
            state_max = T[p.index(pmax)]
         
        state.append(state_max)
    return list(zip(words, state))<jupyter_output><empty_output><jupyter_text>Evaluating the Tagging Accuracy (Validation Data): Modified Viterbi Technique 1<jupyter_code>start = time.time()
tagged_sequence_1 = Viterbi_Modified_Technique_1(test_set_untagged_words)
end = time.time()
difference = end-start
print("Time taken to tag the test sentences (in seconds): ", difference)
##Display comparison of first 50 (word,tag) pairs of tagged sequence 1 vs actual test_run_base 
print("Tagged Sequence using Modified Viterbi Technique 1:\n\n", tagged_sequence_1[:50], "\n\n\n")
print("Actual Test Set:\n\n", test_run_base[:50])
##Finding the number of correct (word, tag) pairs
correct_matches_1 = [i for i, j in zip(tagged_sequence_1, test_run_base) if i == j] 

##Computing the POS Tagger's accuracy
accuracy_score_1 = len(correct_matches_1)/len(tagged_sequence_1)

print("Modified Viterbi Technique 1_POS Tagger's Accuracy: ", accuracy_score_1)
##Display first few correct matches (first 10)
correct_matches_1[:10]
##Incorrect tagged cases (format: [(previous_word, tag),(tag_seq_word, tag_seq_tag), (actual_word, actual_tag)])
incorrect_cases_mod_1 = [[test_run_base[i-1],j] for i, j in enumerate(zip(tagged_sequence_1, test_run_base)) if j[0]!=j[1]]
incorrect_cases_mod_1[:20]  ##First 20
##Incorrect tagged words
incorrect_tagged_words_mod_1 =  [j[0] for i, j in enumerate(zip(tagged_sequence_1, test_run_base)) if j[0]!=j[1]]
incorrect_tagged_words_mod_1[:20]  ##First 20<jupyter_output><empty_output><jupyter_text>Checking POS Tagging of unknown words in `Test_sentences.txt` (Sample Sentences Test Txt file) using **Viterbi_Modified_Technique_1**<jupyter_code>##Words not in corpus (Unknown Words)
tokens= tokens_copy
words_not_in_corpus = list(set(test_tokens) - set(tokens))
print("Unknown words in corpus:\n", words_not_in_corpus);print()
print("Number of Unknown words:",len(words_not_in_corpus))
##Applying 'Viterbi_Modified_Technique_1' 
test_tokens= test_tokens_copy
test_file_words_tagged_1 = Viterbi_Modified_Technique_1(test_tokens)
test_file_words_tagged_1
##Unknown words and their respective POS tags checking using 'Viterbi_Modified_Technique_1' 
unknown_words_tags_1= [tup for tup in test_file_words_tagged_1 for word in words_not_in_corpus if tup[0]==word]
print(unknown_words_tags_1)
unknown_words_tags_1_uniq = sorted(list(set(unknown_words_tags_1)))
print(unknown_words_tags_1_uniq)
##Zip original and modified viterbi technique 1 (for comparison)
orig_mod_viterbi_1 = sorted(list(set(zip(unknown_words_tags_van_vit_uniq, unknown_words_tags_1_uniq))))  
orig_mod_viterbi_1
##Check if the pairs within a tuple are similar in nature or not
[j for i,j in enumerate(orig_mod_viterbi_1) if j[0]==j[1]]
##Check for modified POS tags in 'unknown_words_tags_1_uniq'
Counter([tup[1] for tup in unknown_words_tags_1_uniq]).most_common()
##Modified Cases
##Nouns
noun_words= sorted(list(set([tup[0] for tup in unknown_words_tags_1_uniq if tup[1]=='NOUN'])))
print("Words_Tagged_[Nouns]:\n", noun_words); print()<jupyter_output>Words_Tagged_[Nouns]:
 ['2011', '2013', '2015', '2018', '21st', 'Android', 'Cup', 'FIFA', 'Google', 'ICESAT-2', 'NASA', 'OS', 'Satellite', 'Twitter', 'arriving', 'contested', 'domineering', 'firehose', 'interact', 'invited', 'messages', 'online', 'personality', 'smartphones', 'tournament', 'trips', 'tweets', 'worldwide']<jupyter_text>**Observations:**In case of Probabilistic Tagger, the algorithm assigns the most probable tag (in this case, `NOUN`) to the unknown words.*Modified Viterbi Algorithm Technique 1 shows some improvement in tagging the words with correct POS tags.*Correct `POS tagged Nouns`: `'Android', 'smartphones', 'firehose', 'Satellite', 'messages', 'tournament', 'personality', 'tweets', 'Cup', 'trips', 'ICESAT-2', 'Twitter', 'Google', 'FIFA', 'OS', 'NASA'`*  3. Viterbi Modification-Technique II: *(Viterbi_Modified_Technique_2)* Method that would be incorporated in `Modified Viterbi Algorithm 2`:(i) Multiple Taggers Combined: `Lexicon(Trigram, Bigram, Unigram), Affix, Rule-Based Taggers, and Default Tagger` (in that order where Default Tagger: Tagging the most common POS tag to the unknown words in the corpus).(ii) The Rule-Based Tagger also takes into account most of the morphological cues necessary for proper POS tagging of words.<jupyter_code>##Default Tag in the Universal NLTK corpus (for assigning the DefaultTag in case all tags fail to identify)
from collections import Counter

tags = [pair[1] for pair in train_set_tagged_words]
tag_counts = Counter(tags).most_common()
tag_counts[:1]  ##Most common tag identified in the train corpus<jupyter_output><empty_output><jupyter_text>**Observation:** The most common tag within the training corpus is `NOUN`. This shall be used within the last backoff `Default Tagger`.<jupyter_code>##Rule-Based Tagger: (Taking into account the morphological cues)

##Specify patterns (for Regexp): Rule based tagging 
##Example from the NLTK book
patterns = [
    (r"[0-9]+(st|nd|rd|th)$", 'ADJ'),    #For adjectives like 1st, 2nd, 3rd, 4th, 50th, etc.
    (r"[\*\w-]*\*+[\*\w-]*$", 'X'),      #Others/Foreignwords(bearing at least one *)
    (r'.*ing$', 'VERB'),                 # gerund
    (r'.*ed$', 'VERB'),                  # past tense verbs
    (r'.*es$', 'VERB'),                  # singular present verbs
    (r'.*ould$', 'VERB'),                # modal verbs
    (r'.*\'s$', 'NOUN'),                 # possessive nouns
    (r'.*s$', 'NOUN'),                   # plural nouns
    (r"\*T?\*?-[0-9]+$", "X"),           #Cases: Others
    (r'^-?[0-9]+(.[0-9]+)?$', 'NUM'),    # cardinal numbers
    (r'(The|the|A|a|An|an)$', 'DET'),    # articles or determinants
    (r'.*able$', 'ADJ'),                 # adjectives
    (r'.*ness$', 'NOUN'),                # nouns formed from adjectives
    (r'.*ly$', 'ADV'),                   # adverbs
]
##Defining a 'pos_tagger' function for the Taggers to used in Technique 2: (Lexicon + Rule_Based + DefaultTagger)
random.seed(42)
def pos_tagger(train_set):
    rule_based_tagger = nltk.RegexpTagger(patterns, backoff=nltk.DefaultTagger('NOUN'))
    affix_tagger = nltk.AffixTagger(train_set, backoff= rule_based_tagger)
    unigram_tagger = nltk.UnigramTagger(train_set, backoff= affix_tagger)
    bigram_tagger = nltk.BigramTagger(train_set, backoff= unigram_tagger)
    trigram_tagger = nltk.TrigramTagger(train_set, backoff= bigram_tagger)
    return trigram_tagger

tagger= pos_tagger(train_set) ##Instantiating the tagger object<jupyter_output><empty_output><jupyter_text>Function (3)<jupyter_code>##Defining a function for Modified Viterbi Technique 2
def Viterbi_Modified_Technique_2(words, my_train_bag = train_set_tagged_words):
    state = []
    T = sorted(list(set([pair[1] for pair in my_train_bag])))
    
    for key, word in enumerate(words):
        #initialise list of probability column for a given observation
        p = [] 
        for tag in T:
            if key == 0:
                transition_p = tags_df.loc['.', tag]
            else:
                transition_p = tags_df.loc[state[-1], tag]
                
            # compute emission and state probabilities
            emission_p_instances= word_given_tag(words[key], tag)
            emission_p = emission_p_instances[0]/emission_p_instances[1]
            state_probability = emission_p * transition_p    
            p.append(state_probability)
            
        pmax = max(p)
        if(pmax == 0):
            state_max = tagger.tag([word])[0][1]  ##Using tagger.tag() generated from the pos_tagger to get the POS tag          
        else: 
            state_max = T[p.index(pmax)]
         
        state.append(state_max)
    return list(zip(words, state))<jupyter_output><empty_output><jupyter_text>Evaluating the Tagging Accuracy (Validation Data): Modified Viterbi Technique 2<jupyter_code>start = time.time()
tagged_sequence_2 = Viterbi_Modified_Technique_2(test_set_untagged_words)
end = time.time()
difference = end-start
print("Time taken to tag the test sentences (in seconds): ", difference)
##Display comparison of first 50 (word,tag) pairs of tagged sequence 2 vs actual test_run_base 
print("Tagged Sequence using Modified Viterbi Technique 2:\n\n", tagged_sequence_2[:50], "\n\n\n")
print("Actual Test Set:\n\n", test_run_base[:50])
##Finding the number of correct (word, tag) pairs
correct_matches_2 = [i for i, j in zip(tagged_sequence_2, test_run_base) if i == j] 

##Computing the POS Tagger's accuracy
accuracy_score_2 = len(correct_matches_2)/len(tagged_sequence_2)

print("Modified Viterbi Technique 2_POS Tagger's Accuracy: ", accuracy_score_2)
##First few correct matches- (word, tag) pairs (using Modified Viterbi Technique 2)
correct_matches_2[:10]
##Incorrect tagged cases (format: [(previous_word, tag),(tag_seq_word, tag_seq_tag), (actual_word, actual_tag)])
incorrect_cases_mod_2 = [[test_run_base[i-1],j] for i, j in enumerate(zip(tagged_sequence_2, test_run_base)) if j[0]!=j[1]]
incorrect_cases_mod_2[:20]  ##First 20
##Incorrect tagged words
incorrect_tagged_words_mod_2 =  [j[0] for i, j in enumerate(zip(tagged_sequence_2, test_run_base)) if j[0]!=j[1]]
incorrect_tagged_words_mod_2[:20]  ##First 20<jupyter_output><empty_output><jupyter_text>Checking POS Tagging of unknown words in `Test_sentences.txt` (Sample Sentences Test Txt file) using **Viterbi_Modified_Technique_2**<jupyter_code>##Words not in corpus (Unknown Words)
tokens= tokens_copy
words_not_in_corpus = list(set(test_tokens) - set(tokens))
print("Unknown words in corpus:\n", words_not_in_corpus);print()
print("Number of Unknown words:",len(words_not_in_corpus))
##Applying 'Viterbi_Modified_Technique_2' 
test_tokens= test_tokens_copy
test_file_words_tagged_2 = Viterbi_Modified_Technique_2(test_tokens)
test_file_words_tagged_2
##Unknown words and their respective POS tags checking using 'Viterbi_Modified_Technique_2' 
unknown_words_tags_2= [tup for tup in test_file_words_tagged_2 for word in words_not_in_corpus if tup[0]==word]
print(unknown_words_tags_2)
unknown_words_tags_2_uniq = sorted(list(set(unknown_words_tags_2)))
print(unknown_words_tags_2_uniq)
##Zip original and modified viterbi technique 2 (for comparison)
orig_mod_viterbi_2 = sorted(list(set(zip(unknown_words_tags_van_vit_uniq, unknown_words_tags_2_uniq))))  
orig_mod_viterbi_2
##Check if the pairs within a tuple are similar in nature or not
[j for i,j in enumerate(orig_mod_viterbi_2) if j[0]==j[1]]
##Check for modified POS tags in 'unknown_words_tags_1_uniq'
Counter([tup[1] for tup in unknown_words_tags_2_uniq]).most_common()
##Modified Cases
#(i) Nouns
noun_words= sorted(set([tup[0] for tup in unknown_words_tags_2_uniq if tup[1]=='NOUN']))
print("Words_Tagged_[Nouns]:\n", noun_words); print()

#(ii) Verbs
verb_words= sorted(set([tup[0] for tup in unknown_words_tags_2_uniq if tup[1]=='VERB']))
print("Words_Tagged_[Verbs]:\n", verb_words); print()

#(iii) Num
numbers= sorted(set([tup[0] for tup in unknown_words_tags_2_uniq if tup[1]=='NUM']))
print("Tagged_[Numbers]:\n", numbers); print()

#(iv) Adjective
adj= sorted(set([tup[0] for tup in unknown_words_tags_2_uniq if tup[1]=='ADJ']))
print("Tagged_[Adjectives]:\n", adj); print()

#(v) Determiners
det= sorted(set([tup[0] for tup in unknown_words_tags_2_uniq if tup[1]=='DET']))
print("Tagged_[Determiners]:\n", det); print()<jupyter_output>Words_Tagged_[Nouns]:
 ['Cup', 'FIFA', 'ICESAT-2', 'NASA', 'OS', 'Satellite', 'Twitter', 'interact', 'messages', 'online', 'personality', 'smartphones', 'tournament', 'trips', 'tweets']

Words_Tagged_[Verbs]:
 ['Android', 'arriving', 'contested', 'domineering', 'invited', 'worldwide']

Tagged_[Numbers]:
 ['2011', '2013', '2015', '2018']

Tagged_[Adjectives]:
 ['21st', 'Google']

Tagged_[Determiners]:
 ['firehose']<jupyter_text>**Observations:***Modified Viterbi Algorithm shows a drastic improvement in POS tagging of most of the words with correct POS tags.*(i) All unknown `numbers` were tagged correctly by  Modified Viterbi Technique 2 Model. Example: `'2011', '2013', '2015', '2018'` : All were correctly tagged as `NUM`(ii) Correct `POS tagged Verbs`: `'arriving', 'contested','domineering','invited'`(iii) Correct `POS tagged Nouns`: `'FIFA', 'Cup', 'ICESAT-2', 'NASA', 'OS', 'Satellite', 'Twitter', 'messages', 'personality', 'smartphones', 'tournament','trips', 'tweets'.`(iv) Correctly `POS tagged Adjectives`: `21st`  Conclusion  Compare the tagging accuracies of the modifications with the vanilla Viterbi algorithm<jupyter_code>##Storing accuracies and improvements in variables
acc= round(100*accuracy_score,4)
acc_1= round(100*accuracy_score_1,4)
acc_2= round(100*accuracy_score_2,4)
imp_1= acc_1- acc  ##Improvement in Technique 1  and Technique 2 w.r.t. baseline Viterbi model
imp_2= acc_2 - acc

##Creating a dataframe 'performance_df' to store performance metrics
performance_df= pd.DataFrame({'Model No.':list(range(1,4)),'Model':['Unmodified Viterbi POS Tagger (Baseline Model)',\
                            'Viterbi Modified Technique 1', 'Viterbi Modified Technique 2'], 'POS Tagger\'s Accuracy (%)': \
                             [acc, acc_1, acc_2],\
                             '%Improvement (w.r.t. Baseline Model)':['-',imp_1, imp_2]})
performance_df.set_index('Model No.', inplace= True)
performance_df
##Performance of all the 3 models (Displaying evaluation tagging accuracies)
%matplotlib inline
performance_df_plot= performance_df[['Model','POS Tagger\'s Accuracy (%)']]
performance_df_plot.set_index('Model', inplace= True)
performance_df_plot.plot.line(rot= 90)
plt.title("Performance of all 3 models", fontsize=14, fontweight='bold')
plt.xlabel('Model', fontsize="14", fontstyle='italic')
plt.ylabel('POS Tagger\'s Accuracy (%)', fontsize="12", fontstyle='italic')
plt.show()<jupyter_output><empty_output><jupyter_text>**Observations:**The graph and the table above clearly shows an `increase` in the performance of the models `(increase in tagging accuracy)` as we incorporate modifications within the baseline Vanilla Viterbi algorithm.  List down cases which were incorrectly tagged by original POS tagger and got corrected by your modifications  1. Viterbi (Baseline) Original POS Tagger: Incorrectly Tagged Words (Unknown Words):<jupyter_code>##Unknown words (with Incorrect Tags: Baseline Viterbi): 
print(unknown_words_tags_van_vit_uniq)<jupyter_output>[('2011', '.'), ('2013', '.'), ('2015', '.'), ('2018', '.'), ('21st', '.'), ('Android', '.'), ('Cup', '.'), ('FIFA', '.'), ('Google', '.'), ('ICESAT-2', '.'), ('NASA', '.'), ('OS', '.'), ('Satellite', '.'), ('Twitter', '.'), ('arriving', '.'), ('contested', '.'), ('domineering', '.'), ('firehose', '.'), ('interact', '.'), ('invited', '.'), ('messages', '.'), ('online', '.'), ('personality', '.'), ('smartphones', '.'), ('tournament', '.'), ('trips', '.'), ('tweets', '.'), ('worldwide', '.')]<jupyter_text>**Observation:** All unknown words were incorrectly tagged with the first tag as `'.'`**(Punctuations)** by Viterbi (Baseline) Model.  Comparing the incorrect tags of unknown words (from Baseline Viterbi) with the assigned POS tags obtained from other two models.  2. Model: Viterbi Modification-Technique I (Modified Viterbi Technique 1)<jupyter_code>##List of unique unknown words and POS Tags (using Modified Viterbi Technique 1))
print(unknown_words_tags_1_uniq)<jupyter_output>[('2011', 'NOUN'), ('2013', 'NOUN'), ('2015', 'NOUN'), ('2018', 'NOUN'), ('21st', 'NOUN'), ('Android', 'NOUN'), ('Cup', 'NOUN'), ('FIFA', 'NOUN'), ('Google', 'NOUN'), ('ICESAT-2', 'NOUN'), ('NASA', 'NOUN'), ('OS', 'NOUN'), ('Satellite', 'NOUN'), ('Twitter', 'NOUN'), ('arriving', 'NOUN'), ('contested', 'NOUN'), ('domineering', 'NOUN'), ('firehose', 'NOUN'), ('interact', 'NOUN'), ('invited', 'NOUN'), ('messages', 'NOUN'), ('online', 'NOUN'), ('personality', 'NOUN'), ('smartphones', 'NOUN'), ('tournament', 'NOUN'), ('trips', 'NOUN'), ('tweets', 'NOUN'), ('worldwide', 'NOUN')]<jupyter_text>**SAMPLE (TEST) CASES: CORRECTED BY MODIFICATIONS 1 w.r.t. BASELINE VITERBI:***Modified Viterbi Algorithm Technique 1 shows some improvement in tagging the words with correct POS tags.*Correct `POS tagged Nouns`: `'Android', 'smartphones', 'firehose', 'Satellite', 'messages', 'tournament', 'personality', 'tweets', 'Cup', 'trips', 'ICESAT-2', 'Twitter', 'Google', 'FIFA', 'OS', 'NASA'`***LIST OF 3 CASES TAGGED CORRECTLY IN COMPARISON TO BASELINE POS TAGGER:**1\. ('Satellite', 'NOUN'): 'Satellite' was correctly tagged as 'NOUN' (where the baseline Viterbi incorrectly tagged it as '.')2\. ('smartphones', 'NOUN'): 'smartphones' was correctly tagged as 'NOUN' (where the baseline Viterbi incorrectly tagged it as '.')3\. ('tournament', 'NOUN'): 'tournament' was correctly tagged as 'NOUN' (where the baseline Viterbi incorrectly tagged it as '.')  3. Model: Viterbi Modification-Technique II (Modified Viterbi Technique 2)<jupyter_code>##List of unique unknown words and POS Tags (using Modified Viterbi Technique 2)
print(unknown_words_tags_2_uniq)<jupyter_output>[('2011', 'NUM'), ('2013', 'NUM'), ('2015', 'NUM'), ('2018', 'NUM'), ('21st', 'ADJ'), ('Android', 'VERB'), ('Cup', 'NOUN'), ('FIFA', 'NOUN'), ('Google', 'ADJ'), ('ICESAT-2', 'NOUN'), ('NASA', 'NOUN'), ('OS', 'NOUN'), ('Satellite', 'NOUN'), ('Twitter', 'NOUN'), ('arriving', 'VERB'), ('contested', 'VERB'), ('domineering', 'VERB'), ('firehose', 'DET'), ('interact', 'NOUN'), ('invited', 'VERB'), ('messages', 'NOUN'), ('online', 'NOUN'), ('personality', 'NOUN'), ('smartphones', 'NOUN'), ('tournament', 'NOUN'), ('trips', 'NOUN'), ('tweets', 'NOUN'), ('worldwide', 'VERB')]
{'fraction_non_alphanumeric': 0.13043864848844103, 'fraction_numerical': 0.01698280972139893, 'mean_word_length': 5.161614317019723, 'pattern_counts': {'":': 0, '<': 76, '<?xml version=': 0, '>': 78, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '21', 'dir': 'jupyter-structured-clean-dedup', 'id': '106738', 'license': 'MIT', 'n_tokens_mistral': 11700, 'n_tokens_neox': 10848, 'n_words': 3329, 'path': 'HMM_Viterbi_based_POS_tagging.ipynb', 'repo_name': 'ChaitanyaC22/Syntactic-Processing-POS-Tagger', 'size': '33740'}