<jupyter_start><jupyter_text>Week 8: sequence learningThis time we'll solve a problem of transribing english words, also known as g2p (grapheme2phoneme) * word (sequence of letters in source language) -> translation (sequence of letters in target language) Some letters correspond to several phonemes and others - to none, so we use encoder-decoder architecture to figure that out.This kind of architectures is about converting anything to anything, including * Machine translation and spoken dialogue systems * [Image captioning](http://mscoco.org/dataset/captions-challenge2015) and [image2latex](https://openai.com/requests-for-research/im2latex) (convolutional encoder, recurrent decoder) * Generating [images by captions](https://arxiv.org/abs/1511.02793) (recurrent encoder, convolutional decoder) * Grapheme2phoneme - convert words to transcripts  We chose simplified __Hebrew->English__ machine translation for words and short phrases (character-level), as it is relatively quick to train even without gpu cluster.Since you have already done step1-2 in RNN assignment, we trust you to __read carefully__ through already implemented functions instead of reimplementing them for the third time.__Contributions:__ This notebook is brought to you by* Yandex [MT team](https://tech.yandex.com/translate/)* <NAME> ([Omrigan](https://github.com/Omrigan/)), <NAME> ([TixFeniks](https://github.com/tixfeniks)) and <NAME> ([justheuristic](https://github.com/justheuristic/))* Dataset is parsed from [Wiktionary](https://en.wiktionary.org), which is under CC-BY-SA and GFDL licenses.<jupyter_code>EASY_MODE = True        #If True, only translates phrases shorter than 20 characters (way easier).
                        #Useful for initial coding.
                        #If false, works with all phrases (please switch to this mode for homework assignment)

MODE = "he-to-en"                                #way we translate. Either "he-to-en" or "en-to-he"
END = ';'                                        #end of phrase for both source and target
MAX_OUTPUT_LENGTH = 50 if not EASY_MODE else 20  #maximal length of _generated_ output, does not affect training
REPORT_FREQ       = 100                          #how often to evaluate validation score<jupyter_output><empty_output><jupyter_text>Step 1: preprocessingWe shall store dataset as a dictionary`{ word1:[translation1,translation2,...], word2:[...],...}`.This is mostly due to the fact that many words have several correct translations.<jupyter_code>import numpy as np
from collections import defaultdict
word_to_translation = defaultdict(list) #our dictionary

with open("main_dataset.txt") as fin:
    for line in fin:
        
        ###
        #you may want to cast everything to unicode later during homework phase, just make sure you do it _everywhere_
        ###

        en,he = line[:-1].lower().replace(END,' ').split('\t')
        
        word,trans = (he,en) if MODE=='he-to-en' else (en,he)
                
        if EASY_MODE:
            if max(len(word),len(trans))>20:
                continue
        
        word_to_translation[word+END].append(trans+END)
    
print ("size = ",len(word_to_translation))
#get all unique letters in source language (a.k.a. source dictionary)
all_words = word_to_translation.keys()

source_letters = list(set(''.join(all_words)))
source_to_ix = {l:i for i,l in enumerate(source_letters)}
#get all unique translation letters (a.k.a. target dictionary)

all_translations = [ts for all_ts in word_to_translation.values() for ts in all_ts]

target_letters = list(set([l for ts in all_translations for l in ts]+[" "]))
target_to_ix = {l:i for i,l in enumerate(target_letters)}
#Special tokens
PAD_ix=-1
EOS_ix_source=source_letters.index(END)
EOS_ix_target=target_letters.index(END)
BOS_ix_target = target_letters.index(" ")<jupyter_output><empty_output><jupyter_text>Draw word/translation length distributions to estimate the scope of the task.<jupyter_code>import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize=[8,4])
plt.subplot(1,2,1)
plt.title("words")
plt.hist(list(map(len,all_words)),bins=25);

