<jupyter_start><jupyter_text>CS 401: Natural Language Processing   Project 4    <NAME>   Question 1<jupyter_code>import numpy
import warnings
numpy.set_printoptions(precision=3)
def Viterbi(A, B, x):
    '''Viterbi decoding algorithm (logarithmic probabilities)
       A is the transition probability matrix (includes start state 0)
       B is the emission probability matrix (includes 0's for state 0)
         - stored as a dictionary of (state,symbol) pairs
       x is the sequence of observations'''
       
    n = len(x)                                        # number of observations (t)
    m = len(A)                                        # number of states (including start state)
    v = numpy.zeros((m, n + 1))  - numpy.inf          # matrix of v[q,i] values, initialized to -infinity
    v[0, 0] = 0                                       # log prob of starting in the start state is 0
    s = numpy.zeros((m, n + 1), dtype = numpy.int32)  # s[q,i] = optimal previous state for v[q,i]

    ####################################################################################
    # Fill in the tables (v and s), column by column, according to the recurrence, HERE.
    for i in range(1,n+1): # words
        for j in range(m): # states
            lister = []
            for k in range(m):
                value = v[k,i-1]+A[k,j]+B[j,x[i-1]]
                #print("Previous log prob:",v[k,i-1])
                #print("A value:",A[k,j])
                #print("B value",B[j,x[i-1]],"i:",i,"j:",j,"k:",k)
                lister.append(value)
            v[j,i] = max(lister)
            s[j,i]=lister.index(max(lister))
    ####################################################################################

    maxS = numpy.argmax(v[:,n])  # index (state) of the maximum value in the last column of v
    maxP = v[maxS, n]            # the maximum value in the last column of v

    # Construct the optimal sequence of states by backtracking.

    path = numpy.zeros(n + 1, dtype = numpy.int32)  # init state sequence to be a list of zeroes
    path[n] = maxS                                  # start in state maxS
    for i in range(n - 1, -1, -1):                  # and follow the "links" backwards
        path[i] = s[path[i + 1], i + 1]
        
    #print('maxS = ', maxS)
    #print('v =\n', v)
    #print('s =\n', s)
    return maxP, path
warnings.filterwarnings('ignore')
def main():
    stateNames = ['<s>', 'NNP', 'MD', 'VB', 'JJ', 'NN', 'RB', 'DT']
    
    #                  <s>   NNP     MD      VB      JJ      NN      RB      DT
    A = numpy.matrix([[0.0, 0.2767, 0.0006, 0.0031, 0.0453, 0.0449, 0.0510, 0.2026],  # <s> start
                      [0.0, 0.3777, 0.0110, 0.0009, 0.0084, 0.0584, 0.0090, 0.0025],  # NNP
                      [0.0, 0.0008, 0.0002, 0.7968, 0.0005, 0.0008, 0.1698, 0.0041],  # MD
                      [0.0, 0.0322, 0.0005, 0.0050, 0.0837, 0.0615, 0.0514, 0.2231],  # VB
                      [0.0, 0.0366, 0.0004, 0.0001, 0.0733, 0.4509, 0.0036, 0.0036],  # JJ
                      [0.0, 0.0096, 0.0176, 0.0014, 0.0086, 0.1216, 0.0177, 0.0068],  # NN
                      [0.0, 0.0068, 0.0102, 0.1011, 0.1012, 0.0120, 0.0728, 0.0479],  # RB
                      [0.0, 0.1147, 0.0021, 0.0002, 0.2157, 0.4744, 0.0102, 0.0017]]) # DT    
    Alog = numpy.log(A)
                      
    B = {(0, 'Janet'): 0.0, (0, 'will'): 0.0, (0, 'back'): 0.0, (0, 'the'): 0.000048, (0, 'bill'): 0.0,
         (1, 'Janet'): 0.000032, (1, 'will'): 0.0, (1, 'back'): 0.0, (1, 'the'): 0.000048, (1, 'bill'): 0.0,
         (2, 'Janet'): 0.0, (2, 'will'): 0.308431, (2, 'back'): 0.0, (2, 'the'): 0.0, (2, 'bill'): 0.0,
         (3, 'Janet'): 0.0, (3, 'will'): 0.000028, (3, 'back'): 0.000672, (3, 'the'): 0.0, (3, 'bill'): 0.000028,
         (4, 'Janet'): 0.0, (4, 'will'): 0.0, (4, 'back'): 0.000340, (4, 'the'): 0.0, (4, 'bill'): 0.0,
         (5, 'Janet'): 0.0, (5, 'will'): 0.000200, (5, 'back'): 0.000223, (5, 'the'): 0.0, (5, 'bill'): 0.002337,
         (6, 'Janet'): 0.0, (6, 'will'): 0.0, (6, 'back'): 0.010446, (6, 'the'): 0.0, (6, 'bill'): 0.0,
         (7, 'Janet'): 0.0, (7, 'will'): 0.0, (7, 'back'): 0.0, (7, 'the'): 0.506099, (7, 'bill'): 0.0}
    
    Blog = {(s, t): numpy.log(B[(s,t)]) for (s, t) in B}
         
    words = ['Janet', 'will', 'back', 'the', 'bill']
    
    prob, path = Viterbi(Alog, Blog, words)
    print("Probability:",prob)
    for i in range(len(words)):
        print(words[i], stateNames[path[i+1]])
    
