<jupyter_start><jupyter_text>Part-of-Speech tagging using modified ViterbiLet's learn how to improve POS tagging of unknown words by modifying Viterbi Algorithm. Below is the structure of the notebook. 1. Tagged Treebank corpus is available (Sample data to training and test data set)   - Basic text and structure exploration   2. Creating HMM model on the tagged data set.   - Calculating Emission Probabaility: P(observation|state)   - Calculating Transition Probability: P(state2|state1)   3. Developing algorithm for Viterbi Heuristic   - Model Prediction and Evaluation4. Modifying Viterbi to deal with unknown words 1. Data Preparation<jupyter_code>#Importing libraries
import nltk, re, pprint
import numpy as np
import pandas as pd
import requests
import matplotlib.pyplot as plt
import seaborn as sns
import pprint, time
import random
from sklearn.model_selection import train_test_split
from nltk.tokenize import word_tokenize
# reading the Treebank tagged sentences
wsj = list(nltk.corpus.treebank.tagged_sents(tagset='universal'))
# Splitting into train and validation
random.seed(1234)
train_set, validation_set = train_test_split(wsj,test_size=0.05)

print(len(train_set))
print(len(validation_set))
# Getting list of tagged words
train_tagged_words = [tup for sent in train_set for tup in sent]
len(train_tagged_words)
# Getting list of tagged words
validation = [tup for sent in validation_set for tup in sent]
len(validation)
# tokens 
tokens = [pair[0] for pair in train_tagged_words]
tokens[:10]
# vocabulary
V = set(tokens)
print(len(V))
# number of tags
T = set([pair[1] for pair in train_tagged_words])
len(T)
print(T)<jupyter_output><empty_output><jupyter_text>2. POS Tagging Algorithm - HMMWe'll use the HMM algorithm to tag the words. Given a sequence of words to be tagged, the task is to assign the most probable tag to the word. To every word w, assign the tag t that maximises the likelihood P(t/w). Since P(t/w) = P(w/t). P(t) / P(w), after ignoring P(w), we have to compute P(w/t) and P(t).P(w/t) is basically the probability that given a tag (say Noun), what is the probability of it being w (say 'building'). This can be computed by computing the fraction of all NNs which are equal to w and dividing by the count of all tags t, i.e. P(w/t) = count(w, t) / count(t). The term P(t) is the probability of tag t, and we assume that a tag will depend only on the previous tag (first-order Markov assumption). In other words, the probability of a tag being Noun will depend only on the previous tag t(n-1). So for e.g. if t(n-1) is a ADJ, then t(n) is likely to be an Noun since adjectives often precede a noun (blue coat, tall building etc.).Given the penn treebank tagged dataset, we can compute the two terms P(w/t) and P(t) and store them in two large matrices (emission and transition probabilities respectively). The matrix of P(w/t) will be sparse, since each word will not be seen with most tags ever, and those terms will thus be zero.   Emission Probabilities<jupyter_code># computing P(w/t) and storing in T x V matrix
t = len(T)
v = len(V)
w_given_t = np.zeros((t, v))
# compute word given tag: Emission Probability
def word_given_tag(word, tag, train_bag = train_tagged_words):
    tag_list = [pair for pair in train_bag if pair[1]==tag]
    count_tag = len(tag_list)
    w_given_tag_list = [pair[0] for pair in tag_list if pair[0]==word]
    count_w_given_tag = len(w_given_tag_list)
    
    return (count_w_given_tag, count_tag)
# examples

# large
print("\n", "large")
print(word_given_tag('large', 'ADJ'))
print(word_given_tag('large', 'VERB'))
print(word_given_tag('large', 'NOUN'), "\n")

# will
print("\n", "will")
print(word_given_tag('will', 'VERB'))
print(word_given_tag('will', 'NOUN'))

# book
print("\n", "book")
print(word_given_tag('book', 'NOUN'))
print(word_given_tag('book', 'VERB'))

# He
print("\n", "He")
print(word_given_tag('He', 'NOUN'))
print(word_given_tag('He', 'PRON'))

# one
print("\n", "one")
print(word_given_tag('one', 'NOUN'))
print(word_given_tag('one', 'NUM'))
print(word_given_tag('one', 'ADP'))<jupyter_output><empty_output><jupyter_text>Transition Probabilities<jupyter_code># compute tag given tag: tag2(t2) given tag1 (t1), i.e. Transition Probability