plt.subplot(1,2,2)
plt.title('translations')
plt.hist(list(map(len,all_translations)),bins=25);<jupyter_output><empty_output><jupyter_text>Step 2: auxiliary functionswe need some helper functions that* convert data from strings to integer matrices* sample random minibatches<jupyter_code>def as_matrix(sequences,token_to_i, max_len=None,PAX_ix=PAD_ix):
    """
    convert variable length token sequences into  fixed size matrix
    example usage: 
    >>>print( as_matrix(words[:3],source_to_ix))
    [[15 22 21 28 27 13 -1 -1 -1 -1 -1]
     [30 21 15 15 21 14 28 27 13 -1 -1]
     [25 37 31 34 21 20 37 21 28 19 13]]
    """
    max_len = max_len or max(map(len,sequences))
    
    matrix = np.zeros((len(sequences),max_len),dtype='int32') +PAD_ix
    for i,seq in enumerate(sequences):
        row_ix = list(map(token_to_i.get,seq))[:max_len]
        matrix[i,:len(row_ix)] = row_ix
    
    return matrix
import random
def sample_batch(words,word_to_translation, batch_size):
    """
    sample random batch of words and random correct translation for each word
    example usage:
    batch_x,batch_y = sample_batch(train_words, word_to_translations,10)
    """
    
    #choose words
    batch_words = np.random.choice(words,size=batch_size)
    
    #choose translations
    batch_trans_candidates = list(map(word_to_translation.get,batch_words))
    batch_trans = list(map(random.choice,batch_trans_candidates))
    
    return as_matrix(batch_words,source_to_ix), as_matrix(batch_trans,target_to_ix)<jupyter_output><empty_output><jupyter_text>split the datasetWe hold out 20% of all words to be used for validation.<jupyter_code>from sklearn.cross_validation import train_test_split

train_words,test_words = train_test_split(all_words,test_size=0.1,random_state=42)<jupyter_output><empty_output><jupyter_text>Step 3: Build encoder-decoder (1 point)__assignment starts here__Our architecture consists of two main blocks:* Encoder reads words character by character and outputs code vector (usually a function of last RNN state)* Decoder takes that code vector and produces translations character by characterIn this section, we'll implement __encoder__ the same way you did for week6.5.<jupyter_code>%env THEANO_FLAGS=device=gpu,floatX=float32
import theano
import theano.tensor as T

import lasagne
from lasagne.layers import *<jupyter_output><empty_output><jupyter_text>One more note: in this assignment, we'll be using classes as namespaces:```class my_pocket:    coin = "$"    coins = coin*3    mobile = "nokia 3310"    >>>print my_pocket.coins$$$>>>print my_pocket.mobilenokia 3310```Your first assignment is to implement encoder network using lasagne layers.<jupyter_code>def get_mask_by_eos(is_eos):
    """takes indicator of "it ends now", returns mask.
    Ignores everything after first end."""
    assert is_eos.ndim==2
    is_right_after_eos = T.concatenate([T.zeros_like(is_eos[:,:1]),is_eos[:,:-1]],-1)
    is_after_eos = T.eq(T.cumsum(is_right_after_eos,axis=-1),0).astype('uint8')
    return is_after_eos
class encoder:
    """encoder rnn"""
    
    #input tokens and mask
    input_sequence = T.matrix('token sequence','int32')
    input_mask = get_mask_by_eos(T.eq(input_sequence,EOS_ix_source))
    
    inp = InputLayer(shape=(None, None),input_var=input_sequence,name='encoder input')
    mask = <a layer that takes input_mask>
    
    #embedding
    emb = EmbeddingLayer(<which layer?>,
                         input_size=<how many letters?>,
                         output_size=50)
    
    #encoder rnn
    rnn = GRULayer(incoming=<which layer?>,
                   num_units=512,
                   mask_input=<which layer?>)
    
    #slice last time-step of encoder rnn
    rnn_last = SliceLayer(rnn,-1,axis=1,name='last rnn time-step')
    
    #compute decoder initial state
    code = DenseLayer(rnn_last,512,nonlinearity=T.tanh)<jupyter_output><empty_output><jupyter_text>DecoderIn this section, we will define __one step__ of decoder (just like we defined one step of agent last week).<jupyter_code>from agentnet.memory import RNNCell,GRUCell,LSTMCell
