<jupyter_start><jupyter_text>NLP HW 3: Hidden Markov Model  Preliminaries Downloading data<jupyter_code># from https://medium.com/@Keshav31/colab-features-download-and-upload-e1ec537a83df
from urllib.request import urlretrieve
import os
from zipfile import ZipFile

url = 'https://ttic.uchicago.edu/~kgimpel/teaching/31210-s19/data/31210-s19-hw3.zip'
file = '31210-s19-hw3.zip'

if not os.path.isfile(file):
    urlretrieve(url,file)

with ZipFile(file) as zipf:
    zipf.extractall()

!rm -rf data/
!mkdir data/
!mv 31210-s19-hw3/* data/
!rm -rf 31210-s19-hw3.zip 31210-s19-hw3/<jupyter_output><empty_output><jupyter_text>Loading training data and doing bigram counts<jupyter_code>from collections import Counter
    
word_tag_counts = Counter()
tag_bigram_counts = Counter()
vocab = set()
pos_tags = set()
    
start_token = ('<s>', '<s>')
end_token = ('</s>', '</s>')
    
with open('data/en_ewt.train', 'r') as trainfile:
    prev = start_token
    for row in trainfile.readlines():
        row = row.split()
        if len(row) == 0:
            row = end_token
        elif prev[0] == '</s>': 
            prev = start_token
        if row[0] not in ['<s>', '</s>']:
            vocab.add(row[0])
            pos_tags.add(row[1])
        word_tag_counts[(row[0], row[1])] += 1
        tag_bigram_counts[(prev[1], row[1])] += 1
        prev = row

print('data loaded')
print('vocab size:', str(len(vocab)))
print('num pos tags:', str(len(pos_tags)))<jupyter_output>data loaded
vocab size: 19380
num pos tags: 50<jupyter_text>1. Supervised Parameter Estimation for HMMs  a) Compute probabilities<jupyter_code>import numpy as np

log_p_tau = {}
lambda_tau = 0.1

for y_p in list(pos_tags):
    denom = sum([tag_bigram_counts[(y_p, y_pp)] + lambda_tau
                       for y_pp in list(pos_tags) + ['</s>']])
    
    for y in list(pos_tags) + ['</s>']:
        numer = tag_bigram_counts[(y_p, y)]
        log_p_tau[(y, y_p)] = np.log((numer + lambda_tau)/denom)

for y in list(pos_tags):
    denom = sum([tag_bigram_counts[('<s>', y_pp)] + lambda_tau
                        for y_pp in list(pos_tags)])
    numer = tag_bigram_counts[('<s>', y)]
    log_p_tau[(y, '<s>')] = np.log((numer + lambda_tau)/denom)

log_p_eta = {}
lambda_eta = 0.001
for y in list(pos_tags):
    denom = sum([word_tag_counts[(x_p, y)] + lambda_eta
                       for x_p in list(vocab)])
    for x in list(vocab):
        numer = word_tag_counts[(x, y)]
        log_p_eta[(x, y)] = np.log((numer + lambda_eta)/denom)

# make sure that all the zero probs are right
log_p_tau[('</s>', '<s>')] = -float('inf')
for y in list(pos_tags):
    log_p_tau[('<s>', y)] = -float('inf')
    log_p_tau[(y, '</s>')] = -float('inf')<jupyter_output><empty_output><jupyter_text>b) Check Probabilities<jupyter_code>log_p_tau_filtered = {k: v for k, v in log_p_tau.items()
                        if k[1] == '<s>'}

topkeys = sorted(log_p_tau_filtered, 
                 key=log_p_tau_filtered.get, 
                 reverse=True)[:5]

for key in topkeys:
    print(key[0], np.exp(log_p_tau[key]))

log_p_eta_filtered = {k: v for k, v in log_p_eta.items()
                        if k[1] == 'JJ'}

topkeys = sorted(log_p_eta_filtered, 
                 key=log_p_eta_filtered.get, 
                 reverse=True)[:10]

for key in topkeys:
    print(key[0], np.exp(log_p_eta[key]))<jupyter_output>other 0.023068970800638806
good 0.021605646023451937
new 0.016785282051542234
many 0.013686476641028844
great 0.013686476641028844
same 0.011362372583143814
sure 0.009554736093677673
last 0.009210424381398406
few 0.008952190597188959
little 0.008435723028770062<jupyter_text>2. Preliminaries for Inference with HMMs  a) Log-probability calculation Functions to calculate log-probability and accuracy of tagged sentence<jupyter_code># takes a list of (word, tag) tuples
# should start with <s>
def log_sentence_probability(s):
    total = log_p_tau[('</s>', s[-1][1])]
    for i in range(1, len(s)):
        total += log_p_tau[(s[i][1], s[i-1][1])]
        total += log_p_eta[(s[i][0], s[i][1])] 
    return total

def calc_accuracy_rate(sentences, gold_standards):
    total = 0
    total_correct = 0
    assert(len(sentences) == len(gold_standards))
    for s_num in range(len(sentences)):
        for w_num in range(len(sentences[s_num])):
            total += 1
            if sentences[s_num][w_num][1] == gold_standards[s_num][w_num][1]:
                total_correct += 1
    return total_correct / total<jupyter_output><empty_output><jupyter_text>Reusable function to score prediction functions<jupyter_code>import time

# start_work_func prepares all memoization
#     takes no args, returns nothing
# pred_func does predictions
#     takes a sentence of [(word, gs_tag)]
#     returns predictions [(word, pred_tag)]
def score_prediction_function(start_work_func, pred_func, do_setup=True):
    start_time = time.time()
    if do_setup:
        print('doing setup, building lookup tables...')
        start_work_func()
    print('making predictions...')
    with open('data/en_ewt.dev', 'r') as trainfile:
        current_sent = [start_token]
        predictions = []
        gold_standards = []
        total_log_prob = 0
        lines = trainfile.readlines()
        for row in lines:
            row = row.split()
            if len(row) == 0:
                gold_standards.append(current_sent)
                pred = pred_func(current_sent)
                log_prob = log_sentence_probability(pred)
                predictions.append(pred)
                total_log_prob += log_prob
                current_sent = [start_token]
            else:
                current_sent.append(row)

    end_time = time.time()
    elapsed_time = end_time - start_time

    print()
    tagging_accuracy = calc_accuracy_rate(predictions, gold_standards)
    print('tagging accuracy on DEV:', tagging_accuracy)
    print('time required for predictions (s):', elapsed_time)
    print('log-probability of predictions:', total_log_prob)
start_work_func = lambda: None
pred_func = lambda x: x

score_prediction_function(start_work_func, pred_func)<jupyter_output>doing setup, building lookup tables...
making predictions...

tagging accuracy on DEV: 1.0
time required for predictions (s): 0.06492257118225098
log-probability of predictions: -169936.39757772826<jupyter_text>b) Local predictor baseline<jupyter_code>def local_predictor_setup():
    global memoize_best_tags
    for ix, (k, v) in enumerate(log_p_eta.items()):
        if k[0] not in memoize_best_tags:
            memoize_best_tags[k[0]] = k[1]
        else:
            if v > log_p_eta[(k[0], memoize_best_tags[k[0]])]:
                memoize_best_tags[k[0]] = k[1]

def local_predictor(s):
    prediction = [start_token]
    for gold_standard in s[1:]:
        word = gold_standard[0]
        prediction.append((word, memoize_best_tags[word]))
    return prediction

memoize_best_tags = {}
score_prediction_function(local_predictor_setup, local_predictor)<jupyter_output>doing setup, building lookup tables...
making predictions...

tagging accuracy on DEV: 0.8137153800824986
time required for predictions (s): 1.1839382648468018
log-probability of predictions: -186408.12397588338<jupyter_text>3. Greedy Left-to-Right Algorithms  a) Implement Greedy Left-to-Right<jupyter_code>G_t_calc = lambda x_t, y, G_tm1: log_p_eta[(x_t, y)] + log_p_tau[(y, G_tm1)]

def greedy_ltr_setup():
    global G_t_memo
    for x_t in vocab:
        for G_tm1 in list(pos_tags) + ['<s>']:
            max_so_far = -float('inf')
            for y in pos_tags:
                prob = G_t_calc(x_t, y, G_tm1)
                if prob > max_so_far:
                    G_t_memo[(x_t, G_tm1)] = y
                    max_so_far = prob

def greedy_ltr(sentence):
    G_t = [start_token]
    for word in sentence[1:-1]:
        G_t.append((word[0], G_t_memo[(word[0], G_t[-1][1])]))
    max_so_far = -float('inf')
    x_T = sentence[-1][0]
    for y in pos_tags:
        prob = G_t_calc(x_T, y, G_t[-1][1]) + log_p_tau[('</s>', y)]
        if prob > max_so_far:
            final_g = y
            max_so_far = prob
    G_t.append((x_T, final_g))
    return G_t

G_t_memo = {}
score_prediction_function(greedy_ltr_setup, greedy_ltr)<jupyter_output>doing setup, building lookup tables...
making predictions...

tagging accuracy on DEV: 0.8833235120801414
time required for predictions (s): 30.3159396648407
log-probability of predictions: -166188.89186830737<jupyter_text>3. Greedy Right-to-Left Algorithms  a) Implement Greedy Right-to-Left<jupyter_code>R_t_calc = lambda x_t, y, R_tp1: log_p_eta[(x_t, y)] + log_p_tau[(R_tp1, y)]

def greedy_rtl_setup():
    global R_t_memo
    for x_t in vocab:
        for R_tp1 in list(pos_tags) + ['</s>']:
            max_so_far = -float('inf')
            for y in pos_tags:
                prob = R_t_calc(x_t, y, R_tp1)
                if prob > max_so_far:
                    R_t_memo[(x_t, R_tp1)] = y
                    max_so_far = prob

def greedy_rtl(sentence):
    R_t = [end_token]
    for i in reversed(sentence[2:]):
        R_t.append((i[0], R_t_memo[(i[0], R_t[-1][1])]))
    first_y = None
    max_val = -float('inf')
    for y in pos_tags:
        cur_val = log_p_eta[(sentence[1][0], y)] \
                + log_p_tau[(R_t[-1][1], y)]\
                + log_p_tau[(y, '<s>')]
        if cur_val > max_val:
            max_val = cur_val
            first_y = y
    R_t.append((sentence[1][0], first_y))
    R_t.append(start_token)
    return list(reversed(R_t))[:-1]

R_t_memo = {}
score_prediction_function(greedy_rtl_setup, greedy_rtl)<jupyter_output>doing setup, building lookup tables...
making predictions...

tagging accuracy on DEV: 0.8148939304655274
time required for predictions (s): 30.373260021209717
log-probability of predictions: -176754.90096961826<jupyter_text>b) Results Discussion| Algorithm | Runtime (s) | Tag Accuracy | Log-Prob of Preds ||-----------|-------------|--------------|-------------------|| Local     | 1.23        | 81.37%       | -186408           || GLTR      | 30.11       | 88.33%       | -166188           || GRTL      | 30.62       | 81.49%       | -176754           || Viterbi      | 77.72       | 90.19%       | -163206           | The runtime of GLTR and GRTL were pretty much the same, because they did the exact same amount of work, which was over 50x the work that the local implementation had to do, but for some reason took less than 30x the runtime... Probably has something to do with caching.GRTL did better than local in both log-prob and accuract, because it incorporated more contextual information into its predictions. This is unsurprising.GRTL had noticably lower tag accuracy and log-prob than GLTR. I think this is possibly because the first word in a sentence is pretty likely to be a noun, so the first prediction in GLTR is likely to be correct and will start the algorithm off right. The last thing in a sentence is much more variable, so it's harder to predict, so the odds that the GRTL algorithm will go off the rails right at the start are higher. Also, I think it's possible that because humans understand sentences as they hear them instead of waiting for the sentence to end and then thinking about it, there is probably more "predictive power" coming from the previous words in a sentence than the ones after. It makes sense that language would evolve in that way, because it would make it easier to understand sentences as they are said.  5. Exact Inference with Viterbi<jupyter_code>viterbi_setup = lambda: None

def VL(s, t, y):
    global V, L
    if t == 1:
        V[(t, y)] = log_p_eta[(s[1][0], y)] + log_p_tau[(y, '<s>')]
        L[(t, y)] = None
    elif (t, y) not in V:     
        max_Vty = -float('inf')
        max_Lty = None
        for y_p in pos_tags:
            V_tm1_yp, _ = VL(s, t-1, y_p)
            val = log_p_eta[(s[t][0], y)] + log_p_tau[(y, y_p)] + V_tm1_yp
            if val > max_Vty:
                max_Vty = val
                max_Lty = y_p
        V[(t, y)] = max_Vty
        L[(t, y)] = max_Lty
    return V[(t, y)], L[(t, y)]
    
def goal(s):
    max_goal = -float('inf')
    max_y_hat_t = None
    for y_p in pos_tags:
        last_v, _ = VL(s, len(s) - 1, y_p)
        cur_goal = log_p_tau[('</s>', y_p)] + last_v
        if cur_goal > max_goal:
            max_goal = cur_goal
            max_y_hat_t = y_p
    return max_goal, max_y_hat_t
    
def viterbi_predict(sent):
    global V, L
    V = {}
    L = {}
    rev_ys = [(sent[-1][0], goal(sent)[1])]
    for ix in reversed(range(1, len(sent) - 1)):
        rev_ys.append((sent[ix][0], VL(sent, ix + 1, rev_ys[-1][1])[1]))
    return [start_token] + list(reversed(rev_ys))
    
    
score_prediction_function(viterbi_setup, viterbi_predict)<jupyter_output>doing setup, building lookup tables...
making predictions...

tagging accuracy on DEV: 0.9019225103123159
time required for predictions (s): 77.71943783760071
log-probability of predictions: -163206.89965932636
{'fraction_non_alphanumeric': 0.12530769230769231, 'fraction_numerical': 0.05030769230769231, 'mean_word_length': 2.910075187969925, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 66, 'https://': 2, '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': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '664940', 'license': 'Unlicense', 'n_tokens_mistral': 5063, 'n_tokens_neox': 4611, 'n_words': 1164, 'path': 'hmm.ipynb', 'repo_name': 'laudiacay/for-the-love-of-bayes', 'size': '13000'}