labs/07_seq2seq/Translation_of_Numeric_Phrases_with_Seq2Seq_rendered.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Translation of Numeric Phrases with Seq2Seq\n",
    "\n",
    "In the following we will try to build a **translation model from french phrases describing numbers** to the corresponding **numeric representation** (base 10).\n",
    "\n",
    "This is a toy machine translation task with a **restricted vocabulary** and a **single valid translation for each source phrase** which makes it more tractable to train on a laptop computer and easier to evaluate. Despite those limitations we expect that this task will highlight interesting properties of Seq2Seq models including:\n",
    "\n",
    "- the ability to **deal with different length** of the source and target sequences,\n",
    "- handling token with a **meaning that changes depending on the context** (e.g \"quatre\" vs \"quatre vingts\" in \"quatre cents\"),\n",
    "- basic counting and \"reasoning\" capabilities of LSTM and GRU models.\n",
    "\n",
    "The parallel text data is generated from a \"ground-truth\" Python function named `to_french_phrase` that captures common rules. Hyphenation was intentionally omitted to make the phrases more ambiguous and therefore make the translation problem slightly harder to solve (and also because Olivier had no particular interest hyphenation in properly implementing rules :)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    21 vingt et un\n",
      "    80 quatre vingts\n",
      "    81 quatre vingt un\n",
      "   300 trois cents\n",
      "   213 deux cent treize\n",
      "  1100 mille cent\n",
      "  1201 mille deux cent un\n",
      "301000 trois cent un mille\n",
      " 80080 quatre vingt mille quatre vingts\n"
     ]
    }
   ],
   "source": [
    "from french_numbers import to_french_phrase\n",
    "\n",
    "for x in [21, 80, 81, 300, 213, 1100, 1201, 301000, 80080]:\n",
    "    print(str(x).rjust(6), to_french_phrase(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Generating a Training Set\n",
    "\n",
    "The following will **generate phrases 20000 example phrases for numbers between 1 and 1,000,000** (excluded). We chose to over-represent small numbers by generating all the possible short sequences between 1 and `exhaustive`.\n",
    "\n",
    "We then split the generated set into non-overlapping train, validation and test splits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "from french_numbers import generate_translations\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "\n",
    "numbers, french_numbers = generate_translations(\n",
    "    low=1, high=int(1e6) - 1, exhaustive=5000, random_seed=0)\n",
    "num_train, num_dev, fr_train, fr_dev = train_test_split(\n",
    "    numbers, french_numbers, test_size=0.5, random_state=0)\n",
    "\n",
    "num_val, num_test, fr_val, fr_test = train_test_split(\n",
    "    num_dev, fr_dev, test_size=0.5, random_state=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10000, 5000, 5000)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(fr_train), len(fr_val), len(fr_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2882 deux mille huit cent quatre vingt deux\n",
      "372200 trois cent soixante douze mille deux cents\n",
      "  2193 deux mille cent quatre vingt treize\n",
      "996418 neuf cent quatre vingt seize mille quatre cent dix huit\n",
      "  9172 neuf mille cent soixante douze\n"
     ]
    }
   ],
   "source": [
    "for i, fr_phrase, num_phrase in zip(range(5), fr_train, num_train):\n",
    "    print(num_phrase.rjust(6), fr_phrase)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  2804 deux mille huit cent quatre\n",
      "  3898 trois mille huit cent quatre vingt dix huit\n",
      " 82996 quatre vingt deux mille neuf cent quatre vingt seize\n",
      "366346 trois cent soixante six mille trois cent quarante six\n",
      " 56006 cinquante six mille six\n"
     ]
    }
   ],
   "source": [
    "for i, fr_phrase, num_phrase in zip(range(5), fr_val, num_val):\n",
    "    print(num_phrase.rjust(6), fr_phrase)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Vocabularies\n",
    "\n",
    "Build the vocabularies from the training set only to get a chance to have some out-of-vocabulary words in the validation and test sets.\n",
    "\n",
    "First we need to introduce specific symbols that will be used to:\n",
    "- pad sequences\n",
    "- mark the beginning of translation\n",
    "- mark the end of translation\n",
    "- be used as a placehold for out-of-vocabulary symbols (not seen in the training set).\n",
    "\n",
    "Here we use the same convention as the [tensorflow seq2seq tutorial](https://www.tensorflow.org/tutorials/seq2seq):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "PAD, GO, EOS, UNK = START_VOCAB = ['_PAD', '_GO', '_EOS', '_UNK']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "To build the vocabulary we need to tokenize the sequences of symbols. For the digital number representation we use character level tokenization while whitespace-based word level tokenization will do for the French phrases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def tokenize(sentence, word_level=True):\n",
    "    if word_level:\n",
    "        return sentence.split()\n",
    "    else:\n",
    "        return [sentence[i:i + 1] for i in range(len(sentence))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '3', '4']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('1234', word_level=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['mille', 'deux', 'cent', 'trente', 'quatre']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('mille deux cent trente quatre', word_level=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's now use this tokenization strategy to assign a unique integer token id to each possible token string found the traing set in each language ('French' and 'numeric'): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def build_vocabulary(tokenized_sequences):\n",
    "    rev_vocabulary = START_VOCAB[:]\n",
    "    unique_tokens = set()\n",
    "    for tokens in tokenized_sequences:\n",
    "        unique_tokens.update(tokens)\n",
    "    rev_vocabulary += sorted(unique_tokens)\n",
    "    vocabulary = {}\n",
    "    for i, token in enumerate(rev_vocabulary):\n",
    "        vocabulary[token] = i\n",
    "    return vocabulary, rev_vocabulary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "tokenized_fr_train = [tokenize(s, word_level=True) for s in fr_train]\n",
    "tokenized_num_train = [tokenize(s, word_level=False) for s in num_train]\n",
    "\n",
    "fr_vocab, rev_fr_vocab = build_vocabulary(tokenized_fr_train)\n",
    "num_vocab, rev_num_vocab = build_vocabulary(tokenized_num_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The two languages do not have the same vocabulary sizes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(fr_vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(num_vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      _EOS 2\n",
      "       _GO 1\n",
      "      _PAD 0\n",
      "      _UNK 3\n",
      "      cent 4\n",
      "     cents 5\n",
      "      cinq 6\n",
      " cinquante 7\n",
      "      deux 8\n",
      "       dix 9\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "for k, v in sorted(fr_vocab.items())[:10]:\n",
    "    print(k.rjust(10), v)\n",
    "print('...')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         0 4\n",
      "         1 5\n",
      "         2 6\n",
      "         3 7\n",
      "         4 8\n",
      "         5 9\n",
      "         6 10\n",
      "         7 11\n",
      "         8 12\n",
      "         9 13\n",
      "      _EOS 2\n",
      "       _GO 1\n",
      "      _PAD 0\n",
      "      _UNK 3\n"
     ]
    }
   ],
   "source": [
    "for k, v in sorted(num_vocab.items()):\n",
    "    print(k.rjust(10), v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "We also built the reverse mappings from token ids to token string representations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['_PAD', '_GO', '_EOS', '_UNK', 'cent', 'cents', 'cinq', 'cinquante', 'deux', 'dix', 'douze', 'et', 'huit', 'mille', 'neuf', 'onze', 'quarante', 'quatorze', 'quatre', 'quinze', 'seize', 'sept', 'six', 'soixante', 'treize', 'trente', 'trois', 'un', 'vingt', 'vingts']\n"
     ]
    }
   ],
   "source": [
    "print(rev_fr_vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['_PAD', '_GO', '_EOS', '_UNK', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']\n"
     ]
    }
   ],
   "source": [
    "print(rev_num_vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Seq2Seq with a single GRU architecture\n",
    "\n",
    "<img src=\"images/basic_seq2seq.png\" width=\"80%\" />\n",
    "\n",
    "From: [Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. \"Sequence to sequence learning with neural networks.\" NIPS 2014](https://arxiv.org/abs/1409.3215)\n",
    "\n",
    "\n",
    "\n",
    "For a given source sequence - target sequence pair, we will:\n",
    "- tokenize the source and target sequences;\n",
    "- reverse the order of the source sequence;\n",
    "- build the input sequence by concatenating the reversed source sequence and the target sequence in original order using the `_GO` token as a delimiter, \n",
    "- build the output sequence by appending the `_EOS` token to the source sequence.\n",
    "\n",
    "\n",
    "Let's do this as a function using the original string representations for the tokens so as to make it easier to debug:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "**Exercise**\n",
    "- Build a function which adapts a pair of tokenized sequences to the framework above.\n",
    "- The function should have a reverse_source as an option.\n",
    "\n",
    "*Note*: \n",
    "- The function should output two sequences of string tokens: one to be fed as the input and the other as expected output for the seq2seq network. We will handle the padding later;\n",
    "- Don't forget to insert the `_GO` and `_EOS` special symbols at the right locations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def make_input_output(source_tokens, target_tokens, reverse_source=True):\n",
    "    # TOTO\n",
    "    return input_tokens, output_tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# %load solutions/make_input_output.py\n",
    "def make_input_output(source_tokens, target_tokens, reverse_source=True):\n",
    "    if reverse_source:\n",
    "        source_tokens = source_tokens[::-1]\n",
    "    input_tokens = source_tokens + [GO] + target_tokens\n",
    "    output_tokens = target_tokens + [EOS]\n",
    "    return input_tokens, output_tokens\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "input_tokens, output_tokens = make_input_output(\n",
    "    ['cent', 'vingt', 'et', 'un'],\n",
    "    ['1', '2', '1'],\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['un', 'et', 'vingt', 'cent', '_GO', '1', '2', '1']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '1', '_EOS']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output_tokens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Vectorization of the parallel corpus\n",
    "\n",
    "Let's apply the previous transformation to each pair of (source, target) sequene and use a shared vocabulary to store the results in numpy arrays of integer token ids, with padding on the left so that all input / output sequences have the same length: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "all_tokenized_sequences = tokenized_fr_train + tokenized_num_train\n",
    "shared_vocab, rev_shared_vocab = build_vocabulary(all_tokenized_sequences)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "max_length = 20  # found by introspection of our training set\n",
    "\n",
    "def vectorize_corpus(source_sequences, target_sequences, shared_vocab,\n",
    "                     word_level_source=True, word_level_target=True,\n",
    "                     max_length=max_length):\n",
    "    assert len(source_sequences) == len(target_sequences)\n",
    "    n_sequences = len(source_sequences)\n",
    "    source_ids = np.empty(shape=(n_sequences, max_length), dtype=np.int32)\n",
    "    source_ids.fill(shared_vocab[PAD])\n",
    "    target_ids = np.empty(shape=(n_sequences, max_length), dtype=np.int32)\n",
    "    target_ids.fill(shared_vocab[PAD])\n",
    "    numbered_pairs = zip(range(n_sequences), source_sequences, target_sequences)\n",
    "    for i, source_seq, target_seq in numbered_pairs:\n",
    "        source_tokens = tokenize(source_seq, word_level=word_level_source)\n",
    "        target_tokens = tokenize(target_seq, word_level=word_level_target)\n",
    "        \n",
    "        in_tokens, out_tokens = make_input_output(source_tokens, target_tokens)\n",
    "        \n",
    "        in_token_ids = [shared_vocab.get(t, UNK) for t in in_tokens]\n",
    "        source_ids[i, -len(in_token_ids):] = in_token_ids\n",
    "    \n",
    "        out_token_ids = [shared_vocab.get(t, UNK) for t in out_tokens]\n",
    "        target_ids[i, -len(out_token_ids):] = out_token_ids\n",
    "    return source_ids, target_ids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "X_train, Y_train = vectorize_corpus(fr_train, num_train, shared_vocab,\n",
    "                                    word_level_target=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10000, 20)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10000, 20)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Y_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'deux mille huit cent quatre vingt deux'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fr_train[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'2882'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_train[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  0,  0,  0,  0,  0,  0,  0, 18, 38, 28, 14, 22, 23, 18,  1,  6,\n",
       "       12, 12,  6], dtype=int32)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  6, 12,\n",
       "       12,  6,  2], dtype=int32)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Y_train[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "This looks good. In particular we can note:\n",
    "\n",
    "- the PAD=0 symbol at the beginning of the two sequences,\n",
    "- the input sequence has the GO=1 symbol to separate the source from the target,\n",
    "- the output sequence is a shifted version of the target and ends with EOS=2.\n",
    "\n",
    "Let's vectorize the validation and test set to be able to evaluate our models:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "X_val, Y_val = vectorize_corpus(fr_val, num_val, shared_vocab,\n",
    "                                word_level_target=False)\n",
    "X_test, Y_test = vectorize_corpus(fr_test, num_test, shared_vocab,\n",
    "                                  word_level_target=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5000, 20), (5000, 20))"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_val.shape, Y_val.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5000, 20), (5000, 20))"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_test.shape, Y_test.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### A simple homogeneous Seq2Seq architecture\n",
    "\n",
    "To keep the architecture simple we will use the **same RNN model and weights for both the encoder part** (before the `_GO` token) **and the decoder part** (after the `_GO` token).\n",
    "\n",
    "We may GRU recurrent cell instead of LSTM because it is slightly faster to compute and should give comparable results.\n",
    "\n",
    "**Exercise:**\n",
    "- Build a Seq2Seq model:\n",
    "  - Start with an Embedding layer;\n",
    "  - Add a single GRU layer: the GRU layer should yield a sequence of output vectors, one at each timestep;\n",
    "  - Add a Dense layer to adapt the ouput dimension of the GRU layer to the dimension of the output vocabulary;\n",
    "  - Don't forget to insert some Dropout layer(s), especially after the Embedding layer.\n",
    "\n",
    "Note:\n",
    "- The output dimension of the Embedding layer should be smaller than usual be cause we have small vocabulary size;\n",
    "- The dimension of the GRU should be larger to give the Seq2Seq model enough \"working memory\" to memorize the full input sequence before decoding it;\n",
    "- Your model should output a shape `[batch, sequence_length, vocab_size]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Using TensorFlow backend.\n"
     ]
    }
   ],
   "source": [
    "# %load solutions/simple_seq2seq.py\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Embedding, Dropout, GRU, Dense\n",
    "\n",
    "vocab_size = len(shared_vocab)\n",
    "simple_seq2seq = Sequential()\n",
    "simple_seq2seq.add(Embedding(vocab_size, 32, input_length=max_length))\n",
    "simple_seq2seq.add(Dropout(0.2))\n",
    "simple_seq2seq.add(GRU(256, return_sequences=True))\n",
    "simple_seq2seq.add(Dense(vocab_size, activation='softmax'))\n",
    "\n",
    "# Here we use the sparse_categorical_crossentropy loss to be able to pass\n",
    "# integer-coded output for the token ids without having to convert to one-hot\n",
    "# codes\n",
    "simple_seq2seq.compile(optimizer='adam', loss='sparse_categorical_crossentropy')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's use a callback mechanism to automatically snapshot the best model found so far on the validation set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "from keras.callbacks import ModelCheckpoint\n",
    "from keras.models import load_model\n",
    "\n",
    "\n",
    "best_model_fname = \"simple_seq2seq_checkpoint.h5\"\n",
    "best_model_cb = ModelCheckpoint(best_model_fname, monitor='val_loss',\n",
    "                                save_best_only=True, verbose=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "We need to use np.expand_dims trick on Y: this is required by Keras because of we use a sparse (integer-based) representation for the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train on 10000 samples, validate on 5000 samples\n",
      "Epoch 1/15\n",
      "Epoch 00000: val_loss improved from inf to 0.55353, saving model to simple_seq2seq_checkpoint.h5\n",
      "6s - loss: 0.8348 - val_loss: 0.5535\n",
      "Epoch 2/15\n",
      "Epoch 00001: val_loss improved from 0.55353 to 0.53911, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.5790 - val_loss: 0.5391\n",
      "Epoch 3/15\n",
      "Epoch 00002: val_loss improved from 0.53911 to 0.51253, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.5464 - val_loss: 0.5125\n",
      "Epoch 4/15\n",
      "Epoch 00003: val_loss improved from 0.51253 to 0.42271, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.4853 - val_loss: 0.4227\n",
      "Epoch 5/15\n",
      "Epoch 00004: val_loss improved from 0.42271 to 0.31207, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.3790 - val_loss: 0.3121\n",
      "Epoch 6/15\n",
      "Epoch 00005: val_loss improved from 0.31207 to 0.25047, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.2994 - val_loss: 0.2505\n",
      "Epoch 7/15\n",
      "Epoch 00006: val_loss improved from 0.25047 to 0.16096, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.2147 - val_loss: 0.1610\n",
      "Epoch 8/15\n",
      "Epoch 00007: val_loss improved from 0.16096 to 0.11571, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.1590 - val_loss: 0.1157\n",
      "Epoch 9/15\n",
      "Epoch 00008: val_loss improved from 0.11571 to 0.07938, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.1283 - val_loss: 0.0794\n",
      "Epoch 10/15\n",
      "Epoch 00009: val_loss improved from 0.07938 to 0.06263, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.0957 - val_loss: 0.0626\n",
      "Epoch 11/15\n",
      "Epoch 00010: val_loss improved from 0.06263 to 0.04684, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.0737 - val_loss: 0.0468\n",
      "Epoch 12/15\n",
      "Epoch 00011: val_loss improved from 0.04684 to 0.03337, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.0561 - val_loss: 0.0334\n",
      "Epoch 13/15\n",
      "Epoch 00012: val_loss did not improve\n",
      "5s - loss: 0.0490 - val_loss: 0.0459\n",
      "Epoch 14/15\n",
      "Epoch 00013: val_loss improved from 0.03337 to 0.01852, saving model to simple_seq2seq_checkpoint.h5\n",
      "5s - loss: 0.0347 - val_loss: 0.0185\n",
      "Epoch 15/15\n",
      "Epoch 00014: val_loss did not improve\n",
      "5s - loss: 0.0366 - val_loss: 0.0189\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x7f5a4a328080>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAtQAAAGBCAYAAABGhiYpAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3Xd8VfX9x/HXJwPCCDNhrzAVBUEDCLK0VcEBahXBgSKK\nYnG2tra11lrb2v6q4sa9WlTEhROxyp5BkKmsMMIMI+yQ9f39cS56TUlyIffk3iTv5+NxHrln3PP5\n5Ca2n3z5nO/XnHOIiIiIiMiJiYl0AiIiIiIi5ZkKahERERGRUlBBLSIiIiJSCiqoRURERERKQQW1\niIiIiEgpqKAWERERESkFFdQiIlHCzFqZmTOzuDDdr4OZLTaz/WZ2ezjuWUK8A2bW2of79jezjHDf\nV0QkXFRQi0hIzOwqM0sLFE1bzewzM+sd6bwqKzN7wMz+XcJlvwG+ds4lOueeCEPMOmb2spltCxTp\nq8zs3qPnnXM1nXPrShsnnMysmZm9a2Y7zWyvmS0zs+vDcN/2ZvahmWWa2W4zm2xmHYLOF/tZiUjF\nooJaREpkZncDY4G/AQ2BFsAzwOBI5hUsXKO6FUxLYPmJvLGIz/MxoCZwMlAbGASsOeHsysYbwCa8\nz6I+cC2wPQz3rQNMAjrg/TcxH/gw6Hx5/KxE5EQ557Rp06atyA2vGDgAXFHMNVXxCu4tgW0sUDVw\nrj+QAfwK2AFsBUYEzvUAtgGxQfe6FFgSeB0D3AusBXYBE4B6gXOtAAeMBDYC0wPHhwMbAtf/EVgP\n/Pw47ndd4H47gT8E5RUL/D7w3v3AQqB54NxJwBRgN/A9MKSYz2oq8He8AmwfXhFWOIe4wH4TvKJt\nN14xdlPg+AAgB8gN/Gy+PUacr4B8IDtwTfvAz/J1IDPwGd0HxASuvx6YhVcI7gIeOsY9lwGXFPO9\nOaBt4PWreH90fRaIPwtoFPjd2AN8B3QNeu964HfAisD5V4CE4N+hoGubAO8Gvo904PZicjoAdCnm\n/JnAbCAL+BboH3QuBZgW+HlPAZ4C/l3EfeoFvv/6IX5WRf7O4BX+kwK/H/OBvwAzI/2/Bdq0aSt6\n0wi1iJSkJ5AAvF/MNX/AK0y6AKcB3fGKtaMa4RVzTfEK4KfNrK5zbh5wEDgn6NqrgPGB17cBlwD9\n8IqoPcDThWL3wxsFPN/MOuIVcVcDjYNiHhXK/XrjjTr+DLjfzE4OHL8bGAZcANQCbgAOmVkNvMJo\nPNAAGAo8E8ilKMMD728M5AFFtWO8hffHSBPgcuBvZnaOc+5zvH8teNt5bRanFX6jc+4cYAYwJnDN\nKuDJwGfSOvAZDAdGBL2tB7AOb8T1r8fIZy7wVzMbYWbtivn+jhqC93uQBBwB5gDfBPYnAo8Wuv5q\n4HygDd4fAPcVOo+ZxQAf4RW/TfF+Tnea2flF5DAX7/dtqJm1KHSvpsAnwEN4BfGvgXfNLDlwyXi8\nP5yS8Ira64r5XvsC25xzu4LiHvOzCuF35mm8P4Qa4/2e3FBMXBGJBpGu6LVp0xbdG16Rs62Ea9YC\nFwTtnw+sD7zuDxwmMOoaOLYDODPw+iHg5cDrRLwCu2VgfyXws6D3NcYblY3jx9Hc1kHn7wfeDNqv\njjeS+/PjuF+zoPPzgaGB198Dg4/xvV8JzCh07DngT0V8VlOBh4P2OwZyjA3KIQ5ojjfCnBh07d+B\nVwOvH6CI0dJCsW4MvI4NxOkYdP5mYGrg9fXAxhLuVw1vlH5h4HNbAwwMOl94hPqFoHO3ASuD9jsB\nWUH764FbgvYvANYG/Q5lBF73KJwn3sj2K0XkXBd4GK/1JR9YDHQLnPst8Eah6yfjFc4t8P7YqRF0\nbvyxPnOgGbAZGBbKZ1Xc70zg55QLnBR07m9ohFqbtqjeNEItIiXZBSSV0KPcBK+F4KgNgWM/3MM5\nlxe0fwivvxS8IuUyM6sKXAZ845w7eq+WwPtmlmVmWXgFcT7eCOpRmwrl8cO+c+5QIP+jQrnftiLy\nbI73h0NhLYEeR+8ZuO/VeKPyRQnOeQMQjzcKGqwJsNs5t7/QtU05MUmBOIV/TsH320QxnHOHnXN/\nc86dgdeWMAF4x8zqFfGW4F7lw8fYr/nTy//nc2nC/2oJNCn0ef+en/4Mg3Pe45y71zl3SuCaxcAH\nZmaBe11R6F698f7QagLscc4dLJTTTwRGs78AnnHOvRkUt7jPqrjfmWS8P6gKfxYiEsVUUItISebg\n/XP9JcVcswWvSDiqReBYiZxzK/AKhoH8tN0DvKJioHOuTtCW4JzbHHyLoNdb8UYLATCzanjFzPHc\nryib8FoRjnV8WqF71nTOjS7mXs2DXrfAG5HcWeiaLUA9M0ssdO3RXB3HZ2cgTuGfU1GfZbGcc/vw\nRk5r4PUah0Phz+VYv0ObgPRCn3eic+6Ckm7unNsJ/AuvWK4XuNcbhe5Vwzn3MN7vUt1Ae0ZwTj8w\ns7p4xfQk59yxWmSOxi38WRX3O5OJNzJe+LMQkSimglpEiuWc24vXSvG0mV1iZtXNLN7MBprZPwOX\nvQncZ2bJZpYUuL6kKd2CjQfuwOtDfSfo+Di8PtSW4I0GmllxM4tMBC42s15mVgWvLcJKcb9gLwJ/\nMbN25ulsZvWBj4H2ZnZt4HOJN7NuQb3Xx3KNmXU0s+rAg8BE51x+8AXOuU14D8v93cwSzKwzXv/5\n0c91O9Aq0FNcosD9JwS+/8TAZ3A3x/FzMrM/Br63KmaWgPczy8JrhwmHXwamuauH15f/9jGumQ/s\nN7Pfmlk1M4s1s1PNrFsROf8jcD4u8MfJaGCN83qd/433+3J+4D4J5s153SzwryRpwJ8D329v4OKg\n+9bCaw+Z5Zz7n+nwSvisivydCfyc3gMeCPy31pHie7dFJAqooBaREjnnHsErvu7DG0HbBIwBPghc\n8hBe8bEEWIr34NlDxxHiTbyH5L4KjCIe9TjebAdfmNl+vAe9ehST53K8Xt238EYYD+D1ax85kfsV\n8iheQfoF3uwLLwHVAi0Z5+E9WLYFr2XkH3gznxTlDbwe4214D3wWtejKMLy+6i14D4X+yTn3ZeDc\n0T88dpnZNyF+D7fh9aivA2bi/SHzcojvBW8E+xW80e4twLnAhc65A8dxj+KMx/t81+G11/zP71Cg\n4LwI7wHY9EAuL+I9bHks1fE+u6zAfVviTWF39I+WwXgtI0d/r+/hx/9vvArv92M3Xn/z60H3vRTo\nBowwb272o9vR0eQiP6sQfmfG4LXDbMP7PXml6I9MRKKBOXe8/2ooIlI+mFlNvEKqnXMuPdL5AJjZ\nVLwH216MdC7RxMzW4z1A+WVJ10aKmT2A99DlNWUc93q8z0YLKYlEKY1Qi0iFYmYXB/6pvAZev+xS\nvBkkREREfKGCWkQqmsH8uMBMO7xp7/RPcSIi4hu1fIiIiIiIlEJx88pGpaSkJNeqVatIpyEiIiIi\nFdzChQt3OueSS7qu3BXUrVq1Ii0tLdJpiIiIiEgFZ2YhLaykHmoRERERkVJQQS0iIiIiUgoqqEVE\nRERESkEFtYiIiIhIKaigFhEREREpBRXUIiIiIiKloIJaRERERKQUVFCLiIiIiJSCCmoRERERkVJQ\nQS0iIiIiUgoqqEVERERESkEFdQhy8wv46Nst5OUXRDoVEREREYkyKqhDMHP1Tm57cxGfLN0a6VRE\nREREJMqooA5Bv/bJtGtQk2enrsU5F+l0RERERCSKqKAOQUyMcUu/Nny3bT9Tv8+MdDoiIiIiEkVU\nUIdoUJcmNKmdwLNT10Y6FRERERGJIiqoQxQfG8NNfVszf/1uFm7YHel0RERERCRKqKA+Dld2a07d\n6vE8O3VdpFMRERERkSihgvo4VK8Sx/W9Uvhy5XZWbd8f6XREREREJAqooD5Ow3u2pFp8LOOmqZda\nRERERFRQH7e6NaowrHsLJi3eQsaeQ5FOR0REREQiTAX1CbixTwoAL85Ij3AmIiIiIhJpvhbUZjbA\nzL43szVmdu8xzrcws6/NbJGZLTGzC/zMJ1ya1KnGJV2b8vaCTew+mBPpdEREREQkgnwrqM0sFnga\nGAh0BIaZWcdCl90HTHDOdQWGAs/4lU+43dKvNYdz83lt9vpIpyIiIiIiEeTnCHV3YI1zbp1zLgd4\nCxhc6BoH1Aq8rg1s8TGfsGrbIJFzOzbktTnrOXgkL9LpiIiIiEiE+FlQNwU2Be1nBI4FewC4xswy\ngE+B2451IzMbZWZpZpaWmRk9S3+P7t+GrEO5vLVgU8kXi4iIiEiFFOmHEocBrzrnmgEXAG+Y2f/k\n5Jx73jmX6pxLTU5OLvMki3J6i7r0SKnHizPWkZNXEOl0RERERCQC/CyoNwPNg/abBY4FGwlMAHDO\nzQESgCQfcwq70f3bsHVvNpO+LTfdKiIiIiISRn4W1AuAdmaWYmZV8B46nFTomo3AzwDM7GS8gjp6\nejpC0K99Mic3rsW4aWspKHCRTkdEREREyphvBbVzLg8YA0wGVuLN5rHczB40s0GBy34F3GRm3wJv\nAtc758pVVWpm3NKvNWt2HODLldsjnY6IiIiIlDErZ/UrqampLi0tLdJp/ERefgFnPzKV+jWq8v6t\nvTCzSKckIiIiIqVkZgudc6klXRfphxIrhLjYGEb1bcPiTVnMS98d6XREREREpAypoA6TK85oRlLN\nKjw7dW2kUxERERGRMqSCOkwS4mMZcVYK01ZlsmLLvkinIyIiIiJlRAV1GF1zZktqVo1j3DSNUouI\niIhUFiqow6h2tXiu7tGCj5dsYeOuQ5FOR0RERETKgArqMLuhdwpxMTE8P0Oj1CIiIiKVgQrqMGtY\nK4FfnNGUCWkZZO4/Eul0RERERMRnKqh9MKpvG3LzC3h1dnqkUxERERERn6mg9kFKUg0uOLUxr8/Z\nwP7s3EinIyIiIiI+UkHtk1v6tWF/dh7j522MdCoiIiIi4iMV1D7p1Kw2vdsm8eLMdLJz8yOdjoiI\niIj4RAW1j0b3b0Pm/iO8v2hzpFMREREREZ+ooPZRrzb16dysNs9NW0t+gYt0OiIiIiLiAxXUPjIz\nRvdrw/pdh5i8fFuk0xERERERH6ig9tl5pzQiJakGz05di3MapRYRERGpaFRQ+yw2xri5b2uWbt7L\nrDW7Ip2OiIiIiISZCuoycOnpTWmQWJVnp62JdCoiIiIiEmYqqMtA1bhYbuyTwqw1u1iSkRXpdERE\nREQkjFRQl5Fh3VtQKyGOcdPWRjoVEREREQkjFdRlJDEhnmt7tuSzZdtYl3kg0umIiIiISJiooC5D\n1/dKoUpsDM9PXxfpVEREREQkTFRQl6HkxKoMSW3Ou99ksG1vdqTTEREREZEwUEFdxkb1bU2Bg5dn\npUc6FREREREJAxXUZax5vepc1Lkx/5m7gb2HciOdjoiIiIiUkgrqCLi5bxsO5uTz73kbIp2KiIiI\niJSSCuoI6NikFv07JPPyzHSyc/MjnY6IiIiIlIIK6ggZ3a8Nuw7m8E7apkinIiIiIiKl4GtBbWYD\nzOx7M1tjZvce4/xjZrY4sK0ys0qzjGD3lHqc3qIOz01fR15+QaTTEREREZET5FtBbWaxwNPAQKAj\nMMzMOgZf45y7yznXxTnXBXgSeM+vfKKNmTG6f1sy9hzmk6VbI52OiIiIiJwgP0eouwNrnHPrnHM5\nwFvA4GKuHwa86WM+UednJzWgXYOaPDt1Lc65SKcjIiIiIifAz4K6KRDcIJwROPY/zKwlkAJ8VcT5\nUWaWZmZpmZmZYU80UmJijJv7teG7bfuZuqrifF8iIiIilUm0PJQ4FJjonDvmlBfOueedc6nOudTk\n5OQyTs1fg05rQpPaCTw7dW2kUxERERGRE+BnQb0ZaB603yxw7FiGUsnaPY6qEhfDjX1aMz99Nws3\n7I50OiIiIiJynPwsqBcA7cwsxcyq4BXNkwpfZGYnAXWBOT7mEtWGdm9OnerxPDt1XaRTEREREZHj\n5FtB7ZzLA8YAk4GVwATn3HIze9DMBgVdOhR4y1Xip/KqV4nj+l6t+HLldlZt3x/pdERERETkOFh5\nq2NTU1NdWlpapNMIuz0Hc+j18Fdc0Kkxjww5LdLpiIiIiFR6ZrbQOZda0nXR8lBipVe3RhWGdm/O\nh4s3sznrcKTTEREREZEQqaCOIjf2aQ3AizPUSy0iIiJSXqigjiJN61RjcJemvDV/E7sP5kQ6HRER\nEREJgQrqKHNLv9Yczs3ntdnrI52KiIiIiIRABXWUadcwkZ+f3JDX5qznUE5epNMRERERkRKooI5C\no/u3IetQLm/N31TyxSIiIiISUSqoo9AZLevSPaUeL85YR05eQaTTEREREZFiqKCOUqP7t2HL3mwm\nfbsl0qmIiIiISDFUUEep/u2TOalRIuOmraWgoHwtviMiIiJSmaigjlJmxuj+bViz4wBfrtwe6XRE\nREREpAgqqKPYhZ0a06xuNZ6dtpbytkS8iIiISGWhgjqKxcXGcHPf1izamMX89N2RTkdEREREjkEF\ndZS7IrU59WtU4dlpayOdioiIiIgcgwrqKJcQH8sNvVOY+n0mK7bsi3Q6IiIiIlKICupy4JozW1Kz\nahzjNEotIiIiEnVUUJcDtavFc1WPFny8ZAsbdx2KdDoiIiIiEkQFdTkxsncKcTExvDBjXaRTERER\nEZEgKqjLiYa1Erjs9KZMSNtE5v4jkU5HRERERAJUUJcjo/q2Jie/gFdnp0c6FREREREJUEFdjrRO\nrsnAUxvx+pwN7M/OjXQ6IiIiIoIK6nLnln5t2J+dx/h5GyOdioiIiIiggrrc6dysDme1rc9LM9M5\nkpcf6XREREREKj0V1OXQ6H5t2bH/CO9/sznSqYiIiIhUeiqoy6Gz2tanU9PaPDd9HfkFLtLpiIiI\niFRqKqjLITNjdP82pO88yOTl2yKdjoiIiEilpoK6nDr/lEakJNXg2alrcU6j1CIiIiKRooK6nIqN\nMUb1bc3SzXuZvXZXpNMRERERqbR8LajNbICZfW9ma8zs3iKuGWJmK8xsuZmN9zOfiuay05vSILEq\nz05dG+lURERERCot3wpqM4sFngYGAh2BYWbWsdA17YDfAWc5504B7vQrn4qoalwsI3unMHPNTpZk\nZEU6HREREZFKyc8R6u7AGufcOudcDvAWMLjQNTcBTzvn9gA453b4mE+FdFWPFiQmxDFumkapRURE\nRCLBz4K6KbApaD8jcCxYe6C9mc0ys7lmNsDHfCqkxIR4rj2zJZ8t28a6zAORTkdERESk0on0Q4lx\nQDugPzAMeMHM6hS+yMxGmVmamaVlZmaWcYrRb8RZKcTHxvD89HWRTkVERESk0vGzoN4MNA/abxY4\nFiwDmOScy3XOpQOr8Arsn3DOPe+cS3XOpSYnJ/uWcHmVnFiVIanNeO+bzWzflx3pdEREREQqFT8L\n6gVAOzNLMbMqwFBgUqFrPsAbncbMkvBaQDTMegJG9WlDXkEBL89Mj3QqIiIiIpWKbwW1cy4PGANM\nBlYCE5xzy83sQTMbFLhsMrDLzFYAXwP3OOc0qfIJaFG/Ohd1bsK/525g76HcSKcjIiIiUmlYeVtl\nLzU11aWlpUU6jai0Yss+LnhiBvec34Ffnt020umIiIiIlGtmttA5l1rSdZF+KFHCqGOTWvRrn8zL\nM9PJzs2PdDoiIiIilYIK6gpmdP827DqYw7hpa1VUi4iIiJSBuEgnIOHVI6UePVvXZ+yXq3lm6lq6\nt6pHn3ZJ9GmXzMmNEzGzSKcoIiIiUqEU2UNtZncX90bn3KO+ZFQC9VCXLDs3n7nrdjFj9U5mrM5k\n1XZvwZekmlUDxXUSvdsm0aBWQoQzFREREYleofZQFzdCnRj42gHoxo9T3l0MzC9deuKnhPhY+ndo\nQP8ODQDYtjebmWu84nr6qkzeX+RNB35So8QfRq+7p9QjIT42kmmLiIiIlEslzvJhZtOBC51z+wP7\nicAnzrm+ZZDf/9AIdekUFDhWbN33Q4G9IH0POfkFVImLUXuIiIiISJBQR6hDKai/Bzo7544E9qsC\nS5xzHcKS6XFSQR1eh3PymZdedHtI77Zei4jaQ0RERKSyCUfLx1GvA/PN7H3AgMHAq6VLT6JFtSpq\nDxEREREpjZAWdjGz04E+gANmOOcW+Z1YUTRCXXbUHiIiIiKVWdhaPgI3Ow3oy48F9belT/HEqKCO\nnOD2kJmrd/L99v2A2kNERESkYgpby4eZ3QHcBLyL1/LxbzN73jn3ZOnTLEdyDkFMHMRViXQmEaP2\nEBEREZH/FcpDiUuAns65g4H9GsAc51znMsjvf0RshHr6v+CrhyCxMdRuBnWaQ+3m0PsuqFYHDmd5\nBXfVmmWfWxQoKHCs3Lbvh4cb1R4iIiIi5V04Z/lYCnRzzmUH9hOABc65TmHJ9DhFrKDeOA/WfgV7\nN0HWRu/r3s3w2/VeEf3FH2H2E5BQJ1Bst/C+/uxPUKU67N8OFgM1kqASFJRH20Nmrt7JDLWHiIiI\nSDkUzoL6buA64CezfDjnxoYj0eMVVT3UBQUQE+O93jgPNs6GrE2BonsTHNgG96zzrpl0O3zzGsRV\nCxrhbgYXjYWYWNiz3iu4E5tAbMVbEX77vuwfRq9nrt7JroM5gNce0q99Mtf2bEmzutUjnKWIiIjI\nj8L9UOLpQG+8hxJnapaPE7BpPmz+5qcj3DkHYcwC7/yE62DFB2CxUKuJV2zXbwODn/bO7/jOK7hr\nN/NGvMuxwu0h89N3A3Blt+aMObsdjWpr1FpEREQiT7N8lDcZabB92Y8j3HszAIMRn3jnX78E1n3t\nva5e3+vfbtQJBj8VeP9Cb2S7dnOoVrdctZVs3XuYp75aw4S0TZgZV3Vvwa1nt6FBogprERERiZxw\ntnwUnuXjUiBis3xU2IK6JFsWwc7VP45uZ22Cqokw5DXv/PP9vWsA4mtAcntodx6c/fuIpXy8Nu0+\nxFNfrWHiNxnExxrDe7bi5r6tqV+zaqRTExERkUoonAW1ZvkoD7Ytg93rfiy2ty+Dmg3g8pe9869c\n6M1G0rw7NOsOTbpAfLXI5lyE9TsP8sR/V/PB4s0kxMdyfa9WjOrbmjrVK++UhSIiIlL2NMuH/Kgg\nHz64FTbNgz3p3rGYODjzVjjvL97+3gyo1TSqWkXW7DjA4/9dzcdLtlCjShw39E5hZO8UaleLj3Rq\nIiIiUgn4NcsHwCVolo/y6+BOyFjgPSTZuDOccqk3pd8j7aFmQ2jWzduad4cmXaNiFPv7bft5bMoq\nPl++jVoJcYzq25rrz0qhZtWKNxuKiIiIRI9wP5R4BnBWYHeGZvmoYA7vgaUTvUI7Y4HXOgIw8P+g\nxyg4kAnrpkLzblCnZcRGsZdt3svYL1fx5cod1K0ez8392jC8Z0uqV1FhLSIiIuEX7oI6FmhI0FLl\nzrmNpcrwBKmgLgNHR7EbnurNl73sXZh4g3cueBT7tKGQ2KjM01u8KYvHpqxi2qpMkmpWYXT/tlzd\no4WWOBcREZGwCmfLx23An4DtQD7eTB9ODyVWIvl5sGN5oFVkAWTM90axR8+Bhh1h1RewZor3sGMZ\njmKnrd/NY1+uYtaaXTSsVZVfnt2WK7s1p2qcCmsREREpvXAW1GuAHs65XeFKrjRUUEeJg7u8+a5j\nYmD2U/D1XyH3kHeuRgOvB/uSZyGhFjjna4E9d90uHv1iFfPX76ZJ7QTGnNOOK1KbER8b41tMERER\nqfjCWVB/DZzrnMsLV3KloYI6SuXnwY4V3uh1RhrsXAU3/tcrpD+6A7Ys/nHKPh9GsZ1zzFyzk0e+\nWMXiTVk0r1eN289px6VdmxKnwlpEREROQKkL6sDsHgCnAB2AT4AjR8875x4NQ57HTQV1OTR3HHz3\nsbf0eu5B71ijznDLDO/17nVQNyUsBbZzjqnfZ/LolFUs3byXlKQa3PGzdlx8WhNiY6JnSkARERGJ\nfuEoqP9U3Budc38+wdxKRQV1OfbDKPYCKMiDHjd7x8d29kavL3rMW/0xDJxzTFmxnUenrOK7bftp\n26Amd/68HRec2pgYFdYiIiISgrDO8hFNVFBXMM7BtH/CtIehXmu44jVodGrYbl9Q4Phs2TYe+3IV\na3Yc4KRGidx1bnvO69gQi6JFbERERCT6hFpQF9lcamZjA18/MrNJhbcQkxhgZt+b2Rozu/cY5683\ns0wzWxzYbgzlvlKBmEH/38J1H8GRA/Diz2Dhq16hHQYxMcaFnRsz+c6+PD60C0fyCrj5jYVc/NRM\nvvpuO+XtD0oRERGJPsW1fJzhnFtoZv2Odd45N63YG3tzV68CzgUygAXAMOfciqBrrgdSnXNjQk1Y\nI9QV2IFMeO8myM6CkVMgNvxLjOflF/DB4i08/t9VbNp9mC7N63D3ue3p0y5JI9YiIiLyE6GOUBe5\nxJxzbmHga7GFczG6A2ucc+sCCb0FDAZWFPsuqbxqJsM173krN8bGw+Es2LcZGp4SthBxsTFcfkYz\nBndpwsSFGTz539UMf3k+3VrV5e5zO9CzTf2wxRIREZHKobiWj6VmtuQY21IzWxLCvZsCm4L2MwLH\nCvtF4L4Tzax5EbmMMrM0M0vLzMwMIbSUWzExUCNQ1E65H144Bxa+FrYWkKPiY2MY1r0FX9/Tn78M\nPoWNuw8x7IW5XPXCXNLW7w5rLBEREanYimv5aFncG51zG4q9sdnlwADn3I2B/WvxFogZE3RNfeCA\nc+6Imd0MXOmcO6e4+6rloxI5sAPeGwXrvoZOQwKzgNT0JVR2bj7j523kmalr2XngCH3bJ3P3ue3p\n0ryOL/FEREQk+pX6oUTn3IajW+BQu8DrHUAoQ3ibgeAR52aBY8Exdjnnjs5t/SJwRgj3lcqiZgOv\nBeSc+2DZRHi+P+z4zpdQCfGx3NA7hem/6c/vBp7E0owsLnl6FiNfXcCyzXt9iSkiIiIVQ4lLyJnZ\nTcBE4LnAoWbAByHcewHQzsxSzKwKMBT4yewgZtY4aHcQsDKUpKUSiYmBvvfA8ElgMRBX1ddw1avE\ncXO/Nsz47Tncc34H0jbs4aInZ3LzG2l8t22fr7FFRESkfApl6fHFeA8YznPOdQ0cW+qc61Tizc0u\nAMYCscB/krbFAAAgAElEQVTLzrm/mtmDQJpzbpKZ/R2vkM7DG/Ue7ZwrdghSLR+VWEGBV2A7B/Oe\ng67X+NYCctS+7FxempHOyzPTOZCTx4WdGvPr8zrQKqmGr3FFREQk8sK2sIuZzXPO9TCzRc65rmYW\nB3zjnOscrmSPhwpqIWMhvPRzqNcGrng1rAvBFCXrUA4vzFjHK7PWExdjvDA8lR6tNSOIiIhIRVbq\nHuog08zs90A1MzsXeAf4qLQJipywZmd4LSBH9gUWggn/LCCF1alehXvOP4kv7upLcmJVrn1pPp8s\n2eprTBERESkfQimo7wUygaXAzcCnzrk/+JqVSElS+sAtM6HFmfDR7fDJr8okbLO61Xl3dC86N6vN\nmDe/4aWZ6WUSV0RERKJXKC0fZxxd5CXo2EXOuY99zawIavmQnyjIhxmPQHIH6Di4zMJm5+Zz51uL\n+Xz5Nm7qk8LvBp5MTIxWWhQREalIwtny8YKZ/dCkambDgD+WJjmRsImJhX6/+bGYXvBimbSAJMTH\n8vTVp3Ndz5a8MCOdO95ezJG8fF9jioiISHQqcunxIJcDE83sKqAPMBw4z9esRE6Ec7DqC1g9GTbM\nggsf9XUWkNgY44FBp9C4TjUe/uw7Mvdn89y1qdSuFu9bTBEREYk+JY5QO+fW4c0h/R7wC+A855xW\nupDoYwbD3oSz74Ol73gLwWxf7nNI45Z+bRh7ZRcWbtjDkHFz2Lr3sK8xRUREJLoUWVCb2VIzW2Jm\nS/AWdqkHpADzAsdEok9MLPS7B4Z/6M0C8sLPIGuT72Ev6dqUV0d0Z3PWYS57Zjbfb9vve0wRERGJ\nDkU+lGhmLYt7Y9CS5GVKDyVKyA7sgJUfQbeR3v7RhWF8tGLLPq5/ZT6Hc/N5YXgqZ2quahERkXIr\nHA8l7gkUzfuL2ESiW80GPxbTmxfCuN6+t4B0bFKL927tRcNaCQx/aT4fL9niazwRERGJvOIK6vGB\nrwuBtMDXhUH7IuVH3hE4tBNeOAe+ed3XWUCa1a3OxFt6clrz2owZv4gXZ6zzLZaIiIhEXonzUEcb\ntXzICTuwA969EdKnQecrfZ8FJDs3n7veXsxny7YxsncKf7hAc1WLiIiUJ6G2fBQ5bZ6ZnV7cG51z\n35xIYiIRU7MBXPs+TP8XTP071G/nPcDok4T4WJ666nT+8vEKXpqZzrZ92Tw65DSqxsX6FlNERETK\nXnHzUD9SzDkHnBPmXET8FxML/X8LrftDky7esYO7oHo9b9q9MIuNMf50cUea1Engb59+x879R3h+\nuOaqFhERqUjU8iGVW/Ze72HFFr3gwkd8bQH5cPFmfv3Ot6Qk1eDVEd1pUqeab7FERESk9MK59LhI\nxVWlJnS5Bpa8DS+cDdtX+BZqcJemvDaiO1uzsrnsmdl8t22fb7FERESk7KiglsrtaAvI8A/hcFZg\nFpA3fJsFpFfbJCbc0hOH44pn5zB77U5f4oiIiEjZUUEtAtC6H9wyE5p3h7SXoCDPt1AnN67Fe7ee\nRaPaCVz/8gImfau5qkVERMqz4h5KBIqc7WMvsME551/VIVLWEht6s4AczoLYeO/r/q3Q4OSwh2pa\npxoTb+nFTa+ncfubi9ixL5sb+7QOexwRERHxXygj1M8Ac4HngReAOcA7wPdmdp6PuYmUvZhYqBFY\nLnzKH+H5s2HRv31pAaldPZ7XR3bngk6NeOiTlTz40QoKCsrXQ8IiIiISWkG9BejqnEt1zp0BdAXW\nAecC//QzOZGIOvs+rwXkw1/CB6Mh52DYQyTEx/LUsNMZcVYrXp6Vzm1vLiI7Nz/scURERMQ/oRTU\n7Z1zy4/uOOdWACc557SeslRsR1tA+v8evn3LG63O/D7sYWJijPsv6sgfLjiZT5ZuZfjL89l7KDfs\ncURERMQfoRTUy83sWTPrF9ieAVaYWVVA/68vFVvwLCCuAGKr+BLGzLipb2ueGNaVRRv3cPm42WzJ\nOuxLLBEREQmvEhd2MbNqwK1A78ChWXh91dlAdefcAV8zLEQLu0jEFOR7BbZzsO5raOPPYqGz1+7k\n5tcXUr1qLK+O6M7JjWv5EkdERESKF7aFXZxzh4EngfuBPwKPO+cOOecKyrqYFomomFjv67J34Y1L\n4b8P+vKwYq82SbwzuieGMWTcHGav0VzVIiIi0azEgtrM+gOrgafwRqZXmVlfn/MSiV6nXAqnXwcz\nHoGP7/JGrsPspEa1eO/WXjSuk8B1r8znw8Wbwx5DREREwiOUHupHgPOcc/2cc32B84HH/E1LJIrF\nxMLFj0Pvu2DhK/DuSMjLCXuYJnWq8c7NvTi9RV3ueGsxz09fS0ktWiIiIlL2Qimo451zP0xt4Jxb\nBcT7l5JIOWAGP38Azv0LrPgQNs72JczRuaov7NyYv336HX/+aAX5mqtaREQkqoRSUKeZ2Ytm1j+w\nvQCE9FSgmQ0ws+/NbI2Z3VvMdb8wM2dmJTZ9i0SVs26HX86H1v29/YKCsIeoGhfLk0O7MrJ3Cq/O\nXs9tb36juapFRESiSCgF9WhgBXB7YFsROFYsM4sFngYGAh2BYWbW8RjXJQJ3APNCT1skiiS1876u\n+RKe7wf7toQ9REyM8ceLOnLfhSfz6dJtDH9pPlmHwt9mIiIiIscvlFk+jjjnHnXOXRbYHnPOHQnh\n3t2BNc65dc65HOAtYPAxrvsL8A+8afhEyq/YKrB7Hbx8Puxa60uIG/u05slhXVm8KYvLx81hs+aq\nFhERibgiC2ozW2pmS4raQrh3U2BT0H5G4FhwjNOB5s65T4q7kZmNMrM0M0vLzMwMIbRIBKT0hes+\n8pYof/l82BrKfybH7+LTmvDaDd3Zvi+by56ZxYot+3yJIyIiIqEpboT6IuDiYrZSMbMY4FHgVyVd\n65x73jmX6pxLTU5OLm1oEf80PR1GfA6xVeHVCyFzlS9herapz8RbenlzVT83h1maq1pERCRiiiyo\nnXMbittCuPdmoHnQfrPAsaMSgVOBqWa2HjgTmKQHE6XcS24PIyfD6cOhfhvfwnRolMj7v+xF0zrV\nuF5zVYuIiERMKA8lnqgFQDszSzGzKsBQYNLRk865vc65JOdcK+dcK2AuMMg5p3XFpfyr3QzO/6s3\nZ/W+LbD8fV/CNK5djQm39Pxhrupx0zRXtYiISFnzraB2zuUBY4DJwEpggnNuuZk9aGaD/IorEnWm\n/RPeuR7mjvPl9rWreXNVX9S5MQ9/prmqRUREylpcKBeZWTWgRfACL6Fwzn0KfFro2P1FXNv/eO4t\nUm4MeBgOZsLnv4XDu6H/77yFYcKoalwsTwztSuPaCbwwI51te7MZO7QLCfGxYY0jIiIi/6vEEWoz\nuxhYDHwe2O9iZpOKf5eI/CA+Aa54DbpeA9P+AZ/e48sCMDExxh8u7MgfL+rI5BXbuPaleZqrWkRE\npAyE0vLxAN6c0lkAzrnFQIqPOYlUPLFxMOgp6HUbrJkC2Vm+hRrZO4Unh3Xl2017+cWzs1m5VdPq\niYiI+CmUgjrXObe30DE1aIocLzM47yEYNQ2q14P8PMg55Euoizo34fWR3dl7OJdBT83k8S9Xk5sf\n/lFxERERCa2gXm5mVwGxZtbOzJ4EZvucl0jFVa2O9/XjO+CNS+GwP6PVZ7auzxd39WPgqY157MtV\nDH5Ki8CIiIj4IZSC+jbgFOAIMB7YC9zpZ1IilULbc2HLN94CMPu3+RKiXo0qPDGsK+OuOYMd+48w\n6KmZjP1yFTl5Gq0WEREJFytpzlozO905900Z5VOi1NRUl5amqaqlglj7Nbx1NdRMhms/gHr+PZ6w\n52AOf/5oOR8s3sLJjWvxrys6c0qT2r7FExERKe/MbKFzrsRFB0MZoX7EzFaa2V/M7NQw5CYiR7U5\nG66bBNl74fVBkHfEt1B1a1Rh7NCuPH/tGew8cITBT83i0SkarRYRESmtEkeoAcysETAEuBKoBbzt\nnHvI59yOSSPUUiHt+A72rIcOA8okXNahHP780QreX7SZkxol8q8rTuPUphqtFhERCRbqCHVIBXXQ\nTTsBvwGudM5VKUV+J0wFtVR4374N1etDu5/7HurLFdv5/ftL2XUwh1v7t2HMOW2pGqfFYERERCCM\nLR9mdrKZPWBmS4GjM3w0C0OOIlJYQT7Mfw7evBKWTvQ93M87NmTKXf0Y3KUJT361hkFPzmJpRuFZ\nMkVERKQ4ofRQv4y3qMv5zrn+zrlnnXM7fM5LpHKKiYVr34fmPeDdG2HBi76HrF09nkeHdOGl61LJ\nOpzDJc/M4v8mf8eRvHzfY4uIiFQEx9XyEQ3U8iGVQu5heGcErPoMzr4P+v7aWxjGZ3sP5fKXT1Yw\ncWEG7RvW5F9XnEbnZnV8jysiIhKNSt3yYWYTAl+XmtmSoG2pmS0JZ7IiUkh8NbjyDeg8FA6W3T8I\n1a4ez7+uOI1Xru/GvsN5XPrMbP75uUarRUREilPkCLWZNXbObTWzlsc675zb4GtmRdAItVQqBYEp\n7WJiIGsTJDaC2PgyCb33cC5//WQFE9IyaNegJv93xWl0aa7RahERqTxKPULtnNsaeHmrc25D8Abc\nGq5ERaQYMTHedmQ/vHw+vH2t1w5SBmpXi+efl5/GqyO6ceBIHpc9M4uHP/uO7FyNVouIiAQL5aHE\nc49xbGC4ExGRYlRNhD53w6rP4d+/8BaCKSP9OzRg8l19GZLanHHT1nLhEzNYtHFPmcUXERGJdsX1\nUI8OTJXXoVAPdTqgHmqRstbtRvjFi7BpHrx6ERzILLPQtRLiefgXnXnthu4czsnnF8/O5u+frtRo\ntYiICMX3UNcG6gJ/B+4NOrXfObe7DHI7JvVQS6W3+kt4+xroMBCueKXMw+/LzuXvn67kzfmbaJNc\ng39efhpntKxb5nmIiIj4LewrJZpZAyDh6L5zbuOJp3fiVFCLABlpULcV1EiKWArTV2Vy77tL2Lov\nmxt7p/Cr8zqQEK9VFkVEpOII50qJF5vZaiAdmAasBz4rdYYicuKapXrFdF6OtwBMRtn/kdm3fTKT\n7+rLsO4teGFGOhc8PoOFGyL2j1ciIiIRE8pDiQ8BZwKrnHMpwM+Aub5mJSKhObQTMhbAa4Ng7Vdl\nHj4xIZ6/XdqJf4/swZG8Ai4fN4eHPl7B4Rz1VouISOURSkGd65zbBcSYWYxz7mugxKFvESkDtZrA\nDZO99o//DIHlH0Qkjd7tkph8V1+u6t6CF2emc8ETM1iwXqPVIiJSOYRSUGeZWU1gOvAfM3scOOhv\nWiISssRGMOITaHoGvHM9LPp3RNKoWTWOv17aifE39iA3v4Ahz83hwY80Wi0iIhVfKAX1YOAwcBfw\nObAWuNjPpETkOFWrC9e+DydfDPXaRDSVXm2TmHxnX67p0ZKXZ6Uz8PHpzE/XaLWIiFRcIc/yES00\ny4dIiNKnQ6s+YBaxFGav3clv311Cxp7DXNezFb8Z0IHqVeIilo+IiMjxCOcsH/vNbF+hbZOZvW9m\nrcOTroiE1ca58NrF8OEv4ciBiKXRq00Sn9/Rl+FntuTV2esZ+PgM5q3bFbF8RERE/BBKy8dY4B6g\nKdAM+DUwHngLeNm/1ETkhDXvAf3uhcX/gcdPgzlPQ+7hiKRSo2ocfx58Km/edCbOwZXPz+VPHy7j\n4JG8iOQjIiISbqEU1IOcc8855/Y75/Y5554HznfOvY23kmKRzGyAmX1vZmvM7N5jnL/FzJaa2WIz\nm2lmHU/w+xCRYGZw9u9g5BRoeApM/j08fzYUFEQspZ5t6vP5nX24vlcrXpuzgQGPT2fOWo1Wi4hI\n+RdKQX3IzIaYWUxgGwJkB84V2YBtZrHA08BAoCMw7BgF83jnXCfnXBfgn8Cjx/8tiEiRmneH6ybB\ndR9Dn19BTIxXVC97F/LLfoS4epU4Hhh0Cm+POpMYM4a9MJf7NVotIiLlXCgF9dXAtcAOYHvg9TVm\nVg0YU8z7ugNrnHPrnHM5eC0ig4MvcM7tC9qtQTEFuoiUQkof6HyF93rNFJh4AzzdDZZMgIKyn9au\nR+v6fHZHH0ac1Yo35m7g/LHTmb1mZ5nnISIiEg4lFtSBgvhi51yScy458HqNc+6wc25mMW9tCmwK\n2s8IHPsJM/ulma3FG6G+/Xi/ARE5Tu3Og6FvQnx1eO8meLYXrPiwzNtBqleJ408Xn8KEm3sSF2Nc\n9eI87v9wGdm5mrdaRETKl1Bm+WhvZv81s2WB/c5mdl+4EnDOPe2cawP8Fjjmfc1slJmlmVlaZmZm\nuEKLVE5mcNIFcPMMuPwVcAXw6W8g/0hE0unWqh6f3dGXEWe14vU5G7joyZks37I3IrmIiIiciFBa\nPl4AfgfkAjjnlgBDQ3jfZqB50H6zwLGivAVccqwTzrnnnXOpzrnU5OTkEEKLSIliYuDUy+DWuXD9\nJxBfDfJyYMJ1sPZrKMM56qtVieVPF5/C6zd0Z9/hXC55ehbPT19LQYG6wEREJPqFUlBXd87NL3Qs\nlCeIFgDtzCzFzKrgFeGTgi8ws3ZBuxcCq0O4r4iEU0wsJLX1Xu9ZDxlp8MYl8OpFsGFOmabSt30y\nn9/Zl3NOasDfPv2Oa16ax9a9kZnuT0REJFShFNQ7zawNgQcGzexyYGtJb3LO5eE9tDgZWAlMcM4t\nN7MHzWxQ4LIxZrbczBYDdwPXncg3ISJhktwebv8GBv4f7FoNrwyANy6DAzvKLIV6Naow7pozePiy\nTizamMWAsTP4ZEmJ/5MjIiISMSUuPR5YDfF5oBewB0gHrnHOrfc9u2PQ0uMiZSTnECx4EVZ+BCM+\ng9g4yN4LCbXLLIX0nQe5861FfJuxl8vPaMYDg06hZlUtXS4iImUj1KXHSyyog25YA4hxzu0vbXKl\noYJapIw55z3ImHMQnugKLXtB/99BcocyCZ+bX8AT/13N01+voVnd6jx2ZRfOaFnsmlIiIiJhEWpB\nHcosH1XN7CrgDuAuM7vfzO4PR5IiUg6YeV+dg9OHw+op8MyZ8N7NsHud7+HjY2P41XkdePvmnuQX\nOIY8N4fHpqwiLz9yqz6KiIgEC6WH+kO8BVnygINBm4hUJlVrwjn3wR1LoOcYb+7qJ1Nhy+IyCd+t\nVT0+u7MPg05rwuP/Xc2Q5+awcdehMoktIiJSnFB6qJc5504to3xKpJYPkSixfxss/g/0vtsbxV49\nBRp1gsRGvoee9O0W/vD+UgoKHA8MOoXLz2iGHR1JFxERCZOwtXwAs82sUxhyEpGKJLER9PmVV0zn\nZsN7o+Dx0+CL++Cgv8uIDzqtCZ/f2ZdTmtbmnolLGDN+EVmHcnyNKSIiUpRQRqhXAG3xZvc4Ahjg\nnHOd/U/vf2mEWiRK7V4H0/4JS96GuGpw5mjoNQaq+fcAYX6B47npa3n0i1Uk1azKo0NOo1fbJN/i\niYhI5RK2WT7MrOWxjjvnNpxgbqWiglokymV+D1P/Dsvfh+EfQuv+vodcmrGXO95aRPqug4zq05q7\nz2tP1bhY3+OKiEjFFvZp86KFCmqRcmLnGqjfxmsJmfoPiE+AbjdBleq+hDuUk8dDn6xk/LyNdGxc\niyeGdaFtg0RfYomISOUQzh5qEZHjl9TWK6adg63fwpT7vR7rec9B3pGwh6teJY6/XdqJF4ansm1f\nNhc+MZM35qynvA0aiIhI+aOCWkT8ZQbDxsOIzyGpPXz2G2+BmNVf+hLu3I4N+fzOPpzZuj5//HA5\nI19LI3N/+At4ERGRo1RQi0jZaNkTrv/Y66uu1RSq1/OOZ++F/LywhmqQmMCrI7rxwMUdmblmJwPG\nTuer77aHNYaIiMhRKqhFpOyYeQ8pjvwCmp7uHfv8997Ki8vehYLwrX5oZlx/Vgof39ab5MSq3PBq\nGn/8YBmHc/LDFkNERARUUItIJAQvwtJhIMTEwcQb4JWBsDcjrKHaN0zkwzFncWPvFN6Yu4GLnpzB\nss17wxpDREQqNxXUIhJZJ18Eo2fB4Gdg+zIY1xvWzwxriKpxsdx3UUf+PbIHB47kcekzsxg3bS0F\nBXpgUURESk8FtYhEXkwsdL0aRk2DBqdA7Wa+hOndLonP7+jLz05qyMOffcfVL85jS9ZhX2KJiEjl\noYJaRKJHUlsY8QnUbeVNt/fVXyFrU1hD1K1RhWevOZ1//qIz32ZkMWDsdD5esiWsMUREpHJRQS0i\n0WnXWpj7LDzXB77/LKy3NjOGdGvOp7f3oXVyTcaMX8SvJnzL/uzcsMYREZHKQQW1iESnpLZw8zSo\n3RzeHAqT/wD54S14WyXV4J1benL7OW15f1EGFzwxg4Ubdoc1hoiIVHwqqEUketVvAyOnQLcbYc5T\nMP5KrxUkjOJjY7j7vA5MuLknzsEV4+bw2JRV5OWHbwo/ERGp2Ky8Lcubmprq0tLSIp2GiJS15e9D\nTLw3K4hP9mfn8qdJy3nvm810bVGHsVd2oWX9Gr7FExGR6GZmC51zqSVdpxFqESkfTrn0x2J67jhv\nQZi8nLCGSEyI59EhXXhyWFfW7jjABY/P4J20TZS3gQcRESlbKqhFpPzZuwnmPg2vDIA9G8J++4tP\na8Lnd/alU7Pa3DNxCb8c/w1Zh8JbvIuISMWhglpEyp/z/wpD3oCda7xZQFZ+HPYQTepU4z83nsm9\nA09iyortDBg7g9lrdoY9joiIlH8qqEWkfOo4yJsFpF5rePtq2LYs7CFiY4xb+rXh/VvPonrVWK56\ncR5//WQFR/Lywx5LRETKLxXUIlJ+1UuBGyZ7o9WNTvWO5RwKe5hTm9bmk9v6cM2ZLXhhRjqXPD2b\n1dv3hz2OiIiUTyqoRaR8i6vqjVYDbF4IYzvBig/DHqZalVgeuqQTLw5PZce+bC58Yia/e28p6TsP\nhj2WiIiULyqoRaTiqJ4EdVvChOHw6T2QdyTsIX7esSGf39mXK1Kb8e43GZzzyFRu/c9ClmRkhT2W\niIiUD5qHWkQqlrwc+PIBbxaQxl3gile8PmsfZO4/wiuz0nlj7gb2Z+fRq019bunXhj7tkjAzX2KK\niEjZiYp5qM1sgJl9b2ZrzOzeY5y/28xWmNkSM/uvmbX0Mx8RqQTiqsCAv8HQ8bAnHdJe9i1UcmJV\nfjPgJGbfew6/v+Ak1mYeYPjL87noyZl89O0WrbYoIlJJ+DZCbWaxwCrgXCADWAAMc86tCLrmbGCe\nc+6QmY0G+jvnrizuvhqhFpGQZW2Cmg28Putda6FWU4hP8C3ckbx8Ply0hXHT17Iu8yAt6lXnpj4p\nXJHanIT4WN/iioiIP6JhhLo7sMY5t845lwO8BQwOvsA597Vz7ugj+XOBZj7mIyKVTZ3mXjGddwTe\nuBReOtcrrH1SNS6WId2a8+Vd/Xju2jOoV6MKf/xwOWc9/BVPfbWavYdyfYstIiKR42dB3RTYFLSf\nEThWlJHAZ8c6YWajzCzNzNIyMzPDmKKIVApxVWHgP70VFp/rB8ve9TVcTIxx/imNeP/WXrw16kw6\nNavNv75YRa+H/8tDH69g697DvsYXEZGy5WfLx+XAAOfcjYH9a4Eezrkxx7j2GmAM0M85V+xj+Wr5\nEJETlrUJJt4AGfMh9QY4/+++toAEW7l1H89NW8tHS7YSYzC4S1Nu6deatg0SyyS+iIgcv2ho+dgM\nNA/abxY49hNm9nPgD8CgkoppEZFSqdMcRnwKZ90BWxZDGc7EcXLjWowd2pWpv+7P1T1a8vGSLfz8\n0enc+FoaCzfsLrM8REQk/PwcoY7DeyjxZ3iF9ALgKufc8qBrugIT8UayV4dyX41Qi0hY5B3xWkEO\n74H06dBxcMnvCaPdB3N4bfZ6XpuznqxDuXRrVZfR/dtwdocGmnJPRCRKRHyE2jmXh9fGMRlYCUxw\nzi03swfNLLCsGf8H1ATeMbPFZjbJr3xERH4irqr3dc7T3kIwH90BuWXX21yvRhXuOrc9s+89h/sv\n6siWrGxueDWNAWNn8N43GeRqyj0RkXJDC7uISOWWnwtfPQSzxkLDU+GKVyGpXZmnkZtfwEffbuG5\naev4fvt+mtapxsjeKQzt3pzqVeLKPB8REQl9hFoFtYgIwOop8N7/t3fn8VXXd77HX59zsu8JCZBA\ngCQsBSuCiKAIOrWjUp3q9Op1q2MXa53q7fLoMnW63Ht7p3fsdJvemU7Vtlbb2trWtjO2da0r1AVx\nRUEIEBBCgOz7fr73j+8vqyhoOPxyDu/n43Ee57dx8smvNnnz5fP7fq/1rSCX3A7zzwmlDOccj249\nyM2P7WTDriYKslL5u9Pm8KHT51CUnRZKTSIixysFahGRt6u1Fv74GVj7DSiqCLsantvdzM2P7+Ch\nzQfISI1w6SnlXLO6kvKirLBLExE5LihQi4hMhHPw0Fdh6VVQMj/UUqoPtHPLEzv5rxdriTm4YHEp\n151ZxcLSvFDrEhFJdgrUIiIT0bwbfvhX0N8DF3wHTros7Iqoa+3mx+tq+OWG1+nsG+SsBSVcd2YV\nKyqKNDOIiEgcKFCLiExU2z747TWw+y+w9IOw9puQFn67RWtXPz97ehc/+csuGjv7WFJewHVnVnHO\nomlEIgrWIiJHiwK1iMjRMDgAj98ET3wLylfAR+4/pgvCvJWe/kF+89xefvjETl5v6qKyJJuPr6nk\noqUzSE+Jhl2eiEjCU6AWETmadjziZwBZsNb3V0+SUA0wMBjjvlf284PHdrC5ro1peel8ZFUFV6yY\nRW5GatjliYgkLAVqEZF4efoHsO8FWPP5UOasfjPOOdZVN3Dz4zt4ckcjuRkpfHDlbD68ag5TczPC\nLk9EJOEcaaDWagEiIm9Xbwdsuhte/hXMPBWWXgknfAAywp11w8xYM7+ENfNLeGlPC7c8sYObH9/B\nj9fX8J4FU1k1dwqnVU2hqiRHDzGKiBxFGqEWEXkn2vf7QP3CndCwFeadC1f+2p+bRC0hNQ2d3La+\nhoe3HGBfaw8AJbnpnF41hdOrpnBaZTHlRZkK2CIih6CWDxGRY8E5qH3eb89c5mcG+claWHwpnHT5\npJkB208AABstSURBVFggBnw7yOtNXTy1o5Eng1dDRy8AMwoyfbgOXqX5mSFXKyIyOShQi4iE4eBr\n8MCNsONRwMHsM3xLyKILIS077OqGOefYUd/hw/X2Rp7a2Uhrdz8AlcXZrAxGsFdWTqE4Jz3kakVE\nwqFALSISpta98NJd8OKd0LQTbngOiudCTyuk502alpAhsZhjy/624RHsDTVNdPQOAPCu6bmsrPQB\ne0XlFPIzNXOIiBwfFKhFRCYD52D/Jihd7Pd/dZXfX3IlLLkc8meGW9+bGBiMsam2lSd3NPLUjkY2\n7m6ipz9GxOCEsvzhFpHlc4rITtfz7SKSnBSoRUQmo013w3O3w651gEHlWXDqx+Bd54db12H0Dgzy\n4ustPmDvbOSF15vpH3SkRIyTyguGA/bJswrJSNWiMiKSHBSoRUQms6aaoCXkFz5Mr70JYjGoexHK\nlk66lpDxuvsG2bi7abhF5OW9LcQcpKVEWDarcDhgn1ReQGo0Ena5IiLviAK1iEgiiMWgvwvSc6Dm\nCbjjb6B4gX+QcfGlkDs97AqPSHtPP8/uauLJ7T5gb65rAyArLcryOUXDAfuEsnyikcn9lwURkSEK\n1CIiiaanDV79vX+Qcc8zYFGY+144/9tQUB52dW9Lc2cfz9SMTNG3/WAHALkZKaysnMJplVM4fe4U\n5k/NJaKALSKTlAK1iEgia6j2wfq1e+HaxyAtC3Y+BpmFUHpSyMW9fQfbenhqp3/A8amdjexu7AJg\nSnYaK6uCgF01hYribC0yIyKThgK1iEgyGL3q4s2rYf/LMO1E3xJy4iWQXRxufe/Q3uau4XD95PZG\n9rf5VRyn52VwetUUzphXzBlzi5malxFypSJyPFOgFhFJNl1N8Mpv/cj1vhcgkgqrPgVnfyXsyibE\nOceuxqFVHBt4ckcjTZ19gJ8De/W8Ys6YV8Kpc4rITNMMIiJy7ChQi4gkswOv+hlCypbCiRf7sL3+\nO35+66kLw65uQmIxx+a6NtZvb2BddT3P1jTTNxgjLSXC8jmFrJ5Xwhlzi1lUmqf+axGJKwVqEZHj\nybYH4K4rIDYAZSfDkit80M4sDLuyCevuG2TDribWbatnXXUDWw+0A77/eqg1ZPW8Eqbnqz1ERI4u\nBWoRkeNNRz1s+jW8cCccfBWi6XDDs1A4O+zKjqoDbT2sr24IRrAbaOjoBWDe1BxWzyth9bxiVlQW\nkZWmFRxFZGIUqEVEjlfO+QViqv8Maz7nH2q87x+gtx3mnwdV7/HzXicB5xyv7W9nXbUfvd5Q00Tv\nQIy0aIRlsws5Y14xa+aVcEKZ2kNE5O1ToBYRkRF/+pwfve5phWgaVJzpF45ZfEnYlR1VPf2DPLur\nifXVDTxR3cCWYIGZwqxUVs314fqMecWUFWSGXKmIJAIFahERGWuwH15/GrbeB1vvhYrV8P5/8yPa\nf/keVP0VTF886Zc9fzvq23v5y/YGnqiuZ311AwfbfXtIVUn2cHvIysopZKerPURE3mhSBGozOw/4\nHhAFfuScu2nc+TXAvwKLgcucc3cf7jMVqEVEjgLnYKAHUjP9IjL/vhxwkDfDt4UsWAtzVkNq8jzo\n55xj24GO4faQZ2oa6emPkRo1ls4qZE0wPd+JM7Q8uoh4oQdqM4sC24C/BvYCzwKXO+c2j7pmDpAH\nfA64R4FaRCQkHfVQ/SBsuw+2PwL9nfC3t8JJl0J3i589JEEXkXkzPf2DPLe7mXXVfnq+V/f59pD8\nzFRWzZ0yPD1feVFWyJWKSFgmQ6A+Dfhfzrlzg/0bAZxz/3yIa28H/qhALSIyCfT3wK71MHOZn3bv\nqf+AB/4Rylf4kesFa6F4flK1hgA0dPj2kHXVDayvbhhevbGiOJvV8/zUfCsri8jNSA25UhE5ViZD\noL4YOM85d02wfxWwwjl3wyGuvZ23CNRmdi1wLcCsWbOW7d69Oy41i4jIIdRvhVd+5/uu97/sjxVV\nwcefSJrZQsZzzrH9YMfw6PXTO5vo7h8kGjFOnlXAGXNLWD2/mMUz8kmJRsIuV0TiJKkC9WgaoRYR\nCVHrXth2Pxx8Dc7/lj/2n9fDYJ8fuZ57NmTkh1tjHPQODPL87hbWVdezfnsDm2pbcQ5yM1JYUl7A\norI8FpXmsbA0j8ribIVskSRxpIE6no811wLlo/ZnBsdERCRR5c+E5deMPZaa4UevN/0aIikw5wxY\n8sGkmpIvPSXKaVVTOK1qCl8Amjr7eHKHbw15eW8rt62voX/QD1ClpUSYPy2HhdN9wF5UlsfC6Xnk\nZ6lVRCRZxXOEOgX/UOLZ+CD9LHCFc+7VQ1x7OxqhFhFJXLFB2PusD9Zb74Oqs2HtTf74E9+Eue/1\nS6JHknPktn8wxo76Djbva2NLXRtb6trZUtdGY2ff8DUzCjJZWJrLwmAke2FpHrOLsrTgjMgkFnrL\nR1DE+/DT4kWB25xzXzezrwEbnXP3mNly4PdAIdAD7HfOnfBWn6lALSKSAAb6ICUN9r8Ct6wGF4Ps\nqbDgPJi/FirPgrTknj3DOUd9ey+bRwXszXVt7KzvIBb86s1Ki/Ku6WND9rum52pebJFJYlIE6nhQ\noBYRSTBdTVD9kJ+Sr/rP0NcOl/4cFv4NdDb4UezcaWFXecz09A+y7UD78Ei2D9xttPcMAH7ylNlF\nWcMBe1FpHgvL8ijLz8CSbGYVkclOgVpERCafgT7Y/RcoPxXSsn07yCP/BDOWBVPyvQ+mLkq6KfkO\nxzlHbUt30DIShO39bexu7Bq+Jj8zdXg0e+gByHnTcshIjYZYuUhyU6AWEZHJr6EaNv8nbL0faoOf\n7QWz4FMv+1C941Ho64SiSiick/RtIuN19A6wdX8bm4dCdl0br9W1090/CEA0YlSVZI9pGVlYmsvU\n3ORZ4VIkTArUIiKSWNr3w7YHoGEbnPt1f+ynF8LOx0auyS31Dzde/gu/v3cjRFOhsAIy8o55yWEY\njDl2N3aOjGQHr32tPcPXFOekjRnJXliaR2VJNqmazk/kbVGgFhGRxNfdDE010LRz5D2aAu//N3/+\n1rNg3wt+O7vEB+tZK+Gc/+OPNVRD1hS/4mOSt5G0dPWN6cneUtdG9YEO+gZjAKRFI8ydmkNFSTaV\nxdlUjHoVZKWFXL3I5KRALSIiye/AZmisDgJ3ELrzyuADt/rz/2+pP56R79tGiiph9ipY/lF/vqsp\nqcN2/2CMnfWdI+0i+9vZ1djJnqau4ZlGAAqzUqkozmZO8VDYzmFOcRYVxdlkpWnGETl+KVCLiIhs\ne8CPUg8F7uYamHEKXPxjf/5fqqC/OwjbFSOBe/45/rxzSRm2+wZi7Gnuoqa+k5qGTmoaO4e397f1\njLl2el5GEK5zqAxCd0VxNrOKskhLUQuJJLfJsFKiiIhIuOaf61+jDQ0kOQdnfmGkleTgFr8oTU+L\nD9SxQfhGBeSVjoxuF86B8hVQuviYfytHU1pKhKqSHKpKct5wrqtvgF0NXdQ0dLKrsZOd9Z3UNHTw\nwKv7aRq1UE3EoLwoizlTfMCuLMke3i4ryCSqBWvkOKJALSIix5ehEWczWPHxsedig37EGmCgF5b9\n3Ujg3vEoDHTD6Z/0gbqvE25e7UP28Gs2lC7x7wkqKy2FRWV+yfTxWrr6/Ih2Qye7GjrZGYTujbua\n6OwbHL4uLSXC7CLfMlJRkk1FELQrSrIpyUnXfNqSdBSoRUREhkSikB6M2qZlwTn/NHLOOT8TiQVt\nDn2dMP3d0Lwbap/zI9sA7/kKrPkctNXBXZf7oF0weyR0Tz8RsouP4Td19BRkpbF0VhpLZxWOOT60\nKuTOIGjXBGG7pqGTx7bWDz8YCZCTnjLcQuIfigy2p2STn5V6rL8lkaNCgVpERORImPn2jyE5U+G/\n/3Rkv7sFWnb7WUXAj2ZnFkHdy7DljxDr98fP/zYsvwYatsOfPjM2bBdWQMl8SM89Vt/VUWFmTM3L\nYGpeBisrp4w5Nxhz7GvpHh7ZHnq9tKeFP728b8zDkUXZaWNmHynJSSc3I4XcjNTg3W/nZaaQnqIF\nbWTy0EOJIiIi8RYbhLZ9PnAXVkD+DNj3Itz7eWjeBZ0HR679wI9g8SU+iD/+jZGwPTp4pyTHNHe9\nA4PsaRoK2x3UNHQF750caOt9yz+blhIhb1zYzhveHvueN3xubDDXQ5VyOHooUUREZLKIRKGg3L+G\nlC2Bax7y232dvnWkeReULfXHelqgcTtsf9iPdg+54jf+ock9G2DjbW8M2znTIJIYQTE9JcrcqTnM\nnZoDTBtzrqtvgKbOPtp7BoJXP+09A7SNe2/vGaCtu5/2nn4OtvUOXzu6p/vNv36EvMyR8J03FLbT\n/Sj4+GA+FNrzRu2naLEcQYFaREQkfGnZMG2Rfw2pWAPXP+N7tzsO+rDdsnskcLftg5on4KW7gFH/\n2vyRB2HWCqhZB1vuGRe4ZydMO0lWWsqE5sAeGIzR0TvwhvDd3tMfBPAB2nuD/eFQPsC+lu7ha4eW\neH8rmalRcjNSKMxKo6wgg7KCTGYUZjKjIHgVZjI1N0OzniQ5BWoREZHJzAxyp/nXrBUjx0+4yL8G\neqFljw/czTVQssCfb6z2Ybu3beznXf+s79N+7V7Ydj/kz4S8Gb4NJW+mD97RxI8HKdEIBVlpE1oF\nsn8wNnZ0vLuP9t5B2rv7KHz9ISIddaR1HSCj5yAD/b082rCcu/Ysp6Wrf2wtEWN6fsZwwB4dtsuC\n7YxU9YQnssT/f4yIiMjxLCUdiuf612infASWfdgv3968a2SEO3+mP99cA6/9Cboaxv65z27z4f25\n2/283MNhO3jNWgnRJJuNwznfYjPQ5793gHXfIbV1L0XtdRS11/lZW+aeDRf9h7/+/i/5VpxICuSW\nQgqsWHQCXzz3HDo7O7E7L6Y+/wRqMt/NJlvA9s4Mapu7eXpHI/vbesY8jAlQnJM2HK7LRgXuofBd\nkJWq6QYnMQVqERGRZGUGWUX+NePksedOu96/+nugfR+01kJbLWSX+PMDvf7Ynmd8KB/ypf0+UD/2\nDdh678gId16Z3150kR/hniyrTA70QXudf1kUypf743/4lF9FcygsD3TDgvfB5b/05zfc6u9Bbqmf\n3WXaCX4VTfDf18ce8dMfZhWP9KwPDgCQPdAMkX5mb72d2bF+zgKYMhfe82U44W/pHxhgf2sP+1p7\nqW3ppra5m32t3ext7mbbgXYe3XqQnv7Y6O+CrLToIYP20Cj3tNx09XOHSIFaRETkeJaaMbIS5Ggr\nPj6y8E1fpw+d7XWQmumP5Uz1gbJxh+/l7m2DaDq8+7/583/4JFQ/5IN23gwftvNnwspP+EDa0+Z7\nxyPvsNUhFoPuJt9L3l7n31Oz4KRL/fmfXwz7noeuxpE/M3sVfPhev92yx4f+0iU+SOeWju1h//Sm\ntx6JH33tkKFWmfyZcM2f/SJB+170fynZ8wxkFACQuvcZyu+6gvLyU/3Km5UrYMYyP/c5fl7vps4+\n9rX0UNvSxd7m7uHt2pZuNtW2jlm1EiAaMabnjW0rGd/PnZkW37YS5xyDMcdAbNz7YGzcsRj9g2P3\nB4L9/nH7AzFHzDkuXDIjrrVPlKbNExERkYnrafMPTw61nrx0F+xaNzLy3VrrA/Tnq/35u670LSW5\npcHo9oyRUVzwK1S21QZBfp9fVCcte+T8LWug7qWxNUw/Ea5b77cf/DL0doyMMOeW+Ycyi+fF/14c\nzv5XYMMtfqaW+tf8sUgKfOhPvqWm4yDEBvx9eRNdff4BytqWHmqbu6lt6fKhu7mb2pZu9rf1MDiu\nr6QoO3hwMj+TtJTIIcLvoYPuyDUxBoP9gSAoj/+MeIgY7Pzn8+Py2YdzpNPmKVCLiIhI/DkHfR0j\ns4xs+YMfvW2rhda9/j01G/4+CMS3X+AD+ZDUbJi5DK7+g99//md+5HwoLOeV+ikDE62/u6sJ9m70\nI9irPgkZ+fD4v8CjX4f8cig/FcpX+vfpJx7xiP7AYIwD7b0+dAche7i9pKWbwZgjJWpEIxFSIkY0\nYqREjJSokRKJDO9HRx0bve/PB8eiQ9dGRn3G2M9OPcTX8scP/bWi4z6nojg7zv9DHJoCtYiIiCSu\nmnXgBv0Ic24pZOSFXdGxU78NdjwCe56G15/xI/QWhRv3+FH6nY/5fu2Zp0BmQdjVJjUt7CIiIiKJ\nq2J12BWEp2S+f628zu+37PGtIWnBKO26b/u+dQymLvR92HPOgBMvDq3k450CtYiIiMhkNn6Vzct+\nCbXPjTzs+Mrv4MCrI4H6z/8bMgt90C5b4qdWlLhSoBYRERFJJOk5UHmmf4Gf8WRoNpNYzC/Yc3Cz\n34+m+dU1T7rMz00ucaFALSIiIpLIIhHIKRnZ/sRTfqaQPRt8H/aeDdB+wJ/v6/IzpGTkA84/LAqw\n7GpY9iHobICffyA4HpxzwCkfhuUfhY56+On7R84PvS//GKy41n/d284b+9k4WHEdrPx7f/6HZ7/x\n/MpPwOk3+DpvWTP2/GW/GJk/fJJSoBYRERFJNjlTYeEF/jVaT4vvu+7r9PtmgEFKML+4RfxDoH5n\nZHGejHz/HonClKpx520k0EdT/Yj46M8GPxc5+BHzOWe88XxRhX9PSYf55449n1X0Dm/CsaNZPkRE\nREREDuFIZ/nQGpUiIiIiIhMQ10BtZueZ2VYz225mXzzE+XQz+1Vw/hkzmxPPekREREREjra4BWoz\niwLfB9YCi4DLzWz8wvcfBZqdc3OB7wLfiFc9IiIiIiLxEM8R6lOB7c65nc65PuAu4MJx11wI3BFs\n3w2cbTbU/S4iIiIiMvnFM1DPAPaM2t8bHDvkNc65AaAVmBLHmkREREREjqqEeCjRzK41s41mtrG+\nvj7sckREREREhsUzUNcCo9bJZGZw7JDXmFkKkA80jv8g59ytzrlTnHOnlJSUxKlcEREREZG3L56B\n+llgnplVmFkacBlwz7hr7gGuDrYvBh5xiTYxtoiIiIgc1+K2UqJzbsDMbgAeAKLAbc65V83sa8BG\n59w9wI+Bn5nZdqAJH7pFRERERBJGXJced87dC9w77thXR233AJfEswYRERERkXhKiIcSRUREREQm\nKwVqEREREZEJUKAWEREREZkAS7RJNcysHtgd0pcvBhpC+trJTPc1fnRv40f3Nn50b+NH9zZ+dG/j\nJ8x7O9s5d9g5mxMuUIfJzDY6504Ju45ko/saP7q38aN7Gz+6t/Gjexs/urfxkwj3Vi0fIiIiIiIT\noEAtIiIiIjIBCtRvz61hF5CkdF/jR/c2fnRv40f3Nn50b+NH9zZ+Jv29VQ+1iIiIiMgEaIRaRERE\nRGQCFKiPgJmdZ2ZbzWy7mX0x7HqShZmVm9mjZrbZzF41s0+FXVOyMbOomb1gZn8Mu5ZkYmYFZna3\nmb1mZlvM7LSwa0oWZvaZ4OfBK2b2SzPLCLumRGVmt5nZQTN7ZdSxIjN7yMyqg/fCMGtMVG9yb78Z\n/Ex42cx+b2YFYdaYqA51b0ed+6yZOTMrDqO2t6JAfRhmFgW+D6wFFgGXm9micKtKGgPAZ51zi4CV\nwPW6t0fdp4AtYReRhL4H3O+cexdwErrHR4WZzQA+CZzinHs3EAUuC7eqhHY7cN64Y18EHnbOzQMe\nDvbl7budN97bh4B3O+cWA9uAG491UUnidt54bzGzcuAc4PVjXdCRUKA+vFOB7c65nc65PuAu4MKQ\na0oKzrk659zzwXY7PpTMCLeq5GFmM4HzgR+FXUsyMbN8YA3wYwDnXJ9zriXcqpJKCpBpZilAFrAv\n5HoSlnPuCaBp3OELgTuC7TuAi45pUUniUPfWOfegc24g2H0amHnMC0sCb/LfLcB3gS8Ak/LhPwXq\nw5sB7Bm1vxeFvqPOzOYAS4Fnwq0kqfwr/odPLOxCkkwFUA/8JGin+ZGZZYddVDJwztUC38KPQNUB\nrc65B8OtKulMc87VBdv7gWlhFpPEPgLcF3YRycLMLgRqnXMvhV3Lm1GgltCZWQ7wW+DTzrm2sOtJ\nBmZ2AXDQOfdc2LUkoRTgZOAHzrmlQCf6Z/OjIujnvRD/l5YyINvMPhhuVcnL+Wm+JuVoXyIzsy/h\nWxrvDLuWZGBmWcA/Al8Nu5a3okB9eLVA+aj9mcExOQrMLBUfpu90zv0u7HqSyCrg/Wa2C9+m9B4z\n+3m4JSWNvcBe59zQv6bcjQ/YMnHvBWqcc/XOuX7gd8DpIdeUbA6YWSlA8H4w5HqSipl9CLgAuNJp\nXuKjpQr/l+yXgt9pM4HnzWx6qFWNo0B9eM8C88yswszS8A/I3BNyTUnBzAzfh7rFOfedsOtJJs65\nG51zM51zc/D/zT7inNNI31HgnNsP7DGzBcGhs4HNIZaUTF4HVppZVvDz4Wz0wOfRdg9wdbB9NfBf\nIdaSVMzsPHyb3fudc11h15MsnHObnHNTnXNzgt9pe4GTg5/Fk4YC9WEEDxjcADyA/8H+a+fcq+FW\nlTRWAVfhR09fDF7vC7sokSPwP4A7zexlYAnwf0OuJykEo/53A88Dm/C/oyb9CmmTlZn9EngKWGBm\ne83so8BNwF+bWTX+XwRuCrPGRPUm9/bfgVzgoeD32c2hFpmg3uTeTnpaKVFEREREZAI0Qi0iIiIi\nMgEK1CIiIiIiE6BALSIiIiIyAQrUIiIiIiIToEAtIiIiIjIBCtQiIoKZnWVmfwy7DhGRRKRALSIi\nIiIyAQrUIiIJxMw+aGYbgoUjbjGzqJl1mNl3zexVM3vYzEqCa5eY2dNm9rKZ/d7MCoPjc83sz2b2\nkpk9b2ZVwcfnmNndZvaamd0ZrFYoIiKHoUAtIpIgzGwhcCmwyjm3BBgErgSygY3OuROAx4H/GfyR\nnwL/4JxbjF95cOj4ncD3nXMnAacDdcHxpcCngUVAJX41UxEROYyUsAsQEZEjdjawDHg2GDzOBA4C\nMeBXwTU/B35nZvlAgXPu8eD4HcBvzCwXmOGc+z2Ac64HIPi8Dc65vcH+i8AcYH38vy0RkcSmQC0i\nkjgMuMM5d+OYg2ZfGXede4ef3ztqexD9jhAROSJq+RARSRwPAxeb2VQAMysys9n4n+UXB9dcAax3\nzrUCzWa2Ojh+FfC4c64d2GtmFwWfkW5mWcf0uxARSTIafRARSRDOuc1m9mXgQTOLAP3A9UAncGpw\n7iC+zxrgauDmIDDvBD4cHL8KuMXMvhZ8xiXH8NsQEUk65tw7/ZdBERGZDMyswzmXE3YdIiLHK7V8\niIiIiIhMgEaoRUREREQmQCPUIiIiIiIToEAtIiIiIjIBCtQiIiIiIhOgQC0iIiIiMgEK1CIiIiIi\nE6BALSIiIiIyAf8f9B7EmRxv88cAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5a4f7fbc50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "history = simple_seq2seq.fit(X_train, np.expand_dims(Y_train, -1),\n",
    "                             validation_data=(X_val, np.expand_dims(Y_val, -1)),\n",
    "                             nb_epoch=15, verbose=2, batch_size=32,\n",
    "                             callbacks=[best_model_cb])\n",
    "\n",
    "plt.figure(figsize=(12, 6))\n",
    "plt.plot(history.history['loss'], label='train')\n",
    "plt.plot(history.history['val_loss'], '--', label='validation')\n",
    "plt.ylabel('negative log likelihood')\n",
    "plt.xlabel('epoch')\n",
    "plt.title('Convergence plot for Simple Seq2Seq')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's load the best model found on the validation set at the end of training:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "simple_seq2seq = load_model(best_model_fname)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "If you don't have access to a GPU and cannot wait 10 minutes to for the model to converge to a reasonably good state, feel to use the pretrained model. This model has been obtained by training the above model for ~150 epochs. The validation loss is significantly lower than 1e-5. In practice it should hardly ever make any prediction error on this easy translation problem.\n",
    "\n",
    "Alternatively we will load this imperfect model (trained only to 50 epochs) with a validation loss of ~7e-4. This model makes funny translation errors so I would suggest to try it first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "from keras.utils.data_utils import get_file\n",
    "import os\n",
    "\n",
    "get_file(\"simple_seq2seq_partially_pretrained.h5\", \n",
    "         \"https://github.com/m2dsupsdlclass/lectures-labs/releases/\"\n",
    "         \"download/0.4/simple_seq2seq_partially_pretrained.h5\")\n",
    "\n",
    "filename = os.path.expanduser(os.path.join('~', \n",
    "                                           '.keras/datasets/simple_seq2seq_partially_pretrained.h5'))\n",
    "\n",
    "### Uncomment the following to replace for the fully trained network \n",
    "\n",
    "#get_file(\"simple_seq2seq_pretrained.h5\", \n",
    "#         \"https://github.com/m2dsupsdlclass/lectures-labs/releases/\"\n",
    "#         \"download/0.4/simple_seq2seq_pretrained.h5\")\n",
    "#filename = os.path.expanduser(os.path.join('~', \n",
    "#                                           '.keras/datasets/simple_seq2seq_pretrained.h5'))\n",
    "\n",
    "simple_seq2seq = load_model(filename)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's have a look at a raw prediction on the first sample of the test set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'quatre vingt seize mille deux cent trente sept'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fr_test[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "In numeric array this is provided (along with the expected target sequence) as the following padded input sequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  0,  0,  0,  0,  0, 31, 35, 14, 18, 23, 30, 38, 28,  1, 13, 10,\n",
       "         6,  7, 11]], dtype=int32)"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "first_test_sequence = X_test[0:1]\n",
    "first_test_sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Remember that the `_GO` (symbol indexed at `1`) separates the reversed source from the expected target sequence:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'_GO'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rev_shared_vocab[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Interpreting the model prediction\n",
    "\n",
    "**Exercise **:\n",
    "- Feed this test sequence into the model. What is the shape of the output?\n",
    "- Get the argmax of each output prediction to get the most likely symbols\n",
    "- Dismiss the padding / end of sentence\n",
    "- Convert to readable vocabulary using rev_shared_vocab\n",
    "\n",
    "*Interpretation*\n",
    "- Compare the output with the first example in numerical format `num_test[0]`\n",
    "- What do you think of this way of decoding? Is it correct to use it at inference time?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "prediction shape: (1, 20, 40)\n",
      "prediction token ids: [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0 13 10  6  7 11  2]\n",
      "predicted number: 96237\n",
      "test number: 96237\n"
     ]
    }
   ],
   "source": [
    "# %load solutions/interpret_output.py\n",
    "prediction = simple_seq2seq.predict(first_test_sequence)\n",
    "print(\"prediction shape:\", prediction.shape)\n",
    "\n",
    "# Let's use `argmax` to extract the predicted token ids at each step:\n",
    "predicted_token_ids = prediction[0].argmax(-1)\n",
    "print(\"prediction token ids:\", predicted_token_ids)\n",
    "\n",
    "# We can use the shared reverse vocabulary to map \n",
    "# this back to the string representation of the tokens,\n",
    "# as well as removing Padding and EOS symbols\n",
    "predicted_numbers = [rev_shared_vocab[token_id] for token_id in predicted_token_ids\n",
    "                     if token_id not in (shared_vocab[PAD], shared_vocab[EOS])]\n",
    "print(\"predicted number:\", \"\".join(predicted_numbers))\n",
    "print(\"test number:\", num_test[0])\n",
    "\n",
    "# The model successfully predicted the test sequence.\n",
    "# However, we provided the full sequence as input, including all the solution\n",
    "# (except for the last number). In a real testing condition, one wouldn't\n",
    "# have the full input sequence, but only what is provided before the \"GO\"\n",
    "# symbol\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "In the previous exercise we cheated a bit because we gave the complete sequence along with the solution in the input sequence. To correctly predict we need to predict one token at a time and reinject the predicted token in the input sequence to predict the next token:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def greedy_translate(model, source_sequence, shared_vocab, rev_shared_vocab,\n",
    "                     word_level_source=True, word_level_target=True):\n",
    "    \"\"\"Greedy decoder recursively predicting one token at a time\"\"\"\n",
    "    # Initialize the list of input token ids with the source sequence\n",
    "    source_tokens = tokenize(source_sequence, word_level=word_level_source)\n",
    "    input_ids = [shared_vocab.get(t, UNK) for t in source_tokens[::-1]]\n",
    "    input_ids += [shared_vocab[GO]]\n",
    "\n",
    "    # Prepare a fixed size numpy array that matches the expected input\n",
    "    # shape for the model\n",
    "    input_array = np.empty(shape=(1, model.input_shape[1]),\n",
    "                           dtype=np.int32)\n",
    "    decoded_tokens = []\n",
    "    while len(input_ids) <= max_length:\n",
    "        # Vectorize a the list of input tokens as \n",
    "        # and use zeros padding.\n",
    "        input_array.fill(shared_vocab[PAD])\n",
    "        input_array[0, -len(input_ids):] = input_ids\n",
    "        \n",
    "        # Predict the next output: greedy decoding with argmax\n",
    "        next_token_id = model.predict(input_array)[0, -1].argmax()\n",
    "        \n",
    "        # Stop decoding if the network predicts end of sentence:\n",
    "        if next_token_id == shared_vocab[EOS]:\n",
    "            break\n",
    "            \n",
    "        # Otherwise use the reverse vocabulary to map the prediction\n",
    "        # back to the string space\n",
    "        decoded_tokens.append(rev_shared_vocab[next_token_id])\n",
    "        \n",
    "        # Append prediction to input sequence to predict the next\n",
    "        input_ids.append(next_token_id)\n",
    "\n",
    "    separator = \" \" if word_level_target else \"\"\n",
    "    return separator.join(decoded_tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "un                                       1\n",
      "deux                                     2\n",
      "trois                                    3\n",
      "onze                                     11\n",
      "quinze                                   15\n",
      "cent trente deux                         132\n",
      "cent mille douze                         11020\n",
      "sept mille huit cent cinquante neuf      7859\n",
      "vingt et un                              21\n",
      "vingt quatre                             24\n",
      "quatre vingts                            8\n",
      "quatre vingt onze mille                  91010\n",
      "quatre vingt onze mille deux cent deux   93002\n"
     ]
    }
   ],
   "source": [
    "phrases = [\n",
    "    \"un\",\n",
    "    \"deux\",\n",
    "    \"trois\",\n",
    "    \"onze\",\n",
    "    \"quinze\",\n",
    "    \"cent trente deux\",\n",
    "    \"cent mille douze\",\n",
    "    \"sept mille huit cent cinquante neuf\",\n",
    "    \"vingt et un\",\n",
    "    \"vingt quatre\",\n",
    "    \"quatre vingts\",\n",
    "    \"quatre vingt onze mille\",\n",
    "    \"quatre vingt onze mille deux cent deux\",\n",
    "]\n",
    "for phrase in phrases:\n",
    "    translation = greedy_translate(simple_seq2seq, phrase,\n",
    "                                   shared_vocab, rev_shared_vocab,\n",
    "                                   word_level_target=False)\n",
    "    print(phrase.ljust(40), translation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Why does the partially trained network is able to correctly give the output for\n",
    "\n",
    "`\"sept mille huit cent cinquante neuf\"`\n",
    "\n",
    "but not for:\n",
    "\n",
    "`\"cent mille douze\"` ?\n",
    "\n",
    "The answer is as following:\n",
    "- it is rather easy for the network to learn a correspondance between symbols (first case), by dismissing `\"cent\"` and `\"mille\"`\n",
    "- outputing the right amount of symbols, especially `0s` for `\"cent mille douze\"` requires more reasoning and ability to count."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "quatre vingt et un                       81\n",
      "quarante douze                           42\n",
      "onze cent soixante vingt quatorze        1144\n"
     ]
    }
   ],
   "source": [
    "phrases = [\n",
    "    \"quatre vingt et un\",\n",
    "    \"quarante douze\",\n",
    "    \"onze cent soixante vingt quatorze\",\n",
    "]\n",
    "for phrase in phrases:\n",
    "    translation = greedy_translate(simple_seq2seq, phrase,\n",
    "                                   shared_vocab, rev_shared_vocab,\n",
    "                                   word_level_target=False)\n",
    "    print(phrase.ljust(40), translation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Model evaluation\n",
    "\n",
    "Because **we expect only one correct translation** for a given source sequence, we can use **phrase-level accuracy** as a metric to quantify our model quality.\n",
    "\n",
    "Note that **this is not the case for real translation models** (e.g. from French to English on arbitrary sentences). Evaluation of a machine translation model is tricky in general. Automated evaluation can somehow be done at the corpus level with the [BLEU score](https://en.wikipedia.org/wiki/BLEU) (bilingual evaluation understudy) given a large enough sample of correct translations provided by certified translators but its only a noisy proxy.\n",
    "\n",
    "The only good evaluation is to give a large enough sample of the model predictions on some test sentences to certified translators and ask them to give an evaluation (e.g. a score between 0 and 6, 0 for non-sensical and 6 for the hypothetical perfect translation). However in practice this is very costly to do.\n",
    "\n",
    "Fortunately we can just use phrase-level accuracy on a our very domain specific toy problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def phrase_accuracy(model, num_sequences, fr_sequences, n_samples=300,\n",
    "                    decoder_func=greedy_translate):\n",
    "    correct = []\n",
    "    n_samples = len(num_sequences) if n_samples is None else n_samples\n",
    "    for i, num_seq, fr_seq in zip(range(n_samples), num_sequences, fr_sequences):\n",
    "        if i % 100 == 0:\n",
    "            print(\"Decoding %d/%d\" % (i, n_samples))\n",
    "\n",
    "        predicted_seq = decoder_func(simple_seq2seq, fr_seq,\n",
    "                                     shared_vocab, rev_shared_vocab,\n",
    "                                     word_level_target=False)\n",
    "        correct.append(num_seq == predicted_seq)\n",
    "    return np.mean(correct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Decoding 0/300\n",
      "Decoding 100/300\n",
      "Decoding 200/300\n",
      "Phrase-level test accuracy: 0.373\n"
     ]
    }
   ],
   "source": [
    "print(\"Phrase-level test accuracy: %0.3f\"\n",
    "      % phrase_accuracy(simple_seq2seq, num_test, fr_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Decoding 0/300\n",
      "Decoding 100/300\n",
      "Decoding 200/300\n",
      "Phrase-level train accuracy: 0.437\n"
     ]
    }
   ],
   "source": [
    "print(\"Phrase-level train accuracy: %0.3f\"\n",
    "      % phrase_accuracy(simple_seq2seq, num_train, fr_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Bonus: Decoding with a Beam Search\n",
    "\n",
    "Instead of decoding with greedy strategy that only considers the most-likely next token at each prediction, we can hold a priority queue of the most promising top-n sequences ordered by loglikelihoods.\n",
    "\n",
    "This could potentially improve the final accuracy of an imperfect model: indeed it can be the case that the most likely sequence (based on the conditional proability estimated by the model) starts with a character that is not the most likely alone.\n",
    "\n",
    "**Bonus Exercise:**\n",
    "- build a beam_translate function which decodes candidate translations with a beam search strategy\n",
    "- use a list of candidates, tracking `beam_size` candidates and their corresponding likelihood\n",
    "- compute predictions for the next outputs by using predict with a batch of the size of the beam\n",
    "- be careful to stop appending results if EOS symbols have been found for each candidate!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def beam_translate(model, source_sequence, shared_vocab, rev_shared_vocab,\n",
    "                   word_level_source=True, word_level_target=True,\n",
    "                   beam_size=10, return_ll=False):\n",
    "    \"\"\"Decode candidate translations with a beam search strategy\n",
    "    \n",
    "    If return_ll is False, only the best candidate string is returned.\n",
    "    If return_ll is True, all the candidate strings and their loglikelihoods\n",
    "    are returned.\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# %load solutions/beam_search.py\n",
    "def beam_translate(model, source_sequence, shared_vocab, rev_shared_vocab,\n",
    "                   word_level_source=True, word_level_target=True,\n",
    "                   beam_size=10, return_ll=False):\n",
    "    \"\"\"Decode candidate translations with a beam search strategy\n",
    "    \n",
    "    If return_ll is False, only the best candidate string is returned.\n",
    "    If return_ll is True, all the candidate strings and their loglikelihoods\n",
    "    are returned.\n",
    "    \"\"\"\n",
    "    # Initialize the list of input token ids with the source sequence\n",
    "    source_tokens = tokenize(source_sequence, word_level=word_level_source)\n",
    "    input_ids = [shared_vocab.get(t, UNK) for t in source_tokens[::-1]]\n",
    "    input_ids += [shared_vocab[GO]]\n",
    "    \n",
    "    # initialize loglikelihood, input token ids, decoded tokens for\n",
    "    # each candidate in the beam\n",
    "    candidates = [(0, input_ids[:], [], False)]\n",
    "\n",
    "    # Prepare a fixed size numpy array that matches the expected input\n",
    "    # shape for the model\n",
    "    input_array = np.empty(shape=(beam_size, model.input_shape[1]),\n",
    "                           dtype=np.int32)\n",
    "    while any([not done and (len(input_ids) < max_length)\n",
    "               for _, input_ids, _, done in candidates]):\n",
    "        # Vectorize a the list of input tokens and use zeros padding.\n",
    "        input_array.fill(shared_vocab[PAD])\n",
    "        for i, (_, input_ids, _, done) in enumerate(candidates):\n",
    "            if not done:\n",
    "                input_array[i, -len(input_ids):] = input_ids\n",
    "        \n",
    "        # Predict the next output in a single call to the model to amortize\n",
    "        # the overhead and benefit from vector data parallelism on GPU.\n",
    "        next_likelihood_batch = model.predict(input_array)\n",
    "        \n",
    "        # Build the new candidates list by summing the loglikelood of the\n",
    "        # next token with their parents for each new possible expansion.\n",
    "        new_candidates = []\n",
    "        for i, (ll, input_ids, decoded, done) in enumerate(candidates):\n",
    "            if done:\n",
    "                new_candidates.append((ll, input_ids, decoded, done))\n",
    "            else:\n",
    "                next_loglikelihoods = np.log(next_likelihood_batch[i, -1])\n",
    "                for next_token_id, next_ll in enumerate(next_loglikelihoods):\n",
    "                    new_ll = ll + next_ll\n",
    "                    new_input_ids = input_ids[:]\n",
    "                    new_input_ids.append(next_token_id)\n",
    "                    new_decoded = decoded[:]\n",
    "                    new_done = done\n",
    "                    if next_token_id == shared_vocab[EOS]:\n",
    "                        new_done = True\n",
    "                    if not new_done:\n",
    "                        new_decoded.append(rev_shared_vocab[next_token_id])\n",
    "                    new_candidates.append(\n",
    "                        (new_ll, new_input_ids, new_decoded, new_done))\n",
    "        \n",
    "        # Only keep a beam of the most promising candidates\n",
    "        new_candidates.sort(reverse=True)\n",
    "        candidates = new_candidates[:beam_size]\n",
    "\n",
    "    separator = \" \" if word_level_target else \"\"\n",
    "    if return_ll:\n",
    "        return [(separator.join(decoded), ll) for ll, _, decoded, _ in candidates]\n",
    "    else:\n",
    "        _, _, decoded, done = candidates[0]\n",
    "        return separator.join(decoded)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('1101', -1.1045114756865928),\n",
       " ('11011', -1.4538202644668559),\n",
       " ('10011', -1.4643958261963803),\n",
       " ('1001', -3.1507282904058798),\n",
       " ('11010', -3.3188205038908904),\n",
       " ('1301', -3.620885858319582),\n",
       " ('13011', -3.6414663884884817),\n",
       " ('10010', -3.6993766764354064),\n",
       " ('10101', -4.032213334687242),\n",
       " ('11016', -4.0691016079462656)]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidates = beam_translate(simple_seq2seq, \"cent mille un\",\n",
    "                            shared_vocab, rev_shared_vocab,\n",
    "                            word_level_target=False,\n",
    "                            return_ll=True, beam_size=10)\n",
    "candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('8', -0.17758049862459302),\n",
       " ('88', -1.933639579659939),\n",
       " ('80', -4.7839140226751624),\n",
       " ('98', -5.2766527835719899),\n",
       " ('84', -6.3383559515741581),\n",
       " ('82', -6.8432715468279639),\n",
       " ('9', -6.9183685779571533),\n",
       " ('81', -8.1953830053244019),\n",
       " ('92', -8.2863513233078265),\n",
       " ('89', -8.7994956306065433)]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidates = beam_translate(simple_seq2seq, \"quatre vingts\",\n",
    "                            shared_vocab, rev_shared_vocab,\n",
    "                            word_level_target=False,\n",
    "                            return_ll=True, beam_size=10)\n",
    "candidates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Model Accuracy with Beam Search Decoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Decoding 0/300\n",
      "Decoding 100/300\n",
      "Decoding 200/300\n",
      "Phrase-level test accuracy: 0.380\n"
     ]
    }
   ],
   "source": [
    "print(\"Phrase-level test accuracy: %0.3f\"\n",
    "      % phrase_accuracy(simple_seq2seq, num_test, fr_test,\n",
    "                        decoder_func=beam_translate))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Decoding 0/300\n",
      "Decoding 100/300\n",
      "Decoding 200/300\n",
      "Phrase-level train accuracy: 0.437\n"
     ]
    }
   ],
   "source": [
    "print(\"Phrase-level train accuracy: %0.3f\"\n",
    "      % phrase_accuracy(simple_seq2seq, num_train, fr_train,\n",
    "                        decoder_func=beam_translate))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "When using the partially trained model the test phrase-level is slightly better (0.38 vs 0.37) with the beam decoder than with the greedy decoder. However the improvement is not that important on our toy task. Training the model to convergence would yield a perfect score on the test set anyway.\n",
    "\n",
    "Properly tuned beam search decoding can be critical to improve the quality of Machine Translation systems trained on natural language pairs though."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Going Further\n",
    "\n",
    "We only scratched the surface of sequence-to-sequence systems. To go further, we recommend reading the initial [Sequence to Sequence paper](https://arxiv.org/abs/1409.3215) as well as the following developments, citing this work. Furthermore, here are a few pointers on how to go further if you're interested.\n",
    "\n",
    "### Improved model\n",
    "\n",
    "- Add multiple, larger GRU layers and more dropout regularization.\n",
    "- This should make it possible train a perfect translation model with a smaller amount of labeled samples. Try to train a seq2seq model with only 4000 training sequences or even fewer without overfitting.\n",
    "- You will need a GPU and more training time for that.\n",
    "\n",
    "### Reverse translation: Numeric to French\n",
    "\n",
    "- Build a model, with the same data from Numeric to French\n",
    "- The model should fine work with the same kind of architecture\n",
    "\n",
    "\n",
    "### Separated Encoder-Decoder\n",
    "\n",
    "We may want to build a model with a separated encoder and decoder, to improve performance and be more flexible with the architecture.\n",
    "\n",
    "- The Keras Framework isn't well suited for building an encoder-decoder model up to now;\n",
    "- This repo is an attempt at doing so https://github.com/farizrahman4u/seq2seq - untested;\n",
    "- You might rather want to use TensorFlow directly or PyTorch. \n",
    "\n",
    "### Attention models\n",
    "\n",
    "Having a separated encoder-decoder framework also enables us to build an attention-model:\n",
    "- A good implementation is available for translation here: http://opennmt.net/PythonGuide/\n",
    "- TensorFlow also has working examples: https://www.tensorflow.org/tutorials/seq2seq\n",
    "\n",
    "Attention models are efficient to model longer sequences, to find alignment between input and output sequences, and to model different parts of sequences with seperated meanings\n",
    "\n",
    "\n",
    "### Mastering Neural Machine Translation\n",
    "\n",
    "In complement to studying the TensorFlow seq2seq and OpenNMT code base, you might also want to read the following 55 pages tutorial:\n",
    "\n",
    "[Neural Machine Translation and Sequence-to-sequence Models: A Tutorial](https://arxiv.org/abs/1703.01619) by Graham Neubig."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}