<jupyter_start><jupyter_text>Importing necessary packages<jupyter_code>import nltk,time,random
from nltk.tag import map_tag
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.model_selection import train_test_split
from nltk.tokenize import word_tokenize<jupyter_output><empty_output><jupyter_text>Storing Data from NLTK corpus locally into a variable<jupyter_code>tagged_dataset = list(nltk.corpus.treebank.tagged_sents(tagset='universal'))<jupyter_output><empty_output><jupyter_text>* tagged_dataset - Dataset that is used for training and validating the model. Printing first two elements of the dataset to get feel for how the data is stored<jupyter_code>tagged_dataset[:2]<jupyter_output><empty_output><jupyter_text>Printing total set of POS tags present in the datasetNote:- Universal tagset has 12 POS tags.<jupyter_code>set([Tuple[1] for sent in tagged_dataset for Tuple in sent])<jupyter_output><empty_output><jupyter_text>Printing count of total unique word present in the dataset<jupyter_code>len(set([Tuple[0] for sent in tagged_dataset for Tuple in sent]))<jupyter_output><empty_output><jupyter_text>Segregating Dataset into test and validation set.Note:- Testing is done on data seperately given in the assignment.<jupyter_code>train_set, valid_set = train_test_split(tagged_dataset,test_size=0.05,random_state=20)

print(len(train_set))
print(len(valid_set))<jupyter_output>3718
196<jupyter_text>* train_set - Data set that is used for training.* valid_set - Data set that is used for validation. Converting training data into list of tuples<jupyter_code>train_tagged_words = [Tuple for sent in train_set for Tuple in sent]<jupyter_output><empty_output><jupyter_text>* train_tagged_words - list of (word,POS tag) tuple , obtained from train data set. getting total set of tags<jupyter_code>Tagset = set([Tuple[1] for Tuple in train_tagged_words])<jupyter_output><empty_output><jupyter_text>* Tagset - set of POS tags present in train Data set. Converting validation dataset into list of tuples and wordsNote:- Below code is used to select n random sentence from the validation set.By passing 196 for n,I'm selecting all the sentence in validation set in a random order.<jupyter_code>random.seed(20)
# choose random 5 sents
rndom_num = [random.randint(0,len(valid_set)-1) for x in range(196)]
# list of sents
select_valid_set = [valid_set[i] for i in rndom_num]
# list of tagged words
select_valid_tup = [tup for sent in select_valid_set for tup in sent]
select_valid_words = [tup[0] for sent in select_valid_set for tup in sent]<jupyter_output><empty_output><jupyter_text>* rndom_num - list of n random numbers in validation range* select_valid_set - random sentences chosen from validation set through random numbers present "rndom_num" variable* select_valid_tup - list of (word,POS tag) tuple present in validation set.* select_valid_words - list of words present in validation set. Test dataset hardcoded into the notebook.<jupyter_code>test_set=[['Android','is','a','mobile','operating','system','developed','by','Google','.'],
['Android','has','been','the','best-selling','OS','worldwide','on','smartphones','since','2011','and','on','tablets','since','2013','.'],
['Google','and','Twitter','made','a','deal','in','2015','that','gave','Google','access','to','Twitter\'s','firehose','.'],
['Twitter','is','an','online','news','and','social','networking','service','on','which','users','post','and','interact','with','messages','known','as','tweets','.'],
['Before','entering','politics,','Donald','Trump','was','a','domineering','businessman','and','a','television','personality','.'],
['The','2018','FIFA','World','Cup','is','the','21st','FIFA','World','Cup,','an','international','football','tournament','contested','once','every','four','years','.'],
['This','is','the','first','World','Cup','to','be','held','in','Eastern','Europe','and','the','11th','time','that','it','has','been','held','in','Europe','.'],
['Show','me','the','cheapest','round','trips','from','Dallas','to','Atlanta','.'],
['I','would','like','to','see','flights','from','Denver','to','Philadelphia','.'],
['Show','me','the','price','of','the','flights','leaving','Atlanta','at','about','3','in','the','afternoon','and','arriving','in','San','Francisco','.'],
['NASA','invited','social','media','users','to','experience','the','launch','of','ICESAT-2','Satellite','.']]<jupyter_output><empty_output><jupyter_text>* test_set - Data set used for testing  Base functions necessary to build HMM based POS taggers Function that is used to calculate transition probability from tag "t1" to "t2"<jupyter_code>def t2_given_t1(t2, t1, train_bag = train_tagged_words):
    #Seperating list of tags in training dataset in order as they appear in sentences.
    train_tag_list = [pair[1] for pair in train_bag]
    #Getting total count of tag that is t1
    count_t1 = len([t for t in train_tag_list if t==t1])
    count_t1_t2 = 0
    #Getting count of tag t1 that is followed by t2
    for index in range(len(train_tag_list)-1):
        if train_tag_list[index]==t1 and train_tag_list[index+1] == t2:
            count_t1_t2 += 1
    return (count_t1_t2, count_t1)<jupyter_output><empty_output><jupyter_text>* t2_given_t1() - Name of function that outputs values which is used to calculate transition probability.* train_tag_list - list of POS tag that is present in training dataset in order as they appear.* count_t1 - count of POS tag t1 present in the dataset.* count_t1_t2 - count of POS tags t1 followed by t2. Function that is used to calculate probability of getting a word given a tagNote:- It is also known as emission probability.<jupyter_code>def word_given_tag(word, tag, train_bag = train_tagged_words):
    #getting list of tuples with POS tag that is passed in argument
    tup_list_gn_tag = [pair for pair in train_bag if pair[1]==tag]
    #count of tuples in the obtained list
    tup_count_gn_tag = len(tup_list_gn_tag)
    #getting list of tuples where word and POS tag are as passed in argument
    wd_list_gn_wd = [pair[0] for pair in tup_list_gn_tag if pair[0]==word]
    #count of tuples obtained in the above list
    wd_count_gn_wd = len(wd_list_gn_wd)
    
    return (wd_count_gn_wd, tup_count_gn_tag)<jupyter_output><empty_output><jupyter_text>* word_given_tag() - Function that outputs parameters which is used to calculate emission probability.* tup_list_gn_tag - list of tuples whose POS tag is as passed in the function argument* tup_count_gn_tag - count of tuples present in tup_list_gn_tag* wd_list_gn_wd - list of words whose word is as passed in function argument in taglist* wd_count_gn_wd - count of tuple present in wd_list_gn_wd Generating a matrix that map all transitions from one tag to another tag<jupyter_code>tags_trans_matrix = np.zeros((len(Tagset), len(Tagset)), dtype='float32')