from agentnet.resolver import ProbabilisticResolver
class decoder:
    """single step of decoder rnn"""
    
    inp = InputLayer((None,),name="prev phoneme")
    
    emb = EmbeddingLayer(inp, len(target_letters), 50)
    
    #decoder memory
    prev_gru = InputLayer((None,512))
    
    gru = GRUCell(<...>,<...>) #use shift-tab to figure out what goes here
    
    logits = DenseLayer(gru,len(target_letters),nonlinearity=None)
    
    #probabilities
    probs = NonlinearityLayer(logits,T.nnet.softmax)
    
    #output phonemes
    out = ProbabilisticResolver(probs,assume_normalized=True)
    
    #log-probabilities
    logprobs = NonlinearityLayer(logits,T.nnet.logsoftmax)<jupyter_output><empty_output><jupyter_text>Wire it all together (1 point)Here we define functions for model _inference_ (both greedy and sampled).<jupyter_code>from agentnet import Recurrence
from collections import OrderedDict as od
class model:
    #maximum output length for inference
    n_steps = theano.shared(MAX_OUTPUT_LENGTH)
    
    #initial inputs: indices of "START" special phoneme.
    l_start = InputLayer((None,),T.zeros_like(encoder.input_sequence[:,0])+BOS_ix_target)

    #Here we define recurrence: it's a custom recurrent layer, acting exactly like Agent, 
    #except it's a lasagne layer.
    
    rec = Recurrence(
        #recurrent states
        state_variables=od({decoder.gru:<what decoder.gru becomes on next tick?>,
                            decoder.out:<where decode.out goes on next tick?}),
        
        #initial values for recurrent states
        state_init={decoder.out:l_start,
                    decoder.gru:<what is initial value for decoder.gru?>,},
        
        tracked_outputs=(decoder.out,decoder.probs,decoder.logprobs),
        
        unroll_scan=False,
        n_steps=n_steps
    )
    
    weights = get_all_params(rec,trainable=True)
    
    
    #sample mode
    predicted_translations,probs_seq,logprobs_seq = get_output(rec[decoder.out,decoder.probs,decoder.logprobs])
    auto_updates = rec.get_automatic_updates()

    #output mask
    mask = get_mask_by_eos(T.eq(predicted_translations,EOS_ix_target))
    
    generate_sample = theano.function([encoder.input_sequence],predicted_translations,
                                      updates=auto_updates)
    
    #greedy mode (picking max-probability actions on each step)
    greedy_translations = get_output(rec[decoder.out],recurrence_flags={"greedy":True})
    greedy_auto_updates = rec.get_automatic_updates()
    
    greedy_mask = <compute mask for greedy_translations>
    
    
    generate_greedy = theano.function([<what goes in?>],<what goes out?>,
                                       updates=greedy_auto_updates)
    

    @staticmethod
    def translate(word,sample=False):
        assert word.endswith(END)
        
        #convert to matrix
        word_ix = as_matrix([word.lower()],source_to_ix)
        
        #generate output
        if sample:
            trans_ix = model.generate_sample(word_ix)[0]
        else:
            trans_ix = model.generate_greedy(word_ix)[0]
        
        #convert from int32 to string
        trans = list(map(target_letters.__getitem__,trans_ix))
        
        #crop padding
        if END in trans:
            trans = trans[:trans.index(END)+1]
            
        return ''.join(trans)
        

#test untrained model
#should be random
print ('x:'+all_words[0])
print ('y_sampled:'+model.translate(all_words[0],sample=True))
print ('y_greedy:'+model.translate(all_words[0]))


#praise Cthulhu!<jupyter_output><empty_output><jupyter_text>Scoring functionLogLikelihood is a poor estimator of model performance.* If we predict zero probability once, it shouldn't ruin entire model.* It is enough to learn just one translation if there are several correct ones.* What matters is which output will we produce if we __take most likely phoneme on each step.__Therefore, we will use minimal Levenshtein distance.<jupyter_code>import editdistance #!pip install editdistance

