<jupyter_start><jupyter_text>Assignment 5: Nonparametric Bayesian Segmentation  Setup 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-hw5.zip'
file = '31210-s19-hw5.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-hw5/* data/
!rm -rf 31210-s19-hw5.zip 31210-s19-hw5/<jupyter_output><empty_output><jupyter_text>Parsing in data<jupyter_code>with open('data/cbt-characters.txt') as f:
    sentences = f.readlines()
    sentences = [s.strip() for s in sentences]

with open('data/cbt-boundaries.txt') as f:
    gs_boundaries = f.readlines()
    gs_boundaries = [b.strip() for b in gs_boundaries]

    
assert len(sentences) == len(gs_boundaries)
for b in gs_boundaries:
    for bi in b:
        assert bi in ['0', '1']
        
# build character set for p_char
char_set = set()
for s in sentences:
    for l in s:
        char_set.add(l)

print('sentences loaded and validated.')
print(f'{len(char_set)} characters found.')<jupyter_output>sentences loaded and validated.
54 characters found.<jupyter_text>Calculate BPA for unsegmented corpus<jupyter_code>def calc_bpa(gs_boundaries, boundaries):
    assert len(gs_boundaries) == len(boundaries)
    bound_ctr = 0
    correct = 0
    total = 0
    for sent_ix in range(len(sentences)):
        for char in range(len(sentences[sent_ix][:-1])):
            total += 1
            correct += int(boundaries[sent_ix][char] == gs_boundaries[sent_ix][char])
        bound_ctr += 1
    return correct/total
        
unseg_boundaries = [['0' for _ in sent[:-1]] + ['1'] for sent in sentences]
print(f'unsegmented BPA: {calc_bpa(gs_boundaries, unseg_boundaries)}')<jupyter_output>unsegmented BPA: 0.7327530010591656<jupyter_text>1. Gibbs Sampling Implementation<jupyter_code>import collections

TOT_TOK = '___TOTAL___'

char_probs = {l: 1/len(char_set) for l in char_set}
G_0_memo = {}

def G_0(y, BETA):
    global char_probs
    if (y, BETA) in G_0_memo:
        return G_0_memo[(y, BETA)]
    ret = (1-BETA)**(len(y) - 1) * BETA
    for y_i in y:
        ret *= char_probs[y_i]
    G_0_memo[(y, BETA)] = ret
    return ret

def initialize_seg_counts(sentences, boundaries):
    counter = collections.Counter() 
    for sx, sent in enumerate(sentences):
        start_idx = 0
        for i in range(len(sent)):
            if boundaries[sx][i] == '1':
                counter[sent[start_idx:i+1]] += 1
                counter[TOT_TOK] += 1
                start_idx = i+1
    return counter

# testing segment counter
print(initialize_seg_counts(['thecowsaysmoo'], [['0','0','1','0','0','1','0','0','0','1','0','0','1']]))
import random