main()<jupyter_output>Probability: -33.8388667762
Janet NNP
will MD
back VB
the DT
bill NN<jupyter_text>Question 2<jupyter_code>import time
import nltk
from nltk.corpus import brown
import numpy as np
#nltk.download('universal_tagset')<jupyter_output><empty_output><jupyter_text>Creating training and testing sets<jupyter_code>taggedWords = brown.tagged_words(tagset='universal')
Fulldata = [(word,tag) for (word,tag) in taggedWords]
from sklearn.model_selection import train_test_split
train, test = train_test_split(Fulldata, test_size=0.2,random_state=101) # setting seed 
print(len(train)/(len(train)+len(test))*100) # approx. 80-20 split<jupyter_output>79.99994832895851<jupyter_text>Getting tags (states)<jupyter_code>tag_fd = nltk.FreqDist(tag for (word, tag) in train) # contains unique tags with their frequencies
alltags = {}
index=1
for pos in tag_fd:
    alltags[pos] = index
    index+=1
alltags['<s>'] = 0
for tag in alltags:
    print(tag,alltags[tag])<jupyter_output>NOUN 1
VERB 2
ADP 3
. 4
DET 5
ADJ 6
CONJ 7
PRT 8
NUM 9
PRON 10
ADV 11
X 12
<s> 0<jupyter_text>Initial probabilities<jupyter_code>x = time.time()
init = {}
see = brown.tagged_sents(tagset='universal')
Fullsent = [sent for sent in see]
trainsent, testsent = train_test_split(Fullsent, test_size=0.2,random_state=101) # using same seed 
for sent in trainsent:
    if ('<s>',sent[0][1]) not in init:
        init[('<s>',sent[0][1])] = 0
    init[('<s>',sent[0][1])] +=1
    init[(sent[0][1],'<s>')] = 0
init[('<s>','<s>')]=0
for each in init:
    init[each] = init[each]/len(trainsent)
print("Run-time: ",time.time()-x,"seconds")<jupyter_output>Run-time:  5.346083164215088 seconds<jupyter_text>Constructing transition probability matrix<jupyter_code>x = time.time()
bigramsFreq = {}
allTags = [tag for (word, tag) in train]
bigrams = nltk.ngrams(allTags, 2) # getting bigrams
bigramsFreq = dict(nltk.FreqDist(bigrams))
bigramsFreq2 = {**bigramsFreq}
for each in bigramsFreq2:
    for other in bigramsFreq2:
        if (each[0],other[1]) not in bigramsFreq2: # need to get all combinations of states
            bigramsFreq[each[0],other[1]]=0
del bigramsFreq2
print("Run-time: ",time.time()-x,"seconds")
for pos in tag_fd:
    for each in bigramsFreq:
        if each[0]==pos:
            bigramsFreq[each]=bigramsFreq[each]/tag_fd[pos]
AllBigrams = {**bigramsFreq, **init}
print(len(AllBigrams)) # 13x13 matrix
AllBigrams2 = {**AllBigrams} # deep-copying dictionary
for first,second in AllBigrams2:
    AllBigrams[(alltags[first],alltags[second])] = AllBigrams[(first,second)]
    del AllBigrams[(first,second)]