def get_distance(word,trans):
    """
    A function that takes word and predicted translation
    and evaluates (Levenshtein's) edit distance to closest correct translation
    """
    references = word_to_translation[word]
    assert len(references)!=0,"wrong/unknown word"
    return min(editdistance.eval(trans,ref) for ref in references)
def score(bsize=100):
    """a function that computes levenshtein distance for bsize random samples"""
    
    batch_words = <pick bsize random words from test_words>
    
    <for each word, predict using sample=False>
    <compute get_score for each word in batch_words>
    distances = <array of distances for each pair (word, translation)>
    
    return np.array(distances,dtype='float32')
#should be around 5-50 and decrease rapidly :)
[score(100).mean() for _ in range(10)]<jupyter_output><empty_output><jupyter_text>Step 4: Supervised pre-trainingHere we define a function that trains our model through maximizing log-likelihood a.k.a. minimizing crossentropy.<jupyter_code>from agentnet.learning.generic import get_values_for_actions

class llh_trainer:

    #variable for correct answers
    reference_answers = T.imatrix("reference translations")
    
    #shift 1 step to the past to get "previous answers"
    prev_answers = T.concatenate([T.zeros_like(reference_answers[:,:1])+BOS_ix_target,
                                  reference_answers[:,:-1]],axis=1)
    
    #mask on prev answers
    input_mask = get_mask_by_eos(T.eq(prev_answers,EOS_ix_target))
    
    #create input layers
    l_sequence = InputLayer((None,None),prev_answers)
    l_mask = InputLayer((None,None),input_mask)
    
    #teacher-forced trainer
    rec = Recurrence(state_variables=od({decoder.gru:decoder.prev_gru}),
                     input_sequences={decoder.inp:l_sequence},
                     state_init={decoder.gru:encoder.code},
                     tracked_outputs=(decoder.probs,decoder.logprobs),
                     unroll_scan=False,
                     mask_input=l_mask)
    
    
    #get log-probabilities
    logprobs_seq = get_output(rec[decoder.logprobs])
    auto_updates = rec.get_automatic_updates()
    
    #compute mean crossentropy
    crossentropy = -get_values_for_actions(logprobs_seq,reference_answers)
    
    loss = T.sum(crossentropy*input_mask)/T.sum(input_mask)
    
    #get all params
    weights = get_all_params(rec,trainable=True)

    #weight updates                 
    updates = <compute weight updates>
    
    train_step = theano.function([encoder.input_sequence,reference_answers],loss,
                                 updates=auto_updates+updates)
    
from IPython.display import clear_output
from tqdm import tqdm,trange #or use tqdm_notebook,tnrange

loss_history=[]
editdist_history = []

for i in trange(25000):
    loss_history.append(
            llh_trainer.train_step(*sample_batch(train_words,word_to_translation,32)))
    
    if (i+1)%REPORT_FREQ==0:
        clear_output(True)
        current_scores = score()
        editdist_history.append(current_scores.mean())
        plt.figure(figsize=(8,4))
        plt.subplot(121)
        plt.title('val score distribution')
        plt.hist(current_scores, bins = 20)
        plt.subplot(122)
        plt.title('val score / traning time')
        plt.plot(editdist_history)
        plt.grid()
        plt.show()
        print("llh=%.3f, mean score=%.3f"%(np.mean(loss_history[-10:]),np.mean(editdist_history[-10:])))
for word in train_words[:10]:
    print("%s -> %s"%(word,model.translate(word)))<jupyter_output><empty_output><jupyter_text>Step 5: Policy gradient (3 pts)First we need to define loss function as a custom theano operation.The simple way to do so is```@theano.compile.as_op(input_types,output_type(s),infer_shape)def my_super_function(inputs):    return outputs```__Your task__ is to implement `_compute_levenshtein` function that takes matrices of words and translations, along with input masks, then converts those to actual words and phonemes and computes min-levenshtein via __get_distance__ function above.<jupyter_code>@theano.compile.as_op([T.imatrix]*4,[T.fvector],lambda _,shapes: [shapes[0][:1]])