def t2_given_t1(t2, t1, train_bag = train_tagged_words):
    tags = [pair[1] for pair in train_bag]
    count_t1 = len([t for t in tags if t==t1])
    count_t2_t1 = 0
    for index in range(len(tags)-1):
        if tags[index]==t1 and tags[index+1] == t2:
            count_t2_t1 += 1
    return (count_t2_t1, count_t1)
# examples
print(t2_given_t1(t2='NOUN', t1='ADJ'))
print(t2_given_t1('NOUN', 'DET'))
print(t2_given_t1('NOUN', 'VERB'))
print(t2_given_t1('.', 'NOUN'))
print(t2_given_t1('VERB', 'NOUN'))
#Please note P(tag|start) is same as P(tag|'.')
print(t2_given_t1('DET', '.'))
print(t2_given_t1('VERB', '.'))
print(t2_given_t1('NOUN', '.'))

# creating t x t transition matrix of tags
# each column is t2, each row is t1
# thus M(i, j) represents P(tj given ti)

tags_matrix = np.zeros((len(T), len(T)), dtype='float32')
for i, t1 in enumerate(list(T)):
    for j, t2 in enumerate(list(T)): 
        tags_matrix[i, j] = t2_given_t1(t2, t1)[0]/t2_given_t1(t2, t1)[1]