del AllBigrams2
A = np.zeros((len(alltags), len(alltags))) # square matrix
A = np.matrix(A)
for first,second in AllBigrams:
    A[first,second] = AllBigrams[(first,second)]
A<jupyter_output><empty_output><jupyter_text>Constructing emission probability matrix<jupyter_code># Initializing B matrix with 0s
x = time.time()
B = {}
for tag in alltags:
    for w,t in train:
        B[alltags[tag],w]=0
print("Runtime (in seconds):",time.time()-x)
# For start of sentence word emission probabilities
for sent in trainsent:
    if (0,sent[0][0]) in B:
        B[0,sent[0][0]]+=1
for each in B:
    if each[0]==0:
        B[each] = B[each]/len(trainsent)
# For all other tags' word emission probabilities
word_tag = dict(nltk.FreqDist((word,tag) for (word, tag) in train))
for word,tag in word_tag:
    B[alltags[tag],word]=word_tag[word,tag]/tag_fd[tag]
B<jupyter_output><empty_output><jupyter_text>Question 3<jupyter_code>import random
def substitute(sent,B):
    """
        Helper function to replace unknown words in the
        testset with the most likely tag for it based on
        word structure.
        
        Parameters:
              sent: sentence with words to be tagged
                 B: emission matrix to check if word in 
                    sentence is not in the training set.
      
        Return value: sentence with adjusted words
    """
    lister = []
    sent2 = []
    for key in B:
        lister.append(key[1])
    lister = list(set(lister))
    for word in sent:
        if word not in lister:
            if word[0].isupper() or word[-1]=='s' or word[-2:]=="'s": # possible noun endings
                word = tag_look(1,B) # noun tag
            elif word[-2:]=="ed" or word[-3:]=="ing": # possible verb endings
                word = tag_look(2,B) # verb tag
            elif word[-2:]=="ly": # possible adverb ending
                word = tag_look(11,B) # adverb tag
            else:
                index = random.randint(1,12) # picks a random tag to assign to a
                                             # word (more variance than the max. 'unk' tag)
                word = tag_look(index,B) # else just pick a random tag
        sent2.append(word)
    return sent2
def tag_look(i,Blog):
    """
        Helper function to find the most probable word
        within a given tag category
        
        Parameter:
                i: index of tag
             Blog: Emission matrix   
        Return value: Most common word to appear in tag 'i'
    """
    tups = []
    for key in Blog:
        if key[0] == i:
            tups.append((key[1],Blog[key]))
    tups.sort(reverse=True, key=lambda tup: tup[1])
    return tups[0][0]
warnings.filterwarnings('ignore')
stateNames = ['<s>', 'NOUN', 'VERB', 'ADP', '.', 'DET', 'ADJ', 'CONJ', 'PRT', 'NUM', 'PRON', 'ADV', 'X']
Alog = numpy.log(A)
Blog = {(s, t): numpy.log(B[(s,t)]) for (s, t) in B}
x= time.time()
TP = 0
Total = 0
for sentTags in testsent: # Takes approximately an hour to run
    sent = [x[0] for x in sentTags]
    tags = [x[1] for x in sentTags]
    sent2 = substitute(sent,Blog)   # helper function call to assign probabilities to known words in sentence
    prob, path = Viterbi(Alog, Blog, sent2)
    for i in range(len(sent)):
        if (stateNames[path[i+1]]==tags[i]):
            TP += 1 # True positives
        Total +=1   # Total words
print("Time taken: ",time.time()-x) 
print("Accuracy:",round(TP/Total*100,2),"%")<jupyter_output>Accuracy: 95.72 %
{'fraction_non_alphanumeric': 0.17478211443728686, 'fraction_numerical': 0.06403940886699508, 'mean_word_length': 2.6516776202006227, 'pattern_counts': {'":': 3, '<': 41, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '622773', 'license': 'MIT', 'n_tokens_mistral': 4266, 'n_tokens_neox': 3779, 'n_words': 1055, 'path': 'Part_of_speech_tagger.ipynb', 'repo_name': 'Anamay-Agnihotri/Machine-Learning', 'size': '10565'}