def _compute_levenshtein(words_ix,words_mask,trans_ix,trans_mask):
    """
    A custom theano operation that computes levenshtein loss for predicted trans.
    
    Params:
    - words_ix - a matrix of letter indices, shape=[batch_size,word_length]
    - words_mask - a matrix of zeros/ones, 
       1 means "word is still not finished"
       0 means "word has already finished and this is padding"
    
    - trans_mask - a matrix of output letter indices, shape=[batch_size,translation_length]
    - trans_mask - a matrix of zeros/ones, similar to words_mask but for trans_ix
    
    
    Please implement the function and make sure it passes tests from the next cell.
    
    """
    
    #convert words to strings
    <your code here>
    words = <restore words (a list of strings) from words_ix and words_mask>

    assert type(words) is list
    assert type(words[0]) is str 
    assert len(words)==len(words_ix)
    
    #convert translations to lists
    <your code here>
    translations = <restore trans (a list of lists of phonemes) from trans_ix and trans_mask

    assert type(translations) is list
    assert type(translations[0]) is str
    assert len(translations)==len(trans_ix)

    #computes levenstein distances. can be arbitrary python code.
    distances = <apply get_distance to each pair of [words,translations]>
    
    assert type(distances) in (list,tuple,np.ndarray) and len(distances) == len(words_ix)
    
    distances = np.array(list(distances),dtype='float32')
    return distances

#forbid gradient
from theano.gradient import disconnected_grad
def compute_levenshtein(*args):
    return disconnected_grad(_compute_levenshtein(*[arg.astype('int32') for arg in args]))<jupyter_output><empty_output><jupyter_text>Simple test suite to make sure your implementation is correct. Hint: if you run into any bugs, feel free to use print from inside _compute_levenshtein.<jupyter_code>#test suite
#sample random batch of (words, correct trans, wrong trans)
batch_words = np.random.choice(train_words, size=100 )
batch_trans = list(map(random.choice,map(word_to_translation.get,batch_words )))
batch_trans_wrong = np.random.choice(all_translations,size=100)

batch_words_ix = T.constant(as_matrix(batch_words,source_to_ix))
batch_trans_ix = T.constant(as_matrix(batch_trans,target_to_ix))
batch_trans_wrong_ix = T.constant(as_matrix(batch_trans_wrong,target_to_ix))

batch_words_mask = get_mask_by_eos(T.eq(batch_words_ix,EOS_ix_source))
batch_trans_mask = get_mask_by_eos(T.eq(batch_trans_ix,EOS_ix_target))
batch_trans_wrong_mask = get_mask_by_eos(T.eq(batch_trans_wrong_ix,EOS_ix_target))

#assert compute_levenshtein is zero for ideal translations
correct_answers_score = compute_levenshtein(batch_words_ix,batch_words_mask,
                                            batch_trans_ix,batch_trans_mask).eval()

assert np.all(correct_answers_score==0),"a perfect translation got nonzero levenshtein score!"

print("Everything seems alright!")
#assert compute_levenshtein matches actual scoring function
wrong_answers_score = compute_levenshtein(batch_words_ix,batch_words_mask,
                                            batch_trans_wrong_ix,batch_trans_wrong_mask).eval()

true_wrong_answers_score = np.array(list(map(get_distance,batch_words,batch_trans_wrong)))

assert np.all(wrong_answers_score==true_wrong_answers_score),"for some word symbolic levenshtein is different from actual levenshtein distance"