#Populating matrix with transition probability of moving from one POS tag to another POS tag
for i, t1 in enumerate(list(Tagset)):
    for j, t2 in enumerate(list(Tagset)): 
        #transition probability is calculated as (count of tag t1 followed by t2) / (count of tag t1)
        tags_trans_matrix[i, j] = t2_given_t1(t2, t1)[0]/t2_given_t1(t2, t1)[1]

tags_trans_matrix<jupyter_output><empty_output><jupyter_text>* tags_matix - matrix used to store transition probability. Converting the mapping matrix into a DataFrame<jupyter_code>tags_trans_df = pd.DataFrame(tags_trans_matrix, columns = list(Tagset), index=list(Tagset))
tags_trans_df<jupyter_output><empty_output><jupyter_text>* tags_trans_df - DataFrame which is created from the matrix tags_trans_matrix  Plain Viterbi Algorithm Plain Viterbi function implementation without handling any unknown words.<jupyter_code>def Plain_Viterbi(words, train_bag = train_tagged_words):
    pred_tag = []
    Tagset = list(set([pair[1] for pair in train_bag]))
    #Below for loop parses through list of all words sequentially.
    for key, word in enumerate(words):
        resultant_prob_lst = []
        #Below for loop parses through list of available tagset.
        for tag in Tagset:
            #Transition Probability is calculated between two tags using Data Frame generated previously.
            #For the starting word there is no intial tag available.so we assign tag "." which 
            #indicates starting of the sentence.
            if key == 0:
                trans_prob = tags_trans_df.loc['.', tag]
            else:
                trans_prob = tags_trans_df.loc[pred_tag[-1], tag]
                
            # Computing Emission probability
            emission_count,emission_tot=word_given_tag(words[key], tag)
            emission_prob = emission_count/emission_tot
            # State Probability is the product of emission and transition probability.
            resultant_prob = emission_prob * trans_prob
            resultant_prob_lst.append(resultant_prob)    
        max_prob = max(resultant_prob_lst)
        
        #Selecting next tag that has maximum probability of occuring.
        max_prob_tag = Tagset[resultant_prob_lst.index(max_prob)] 
        pred_tag.append(max_prob_tag)
    return list(zip(words, pred_tag))<jupyter_output><empty_output><jupyter_text>* Plain_Viterbi() - Function that implements plain viterbi algorithm.* pred_tag - variable used to store sequence of POS tags for the passed word sequence.* resultant_prob_lst - variable containing list of probability for next POS tag.* trans_prob -  variable that stores trasitional probability.* emission_prob -  variable that stores emission probability.* emission_count - variable that stores count of word given tag in the training data set.* emission_tot - variable that stores specified tag count in training data set.* resultant_prob - resultant probability of a tag for the next word.* max_prob - value of maximum probability from the list of resultant_prob.* max_prob_tag - variable that stores tag which has maximum probability for the next word. Predicting tag for words by plain viterbi algorithm for words in validation set<jupyter_code>#Tagging the POS tags for validation set