def choose_new_value(sentences, boundaries, counts, s_ix, b_ix, s, BETA, GAMMA):
    y_full_start = 0
        
    sentences = sentences[s_ix]
    cur_bnd = boundaries[s_ix]
    for i in range(b_ix-1, -1, -1):
        if cur_bnd[i] == 1:
            y_full_start = i + 1
            break
    y_full_stop = len(sentences)
    for i in range(b_ix+1, len(sentences)):
        if cur_bnd[i] == 1:
            y_full_stop = i + 1
            break
    
    y_full = sentences[y_full_start:y_full_stop + 1]
    y_prev = sentences[y_full_start:b_ix + 1]
    y_next = sentences[b_ix + 1:y_full_stop + 1]
    
    old_bi = cur_bnd[b_ix]
    
    if old_bi == 1:
        n_y_prev = counts[y_prev] - 1
        n_y_next = counts[y_next] - 1
        n_y_full = counts[y_full]
        n_y_total = counts[TOT_TOK] - 2
    else:
        n_y_prev = counts[y_prev]
        n_y_next = counts[y_next]
        n_y_full = counts[y_full] - 1
        n_y_total = counts[TOT_TOK] - 1
    
    p_bi_0 = (n_y_full + s*G_0(y_full, BETA)) / (n_y_total + s)
    p_bi_1 = (n_y_prev + s*G_0(y_prev, BETA))\
                * (1 - GAMMA)\
                * (n_y_next + int(y_prev == y_next) + s*G_0(y_next, BETA))\
                / ((n_y_total + s) * (n_y_total + 1 + s))
    
    
    new_bi = str(int(random.random() * (p_bi_0 + p_bi_1) < p_bi_0))[0]
    
    boundaries[s_ix][b_ix] = new_bi
    
    if old_bi == new_bi:
        return 0, boundaries
    elif old_bi == 1 and new_bi == 0:
        counts[y_full] += 1
        counts[y_prev] -= 1
        counts[y_next] -= 1
        counts[TOT_TOK] -= 1
    elif old_bi == 0 and new_bi == 1:
        counts[y_full] -= 1
        counts[y_prev] += 1
        counts[y_next] += 1
        counts[TOT_TOK] += 1

    return 1, boundaries
    
    
def gibbs_samp_iter(sentences, cur_boundaries, counts, s, BETA, GAMMA, n):
    nbc = 0
    for s_ix in range(len(sentences)):
        for b_ix in range(len(sentences[s_ix]) - 1):
            ct, cur_boundaries = choose_new_value(sentences, cur_boundaries, 
                         counts, s_ix, b_ix, s, BETA, GAMMA)
            nbc += ct
    print(f'finished iteration {n}')
    print(f'    BPA: {calc_bpa(gs_boundaries, cur_boundaries)}')
    print(f'    NBC: {nbc}')
    return cur_boundaries
            
    
def gibbs_init(sentences, GAMMA):
    bdys = []
    for sent in sentences:
        bdys += [[str(int(random.random() < GAMMA))[0] for _ in sent[:-1]] + ['1']]
    return bdys
    

N_ITERS = 5
final_bpa_hypers = {}
def gibbs_train(sentences, gs_boundaries, s, BETA, GAMMA):
    if (s, BETA, GAMMA) in final_bpa_hypers:
        return
    cur_boundaries = gibbs_init(sentences, GAMMA)
    counts = initialize_seg_counts(sentences, cur_boundaries)
    for n in range(1, N_ITERS+1):
        cur_boundaries = gibbs_samp_iter(sentences, cur_boundaries, counts, s, BETA, GAMMA, n)
    final_bpa_hypers[(s,BETA,GAMMA)] = calc_bpa(gs_boundaries, cur_boundaries)
    return cur_boundaries

gibbs_train(sentences, gs_boundaries, 0.2, 0.5, 0.2)
# this ends up stablizing around 73.2% accuracy.<jupyter_output><empty_output><jupyter_text>2. Experimentation  a. Changing hyperparameters<jupyter_code>from tqdm import tqdm
import itertools

GAMMA_LIST = [0.1, 0.2, 0.3]
BETA_LIST = [0.1, 0.2, 0.5]
s_LIST = [0.1, 0.2, 0.5, 1]

for s, BETA, GAMMA in tqdm(list(itertools.product(s_LIST, BETA_LIST, GAMMA_LIST))):
    gibbs_train(sentences, gs_boundaries, s, BETA, GAMMA)

print(final_bpa_hypers)
# everything seemed to bes<jupyter_output>0%|          | 0/36 [00:00<?, ?it/s][A[A
{'fraction_non_alphanumeric': 0.13027950310559006, 'fraction_numerical': 0.03152173913043478, 'mean_word_length': 2.9515337423312884, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 18, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '145450', 'license': 'Unlicense', 'n_tokens_mistral': 2699, 'n_tokens_neox': 2546, 'n_words': 539, 'path': 'nonparametric-bayes-segmentation.ipynb', 'repo_name': 'laudiacay/for-the-love-of-bayes', 'size': '6440'}