print("Everything seems alright!")<jupyter_output><empty_output><jupyter_text>Once you got it working...* You may now want to __remove/comment asserts__ from function code for a slight speed-up.* There's a more detailed tutorial on custom theano ops here: [docs](http://deeplearning.net/software/theano/extending/extending_theano.html), [example](https://gist.github.com/justheuristic/9f4ffef6162a8089c3260fc3bbacbf46).  Self-critical policy gradientIn this section you'll implement algorithm called self-critical sequence training (here's an [article](https://arxiv.org/abs/1612.00563)).The algorithm is a vanilla policy gradient with a special baseline. $$ \nabla J = E_{x \sim p(s)} E_{y \sim \pi(y|x)} \nabla log \pi(y|x) \cdot (R(x,y) - b(x)) $$Here reward R(x,y) is a __negative levenshtein distance__ (since we minimize it). The baseline __b(x)__ represents how well model fares on word __x__.In practice, this means that we compute baseline as a score of greedy translation, $b(x) = R(x,y_{greedy}(x)) $.Luckily, we already obtained the required outputs: `model.greedy_translations, model.greedy_mask` and we only need to compute levenshtein using `compute_levenshtein` function.<jupyter_code>from agentnet.learning.generic import get_values_for_actions

class trainer:    
    
    rewards = -compute_levenshtein(encoder.input_sequence,encoder.input_mask,
                                   model.predicted_translations,model.mask,)
    
    baseline = <compute __negative__ levenshtein for greedy mode>
    
    #compute advantage using rewards and baseline
    advantage = <your code - compute advantage>
    
    
    #compute log_pi(a_t|s_t), shape = [batch,seq_length]
    phoneme_logprobs = get_values_for_actions(model.logprobs_seq, model.predicted_translations)
    
    #policy gradient
    J = phoneme_logprobs*advantage[:,None]
    
    loss = -T.sum(J*model.mask) / model.mask.sum()
    
    
    #regularize with negative entropy
    entropy = <compute entropy matrix of shape [batch,seq_length], H=-sum(p*log_p), don't forget the sign!>

    loss -= 0.01*(model.mask*entropy).sum() / model.mask.sum()
    
    
    # Compute weight updates, clip by norm
    grads = T.grad(loss,model.weights)
    grads = lasagne.updates.total_norm_constraint(grads,10)

    updates = lasagne.updates.adam(grads, model.weights,learning_rate=1e-5) 

    train_step = theano.function([encoder.input_sequence],loss,
                                 updates = model.auto_updates+model.greedy_auto_updates+updates)<jupyter_output><empty_output><jupyter_text>Policy gradient training<jupyter_code>for i in trange(100000):
    loss_history.append(
        trainer.train_step(sample_batch(train_words,word_to_translation,32)[0])
        )
    
    if (i+1)%REPORT_FREQ==0:
        clear_output(True)
        current_scores = score()
        editdist_history.append(current_scores.mean())
        plt.figure(figsize=(8,4))
        plt.subplot(121)
        plt.title('val score distribution')
        plt.hist(current_scores, bins = 20)
        plt.subplot(122)
        plt.title('val score / traning time')
        plt.plot(editdist_history)
        plt.grid()
        plt.show()
        print("J=%.3f, mean score=%.3f"%(np.mean(loss_history[-10:]),np.mean(editdist_history[-10:])))
model.translate("EXAMPLE;")<jupyter_output><empty_output><jupyter_text>Results<jupyter_code>predicted_translations = list(map(model.translate,tqdm(test_words)))
distances = map(get_score,test_words,predicted_translations)

print "Mean Levenshtein distance:",np.mean(distances)
print "Median Levenshtein distance:",np.median(distances)
plt.hist(distances,range=[0,10]);<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0979077367058524, 'fraction_numerical': 0.012731825319356618, 'mean_word_length': 3.8776650796936454, 'pattern_counts': {'":': 1, '<': 94, '<?xml version=': 0, '>': 105, 'https://': 9, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '109090', 'license': 'MIT', 'n_tokens_mistral': 7660, 'n_tokens_neox': 7212, 'n_words': 1824, 'path': 'week8/8.1_translation_scst.ipynb', 'repo_name': 'oleg-kachan/reinforcement_learning', 'size': '23589'}