start_time = time.time()
tagged_word_seq = Plain_Viterbi(select_valid_words)
end_time = time.time()
time_diff = end_time-start_time
print("Time taken in seconds: ", time_diff)<jupyter_output>Time taken in seconds:  558.8093910217285<jupyter_text>* start_time - starting time of prediction.* end_time - ending time of prediction.* time_diff - time taken for the prediction to complete.* tagged_word_seq - validation word sequence which has been tagged. Calculating Accuracy of plain viterbi algorithm for words in validation sets<jupyter_code>#Getting list of tuples whose actual and predicted value matches
correct_pred_list = [i for i, j in zip(tagged_word_seq, select_valid_tup) if i == j] 
#Accuracy is count of tuple that matches / count of total tuple
accuracy = len(correct_pred_list)/len(tagged_word_seq)
accuracy<jupyter_output><empty_output><jupyter_text>* correct_pred_list - list of (words,POS tag) tuple that matches with acutual value* accuracy - accuracy of the model POS tagging for test set<jupyter_code>for i in range(len(test_set)):
    print(str(Plain_Viterbi(test_set[i])))
    print('\n\n')<jupyter_output>[('Android', '.'), ('is', 'VERB'), ('a', 'DET'), ('mobile', 'ADJ'), ('operating', 'NOUN'), ('system', 'NOUN'), ('developed', 'VERB'), ('by', 'ADP'), ('Google', '.'), ('.', '.')]



[('Android', '.'), ('has', 'VERB'), ('been', 'VERB'), ('the', 'DET'), ('best-selling', 'ADJ'), ('OS', '.'), ('worldwide', '.'), ('on', 'ADP'), ('smartphones', '.'), ('since', 'ADP'), ('2011', '.'), ('and', 'CONJ'), ('on', 'ADP'), ('tablets', 'NOUN'), ('since', 'ADP'), ('2013', '.'), ('.', '.')]



[('Google', '.'), ('and', 'CONJ'), ('Twitter', '.'), ('made', 'VERB'), ('a', 'DET'), ('deal', 'NOUN'), ('in', 'ADP'), ('2015', '.'), ('that', 'DET'), ('gave', 'VERB'), ('Google', '.'), ('access', 'NOUN'), ('to', 'PRT'), ("Twitter's", '.'), ('firehose', '.'), ('.', '.')]