tags_matrix
# convert the matrix to a df for better readability
tags_df = pd.DataFrame(tags_matrix, columns = list(T), index=list(T))
tags_df
tags_df.loc['.', :]<jupyter_output><empty_output><jupyter_text>2. Build the vanilla Viterbi based POS taggerLet's now use the computed probabilities P(w, tag) and P(t2, t1) to assign tags to each word in the document. We'll run through each word w and compute P(tag/w)=P(w/tag).P(tag) for each tag in the tag set, and then assign the tag having the max P(tag/w).We'll store the assigned tags in a list of tuples, similar to the list 'train_tagged_words'. Each tuple will be a (token, assigned_tag). As we progress further in the list, each tag to be assigned will use the tag of the previous token.Note: P(tag|start) = P(tag|'.')<jupyter_code>len(train_tagged_words)
# Viterbi Heuristic
def Viterbi(words, train_bag = train_tagged_words):
    state = []
    T = list(set([pair[1] for pair in 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 = word_given_tag(words[key], tag)[0]/word_given_tag(words[key], tag)[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)
        print(key)
    return list(zip(words, state))<jupyter_output><empty_output><jupyter_text>Evaluating on Validation Set<jupyter_code># list of tagged words
validation_run_base = [tup for sent in validation_set for tup in sent]

# list of untagged words
validation_tagged_words = [tup[0] for sent in validation_set for tup in sent]
print(len(validation_set))
print(len(validation_tagged_words))
# tagging the test sentences
start = time.time()
validation_Viterbi1 = Viterbi(validation_tagged_words)
end = time.time()
difference = end-start
print("Time taken in seconds: ", difference)
print(len(validation_tagged_words))
#print(test_run_base)
# accuracy
check = [i for i, j in zip(validation_Viterbi1, validation_run_base) if i == j] 
accuracy = len(check)/len(validation_Viterbi1)

print(accuracy)
incorrect_tagged_cases = [[validation_run_base[i-1],j] for i, j in enumerate(zip(validation_Viterbi1, validation_run_base)) if j[0]!=j[1]]
incorrect_tagged_cases
## Testing
test_cases_shared = '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, <NAME> 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.'
test_words = word_tokenize(test_cases_shared)

start = time.time()
tagged_seq = Viterbi(test_words)
end = time.time()
difference = end-start
print(tagged_seq)
print(difference)<jupyter_output><empty_output><jupyter_text>3. Solve the problem of unknown words  Modification -1: tags of all unknown words are replaced by Noun (Noun being the most common tag)<jupyter_code>## Modification -1: all unknown words are replaced by Noun (Noun being the most common tag)

def Viterbi_modf1(test_words, train_bag = train_tagged_words):
    tagged_seq = Viterbi(test_words)
    V = list(set([pair[0] for pair in train_bag]))
    
    words = [pair[0] for pair in tagged_seq]
    Viterbi_tags = [pair[1] for pair in tagged_seq]
    
    for key, word in enumerate(words):
        if word not in V:
            Viterbi_tags[key] = 'NOUN'
            
    
    return list(zip(words, Viterbi_tags))           
    
validation_Viterbimodf1 = Viterbi_modf1(validation_tagged_words)
# accuracy
check_modf1 = [i for i, j in zip(validation_Viterbimodf1, validation_run_base) if i == j] 
accuracy = len(check_modf1)/len(validation_Viterbimodf1)

accuracy
start = time.time()
tagged_seq2_test = Viterbi_modf1(test_words)
end = time.time()
difference = end-start

tagged_seq2_test<jupyter_output><empty_output><jupyter_text>Modification -2: Rules-based algorithm for unknown words and making it work in tandem with Viterbi<jupyter_code>## Viterbi Modification -2: 
## 1. all unknown words with first letter capital/ all letters capitals are tagged as Noun, numbers are tagged as NUM, words ending with '-ous' as ADJ, and rest as Noun

def Viterbi_modf2(test_words, train_bag = train_tagged_words):
    tagged_seq = Viterbi(test_words)
    V = list(set([pair[0] for pair in train_bag]))
    
    words = [pair[0] for pair in tagged_seq]
    Viterbi_tags = [pair[1] for pair in tagged_seq]
    
    for key, word in enumerate(words):
        if word not in V:
            ## word ending with '-ous'
            if word[-3:] == 'ous':
                Viterbi_tags[key] = 'ADJ'
            
            ## if word is number
            elif (word.isdigit() == True or word[:-2].isdigit() == True):
                Viterbi_tags[key] = 'NUM'
                
            ## all letters capitalised
            elif word.upper() == word:
                Viterbi_tags[key] = 'NOUN'
                
            ## first letter is capitalised:
            elif word[0].upper() == word[0]:
                Viterbi_tags[key] = 'NOUN' 
                
            else: 
                Viterbi_tags[key] = 'NOUN'
    
    return list(zip(words, Viterbi_tags))       
validation_Viterbimodf2 = Viterbi_modf2(validation_tagged_words)


# accuracy
check_modf2 = [i for i, j in zip(validation_Viterbimodf2, validation_run_base) if i == j] 
accuracy = len(check_modf2)/len(validation_Viterbimodf2)

accuracy

## changing the code of Num to incorporate st, th, nd improved the accuracy by 1%
start = time.time()
tagged_seq3_test = Viterbi_modf2(test_words)
end = time.time()
difference = end-start

tagged_seq3_test<jupyter_output><empty_output><jupyter_text>Viterbi Modification -3: State probability is dependent only on transition probability for the unknown words<jupyter_code># Viterbi Modification -3: state probability is dependent only on transition probability
def Viterbi_modf3(words, train_bag = train_tagged_words):
    state = []
    T = list(set([pair[1] for pair in 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 = word_given_tag(words[key], tag)[0]/word_given_tag(words[key], tag)[1]
            
            if word in V:
                state_probability = transition_p * emission_p              
            else:
                state_probability = 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)
        print(key)
    return list(zip(words, state))
# tagging the test sentences
start = time.time()
validation_Viterbimodf3 = Viterbi_modf3(validation_tagged_words)
end = time.time()
difference1 = end-start
# accuracy
check = [i for i, j in zip(validation_Viterbimodf3, validation_run_base) if i == j] 

accuracy = len(check)/len(validation_Viterbimodf3)
print(accuracy)
start = time.time()
tagged_seq3_test = Viterbi_modf3(test_words)
end = time.time()
difference = end-start
tagged_seq3_test<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09826042652303661, 'fraction_numerical': 0.012591891695174322, 'mean_word_length': 3.826132771338251, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '200143', 'license': 'Apache-2.0', 'n_tokens_mistral': 4593, 'n_tokens_neox': 4369, 'n_words': 1472, 'path': '05Natural Language Processing/03Assignment - Syntactic Analysis/Part+1-+POS+Tagging-Viterbi_modified+Soln.ipynb', 'repo_name': 'talk2sunil83/UpgradLearning', 'size': '13745'}