[('Twitter', '.'), ('is', 'VERB'), ('an', 'DET'), ('online', '.'), ('news', 'NOUN'), ('and', 'CONJ'), ('social', 'ADJ'), ('networking', 'NOUN'), ('service', 'NOUN'), ('on', 'ADP'), ('which', 'DET'), ('users', 'NOUN'), ('post', 'NOUN'), ('and', 'C[...]<jupyter_text>Method 1 : Viterbi with Rule based Algorithm to handle unknown words Creating rule based tagger, along with patterns that is used to calculate the tags<jupyter_code>patterns = [
    (r'.*ing$', 'VBG'),              # gerund
    (r'.*ed$', 'VBD'),               # past tense
    (r'.*es$', 'VBZ'),               # 3rd singular present
    (r'.*ould$', 'MD'),              # modals
    (r'.*\'s$', 'NN$'),              # possessive nouns
    (r'.*s$', 'NNS'),                # plural nouns
    (r'^-?[0-9]+(.[0-9]+)?$', 'CD'), # cardinal numbers
    (r'.*', 'NN')                    # nouns
]


#Rule based tagger
rule_based_tagger = nltk.RegexpTagger(patterns)<jupyter_output><empty_output><jupyter_text>* pattern - list of pattern to be checked by rule based tagger.* rule_based_tagger - regextagger object Viterbi function implementation that handles unknown words by rule based taggingNote:- In this algorithm if a word is unknown,instead of tagging a random tag for unkown word ,we use rule based tagging method.Please see the comments inside code for understanding of the algorithm.<jupyter_code>def Rule_Viterbi(words, train_bag = train_tagged_words):
    pred_tag = []
    Tagset = list(set([pair[1] for pair in train_bag]))
    #Below for loop parses through list of all words sequentially.
    for key, word in enumerate(words):
        resultant_prob_lst = []
        #Below for loop parses through list of available tagset
        for tag in Tagset:
            #Transition Probability is calculated between two tags.
            #For the starting word there is no intial tag available.so we assign tag "." which indicates starting of the sentence.
            if key == 0:
                trans_prob = tags_trans_df.loc['.', tag]
            else:
                trans_prob = tags_trans_df.loc[pred_tag[-1], tag]
                
            # Computing Emission probability
            emission_count,emission_tot=word_given_tag(words[key], tag)
            emission_prob = emission_count/emission_tot
            # State Probability is the product of emission and transition probability.
            resultant_prob = emission_prob * trans_prob
            resultant_prob_lst.append(resultant_prob)
        
        max_prob = max(resultant_prob_lst)
        #If max_prob=0 , it means word is unknown ,then we use rule based tagger as given in else condition.
        if(max_prob!=0.0):
            #Selecting next tag that has maximum probability of occuring.
            max_prob_tag = Tagset[resultant_prob_lst.index(max_prob)] 
        else:
            #map_tag() is used to map normal POS tagset to universal tagset.
            max_prob_tag=map_tag('en-ptb', 'universal',rule_based_tagger.tag([word])[0][1])
        pred_tag.append(max_prob_tag)
    return list(zip(words, pred_tag))<jupyter_output><empty_output><jupyter_text>Predicting tag for words by viterbi algorithm,handling unknown words by rule based tagging<jupyter_code>#Tagging the POS tags for validation set
start_time = time.time()
tagged_word_seq = Rule_Viterbi(select_valid_words)
end_time = time.time()
time_diff = end_time-start_time
print("Time taken in seconds: ", time_diff)<jupyter_output>Time taken in seconds:  513.1577730178833<jupyter_text>Calculating Accuracy of viterbi algorithm,along with rule based tagging for handling unknown words<jupyter_code>#Getting list of tuples whose actual and predicted value matches
correct_pred_list = [i for i, j in zip(tagged_word_seq, select_valid_tup) if i == j]
#Accuracy is count of tuple that matches / count of total tuple
accuracy = len(correct_pred_list)/len(tagged_word_seq)
accuracy
for i in range(len(test_set)):
    print(str(Rule_Viterbi(test_set[i])))
    print('\n\n')<jupyter_output>[('Android', 'NOUN'), ('is', 'VERB'), ('a', 'DET'), ('mobile', 'ADJ'), ('operating', 'NOUN'), ('system', 'NOUN'), ('developed', 'VERB'), ('by', 'ADP'), ('Google', 'NOUN'), ('.', '.')]



[('Android', 'NOUN'), ('has', 'VERB'), ('been', 'VERB'), ('the', 'DET'), ('best-selling', 'ADJ'), ('OS', 'NOUN'), ('worldwide', 'NOUN'), ('on', 'ADP'), ('smartphones', 'VERB'), ('since', 'ADP'), ('2011', 'NUM'), ('and', 'CONJ'), ('on', 'ADP'), ('tablets', 'NOUN'), ('since', 'ADP'), ('2013', 'NUM'), ('.', '.')]



[('Google', 'NOUN'), ('and', 'CONJ'), ('Twitter', 'NOUN'), ('made', 'VERB'), ('a', 'DET'), ('deal', 'NOUN'), ('in', 'ADP'), ('2015', 'NUM'), ('that', 'ADP'), ('gave', 'VERB'), ('Google', 'NOUN'), ('access', 'NOUN'), ('to', 'PRT'), ("Twitter's", 'X'), ('firehose', 'NOUN'), ('.', '.')]



[('Twitter', 'NOUN'), ('is', 'VERB'), ('an', 'DET'), ('online', 'NOUN'), ('news', 'NOUN'), ('and', 'CONJ'), ('social', 'ADJ'), ('networking', 'NOUN'), ('service', 'NOUN'), ('on', 'ADP'), ('which', 'DET'), ('use[...]<jupyter_text>Method 2:- Viterbi with Probabilistic method to handle unkown words viterbi algorithm where unkown words are handled by probabilistic approach<jupyter_code>def Prob_Viterbi(words, train_bag = train_tagged_words):
    pred_tag = []
    Tagset = list(set([pair[1] for pair in train_bag]))
    #Below for loop parses through list of all words sequentially.
    for key, word in enumerate(words):
        resultant_prob_lst = []
        Trans_prob=[]
        #Below for loop parses through list of available tagset
        for tag in Tagset:
            #Transition Probability is calculated between two tags.
            #For the starting word there is no intial tag available.so we assign tag "." which indicates starting of the sentence.
            if key == 0:
                trans_prob = tags_trans_df.loc['.', tag]
            else:
                trans_prob = tags_trans_df.loc[pred_tag[-1], tag]
                
            # Computing Emission probability
            emission_count,emission_tot=word_given_tag(words[key], tag)
            emission_prob = emission_count/emission_tot
            # State Probability is the product of emission and transition probability.
            resultant_prob = emission_prob * trans_prob
            resultant_prob_lst.append(resultant_prob)
            Trans_prob.append(trans_prob)

        max_prob = max(resultant_prob_lst)
        max_prob_tag = Tagset[resultant_prob_lst.index(max_prob)]
        #If emission probability is 0,then we consider only transition probability to decide next POS tag
        if(max_prob==0.0):
            max_prob = max(Trans_prob)
            max_prob_tag = Tagset[Trans_prob.index(max_prob)]
        pred_tag.append(max_prob_tag)
    return list(zip(words, pred_tag))<jupyter_output><empty_output><jupyter_text>Trans_prob - variable containing list of probability of next POS tag Predicting tag for words by viterbi algorithm,handling unknown words by probabilistic tagging<jupyter_code>#Tagging the POS tags for validation set
start_time = time.time()
tagged_word_seq = Prob_Viterbi(select_valid_words)
end_time = time.time()
time_diff = end_time-start_time
print("Time taken in seconds: ", time_diff)<jupyter_output>Time taken in seconds:  514.9112617969513<jupyter_text>Calculating Accuracy of viterbi algorithm,along with probabilistic tagging for unknown words<jupyter_code>#Getting list of tuples whose actual and predicted value matches
correct_pred_list = [i for i, j in zip(tagged_word_seq, select_valid_tup) if i == j]
#Accuracy is count of tuple that matches / count of total tuple
accuracy = len(correct_pred_list)/len(tagged_word_seq)
accuracy
for i in range(len(test_set)):
    print(str(Prob_Viterbi(test_set[i])))
    print('\n\n')<jupyter_output>[('Android', 'NOUN'), ('is', 'VERB'), ('a', 'DET'), ('mobile', 'ADJ'), ('operating', 'NOUN'), ('system', 'NOUN'), ('developed', 'VERB'), ('by', 'ADP'), ('Google', 'NOUN'), ('.', '.')]



[('Android', 'NOUN'), ('has', 'VERB'), ('been', 'VERB'), ('the', 'DET'), ('best-selling', 'ADJ'), ('OS', 'NOUN'), ('worldwide', 'NOUN'), ('on', 'ADP'), ('smartphones', 'NOUN'), ('since', 'ADP'), ('2011', 'NOUN'), ('and', 'CONJ'), ('on', 'ADP'), ('tablets', 'NOUN'), ('since', 'ADP'), ('2013', 'NOUN'), ('.', '.')]



[('Google', 'NOUN'), ('and', 'CONJ'), ('Twitter', 'NOUN'), ('made', 'VERB'), ('a', 'DET'), ('deal', 'NOUN'), ('in', 'ADP'), ('2015', 'NOUN'), ('that', 'ADP'), ('gave', 'VERB'), ('Google', 'X'), ('access', 'NOUN'), ('to', 'PRT'), ("Twitter's", 'VERB'), ('firehose', 'X'), ('.', '.')]



[('Twitter', 'NOUN'), ('is', 'VERB'), ('an', 'DET'), ('online', 'NOUN'), ('news', 'NOUN'), ('and', 'CONJ'), ('social', 'ADJ'), ('networking', 'NOUN'), ('service', 'NOUN'), ('on', 'ADP'), ('which', 'DET'), ('use[...]
{'fraction_non_alphanumeric': 0.15294230954444765, 'fraction_numerical': 0.010257151112395262, 'mean_word_length': 4.784679665738161, 'pattern_counts': {'":': 0, '<': 94, '<?xml version=': 0, '>': 94, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '25', 'dir': 'jupyter-structured-clean-dedup', 'id': '377722', 'license': 'MIT', 'n_tokens_mistral': 6797, 'n_tokens_neox': 6447, 'n_words': 1952, 'path': 'Notebook.ipynb', 'repo_name': 'hariharan-palanichamy/Parts-of-Speech-Tagging', 'size': '20766'}