![](\"../img/drumpf.png\")
\n",
"\n",
"https://twitter.com/deepdrumpf"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Other applications of language models?"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Outlook: Importance of Language Models\n",
"\n",
"- State of the art NLP models utilise **transfer learning**\n",
"- Good (neural) language models are excellent starting points for transfer learning\n",
" * Step 1: unsupervised language model **pre-training**\n",
" * Step 2: supervised language model **fine-tuning**"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Outlook: How to build good language models?\n",
"\n",
"- Train them on large datasets\n",
"- Use a large number of features/parameters"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"... but first, the basics"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Overview\n",
"\n",
"* Language Modelling from scratch\n",
"* Evaluation\n",
"* Dealing with Out-Of-Vocabulary words (OOVs)\n",
"* Training\n",
"* Smoothing"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Formally\n",
"Models the probability \n",
"\n",
"$$\\prob(w_1,\\ldots,w_d)$$ \n",
"\n",
"of observing sequences of words \\\\(w_1,\\ldots,w_d\\\\). "
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Without loss of generality: \n",
"\n",
"\\begin{align}\n",
"\\prob(w_1,\\ldots,w_d) &= p(w_1) p(w_2|w_1) p(w_3|w_1, w_2) \\ldots \\\\\n",
" &= \\prob(w_1) \\prod_{i = 2}^d \\prob(w_i|w_1,\\ldots,w_{i-1})\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Structured Prediction\n",
"\n",
"predict word $y=w_i$ \n",
"* conditioned on history $\\x=w_1,\\ldots,w_{i-1}$."
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## N-Gram Language Models\n",
"\n",
"Impossible to estimate sensible probability for each history \n",
"\n",
"$$\n",
"\\x=w_1,\\ldots,w_{i-1}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Change **representation**\n",
"truncate history to last $n-1$ words: \n",
"\n",
"$$\n",
"\\mathbf{f}(\\x)=w_{i-(n-1)},\\ldots,w_{i-1}\n",
"$$\n",
"\n",
"$\\prob(\\text{bigly}|\\text{...,blah, blah, blah, we, will, win}) \n",
"= \\prob(\\text{bigly}|\\text{we, will, win})$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Unigram LM\n",
"\n",
"Set $n=1$:\n",
"$$\n",
"\\prob(w_i|w_1,\\ldots,w_{i-1}) = \\prob(w_i).\n",
"$$\n",
"\n",
"$\\prob(\\text{bigly}|\\text{we, will, win}) = \\prob(\\text{bigly})$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Bigram LM\n",
"\n",
"Set $n=2$:\n",
"$$\n",
"\\prob(w_i|w_1,\\ldots,w_{i-1}) = \\prob(w_i|w_{i-1}).\n",
"$$\n",
"\n",
"$\\prob(\\text{bigly}|\\text{we, will, win}) = \\prob(\\text{bigly}|\\text{win})$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### *Uniform* LM\n",
"Set $n=0$:\n",
"\n",
"Same probability for each word in the vocabulary \\\\(\\vocab\\\\):\n",
"\n",
"$$\n",
"\\prob(w_i|w_1,\\ldots,w_{i-1}) = \\frac{1}{|\\vocab|}.\n",
"$$\n",
"\n",
"$\\prob(\\text{big}) = \\prob(\\text{bigly}) = \\frac{1}{|\\vocab|}$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us look at a training set and create a uniform LM from it."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['Can', \"'t\", 'even', 'call', 'this', 'a', 'blues', 'song', 'It']"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"train[:9]"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.9999999999999635"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"vocab = set(train)\n",
"baseline = UniformLM(vocab)\n",
"sum([baseline.probability(w) for w in vocab])"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"What about words outside the vocabulary? What is their probability?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Sampling\n",
"* Sampling from an LM is easy and instructive\n",
"* Usually, the better the LM, the better the samples"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Sample **incrementally**, one word at a time "
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def sample_once(lm, history, words):\n",
" probs = [lm.probability(word, *history) for word in words]\n",
" return np.random.choice(words,p=probs)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'sunrise'"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sample_once(baseline, [], list(baseline.vocab)) "
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def sample(lm, initial_history, amount_to_sample):\n",
" words = list(lm.vocab)\n",
" result = []\n",
" result += initial_history\n",
" for _ in range(0, amount_to_sample):\n",
" history = result[-(lm.order - 1):]\n",
" result.append(sample_once(lm,history,words))\n",
" return result"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['dummies',\n",
" 'find',\n",
" 'being',\n",
" 'bars',\n",
" 'clap',\n",
" 'rapping',\n",
" 'droppin',\n",
" 'fender',\n",
" 'hated',\n",
" 'Recognize']"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sample(baseline, [], 10)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Evaluation\n",
"* **Extrinsic**: how does it improve a downstream task?\n",
"* **Intrinsic**: how well does it model language?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Intrinsic Evaluation\n",
"**Shannon Game**: Predict next word, win if prediction matches the word in actual corpus\n",
"\n",
"> Our horrible trade agreements with [???]\n",
"\n",
"The expected reward is the probability of the corpus."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Formalised by\n",
"\n",
"\\begin{align}\n",
"\\prob(w_1) \\prob(w_2|w_1) \\ldots \\prob(w_T|w_1,\\ldots,w_{T-1}) &= \\prod_{i=1}^T \\prob(w_i|w_1,\\ldots,w_{i-1})\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"But then the longer the sequence, the lower the probability...\n",
"\n",
"$\\to$ normalise by the length"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Perplexity \n",
"Given test sequence \\\\(w_1,\\ldots,w_T\\\\), perplexity \\\\(\\perplexity\\\\) is **geometric mean of inverse probabilities** or, put differently the **inverse probability of the test set, normalised by the number of words**:\n",
"\n",
"\\begin{align}\n",
"\\perplexity(w_1,\\ldots,w_T) &= \\sqrt[T]{\\frac{1}{\\prob(w_1)} \\frac{1}{\\prob(w_2|w_1)} \\ldots} \\\\\n",
"&= \\sqrt[T]{\\prod_i^T \\frac{1}{\\prob(w_i|w_1,\\ldots,w_{i-1})}}\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Perplexity for a bigram language model:\n",
"\n",
"\\begin{align}\n",
"\\perplexity(w_1,\\ldots,w_T) &= \\sqrt[T]{\\prod_i^T \\frac{1}{\\prob(w_i|w_{i-1})}}\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Perplexity for a unigram language model:\n",
"\n",
"\\begin{align}\n",
"\\perplexity(w_1,\\ldots,w_T) &= \\sqrt[T]{\\prod_i^T \\frac{1}{\\prob(w_i)}}\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Perplexity for a uniform language model:\n",
"\n",
"\\begin{align}\n",
"\\perplexity(w_1,\\ldots,w_T) &= \\sqrt[T]{\\prod_i^T \\frac{1}{1/|V|}} = |V|\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Brief note on inverse functions\n",
"\n",
"- $T$ is the number of words under consideration, e.g. for bigram language models, it is 2.\n",
"- For simplicity, assume $a = \\frac{1}{p(w_1, ... w_T)}$\n",
"- $\\sqrt[T]{a}$ is the inverse function of $a^T$\n",
"- Meaning, we are looking for a number for the Perplexity $PP$, which, when multiplied with itself $T$ times, results in $a$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Interpretation\n",
"\n",
"Consider LM where \n",
"* at each position there are exactly **2** possible words with $\\frac{1}{2}$ probability each\n",
"* in test sequence, one of these is always the true word "
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Then \n",
"\n",
"* $\\perplexity(w_1,\\ldots,w_T) = \\sqrt[T]{2 \\cdot 2 \\cdot\\ldots} = 2$\n",
"* Whenever a model has to guess the next word, it is confused as to which one the 2 to pick\n",
"* Perplexity $\\approx$ average number of choices\n",
"* The lower the number of average choice, i.e. the lower the Perplexity, the better"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Perplexity of uniform LM on an **unseen** test set?"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"inf"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"perplexity(baseline, test)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Problem: model assigns **zero probability** to words not in the vocabulary. "
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[('does', 0.0),\n",
" ('Ceremonies', 0.0),\n",
" ('Masquerading', 0.0),\n",
" ('also', 0.0),\n",
" ('Creativity', 0.0)]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[(w,baseline.probability(w)) for w in test if w not in vocab][:5]"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## The Long Tail\n",
"New words not specific to our corpus: \n",
"* long **tail** of words that appear only a few times\n",
"* each individual one has low probability, but probability of seeing any long tail word is high\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Let us plot word frequency ranks (x-axis) against frequency (y-axis) "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"["
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"plt.xscale('log')\n",
"plt.yscale('log') \n",
"plt.plot(ranks, sorted_counts)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"In log-space such rank vs frequency graphs are **linear** \n",
"\n",
"* Known as **Zipf's Law**\n",
"\n",
"Let $r_w$ be the rank of a word \\\\(w\\\\), and \\\\(f_w\\\\) its frequency:\n",
"\n",
"$$\n",
" f_w \\propto \\frac{1}{r_w}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Out-of-Vocabularly (OOV) Tokens\n",
"In your test set, there will virtually always be words with zero training counts.\n",
"\n",
"Why is this a problem?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"* If probability of a word in the test set is 0, the entire probability of the test set is 0\n",
" * Perplexity is based on inverse probability of test set\n",
" * Since we cannot divide by 0, we cannot compute perplexity at all at this point\n",
"* Underestimating probability of unseen words\n",
" * Downstream application performance suffers"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Solutions:\n",
"1. Remove unseen words from test set (pretend there is no problem)?\n",
"2. Use subword tokenisation to ensure there are no `OOV` tokens?\n",
"3. **Replace unseen words with out-of-vocabularly token, estimate its probability (`OOV` injection)?**\n",
"4. Move probability mass to unseen words (smoothing)?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### `OOV` Injection Procedures\n",
"\n",
"* For the test set: mark all words not in the training vocabulary as `OOV`\n",
"* For the training set: when a word occurs for the first time, mark it as `OOV`"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Replacing Words with OOV Tokens"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['with', 'the', 'lyrics', 'of', 'the', 'year', 'Than', 'the', 'gimmick', 'with', 'the', 'gear', 'and', 'the', 'right', 'puppeteer', 'Now', 'you', 'can', 'be', 'the', 'next', 'rock', 'Shakespear', 'you', \"'\", 're', 'still', '10', 'steps', 'away', 'from', 'having', 'a', 'career', 'You', 'step', 'up', 'the', 'plate']\n",
"['with', 'the', 'lyrics', 'of', 'the', '[OOV]', '[OOV]', 'the', '[OOV]', 'with', 'the', '[OOV]', 'and', 'the', 'right', '[OOV]', 'Now', 'you', 'can', 'be', 'the', 'next', 'rock', '[OOV]', 'you', \"'\", 're', 'still', '10', 'steps', 'away', 'from', '[OOV]', 'a', 'career', 'You', '[OOV]', 'up', 'the', 'plate']\n"
]
}
],
"source": [
"print(test[60:100])\n",
"\n",
"# Replace every word not within the vocabulary with the `OOV` symbol\n",
"# [word if word in vocab else OOV for word in data]\n",
"print(replace_OOVs(baseline.vocab, test[60:100]))"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Injecting OOV Tokens for New Word Events\n",
"\n",
"Consider the \"words\"\n",
"\n",
"> AA AA BB BB AA\n",
"\n",
"Going left to right, how often do I see new words?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inject `OOV` tokens to mark these \"new word events\""
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['[OOV]', 'AA', '[OOV]', 'BB', 'AA']"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"inject_OOVs([\"AA\",\"AA\",\"BB\",\"BB\",\"AA\"])"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Estimate `OOV` Probability\n",
"What is the probability of seeing a word you haven't seen before?"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Train on replaced data..."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1287.9999999984573"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"oov_train = inject_OOVs(train)\n",
"oov_vocab = set(oov_train)\n",
"oov_test = replace_OOVs(oov_vocab, test)\n",
"oov_baseline = UniformLM(oov_vocab)\n",
"perplexity(oov_baseline,oov_test)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"![](\"../img/quiz_time.png\")
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"unigram = NGramLM(oov_train,1)\n",
"plot_probabilities(unigram)\n",
"# sum([unigram.probability(w) for w in unigram.vocab])"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The unigram LM has substantially reduced (and hence better) perplexity than the uniform LM:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"(1287.9999999984573, 128.9093846843014)"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"perplexity(oov_baseline,oov_test), perplexity(unigram,oov_test)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Its samples look (a little) more reasonable:"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['hands', 'play', 'below', 'never', 'around', 'type', 'grows', 'about', 'debate', 'himself'] \n",
"\n",
"['the', '[OOV]', 'to', 'in', 'Singing', '[OOV]', '[OOV]', \"'m\", 'live', 'to']\n"
]
}
],
"source": [
"print(sample(oov_baseline, [], 10), \"\\n\")\n",
"print(sample(unigram, [], 10))"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Bigram Model\n",
"We can do better by setting $n=2$"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAA0MAAAH5CAYAAABDDuXVAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAsCUlEQVR4nO3dfZBXdb3A8c/ysLusy64GumAuCz6gkAq6JIKBdE0QzfDWCFouWWhx750RRC2JTHMy1HgyE5+uRtYVURE1tdE1A1HJRty1WzJpJi1jyyBULFoBwrl/MPyu6y4LuwIrfF+vmTPDnt/3d/Z7vvNb2Dfn95CXZVkWAAAAienQ3hMAAABoD2IIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJLUqb0nsLts3bo1/vKXv0TXrl0jLy+vvacDAAC0kyzLYsOGDXHooYdGhw47vv6z38TQX/7ylygvL2/vaQAAAB8Rq1atisMOO2yHt+83MdS1a9eI2HbCJSUl7TwbAACgvTQ0NER5eXmuEXZkv4mh7U+NKykpEUMAAMBOXz7jDRQAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASFKn9p7A/qr3lY+39xT2uJXXn9XeUwAAgDZzZQgAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJHVq7wmQpt5XPt7eU9jjVl5/VntPAQCAFrgyBAAAJEkMAQAASRJDAABAksQQAACQJDEEAAAkSQwBAABJEkMAAECSxBAAAJAkMQQAACRJDAEAAEkSQwAAQJLEEAAAkCQxBAAAJEkMAQAASRJDAABAksQQAACQJDEEAAAkSQwBAABJalMMzZ07N/r06ROFhYVRWVkZS5cu3eHYhx56KE4//fQ4+OCDo6SkJIYMGRJPPvlkk3ELFy6M/v37R0FBQfTv3z8WLVrUlqkBAADsklbH0IIFC2Ly5Mkxbdq0qKmpiWHDhsXo0aOjrq6u2fHPPvtsnH766fHEE0/E8uXL49Of/nScffbZUVNTkxuzbNmyGDduXFRVVcUrr7wSVVVVMXbs2HjxxRfbfmYAAAAtyMuyLGvNHQYPHhwnnnhi3Hrrrbl9/fr1i3POOSemT5++S8f4xCc+EePGjYvvfOc7ERExbty4aGhoiF/84he5MWeccUYcdNBBMX/+/F06ZkNDQ5SWlsb69eujpKSkFWe0Z/S+8vH2nsIet/L6s9p8X+sDAMCesqtt0KorQ5s2bYrly5fHyJEjG+0fOXJkvPDCC7t0jK1bt8aGDRviYx/7WG7fsmXLmhxz1KhRLR5z48aN0dDQ0GgDAADYVa2KobVr18aWLVuirKys0f6ysrJYvXr1Lh1j5syZ8e6778bYsWNz+1avXt3qY06fPj1KS0tzW3l5eSvOBAAASF2b3kAhLy+v0ddZljXZ15z58+fHNddcEwsWLIhDDjnkQx1z6tSpsX79+ty2atWqVpwBAACQuk6tGdy9e/fo2LFjkys2a9asaXJl54MWLFgQEyZMiAceeCA+85nPNLqtR48erT5mQUFBFBQUtGb6AAAAOa26MpSfnx+VlZVRXV3daH91dXUMHTp0h/ebP39+XHjhhXHvvffGWWc1fVH5kCFDmhzzqaeeavGYAAAAH0arrgxFREyZMiWqqqpi0KBBMWTIkLjjjjuirq4uJk6cGBHbnr721ltvxT333BMR20Jo/PjxcdNNN8XJJ5+cuwLUpUuXKC0tjYiISZMmxfDhw+OGG26IMWPGxCOPPBJPP/10PPfcc7vrPAEAABpp9WuGxo0bF3PmzIlrr702Bg4cGM8++2w88cQTUVFRERER9fX1jT5z6Pbbb4/33nsv/uu//it69uyZ2yZNmpQbM3To0Ljvvvvixz/+cRx//PExb968WLBgQQwePHg3nCIAAEBTrf6coY8qnzO09/mcoZb5nCEAgPaxRz5nCAAAYH8hhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASFKbYmju3LnRp0+fKCwsjMrKyli6dOkOx9bX18cXv/jFOProo6NDhw4xefLkJmPmzZsXeXl5TbZ//etfbZkeAADATrU6hhYsWBCTJ0+OadOmRU1NTQwbNixGjx4ddXV1zY7fuHFjHHzwwTFt2rQYMGDADo9bUlIS9fX1jbbCwsLWTg8AAGCXtDqGZs2aFRMmTIiLLroo+vXrF3PmzIny8vK49dZbmx3fu3fvuOmmm2L8+PFRWlq6w+Pm5eVFjx49Gm0AAAB7SqtiaNOmTbF8+fIYOXJko/0jR46MF1544UNN5J133omKioo47LDD4rOf/WzU1NS0OH7jxo3R0NDQaAMAANhVrYqhtWvXxpYtW6KsrKzR/rKysli9enWbJ3HMMcfEvHnz4tFHH4358+dHYWFhnHLKKfH666/v8D7Tp0+P0tLS3FZeXt7m7w8AAKSnTW+gkJeX1+jrLMua7GuNk08+OS644IIYMGBADBs2LO6///7o27dv3HzzzTu8z9SpU2P9+vW5bdWqVW3+/gAAQHo6tWZw9+7do2PHjk2uAq1Zs6bJ1aIPo0OHDvHJT36yxStDBQUFUVBQsNu+JwAAkJZWXRnKz8+PysrKqK6ubrS/uro6hg4dutsmlWVZ1NbWRs+ePXfbMQEAAN6vVVeGIiKmTJkSVVVVMWjQoBgyZEjccccdUVdXFxMnToyIbU9fe+utt+Kee+7J3ae2tjYitr1Jwttvvx21tbWRn58f/fv3j4iI7373u3HyySfHUUcdFQ0NDfHDH/4wamtr45ZbbtkNpwgAANBUq2No3LhxsW7durj22mujvr4+jj322HjiiSeioqIiIrZ9yOoHP3PohBNOyP15+fLlce+990ZFRUWsXLkyIiL+/ve/x9e+9rVYvXp1lJaWxgknnBDPPvtsnHTSSR/i1AAAAHYsL8uyrL0nsTs0NDREaWlprF+/PkpKStp7OtH7ysfbewp73Mrrz2rzfa0PAAB7yq62QZveTQ4AAGBfJ4YAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJLUphiaO3du9OnTJwoLC6OysjKWLl26w7H19fXxxS9+MY4++ujo0KFDTJ48udlxCxcujP79+0dBQUH0798/Fi1a1JapAQAA7JJWx9CCBQti8uTJMW3atKipqYlhw4bF6NGjo66urtnxGzdujIMPPjimTZsWAwYMaHbMsmXLYty4cVFVVRWvvPJKVFVVxdixY+PFF19s7fQAAAB2SV6WZVlr7jB48OA48cQT49Zbb83t69evX5xzzjkxffr0Fu87YsSIGDhwYMyZM6fR/nHjxkVDQ0P84he/yO0744wz4qCDDor58+fv0rwaGhqitLQ01q9fHyUlJbt+QntI7ysfb+8p7HErrz+rzfe1PgAA7Cm72gatujK0adOmWL58eYwcObLR/pEjR8YLL7zQtpnGtitDHzzmqFGjWjzmxo0bo6GhodEGAACwq1oVQ2vXro0tW7ZEWVlZo/1lZWWxevXqNk9i9erVrT7m9OnTo7S0NLeVl5e3+fsDAADpadMbKOTl5TX6OsuyJvv29DGnTp0a69evz22rVq36UN8fAABIS6fWDO7evXt07NixyRWbNWvWNLmy0xo9evRo9TELCgqioKCgzd8TAABIW6uuDOXn50dlZWVUV1c32l9dXR1Dhw5t8ySGDBnS5JhPPfXUhzomAABAS1p1ZSgiYsqUKVFVVRWDBg2KIUOGxB133BF1dXUxceLEiNj29LW33nor7rnnntx9amtrIyLinXfeibfffjtqa2sjPz8/+vfvHxERkyZNiuHDh8cNN9wQY8aMiUceeSSefvrpeO6553bDKQIAADTV6hgaN25crFu3Lq699tqor6+PY489Np544omoqKiIiG0fsvrBzxw64YQTcn9evnx53HvvvVFRURErV66MiIihQ4fGfffdF9/+9rfjqquuiiOOOCIWLFgQgwcP/hCnBgAAsGOt/pyhjyqfM7T3+ZyhlvmcIQCA9rFHPmcIAABgfyGGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIUptiaO7cudGnT58oLCyMysrKWLp0aYvjlyxZEpWVlVFYWBiHH3543HbbbY1unzdvXuTl5TXZ/vWvf7VlegAAADvV6hhasGBBTJ48OaZNmxY1NTUxbNiwGD16dNTV1TU7/s0334wzzzwzhg0bFjU1NfGtb30rLrnkkli4cGGjcSUlJVFfX99oKywsbNtZAQAA7ESn1t5h1qxZMWHChLjooosiImLOnDnx5JNPxq233hrTp09vMv62226LXr16xZw5cyIiol+/fvHSSy/FjBkz4gtf+EJuXF5eXvTo0aONpwEAANA6rboytGnTpli+fHmMHDmy0f6RI0fGCy+80Ox9li1b1mT8qFGj4qWXXorNmzfn9r3zzjtRUVERhx12WHz2s5+NmpqaFueycePGaGhoaLQBAADsqlbF0Nq1a2PLli1RVlbWaH9ZWVmsXr262fusXr262fHvvfderF27NiIijjnmmJg3b148+uijMX/+/CgsLIxTTjklXn/99R3OZfr06VFaWprbysvLW3MqAABA4tr0Bgp5eXmNvs6yrMm+nY1///6TTz45LrjgghgwYEAMGzYs7r///ujbt2/cfPPNOzzm1KlTY/369blt1apVbTkVAAAgUa16zVD37t2jY8eOTa4CrVmzpsnVn+169OjR7PhOnTpFt27dmr1Phw4d4pOf/GSLV4YKCgqioKCgNdMHAADIadWVofz8/KisrIzq6upG+6urq2Po0KHN3mfIkCFNxj/11FMxaNCg6Ny5c7P3ybIsamtro2fPnq2ZHgAAwC5r9dPkpkyZEv/93/8dd999d6xYsSIuvfTSqKuri4kTJ0bEtqevjR8/Pjd+4sSJ8ec//zmmTJkSK1asiLvvvjvuuuuuuPzyy3Njvvvd78aTTz4Zf/rTn6K2tjYmTJgQtbW1uWMCAADsbq1+a+1x48bFunXr4tprr436+vo49thj44knnoiKioqIiKivr2/0mUN9+vSJJ554Ii699NK45ZZb4tBDD40f/vCHjd5W++9//3t87Wtfi9WrV0dpaWmccMIJ8eyzz8ZJJ520G04RAACgqbxs+7sZ7OMaGhqitLQ01q9fHyUlJe09neh95ePtPYU9buX1Z7X5vtYHAIA9ZVfboE3vJgcAALCvE0MAAECSxBAAAJAkMQQAACRJDAEAAElq9VtrA3ued9sDANjzXBkCAACSJIYAAIAkiSEAACBJYggAAEiSN1AA9jneYAIA2B1cGQIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJHVq7wkAsHv1vvLx9p7CHrfy+rPaewoA7AdcGQIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACS1Km9JwAAe0vvKx9v7ynsFSuvP6u9pwCwT3BlCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEhSp/aeAADw0dD7ysfbewp7xcrrz2rT/awP7H9cGQIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkg9dBQDgQ/OhtC1LYX32xQ/sdWUIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABIkhgCAACSJIYAAIAkiSEAACBJYggAAEiSGAIAAJLUphiaO3du9OnTJwoLC6OysjKWLl3a4vglS5ZEZWVlFBYWxuGHHx633XZbkzELFy6M/v37R0FBQfTv3z8WLVrUlqkBAADsklbH0IIFC2Ly5Mkxbdq0qKmpiWHDhsXo0aOjrq6u2fFvvvlmnHnmmTFs2LCoqamJb33rW3HJJZfEwoULc2OWLVsW48aNi6qqqnjllVeiqqoqxo4dGy+++GLbzwwAAKAFnVp7h1mzZsWECRPioosuioiIOXPmxJNPPhm33nprTJ8+vcn42267LXr16hVz5syJiIh+/frFSy+9FDNmzIgvfOELuWOcfvrpMXXq1IiImDp1aixZsiTmzJkT8+fPb3YeGzdujI0bN+a+Xr9+fURENDQ0tPaU9oitG//R3lPY4z7MWlufllmfllmfllmfHUthbSKsz85Yn5ZZn5ZZnx37qPweHvH/c8myrOWBWSts3Lgx69ixY/bQQw812n/JJZdkw4cPb/Y+w4YNyy655JJG+x566KGsU6dO2aZNm7Isy7Ly8vJs1qxZjcbMmjUr69Wr1w7ncvXVV2cRYbPZbDabzWaz2WzNbqtWrWqxb1p1ZWjt2rWxZcuWKCsra7S/rKwsVq9e3ex9Vq9e3ez49957L9auXRs9e/bc4ZgdHTNi29WjKVOm5L7eunVr/PWvf41u3bpFXl5ea05rv9DQ0BDl5eWxatWqKCkpae/pfORYnx2zNi2zPi2zPi2zPi2zPi2zPi2zPi1LfX2yLIsNGzbEoYce2uK4Vj9NLiKaxEaWZS0GSHPjP7i/tccsKCiIgoKCRvsOPPDAFuedgpKSkiQf8LvK+uyYtWmZ9WmZ9WmZ9WmZ9WmZ9WmZ9WlZyutTWlq60zGtegOF7t27R8eOHZtcsVmzZk2TKzvb9ejRo9nxnTp1im7durU4ZkfHBAAA+LBaFUP5+flRWVkZ1dXVjfZXV1fH0KFDm73PkCFDmox/6qmnYtCgQdG5c+cWx+zomAAAAB9Wq58mN2XKlKiqqopBgwbFkCFD4o477oi6urqYOHFiRGx7Lc9bb70V99xzT0RETJw4MX70ox/FlClT4uKLL45ly5bFXXfd1ehd4iZNmhTDhw+PG264IcaMGROPPPJIPP300/Hcc8/tptPc/xUUFMTVV1/d5KmDbGN9dszatMz6tMz6tMz6tMz6tMz6tMz6tMz67Jq8LNvZ+801NXfu3Ljxxhujvr4+jj322Jg9e3YMHz48IiIuvPDCWLlyZSxevDg3fsmSJXHppZfG73//+zj00EPjm9/8Zi6etnvwwQfj29/+dvzpT3+KI444Iq677rr4/Oc//+HODgAAYAfaFEMAAAD7ula9ZggAAGB/IYYAAIAkiSEAACBJYoiPrBEjRkReXl7k5eVFbW1tu85l5cqVubkMHDiwXecCwL7twgsvjHPOOae9p7FP6927d8yZMyf3dV5eXjz88MPtNp/2NGLEiJg8eXJ7T2OfJYb2IRdeeGFcc8017T2Nveriiy/OvWvhdj/5yU/ipJNOigMOOCC6du0aw4cPj8cee6zJfbds2RKzZ8+O448/PgoLC+PAAw+M0aNHx/PPP58bc/bZZ8dnPvOZZr/3smXLIi8vL15++eUoLy+P+vr6uOyyy3b/SbJPmzdvXhx44IHtPY2PLOtDS3b0+PjgL7r7m5tuuinmzZu3W461v6/V+6X4exB7nhjiI62oqCh69OgRnTpt+0isyy+/PL7+9a/H2LFj45VXXonf/OY3MWzYsBgzZkz86Ec/yt0vy7I477zz4tprr41LLrkkVqxYEUuWLIny8vIYMWJE7n+PJkyYEM8880z8+c9/bvK977777hg4cGCceOKJ0bFjx+jRo0cUFxfvlfMGYP9VWlrqPwngI0IM7aN69+4d3/ve92L8+PFRXFwcFRUV8cgjj8Tbb78dY8aMieLi4jjuuOPipZdeau+p7ja//vWvY+bMmfGDH/wgLr/88jjyyCOjX79+cd1118XkyZNjypQpsWrVqoiIuP/+++PBBx+Me+65Jy666KLo06dPDBgwIO6444743Oc+FxdddFG8++678dnPfjYOOeSQJv9D949//CMWLFgQEyZMaIcz3X22bt0aN9xwQxx55JFRUFAQvXr1iuuuuy4iIr75zW9G3759o6ioKA4//PC46qqrYvPmzbn7XnPNNTFw4MD46U9/Gr17947S0tI477zzYsOGDe11OnvEhg0b4ktf+lIccMAB0bNnz5g9e3ajpxxs2rQpvvGNb8THP/7xOOCAA2Lw4MG5z1FbvHhxfOUrX4n169fnnka5v/2v5c7W529/+1uMHz8+DjrooCgqKorRo0fH66+/HhH75/r8/Oc/jwMPPDC2bt0aERG1tbWRl5cXV1xxRW7M17/+9Tj//PNj3bp1cf7558dhhx0WRUVFcdxxxzX6wPGIbZ+xd9xxx0WXLl2iW7du8ZnPfCbefffdvXpOH8aeeHyMGDEi/vznP8ell16a2x8Ru7Se+4r3P02uuSs7AwcObPSzcs0110SvXr2ioKAgDj300LjkkksiIna4Vuy/3n333dzvfj179oyZM2c2ur2ln7mI/78a++STT0a/fv2iuLg4zjjjjKivr9/bp/KRIYb2YbNnz45TTjklampq4qyzzoqqqqoYP358XHDBBfHyyy/HkUceGePHj4/95aOk5s+fH8XFxfH1r3+9yW2XXXZZbN68ORYuXBgREffee2/07ds3zj777GbHrlu3Lqqrq6NTp04xfvz4mDdvXqN1euCBB2LTpk3xpS99ac+d0F4wderUuOGGG+Kqq66KV199Ne69994oKyuLiIiuXbvGvHnz4tVXX42bbrop7rzzzpg9e3aj+7/xxhvx8MMPx2OPPRaPPfZYLFmyJK6//vr2OJU9ZsqUKfH888/Ho48+GtXV1bF06dJ4+eWXc7d/5Stfieeffz7uu++++O1vfxvnnntunHHGGfH666/H0KFDY86cOVFSUhL19fVRX18fl19+eTueze63s/W58MIL46WXXopHH300li1bFlmWxZlnnhmbN2/eL9dn+PDhsWHDhqipqYmIbR8q3r1791iyZEluzOLFi+PUU0+Nf/3rX1FZWRmPPfZY/O53v4uvfe1rUVVVFS+++GJERNTX18f5558fX/3qV2PFihWxePHi+PznP79P/Z29Jx4fDz30UBx22GFx7bXX5vZHxE7Xc3/14IMPxuzZs+P222+P119/PR5++OE47rjjIiJ2uFbsv6644or41a9+FYsWLYqnnnoqFi9eHMuXL8/d3tLP3Hb/+Mc/YsaMGfHTn/40nn322airq9vn/27+UDL2SRUVFdkFF1yQ+7q+vj6LiOyqq67K7Vu2bFkWEVl9fX17TPFDO/XUU7NJkyblvj7jjDOyAQMG7HB8aWlp9h//8R9ZlmXZMccck40ZM6bZcX/961+ziMhuuOGGLMuybMWKFVlEZM8880xuzPDhw7Pzzz+/yX2vvvrqFufwUdLQ0JAVFBRkd9555y6Nv/HGG7PKysrc11dffXVWVFSUNTQ05PZdccUV2eDBg3f7XNtLQ0ND1rlz5+yBBx7I7fv73/+eFRUVZZMmTcr++Mc/Znl5edlbb73V6H6nnXZaNnXq1CzLsuzHP/5xVlpaujenvdfsbH1ee+21LCKy559/Pnf72rVrsy5dumT3339/lmX75/qceOKJ2YwZM7Isy7Jzzjknu+6667L8/PysoaEh93fxihUrmr3vmWeemV122WVZlmXZ8uXLs4jIVq5cudfmvjvtycdHRUVFNnv27J3O4f3ruS/58pe/nPs3qrlzHTBgQHb11VdnWZZlM2fOzPr27Ztt2rSp2WPt6lrtbz543hGRLVq0qN3mszds2LAhy8/Pz+67777cvnXr1mVdunRp1c9cRGR//OMfc2NuueWWrKysbO+dyEeMK0P7sOOPPz735+3/27/9f4vev2/NmjV7d2LtJMuyVj1FYPvYY445JoYOHRp33313RGy7GrJ06dL46le/ukfmubesWLEiNm7cGKeddlqztz/44IPxqU99KvdaqKuuuirq6uoajendu3d07do193XPnj33q8fTn/70p9i8eXOcdNJJuX2lpaVx9NFHR0TEyy+/HFmWRd++faO4uDi3LVmyJN544432mvZes7P1WbFiRXTq1CkGDx6cu71bt25x9NFHx4oVK/b6fPeWESNGxOLFiyPLsli6dGmMGTMmjj322HjuuefiV7/6VZSVlcUxxxwTW7Zsieuuuy6OP/746NatWxQXF8dTTz2V+zkbMGBAnHbaaXHcccfFueeeG3feeWf87W9/a+ez23V7+/Gxs/XcX5177rnxz3/+Mw4//PC4+OKLY9GiRfHee++197RoB2+88UZs2rQphgwZktv3sY99rNU/c0VFRXHEEUfkvt7f/m1vLTG0D+vcuXPuz9t/sW9u3/bntu/r+vbtm/uL4IP+8pe/RENDQxx11FG5sa+++mqzx9n+F8L2sRHb3khh4cKF0dDQED/+8Y+joqJihxGxr+jSpcsOb/v1r38d5513XowePToee+yxqKmpiWnTpjVZ2/c/niK2Pab2l8dTROSejvTBiN6+f+vWrdGxY8dYvnx51NbW5rYVK1bETTfdtNfnu7ftbH2yHTydq7X/MbGvGTFiRCxdujReeeWV6NChQ/Tv3z9OPfXUWLJkSe4pchERM2fOjNmzZ8c3vvGNeOaZZ6K2tjZGjRqV+znr2LFjVFdXxy9+8Yvo379/3HzzzXH00UfHm2++2Z6nt8v29uNjZ+u5r+rQoUOTtXr/U5rKy8vjD3/4Q9xyyy3RpUuX+M///M8YPnx4ozGkYUc/Uzu7/YM/c839276zY+/PxBD7jPPOOy/eeeeduP3225vcNmPGjOjcuXN84QtfyI19/fXX4+c//3mTsTNnzoxu3brF6aefnts3duzY6NixY9x7773xk5/8JL7yla/s87/MHXXUUdGlS5f45S9/2eS2559/PioqKmLatGkxaNCgOOqoo5p9R7393RFHHBGdO3eO3/zmN7l9DQ0NuRebnnDCCbFly5ZYs2ZNHHnkkY22Hj16REREfn5+bNmypV3mv6ftbH369+8f7733XqPXbKxbty5ee+216NevX0Tsn+uz/XVDc+bMiVNPPTXy8vLi1FNPjcWLFzeKoe1XjS644IIYMGBAHH744Y1eyByx7ZeQU045Jb773e9GTU1N5Ofnx6JFi9rjtFptTz4+mtu/K+u5Lzr44IMbvdanoaGhSRB36dIlPve5z8UPf/jDWLx4cSxbtiz+93//NyL2z58xmnfkkUdG586d49e//nVu39/+9rd47bXXImLXfuZoqlN7TwB21ZAhQ2LSpElxxRVXxKZNm+Kcc86JzZs3x89+9rO46aabYs6cOVFeXh4R22LogQceiC9/+cvxgx/8IE477bRoaGiIW265JR599NF44IEH4oADDsgdu7i4OMaNGxff+ta3Yv369XHhhRe201nuPoWFhfHNb34zvvGNb0R+fn6ccsop8fbbb8fvf//7OPLII6Ouri7uu++++OQnPxmPP/74PvML2O7UtWvX+PKXvxxXXHFFfOxjH4tDDjkkrr766ujQoUPk5eVF375940tf+lKMHz8+Zs6cGSeccEKsXbs2nnnmmTjuuOPizDPPjN69e8c777wTv/zlL2PAgAFRVFQURUVF7X1qu8XO1ueoo46KMWPGxMUXXxy33357dO3aNa688sr4+Mc/HmPGjImI2C/Xp7S0NAYOHJj7uydiWyCde+65sXnz5hgxYkREbPvFZeHChfHCCy/EQQcdFLNmzYrVq1fnfil58cUX45e//GWMHDkyDjnkkHjxxRfj7bff3md+admTj4/evXvHs88+G+edd14UFBRE9+7dd7qe+6p/+7d/i3nz5sXZZ58dBx10UFx11VXRsWPH3O3z5s2LLVu2xODBg6OoqCh++tOfRpcuXaKioiIiotm1Yv9UXFwcEyZMiCuuuCK6desWZWVlMW3atOjQYdu1jV35maMZe/tFSuwezb1gMj7w4sE333wzi4ispqZmr85td/ngGyhsd9ddd2WDBg3KunTpkhUVFWWf+tSnskcffbTJuM2bN2czZszIPvGJT2QFBQVZSUlJNmrUqGzp0qXNfr8XXnghi4hs5MiRO5zTvvQGClmWZVu2bMm+973vZRUVFVnnzp2zXr16Zd///vezLNv2ZgjdunXLiouLs3HjxmWzZ89u9ELm5s519uzZWUVFxd47gb2goaEh++IXv5gVFRVlPXr0yGbNmpWddNJJ2ZVXXpllWZZt2rQp+853vpP17t0769y5c9ajR4/s3//937Pf/va3uWNMnDgx69atWxYRuRc97y92tj5//etfs6qqqqy0tDTr0qVLNmrUqOy1115rdIz9cX0uu+yyLCKy3/3ud7l9AwYMyA4++OBs69atWZZte2HzmDFjsuLi4uyQQw7Jvv3tb2fjx4/PvXD+1VdfzUaNGpUdfPDBWUFBQda3b9/s5ptvbo/TabM99fhYtmxZdvzxx2cFBQXZ9l9Vdrae+5L3v4HC+vXrs7Fjx2YlJSVZeXl5Nm/evEZvoLBo0aJs8ODBWUlJSXbAAQdkJ598cvb000/njtXcWqUgxTdQyLJtb6JwwQUXZEVFRVlZWVl24403Nvp9aWc/c829acmiRYuSeux8UF6WJfwkQT7SRowYEQMHDvxIfbL2NddcEw8//HDU1ta291TYQ9599934+Mc/HjNnztznP2dqT7A+tMTjY9ecf/750bFjx/jZz37W3lOB5HnNEB9pc+fOjeLi4txzo9tLXV1dFBcXx/e///12nQe7X01NTcyfPz/eeOONePnll3OfLeUpBdtYH1ri8dE67733Xrz66quxbNmy+MQnPtHe0wHCa4b4CPuf//mf+Oc//xkREb169WrXuRx66KG5q0EFBQXtOhd2vxkzZsQf/vCHyM/Pj8rKyli6dKnn3b+P9aElHh+77ne/+10MHTo0Pv3pT8fEiRPbezpARHiaHAAAkCRPkwMAAJIkhgAAgCSJIQAAIEliCAAASJIYAgAAkiSGAACAJIkhAAAgSWIIAABI0v8BK9t0kjmg7TMAAAAASUVORK5CYII=",
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"bigram = NGramLM(oov_train,2)\n",
"plot_probabilities(bigram, (\"I\",)) # bigrams starting with \"I\""
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Samples should look (slightly) more fluent:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"\"I set em Yo [OOV] enemies [OOV] [OOV] is yours what the [OOV] it So it There 's mind [OOV] Recognize your [OOV] up [OOV] [OOV] wanna get up [OOV] and\""
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\" \".join(sample(bigram, ['I'], 30)) # try: I, FIND, [OOV]"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"How about perplexity?"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"inf"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"perplexity(bigram,oov_test)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Some contexts where OOV word (and others) haven't been seen, hence 0 probability..."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bigram.probability(\"[OOV]\",\"money\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Out-of-Vocabularly (OOV) Tokens\n",
"In your test set, there will virtually always be words with zero training counts.\n",
"\n",
"Solutions:\n",
"1. Remove unseen words from test set (pretend there is no problem)?\n",
"2. Use subword tokenisation to ensure there are no `OOV` tokens?\n",
"3. Replace unseen words with out-of-vocabularly token, estimate its probability (`OOV` injection)?\n",
"4. **Move probability mass to unseen words (smoothing)?**"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Smoothing\n",
"\n",
"Maximum likelihood \n",
"* **underestimates** true probability of some words \n",
"* **overestimates** the probabilities of other\n",
"\n",
"Solution: _smooth_ the probabilities and **move mass** from seen to unseen events."
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Laplace Smoothing / Additive Smoothing\n",
"\n",
"Add **pseudo counts** to each event in the dataset \n",
"\n",
"$$\n",
"\\param^{\\alpha}_{w,h} = \\frac{\\counts{\\train}{h,w} + \\alpha}{\\counts{\\train}{h} + \\alpha \\lvert V \\rvert } \n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.0007704160246533128"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"laplace_bigram = LaplaceLM(bigram, 0.1) \n",
"laplace_bigram.probability(\"[OOV]\",\"money\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Perplexity should look better now:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"255.11837473847797"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"perplexity(LaplaceLM(bigram, 0.001),oov_test)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Example\n",
"Consider three events:"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/html": [
"
"
],
"text/plain": [
""
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c = [\"word\", \"train count\", \"MLE\", \"Laplace\", \"Same Denominator\"]\n",
"r1 = [\"smally\", \"0\", \"0/3\", \"1/6\", \"0.5/3\"]\n",
"r2 = [\"bigly\", \"1\", \"1/3\", \"2/6\", \"1/3\"]\n",
"r3 = [\"tremendously\", \"2\", \"2/3\", \"3/6\", \"1.5/3\"]\n",
"util.Table([r1,r2,r3], column_names=c)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Interpolation / Jelinek-Mercer Smoothing\n",
"* Laplace Smoothing assigns mass **uniformly** to the words that haven't been seen in a context."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"(0.0005656108597285067, 0.0005656108597285067)"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"laplace_bigram.probability('rhyme','man'), \\\n",
"laplace_bigram.probability('of','man') \n",
"# also try: 'skies','skies' vs. '[/BAR]','skies'"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Problem: not all unseen words (in a context) are equal"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"With **interpolation** we can do better: \n",
"* give more mass to words likely under the $n-1$-gram model. \n",
" * Use $\\prob(\\text{of})$ for estimating $\\prob(\\text{of} | \\text{man})$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"* Combine $n$-gram model \\\\(p'\\\\) and a back-off \\\\(n-1\\\\) model \\\\(p''\\\\): \n",
"\n",
"$$\n",
"\\prob_{\\alpha}(w_i|w_{i-n+1},\\ldots,w_{i-1}) = \\alpha \\cdot \\prob'(w_i|w_{i-n+1},\\ldots,w_{i-1}) + \\\\ (1 - \\alpha) \\cdot \\prob''(w_i|w_{i-n+2},\\ldots,w_{i-1})\n",
"$$\n"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"(0.0014514278429372768, 0.009276517083120857)"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"interpolated = InterpolatedLM(bigram,unigram,0.01)\n",
"interpolated.probability('rhyme','man'), \\\n",
"interpolated.probability('of','man')"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Can we find a good $\\alpha$ parameter? Tune on some **development set**!"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAz8AAAH5CAYAAACve4DDAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAABWFUlEQVR4nO3dd3yV9d3/8fdZ2ckhiwwSCHuGAAFUnAiCyKir0Npa25u2jjqoaK0dWu/bW6r9Wfdqb1tat7ViAXGACxBXAmGPAAESSAghe57knOv3R4ZEhiQkuc54PR+P85Ccc534jl5A3vl8r+9lMQzDEAAAAAD4OavZAQAAAACgJ1B+AAAAAAQEyg8AAACAgED5AQAAABAQKD8AAAAAAgLlBwAAAEBAoPwAAAAACAh2swN0hsfj0aFDhxQZGSmLxWJ2HAAAAAAmMQxDVVVVSk5OltV66tmOT5afQ4cOKTU11ewYAAAAALxEfn6+UlJSTnmMT5afyMhISc1fYFRUlMlpAAAAAJilsrJSqampbR3hVHyy/LQudYuKiqL8AAAAADity2HY8AAAAABAQKD8AAAAAAgIlB8AAAAAAYHyAwAAACAgUH4AAAAABATKDwAAAICAQPkBAAAAEBAoPwAAAAACAuUHAAAAQECg/AAAAAAICJQfAAAAAAGB8gMAAAAgIFB+AAAAAAQEyg8AAACAgED5AQAAABAQKD8AAAAAAgLlBwAAAECHGIZhdoROsZsdAAAAAIBv+dk/syUZumP6UA1LjDI7zmlj8gMAAADgtB2tbtBHO4u1anuxgu02s+N0COUHAAAAwGlbsaVIbo+h9D5O9Y8LNztOh1B+AAAAAJy2ZTmHJElzMpJNTtJxlB8AAAAAp+VQeZ2+3FcqSZo5OsnkNB1H+QEAAABwWpZvap76TEyLUXKvUJPTdBzlBwAAAMBpWbqxufzMHuN7S94kyg8AAACA07D3SLW2HKyUzWrRZaMSzY7TKZQfAAAAAN9q2cZCSdJ5g+IUGxFscprOofwAAAAAOCXDMLR040FJvrnLWyvKDwAAAIBT2lZYqT1HahRkt2rayASz43Qa5QcAAADAKbVudHDx0N6KDHGYnKbzKD8AAAAATsrjMbS85XqfOT66y1sryg8AAACAk1p/oEwHy+sUEWzXxcN6mx3njFB+AAAAAJxU65K3aSMSFOKwmZzmzFB+AAAAAJxQk9ujFZubl7z56o1Nj0X5AQAAAHBCn+09qpJql6LDHDpvUJzZcc4Y5QcAAADACS3NaV7ydll6khw2368Ovv8VAAAAAOhyDU1uvbu1SJI024dvbHosyg8AAACA43y884iq6puUGBWiiWkxZsfpEpQfAAAAAMdp3eVt1ugkWa0Wk9N0DcoPAAAAgHZqGpr0wfbDknz/xqbHovwAAAAAaGfV9sOqb/QoLTZM6X2cZsfpMpQfAAAAAO207vI2JyNZFot/LHmTKD8AAAAAjlFe69Lq3COS/GeXt1aUHwAAAABt3tlSpEa3oWGJkRqcEGl2nC5F+QEAAADQpm3Jmx9tdNCK8gMAAABAknS4sl6f5x2VJM0eTfkBAAAA4KeWbyqUYUjj+vZSakyY2XG6HOUHAAAAgCRp2cavd3nzR5QfAAAAADpwtFY5+eWyWqSZfrjkTaL8AAAAAJC0bFPz1GfSwDjFRwabnKZ7UH4AAAAAtLuxqb+i/AAAAAABbmdRlXYerpLDZtH0kYlmx+k2lB8AAAAgwC3deFCSdOGQ3nKGOUxO030oPwAAAEAAMwxDyzYWSvLPG5sei/IDAAAABLCc/HIdKK1VqMOmqcN7mx2nW1F+AAAAgADWOvW5ZESCwoLsJqfpXh0uP6tXr9bs2bOVnJwsi8Wit956q93rP/7xj2WxWNo9zj777HbHNDQ06JZbblFcXJzCw8M1Z84cFRQUnNEXAgAAAKBj3B5Dyzf5/y5vrTpcfmpqapSRkaEnn3zypMdceumlKiwsbHusWLGi3esLFizQkiVL9Oqrr2rt2rWqrq7WrFmz5Ha7O/4VAAAAAOiUL/KOqriqQVEhdl0wJN7sON2uw3OtGTNmaMaMGac8Jjg4WImJJ94ir6KiQs8//7xeeOEFTZ06VZL04osvKjU1VatWrdL06dM7GgkAAABAJyzb2Dz1mTEqSUF2/78iplu+wo8//li9e/fWkCFD9LOf/UzFxcVtr2VnZ6uxsVHTpk1rey45OVmjRo3SunXrTvj5GhoaVFlZ2e4BAAAAoPNcTR6t2Fwkyf93eWvV5eVnxowZeumll/Thhx/q4Ycf1ldffaWLL75YDQ0NkqSioiIFBQUpOjq63fsSEhJUVFR0ws+5aNEiOZ3OtkdqampXxwYAAAACyprcI6qoa1R8ZLDOHhBrdpwe0eXbOcybN6/t16NGjdL48ePVr18/vf3227ryyitP+j7DMGSxWE742t13363bb7+97ePKykoKEAAAAHAGlrYseZuZniSb9cTfh/ubbl/Yl5SUpH79+ik3N1eSlJiYKJfLpbKysnbHFRcXKyEh4YSfIzg4WFFRUe0eAAAAADqnzuXWym2HJQXOkjepB8rP0aNHlZ+fr6SkJElSZmamHA6HVq5c2XZMYWGhtmzZokmTJnV3HAAAACDgfbDjsGpdbqXGhGpsai+z4/SYDi97q66u1u7du9s+zsvLU05OjmJiYhQTE6M//OEPuuqqq5SUlKR9+/bpN7/5jeLi4nTFFVdIkpxOp+bPn6+FCxcqNjZWMTExuuOOO5Sent62+xsAAACA7rM0p3nJ2+zRySe99MQfdbj8ZGVlafLkyW0ft16Lc9111+mZZ57R5s2b9c9//lPl5eVKSkrS5MmT9dprrykyMrLtPY888ojsdrvmzp2ruro6TZkyRYsXL5bNZuuCLwkAAADAyVTUNerjnUckSbMD4Mamx7IYhmGYHaKjKisr5XQ6VVFRwfU/AAAAQAe8npWvX72xSYN7R+j9X17g85OfjnQD/7+TEQAAAIA2rTc2nZMRWEveJMoPAAAAEDCOVDXo090lkgJvyZtE+QEAAAACxjtbCuUxpIwUp9Liws2O0+MoPwAAAECAaNvlLQCnPhLlBwAAAAgIB8vrlLW/TBaLNGs05QcAAACAn2rd6GBiWowSnSEmpzEH5QcAAAAIAK1L3uaMCcypj0T5AQAAAPze7uJqbSuslN1q0WWjksyOYxrKDwAAAODnlrYseTt/cJyiw4NMTmMeyg8AAADgxwzD0PKNLHmTKD8AAACAX9t6qFJ7S2oUbLfqkhGJZscxFeUHAAAA8GOtS96mDk9QRLDd5DTmovwAAAAAfsrjMdq2uA7UG5sei/IDAAAA+Kms/WUqrKhXZLBdFw2NNzuO6Sg/AAAAgJ9auvGgJGnayESFOGwmpzEf5QcAAADwQ41uj1ZsLpLELm+tKD8AAACAH1q356hKa1yKDQ/SuQNjzY7jFSg/AAAAgB9amtO80cFl6Umy2/i2X6L8AAAAAH6nvtGt97ey5O2bKD8AAACAn/l4Z7GqGpqU7AxRZt9os+N4DcoPAAAA4Gdab2w6KyNZVqvF5DTeg/IDAAAA+JGq+kZ9sL1YkjSHG5u2Q/kBAAAA/MjKbYfV0OTRgLhwjUyOMjuOV6H8AAAAAH5kWcuSt9kZybJYWPJ2LMoPAAAA4CfKalxak1siiV3eToTyAwAAAPiJFVsK1eQxNDI5SgPjI8yO43UoPwAAAICfaL2xKRsdnBjlBwAAAPADRRX1+nJfqaTmLa5xPMoPAAAA4AeWbzokw5DG94tWn16hZsfxSpQfAAAAwA+03tiUjQ5OjvIDAAAA+Lh9JTXaVFAhm9Wiy9KTzI7jtSg/AAAAgI9rvbfPpIGxiosINjmN96L8AAAAAD7MMIyvl7yx0cEpUX4AAAAAH7ajqEq5xdUKslk1fVSi2XG8GuUHAAAA8GGtU5+LhsYrKsRhchrvRvkBAAAAfJRhGG3X+7DL27ej/AAAAAA+av2BchWU1Sk8yKYpwxLMjuP1KD8AAACAj2qd+lwyIkGhQTaT03g/yg8AAADgg9weQ8s3FUpiydvpovwAAAAAPujzvUdVUt2gXmEOnTco3uw4PoHyAwAAAPigpTnNS95mjEpSkJ1v608H/5UAAAAAH9PQ5NY7W1qWvHFj09NG+QEAAAB8zOpdJaqsb1LvyGBN7B9jdhyfQfkBAAAAfEzrjU1njU6WzWoxOY3voPwAAAAAPqTW1aRV2w5LYpe3jqL8AAAAAD5k1fZi1TW61S82TBkpTrPj+BTKDwAAAOBDWnd5mz06WRYLS946gvIDAAAA+IiK2kZ9sqtYEkveOoPyAwAAAPiId7cWqtFtaFhipIYkRJodx+dQfgAAAAAf0brL22zu7dMplB8AAADABxRX1euzPUclNV/vg46j/AAAAAA+4O1NhfIY0pjUXuobG2Z2HJ9E+QEAAAB8wLKWJW9zWPLWaZQfAAAAwMvll9Zq/YFyWS3SrNFJZsfxWZQfAAAAwMst29Q89Tl7QKx6R4WYnMZ3UX4AAAAAL9d6Y1OWvJ0Zyg8AAADgxXIPV2lHUZUcNosuHZVodhyfRvkBAAAAvFjrvX0uGByvXmFBJqfxbZQfAAAAwEsZhtFWfuaMYcnbmaL8AAAAAF5q88EK7T9aqxCHVVOHJ5gdx+dRfgAAAAAv1brRwdThCQoPtpucxvdRfgAAAAAv5PEYWr6pUBK7vHUVyg8AAADghb7cV6qiynpFhth14dB4s+P4hQ6Xn9WrV2v27NlKTk6WxWLRW2+9ddJjr7/+elksFj366KPtnm9oaNAtt9yiuLg4hYeHa86cOSooKOhoFAAAAMBvtW50cOnIRAXbbSan8Q8dLj81NTXKyMjQk08+ecrj3nrrLX3xxRdKTj5+RLdgwQItWbJEr776qtauXavq6mrNmjVLbre7o3EAAAAAv9Po9uidzS1L3tjlrct0+KqpGTNmaMaMGac85uDBg7r55pv13nvvaebMme1eq6io0PPPP68XXnhBU6dOlSS9+OKLSk1N1apVqzR9+vSORgIAAAD8ytrcEpXVNiouIkjnDIg1O47f6PJrfjwej6699lrdeeedGjly5HGvZ2dnq7GxUdOmTWt7Ljk5WaNGjdK6detO+DkbGhpUWVnZ7gEAAAD4q2UtS95mpifJbuMy/a7S5f8lH3zwQdntdt16660nfL2oqEhBQUGKjo5u93xCQoKKiopO+J5FixbJ6XS2PVJTU7s6NgAAAOAV6hvdem9r8/fFLHnrWl1afrKzs/XYY49p8eLFslgsHXqvYRgnfc/dd9+tioqKtkd+fn5XxAUAAAC8zoc7ilXjcqtPr1CN6xv97W/AaevS8rNmzRoVFxerb9++stvtstvt2r9/vxYuXKi0tDRJUmJiolwul8rKytq9t7i4WAkJJ75rbXBwsKKioto9AAAAAH/UemPT2RnJHR4o4NS6tPxce+212rRpk3JyctoeycnJuvPOO/Xee+9JkjIzM+VwOLRy5cq29xUWFmrLli2aNGlSV8YBAAAAfEplfaM+3FksiRubdocO7/ZWXV2t3bt3t32cl5ennJwcxcTEqG/fvoqNbb8bhcPhUGJiooYOHSpJcjqdmj9/vhYuXKjY2FjFxMTojjvuUHp6etvubwAAAEAgen/rYbmaPBoYH67hSZFmx/E7HS4/WVlZmjx5ctvHt99+uyTpuuuu0+LFi0/rczzyyCOy2+2aO3eu6urqNGXKFC1evFg2GzdvAgAAQOBqvbHpnIw+LHnrBhbDMAyzQ3RUZWWlnE6nKioquP4HAAAAfuFodYMmPvCB3B5DH91xkfrHhZsdySd0pBuwaTgAAADgBVZsKZLbYyi9j5Pi000oPwAAAIAXWJbTuuSNjQ66C+UHAAAAMNmh8jp9ua9UFos0KyPJ7Dh+i/IDAAAAmGz5puapz4S0GCU5Q01O478oPwAAAIDJWnd5m82St25F+QEAAABMtPdItbYcrJTNatFloxLNjuPXKD8AAACAiVqnPucNilNsRLDJafwb5QcAAAAwiWEYWraRXd56CuUHAAAAMMm2wkrtOVKjYLtV00YmmB3H71F+AAAAAJO0Lnm7eFhvRYY4TE7j/yg/AAAAgAk8HkPLNxZKYslbT6H8AAAAACZYf6BMB8vrFBFs1+Rhvc2OExAoPwAAAIAJWpe8TRuRoBCHzeQ0gYHyAwAAAPSwJrdHKzY3L3mbPYYlbz2F8gMAAAD0sM/2HlVJtUvRYQ6dNyjO7DgBg/IDAAAA9LClOc1L3i5LT5LDxrfkPYX/0gAAAEAPamhy692tRZLY5a2nUX4AAACAHvTxziOqqm9SkjNEE9JizI4TUCg/AAAAQA9q3eVt1ugkWa0Wk9MEFsoPAAAA0ENqGpr0wfbDkqTZLHnrcZQfAAAAoIes3HZY9Y0epcWGKb2P0+w4AYfyAwAAAPSQZS1L3uZkJMtiYclbT6P8AAAAAD2gvNal1blHJElzuLGpKSg/AAAAQA94Z0uRGt2GhidFaVDvSLPjBCTKDwAAANADWm9syr19zEP5AQAAALrZ4cp6fZ53VFLzFtcwB+UHAAAA6GbLNxXKMKRxfXspNSbM7DgBi/IDAAAAdLOlG1ny5g0oPwAAAEA3OnC0Vhvzy2W1SDNHU37MRPkBAAAAutGyTc1Tn0kD4xQfGWxymsBG+QEAAAC6Ebu8eQ/KDwAAANBNdhZVaefhKgXZrJo+KtHsOAGP8gMAAAB0k6UbD0qSLhwaL2eow+Q0oPwAAAAA3cAwDC3bWChJms2SN69A+QEAAAC6QU5+uQ6U1irUYdPU4b3NjgNRfgAAAIBu0Tr1uWREgsKC7CangUT5AQAAALqc22No+SZ2efM2lB8AAACgi32Rd1TFVQ1yhjp0wZB4s+OgBeUHAAAA6GLLNjZPfWaMSlSQnW+5vQX/JwAAAIAu5GryaMXmIkksefM2lB8AAACgC63JPaKKukbFRwbrrAGxZsfBMSg/AAAAQBda2rLkbWZ6kmxWi8lpcCzKDwAAANBF6lxurdx2WJI0ZwxL3rwN5QcAAADoIh/sOKxal1upMaEam9rL7Dj4BsoPAAAA0EWW5jQveZs9OlkWC0vevA3lBwAAAOgCFXWN+njnEUksefNWlB8AAACgC7y3tUgut0dDEiI0LDHK7Dg4AcoPAAAA0AVab2zKvX28F+UHAAAAOENHqhr06e4SSdKs0ZQfb0X5AQAAAM7Qis2F8hhSRopTaXHhZsfBSVB+AAAAgDPUuuRtNkvevBrlBwAAADgDB8vrlLW/TBYL5cfbUX4AAACAM9A69Tmrf4wSokJMToNTofwAAAAAZ6D1xqZzMvqYnATfhvIDAAAAdNLu4mptK6yU3WrRjFGJZsfBt6D8AAAAAJ20tGXJ2/mD4xQdHmRyGnwbyg8AAADQCYZhfH1j0zFsdOALKD8AAABAJ2w9VKm8khoF2626ZARL3nwB5QcAAADohNYlb1OHJygi2G5yGpwOyg8AAADQQR6PwY1NfRDlBwAAAOigrP1lKqyoV2SwXRcNjTc7Dk4T5QcAAADooKUbD0qSpo9KVIjDZnIanC7KDwAAANABjW6PVmwuksSSN1/T4fKzevVqzZ49W8nJybJYLHrrrbfavf6HP/xBw4YNU3h4uKKjozV16lR98cUX7Y5paGjQLbfcori4OIWHh2vOnDkqKCg4oy8EAAAA6Amf7i5RaY1LseFBOndgrNlx0AEdLj81NTXKyMjQk08+ecLXhwwZoieffFKbN2/W2rVrlZaWpmnTpunIkSNtxyxYsEBLlizRq6++qrVr16q6ulqzZs2S2+3u/FcCAAAA9IBlGwslSZelJ8luYyGVL7EYhmF0+s0Wi5YsWaLLL7/8pMdUVlbK6XRq1apVmjJliioqKhQfH68XXnhB8+bNkyQdOnRIqampWrFihaZPn/6t/97Wz1lRUaGoqKjOxgcAAAA6pL7RrQn3r1JVQ5P+dcM5mpAWY3akgNeRbtCtVdXlcukvf/mLnE6nMjIyJEnZ2dlqbGzUtGnT2o5LTk7WqFGjtG7duhN+noaGBlVWVrZ7AAAAAD3t453FqmpoUrIzRJl9o82Ogw7qlvKzfPlyRUREKCQkRI888ohWrlypuLg4SVJRUZGCgoIUHd3+ZElISFBRUdEJP9+iRYvkdDrbHqmpqd0RGwAAADilpcfc28dqtZicBh3VLeVn8uTJysnJ0bp163TppZdq7ty5Ki4uPuV7DMOQxXLiE+juu+9WRUVF2yM/P787YgMAAAAnVVXfqA+2N39Pyy5vvqlbyk94eLgGDRqks88+W88//7zsdruef/55SVJiYqJcLpfKysravae4uFgJCQkn/HzBwcGKiopq9wAAAAB60spth9XQ5NGAuHCNTOb7UV/UI9tTGIahhoYGSVJmZqYcDodWrlzZ9nphYaG2bNmiSZMm9UQcAAAAoMOOXfJ2shVL8G72jr6hurpau3fvbvs4Ly9POTk5iomJUWxsrP73f/9Xc+bMUVJSko4ePaqnn35aBQUF+u53vytJcjqdmj9/vhYuXKjY2FjFxMTojjvuUHp6uqZOndp1XxkAAADQRUprXFqbWyJJmjOGJW++qsPlJysrS5MnT277+Pbbb5ckXXfddXr22We1Y8cO/eMf/1BJSYliY2M1YcIErVmzRiNHjmx7zyOPPCK73a65c+eqrq5OU6ZM0eLFi2Wz2brgSwIAAAC61jtbCtXkMTQyOUoD4yPMjoNOOqP7/JiF+/wAAACgJ8177jN9kVequ2cM0/UXDjQ7Do7hNff5CQTZ+8t07fNf6KMdp97NDgAAAL6pqKJeX+4rlSTNYpc3n9bhZW9o772tRVqTW6LK+iZdNDSei98AAAD8zPJNh2QY0oS0aPXpFWp2HJwBJj9n6GfnD1CIw6qN+eX6ZNcRs+MAAACgi7Xu8jaHqY/Po/ycofjIYP3wrH6SpMc+yJUPXkIFAACAk8grqdGmggrZrBbNSE8yOw7OEOWnC/z8wgEKtlu14UC51rRsgQgAAADft7xl6jNpYKziIoJNToMzRfnpAr0jQ/QDpj8AAAB+xTAMlrz5GcpPF7mhZfqTvb9Mn+4+anYcAAAAnKEdRVXKLa5WkN2q6aMSzY6DLkD56SK9o0J0zVl9JUmPfbCL6Q8AAICPa536TB4ar6gQh8lp0BUoP13ohgsHKshu1Vf7yvTZHqY/AAAAvsowDC1rW/LWx+Q06CqUny6UEBWiayY2T38eXcW1PwAAAL5q/YFyFZTVKTzIpouH9TY7DroI5aeL3XDhQAXZrPpyX6k+28v0BwAAwBe1Tn0uGZGg0CCbyWnQVSg/XSzRGaLvTUyVJD22KtfkNAAAAOgot8fQ8k2FkqQ5Y9jlzZ9QfrrBjRc1T3++yCvV50x/AAAAfMrne4+qpLpBvcIcOm9QvNlx0IUoP90gyRmquRNSJDH9AQAA8DVLc5qXvM0YlaQgO98u+xP+b3aTGy8aJIfNos/2HtWXeaVmxwEAAMBpaGhy650tLUveuLGp36H8dJM+vUI1d3zLtT8f7DI5DQAAAE7H6l0lqqxvUkJUsCb2jzE7DroY5acb3TS5efrz6e6jytrH9AcAAMDbtd7YdNboZNmsFpPToKtRfrpRn16hujqzdfrDtT8AAADerNbVpFXbDkuSZrPkzS9RfrrZTRcNlN1q0ZrcEmXvZ/oDAADgrVZuO6y6Rrf6xYYpI8Vpdhx0A8pPN0uNCdPVmc07vz3Kzm8AAABea9nG5o0OZo9OlsXCkjd/RPnpAb+YPKht+rP+QJnZcQAAAPANFbWN+mRXsSRubOrPKD89IDUmTFeO6yOJ+/4AAAB4o3e3FqrRbWhYYqSGJESaHQfdhPLTQ26ePFg2q0Wf7DqinPxys+MAAADgGK27vLHRgX+j/PSQvrFhumJs6/SH+/4AAAB4i+Kqen2256gkbmzq7yg/PejmyYNks1r00c4j2sj0BwAAwCu8valQHkMak9pLqTFhZsdBN6L89KC0uHBdPqZ5+vM49/0BAADwCq1L3pj6+D/KTw+7+eJBslqkD3YUa3NBhdlxAAAAAlp+aa02HCiX1SLNGp1kdhx0M8pPD+t/zPTnsQ+49gcAAMBMyzY1T33OHhCr3lEhJqdBd6P8mKB1+rNqe7G2HGT6AwAAYJalOSx5CySUHxMMiI9o+w32GNf+AAAAmGL1riPaUVQlh82iGaNY8hYIKD8mufniwbJYpJXbDmvrIaY/AAAAPSm/tFa3vrpBkjRvQqqcYQ6TE6EnUH5MMqh3hGaPbp7+sPMbAABAz6lvdOuGF7NVXtuojBSnfjdzhNmR0EMoPya6dcogWSzSe1sPa3thpdlxAAAA/J5hGPrNm5u19VClYsOD9MwPMxXisJkdCz2E8mOiQb0jNTO9eX0p0x8AAIDu9491+/TmhoOyWS168ppxSu4VanYk9CDKj8lundJ87c87W4q0o4jpDwAAQHf5Mq9U97+9XZJ094xhOmdgrMmJ0NMoPyYbkhCpy1qmP098sNvkNAAAAP6pqKJeN720Xk0eQ98Zk6z55/U3OxJMQPnxArdePFiS9PbmQu0sqjI5DQAAgH9paHLrxpeyVVLdoGGJkVp0ZbosFovZsWACyo8XGJoYqcvSEyVJj3/ItT8AAABd6b5l27ThQLmiQux67tpMhQXZzY4Ek1B+vMStU5qnPys2Fyr3MNMfAACArvDaVwf08hcHZLFIj39/rPrFhpsdCSai/HiJYYlRunRkogxDevxDrv0BAAA4Uzn55fr9W1slSQsvGaKLhvY2ORHMRvnxIq3Tn+WbDml3MdMfAACAziqpbtCNL2bL5fZo2ogE3XTRILMjwQtQfrzIiOQoTRuRIMOQnmD6AwAA0CmNbo9+8dJ6FVbUa2B8uB6emyGrlQ0OQPnxOq3Tn2UbD2nPkWqT0wAAAPieRSt26Iu8UkUE2/XcteMVGeIwOxK8BOXHy4zq49QlIxLkMaQnmf4AAAB0yH9yDupvn+ZJkh6em6FBvSNMTgRvQvnxQre1TH/+k3NQe5n+AAAAnJZthyp11783SZJunjxI00cmmpwI3oby44VG9XFq6vDeTH8AAABOU3mtS9e/mKX6Ro8uGBKvX14yxOxI8EKUHy9125Tm37Bv5RxUXkmNyWkAAAC8l9tj6NZXc5RfWqe+MWF6/HtjZGODA5wA5cdLpac4dfEwpj8AAADf5s8rd2r1riMKcVj17A8z1SssyOxI8FKUHy/Weu3PWzkHtf8o0x8AAIBvendLkZ76aI8k6cGrRmtEcpTJieDNKD9eLCO1ly4aGi+3x2D6AwAA8A27i6u08PUcSdL88/rrO2P6mBsIXo/y4+Vapz9vbjioA0drTU4DAADgHarqG/XzF7JV43Lr7AExunvGMLMjwQdQfrzc2L7RumBI8/TnqY+Y/gAAAHg8hm5/faP2HqlRkjNET14zTnYb39bi23GW+IDW6c+/1xcov5TpDwAACGxPf7xbK7cdVpCteYODuIhgsyPBR1B+fEBmv2idPzhOTR5DT3/M9AcAAASuj3YW6+GVuyRJ/3P5SGWk9jI3EHwK5cdHLJjaPP35VxbTHwAAEJj2H63Rba9skGFI15zVV/Mm9DU7EnwM5cdHZPaL0XmDWqc/e8yOAwAA0KNqXU26/oVsVdY3aWzfXrp39gizI8EHUX58yG0t0583svN1sLzO5DQAAAA9wzAM3fXvzdpRVKW4iGA9+8NMBdttZseCD6L8+JAJaTGaNDBWjW5DT7PzGwAACBDPr83Tso2HZLda9MwPxykhKsTsSPBRlB8f07rz2+tZ+TrE9AcAAPi5dXtKtOidHZKk388aoQlpMSYngi+j/PiYswbE6uwBMWp0G3qGa38AAIAfO1hep5tf3iC3x9CV4/roR+f0MzsSfBzlxwfdNmWIJOm1r/JVWMH0BwAA+J/6RrdufDFbpTUujUyO0gNXpMtisZgdCz6O8uODzhkYq7P6x8jl9uhZpj8AAMDPGIahe/6zRZsKKhQd5tCzP8xUiIMNDnDmKD8+qnXnt1e+yldRRb3JaQAAALrOS18c0OtZBbJapCe+P06pMWFmR4KfoPz4qHMGxGpiWoxcTR49+wnTHwAA4B+y95fpvmVbJUm/unSYzhscZ3Ii+JMOl5/Vq1dr9uzZSk5OlsVi0VtvvdX2WmNjo+666y6lp6crPDxcycnJ+tGPfqRDhw61+xwNDQ265ZZbFBcXp/DwcM2ZM0cFBQVn/MUEEovF0jb9efnLAzpcyfQHAAD4tuLKet34YrYa3YZmpifp+gsGmB0JfqbD5aempkYZGRl68sknj3uttrZW69ev1+9//3utX79eb775pnbt2qU5c+a0O27BggVasmSJXn31Va1du1bV1dWaNWuW3G5357+SADRpYKzG94tm+gMAAHyeq8mjm15ar+KqBg1JiNBDV49mgwN0OYthGEan32yxaMmSJbr88stPesxXX32liRMnav/+/erbt68qKioUHx+vF154QfPmzZMkHTp0SKmpqVqxYoWmT59+3OdoaGhQQ0ND28eVlZVKTU1VRUWFoqKiOhvfL6zJPaJrn/9SwXar1vxqsnpz0y8AAOCD7vnPFv3zs/2KDLFr6c3nqX9cuNmR4CMqKyvldDpPqxt0+zU/FRUVslgs6tWrlyQpOztbjY2NmjZtWtsxycnJGjVqlNatW3fCz7Fo0SI5nc62R2pqanfH9hnnDYrTuL691NDk0XOr95odBwAAoMPeyC7QPz/bL0l6dN4Yig+6TbeWn/r6ev3617/WNddc09bCioqKFBQUpOjo6HbHJiQkqKio6ISf5+6771ZFRUXbIz8/vztj+5Tma3+a7/vz0hf7daSq4VveAQAA4D02F1ToN0s2S5IWTB2sKcMTTE4Ef9Zt5aexsVHf+9735PF49PTTT3/r8YZhnHRdZ3BwsKKioto98LULBsdpTGov1Td69JfVXPsDAAB8Q2mNSze8mC1Xk0dThvXWrRcPNjsS/Fy3lJ/GxkbNnTtXeXl5WrlyZbuykpiYKJfLpbKysnbvKS4uVkICTb8zjt357YXP96ukmukPAADwbk1uj255Zb0Oltepf1y4/jxvjKxWNjhA9+ry8tNafHJzc7Vq1SrFxsa2ez0zM1MOh0MrV65se66wsFBbtmzRpEmTujpOwLhoSLwyWqY/f+XaHwAA4OX+9N5Ofbr7qMKCbHru2kw5Qx1mR0IA6HD5qa6uVk5OjnJyciRJeXl5ysnJ0YEDB9TU1KSrr75aWVlZeumll+R2u1VUVKSioiK5XC5JktPp1Pz587Vw4UJ98MEH2rBhg374wx8qPT1dU6dO7dIvLpBYLBYtmNI8/fnnZ0x/AACA91q+6VDbRk1/ujpDQxIiTU6EQNHh8pOVlaWxY8dq7NixkqTbb79dY8eO1T333KOCggItXbpUBQUFGjNmjJKSktoex+7k9sgjj+jyyy/X3Llzde655yosLEzLli2TzWbruq8sAF00NF6jU5yqa3Trr2uY/gAAAO+zs6hKv3pjkyTp+gsHaOboJJMTIZCc0X1+zNKRvbwDzQfbD2v+P7IUFmTT2rsuVkx4kNmRAAAAJEkVdY36zpNrte9orc4bFKfFP5kgu63b77wCP+dV9/lBz7p4WG+l93Gq1sX0BwAAeA+Px9CCVzdo39Fa9ekVqie+P5bigx7HGednLBaLbm299mfdPpXVuExOBAAAID36Qa4+2nlEwXarnrs2U9GsToEJKD9+aOrw3hqZHKUal1v/t5bpDwAAMNeqbYf1+Ae5kqQHrkjXqD5OkxMhUFF+/NCx059/rNuv8lqmPwAAwBx7j1Trl6/lSJKuO6efrspMMTcQAhrlx09NG5Gg4UlRqm5o0vNr88yOAwAAAlB1Q5OufyFbVQ1NmpAWrd/NGmF2JAQ4yo+fslgsuq1l+vP3T/cx/QEAAD3KMAz96o2Nyi2uVkJUsJ76wTg52OAAJuMM9GPTRiRoWGKkqhua9DemPwAAoAc9+8lerdhcJIfNoqd/kKnekSFmRwIoP/7Mam0//amobTQ5EQAACARrco/oT+/tkCT9Yc5IZfaLNjkR0Izy4+emj0zU0IRIVTU06W+fMv0BAADdK7+0Vre8skEeQ5o3PlXXTOxrdiSgDeXHz1mtX+/89rdP81RRx/QHAAB0jzqXW9e/kK3y2kZlpDh133dGymKxmB0LaEP5CQAzRiVqSEKEquqbtPjTfWbHAQAAfsgwDP1myWZtK6xUbHiQnvlhpkIcNrNjAe1QfgKA1WrRLRc3T3+eX7tXlfVMfwAAQNf6x7p9WrLhoGxWi568ZpySe4WaHQk4DuUnQFyWnqRBvSNUWd+kfzD9AQAAXejLvFLd//Z2SdLdM4bpnIGxJicCTozyEyBsVotuuXiQJOn/1uapiukPAADoAkUV9brppWw1eQx9Z0yy5p/X3+xIwElRfgLIrNHJGhgfroq6Rv1j3T6z4wAAAB/X0OTWDS9mq6TapWGJkfrjlaPZ4ABejfITQGzH7Pz2f2vzVN3QZHIiAADgy/6wdJty8svlDHXoL9eOV2gQGxzAu1F+Asys0ckaEB+u8lqmPwAAoPNe/fKAXvnygCwW6bHvjVHf2DCzIwHfivITYNpd+7Nmr2qY/gAAgA7acKBM9/xnqyRp4SVDdNHQ3iYnAk4P5ScAzR6drP5x4SqrbdQ/P9tvdhwAAOBDjlQ16MYX18vl9mjaiATddNEgsyMBp43yE4DsNqtuntz8B9Vfmf4AAIDT1Oj26OaX16uosl4D48P18NwMWa1scADfQfkJUN8Zk6y02DCV1rj04udMfwAAwLdbtGKHvsgrVUSwXc9dO16RIQ6zIwEdQvkJUHabVb9omf78ZfVe1bqY/gAAgJP7T85B/e3TPEnSw3MzNKh3hMmJgI6j/ASwK8b2Ud+YMB2tcemlzw+YHQcAAHiprYcqdNe/N0mSbp48SNNHJpqcCOgcyk8As9usurll57fnVu9RncttciIAAOBtymtduuHFbNU3enThkHj98pIhZkcCOo3yE+CuGNtHqTGhKql26aUvuPYHAAB8ze0xdMsrG5RfWqe+MWF67HtjZGODA/gwyk+Acxyz89uzn+xl+gMAANo8/P5OrcktUYjDqmd/mKleYUFmRwLOCOUHunJcilKiQ1VS3aCXv+TaHwAAIL27pVBPf7xHkvTgVaM1IjnK5ETAmaP8QI5jdn579pM9qm9k+gMAQCDLPVylha9vlCTNP6+/vjOmj8mJgK5B+YEk6apxKerTK1RHqhr0CtMfAAACVmV9o65/IVs1LrfOHhCju2cMMzsS0GUoP5AkBdmtumnyQElMfwAACFQej6GFr2/U3pIaJTlD9OQ142S38e0i/AdnM9p8NzNVyc4QHa5s0Gtf5ZsdBwAA9LCnPtqtldsOK8jevMFBXESw2ZGALkX5QZsgu1U3tlz788zHTH8AAAgkH+0s1p9X7ZIk3f+dUcpI7WVuIKAbUH7QztzxKUpyhqiosl6vZzH9AQAgEOwrqdFtr2yQYUg/OKuv5k5INTsS0C0oP2gn2G7TTRc1X/vzzMd71NDE9AcAAH9W62rSDS9mq7K+SWP79tI9s0eYHQnoNpQfHGfuhFQlRoWosKJer2cVmB0HAAB0E8Mw9Ks3NmlHUZXiIoL17A8zFWy3mR0L6DaUHxwn2G7Tja3Tn492M/0BAMBP/d+aPC3fVCi71aJnfjhOCVEhZkcCuhXlByc0b0KqEqKCdaiiXm9kM/0BAMDfrNtdokXvbJck/X7WCE1IizE5EdD9KD84oRCHTTdc2Dz9efqjPXI1eUxOBAAAusrB8jrd/MoGeQzpynF99KNz+pkdCegRlB+c1Pcn9lV8ZLAOltfp3+uZ/gAA4A/qG9268cVslda4NKpPlB64Il0Wi8XsWECPoPzgpI6d/jz10W41upn+AADgywzD0O/f2qJNBRWKDnPo2R9mKsTBBgcIHJQfnNIPzuqruIhgFZTV6U2mPwAA+LQXvzigf2UXyGqRnvj+OKVEh5kdCehRlB+cUvP0Z4Ak6YkPmf4AAOCrsveX6r+XbZUk/erSYTpvcJzJiYCeR/nBt/rBWf0UFxGkgrI6LVl/0Ow4AACgg4or63XDi+vV6DY0Mz1J118wwOxIgCkoP/hWoUE2XX9B87U/T3LtDwAAPsXV5NGNL63XkaoGDUmI0ENXj2aDAwQsyg9Oyw/O7qvY8CAdKK3VWxuY/gAA4Cvuf3ubsveXKTLErueuHa/wYLvZkQDTUH5wWsKC7Pp5y4j8yY92q4npDwAAXu+N7AL987P9kqRH541R/7hwkxMB5qL84LRde04/xYQHaf/RWv0n55DZcQAAwClsLqjQb5ZsliQtmDpYU4YnmJwIMB/lB6ctLMiun53P9AcAAG93tLpBN7yYLVeTR1OH99atFw82OxLgFSg/6JAfndNP0WEO5ZXUaNkmpj8AAHibJrdHt7yyQQfL69Q/Llx/njdGVisbHAAS5QcdFB5s109bpj9PfLBbbo9hciIAAHCsh97bqXV7jiosyKbnrs1UVIjD7EiA16D8oMOum5SmXmEO7S2p0bKNTH8AAPAWyzYe0l9W75Uk/enqDA1JiDQ5EeBdKD/osIjgr6/9efzDXKY/AAB4gR1FlfrVG5skSddfOEAzRyeZnAjwPpQfdMqPzuknZ6hDe4/UaDnX/gAAYKqyGpeufyFbdY1unTcoTndOG2p2JMArUX7QKZEhDv30vP6SpCc+5NofAADM8vHOYl362GrtP1qrPr1C9cT3x8pu41s84ET4nYFOu+7cNEWF2LW7uForNheaHQcAgIBS09Ck3yzZrB///SsdrmzQgPhw/f0nExQdHmR2NMBrUX7QaVEhDs0/r2Xntw9z5WH6AwBAj/gyr1SXPrZaL39xQJL0k3PTtOLW89ngAPgWlB+ckR+fm6bIELt2Ha7WO1uKzI4DAIBfq29064EV2zXvL58pv7ROfXqF6uWfnaV7Z49UiMNmdjzA61F+cEacoQ7917nN1/48/gHTHwAAusvmggrNfmKt/rJ6rwxDmjs+Re8uOF+TBsaZHQ3wGZQfnLH/Ore/IoPt2nm4Su9tZfoDAEBXanR79OiqXbri6U+VW1ytuIhg/d+PxuuhqzMUyQ1MgQ6h/OCMOcMc+sm5aZKkx5j+AADQZXIPV+mqZ9bp0VW5avIYmjk6SSt/eYGmjkgwOxrgkyg/6BL/dV5/RQTbtaOoSu9vY/oDAMCZ8HgM/d+avZr5xFptKqiQM9Shx78/Vk9dM47d3IAzQPlBl+gVFnTM9Gc30x8AADopv7RW3/vr57r/7e1yNXl00dB4vf/LCzQnI9nsaIDPo/ygy8xvmf5sL6zUyu2HzY4DAIBPMQxDr3x5QJc+ulpf5pUqPMimRVem6+8/nqCEqBCz4wF+ocPlZ/Xq1Zo9e7aSk5NlsVj01ltvtXv9zTff1PTp0xUXFyeLxaKcnJzjPkdDQ4NuueUWxcXFKTw8XHPmzFFBQUFnvwZ4iV5hQbpuUj9JzTu/GQbTHwAATsfhynr9ZPFXuvvNzapxuTWxf4zeue0CfX9iX1ksFrPjAX6jw+WnpqZGGRkZevLJJ0/6+rnnnqs//vGPJ/0cCxYs0JIlS/Tqq69q7dq1qq6u1qxZs+R2uzsaB17mp+cNUHiQTVsPVWrV9mKz4wAA4PWWbjykaY+s1sc7jyjIbtXvZg7Xqz87W31jw8yOBvgde0ffMGPGDM2YMeOkr1977bWSpH379p3w9YqKCj3//PN64YUXNHXqVEnSiy++qNTUVK1atUrTp0/vaCR4kejwIP1oUpqe+XiPHvtgl6YO781PrAAAOIGyGpd+958tentToSQpvY9Tf56bocEJkSYnA/xXj1/zk52drcbGRk2bNq3tueTkZI0aNUrr1q074XsaGhpUWVnZ7gHv9bPzBygsyKYtByv14Q6mPwAAfNOHOw5r2qOr9famQtmtFi2YOlhv3jSJ4gN0sx4vP0VFRQoKClJ0dHS75xMSElRUdOItkhctWiSn09n2SE1N7Ymo6KSY8CBde07ztT+Pce0PAABtquobddcbm/Rfi7N0pKpBg3tHaMlN52rB1CFy2NiHCuhuXvO7zDCMky6Puvvuu1VRUdH2yM/P7+F06Kifnz9AoQ6bNhVU6KOdTH8AAPhsz1Fd+ugavZaVL4tF+tn5/bXslvOUnuI0OxoQMHq8/CQmJsrlcqmsrKzd88XFxUpIOPHdioODgxUVFdXuAe8WGxH89fRnFdMfAEDgqm90675lW/X9v36ug+V1So0J1as/O1u/nTlCIQ6b2fGAgNLj5SczM1MOh0MrV65se66wsFBbtmzRpEmTejoOutHPLxigEIdVGwsq9PGuI2bHAQCgx+Xkl+uyx9fo75/ukyR9f2JfvXPbBTprQKy5wYAA1eHd3qqrq7V79+62j/Py8pSTk6OYmBj17dtXpaWlOnDggA4dOiRJ2rlzp6TmiU9iYqKcTqfmz5+vhQsXKjY2VjExMbrjjjuUnp7etvsb/ENcRLCuPbuf/romT4+tytVFQ+LZ+Q0AEBBcTR498WGunv54j9weQ70jg/Xg1aM1eWhvs6MBAa3Dk5+srCyNHTtWY8eOlSTdfvvtGjt2rO655x5J0tKlSzV27FjNnDlTkvS9731PY8eO1bPPPtv2OR555BFdfvnlmjt3rs4991yFhYVp2bJlstkY/fqbn18wUCEOq3Lyy7U6t8TsOAAAdLudRVW64ulP9cSHu+X2GJqTkaz3f3kBxQfwAhbDBy/GqKyslNPpVEVFBdf/+ID/Wb5Nz6/N07i+vfTvGycx/QEA+CW3x9Bf1+zVn9/fJZfbo+gwh+6/PF0zRyeZHQ3wax3pBl6z2xv81/UXDlCw3ar1B8q1djfTHwCA/9l/tEbznvtMf3xnh1xuj6YM6633fnkBxQfwMpQfdLvekSG65qy+ktj5DQDgXwzD0Auf79elj65R1v4yRQTb9dBVo/V/141X78gQs+MB+AbKD3rEDRcOVJDdqqz9ZVq356jZcQAAOGOFFXX60d++1O/f2qK6RrfOHhCjdxecr7kTUlniDXgpyg96REJUiK6Z2Dz9eXTVLqY/AACfZRiGlmwo0LRHVmtNbomC7VbdO3uEXv7p2UqJDjM7HoBToPygx9xw4UAF2az6al+ZPmP6AwDwQUerG3Tji+v1y9c2qqq+SRmpvbTitvP1k3P7y2pl2gN4O8oPekyiM0Tfn5gqSXr0g1yT0wAA0DHvby3S9EdX692tRbJbLbpj2hD9+4ZzNDA+wuxoAE4T5Qc96oaLmqc/X+aVMv0BAPiEyvpGLXx9o37+QrZKql0amhCp/9x8rm6+eLDsNr6VAnwJv2PRo5KcoZo3oXn689gHu0xOAwDAqX26u0SXPrJa/15fIKuleQn30lvO1chkp9nRAHSC3ewACDw3XjRQr351QJ/vLdUXe4/qrAGxZkcCAKCdOpdbf3xnu/7x2X5JUr/YMP15boYy+8WYnAzAmWDygx6X3CtUc8c3T39+/58t2nKwwuREAAB8LXt/mS57fE1b8bn27H5657bzKT6AH2DyA1P8YvIgLd9UqF2HqzX7ybWaNz5Vd0wfqriIYLOjAQACVEOTW4+tytWzn+yRx5ASo0L0p++O1vmD482OBqCLWAwfvOFKZWWlnE6nKioqFBUVZXYcdNKh8jr98Z0dWrrxkCQpMtiuW6cM1nWT0hRkZygJAOg52w5V6vbXc7SjqEqSdOXYPrp3zkg5Qx0mJwPwbTrSDSg/MN1X+0p137Kt2nKwUpI0IC5cv581QpOH9TY5GQDA3zW5PXpu9V49umqXGt2GYsOD9L9XpOvSUYlmRwNwmig/8Dluj6E3svP1p/d2qqTaJUm6aGi8fjdzhAb15v4JAICut/dItRb+a6M2HCiXJE0bkaAHrkxnCTbgYyg/8FmV9Y168sPd+vuneWp0G7JbLfrxpDTdOnWwokJYegAAOHMej6F/frZPf3x3h+obPYoMtusPc0bqynF9ZLFYzI4HoIMoP/B5e49U6/63t+vDHcWSpNjwIN05fai+Oz5VNit/MQEAOudgeZ3u/NdGrWu50fZ5g+L00NWjldwr1ORkADqL8gO/8dHOYv3P8m3ae6RGkjQyOUr3zh6pif3ZbhQAcPoMw9Ab2QX672XbVNXQpFCHTb+5bJh+cFY/WfmhGuDTKD/wK41uj/6xbp8e+yBXVfVNkqTZGcn69Yxh6sNP6gAA3+JIVYPufnOzVm0/LEka17eXHp47Rv3jwk1OBqArUH7gl0qqG/Tw+7v06lcHZBhSiMOqGy4cqOsvGKjQIJvZ8QAAXuidzYX67VtbVFrjUpDNql9eMkQ/v2AAS6gBP0L5gV/bcrBC/71sm77cVypJ6tMrVHdfNkwz05O4UBUAIEmqqG3UvUu36K2c5nvJDU+K0iPzMjQske8bAH9D+YHfMwxDb28u1ANvb9ehinpJ0sS0GN0ze4RG9XGanA4AYKZPdh3RXW9sUlFlvawW6aaLBunWKYO5gTbgpyg/CBh1LreeW71Hz36yR/WNHlks0vcmpOqOaUMVy30aACCg1DQ06YEV2/XSFwckNd80++G5GRrbN9rkZAC6E+UHAedgeZ0Wrdiu5ZsKJUmRIXbdNmWwrpuUJoeNn/QBgL/7al+pFr6+UQdKayVJP56UprsuHcY1oUAAoPwgYH2ZV6r7lm3V1kOVkqSB8eH6/awRumhob5OTAQC6Q32jW4+s3KW/rNkrw2i+DvRPV4/WpEFxZkcD0EMoPwhobo+hf2Xl60/v7dTRGpck6eJhvfW7mcM1ID7C5HQAgK6y5WCFbn89R7sOV0uSvpuZot/PHqGoEIfJyQD0JMoPIKmirlFPfJCrxev2qcljyGGz6Cfn9tfNFw/iL0YA8GFNbo+e/niPHv8gV00eQ3ERwVp0ZbouGZFgdjQAJqD8AMfYc6Ra/7N8mz7eeUSSFBcRpDunD9V3M1O5qzcA+JjdxVVa+PpGbSyokCRdlp6o+y9PV0x4kMnJAJiF8gOcwEc7ivU/y7dpb0mNJCm9j1P3zh6h8WkxJicDAHwbj8fQ39ft00Pv7lBDk0dRIXb9z+WjNCcjmXu8AQGO8gOchKvJo3+s26fHP8hVVUOTJGlORrLuvmyYkpyhJqcDAJxIfmmt7vjXRn2R13xz6wuHxOvBq0Yr0RlicjIA3oDyA3yLI1UNevj9nXotK1+GIYU6bLrxooH6+QUDFOJgW1QA8AaGYej1rHz997JtqnG5FRZk029nDtc1E/sy7QHQhvIDnKbNBRW6b9lWZe0vk9S8RepvZw7XjFGJ/MUKACYqrqzXr9/crA93FEuSJqRF6/99N0P9YsNNTgbA21B+gA4wDEPLNhVq0YrtKqyolySdPSBG98waqRHJnF8A0NOWbzqk3721ReW1jQqyWXXH9CGaf94A2dikBsAJUH6ATqh1NenZT/bquU/2qKHJI6tF+v7Evlo4bSi7CAFAN6t1NemdzUV6PSu/7dqeUX2i9Oe5YzQkIdLkdAC8GeUHOAMFZbVa9M4Ovb2pUJIUFWLXgqlDdO05/eSwWU1OBwD+wzAMfZlXqjeyC7Ric6FqXG5Jks1q0S8mD9ItFw/iz10A34ryA3SBz/ce1X3Ltml7YaUkaVDvCN0za4QuGBJvcjIA8G0FZbX6d/ZB/Xt9gQ6U1rY93y82TFePS9GVmSnq04sdOAGcHsoP0EXcHkOvfZWv//f+TpXWuCRJU4f31m9njlD/OC66BYDTVetq0rtbivRGdoHW7Tna9nxEsF0z05N09fgUje8XzWYzADqM8gN0sYraRj32Qa7++dk+NXkMOWwW/dd5/XXz5EGKDHGYHQ8AvJJhGPpqX5neyM7X25u+XtZmsUiTBsbq6swUTR+ZqLAgu8lJAfgyyg/QTXYXV+m+Zdu0JrdEkhQXEaxfXTpUV49LkZVdiABAUvOytjfXNy9r23/0+GVtV4zro5ToMBMTAvAnlB+gGxmGoQ93FOt/lm/Tvpa/1EenOHXv7JHK7BdtcjoAMMfJlrWFB9k0a3Qyy9oAdBvKD9ADGprcWvzpPj3x4W5VNzRJkq4Y20d3XTpMic4Qk9MBQPczDENZ+8v0RlaB3t5c2PZnofT1srZLR7GsDUD3ovwAPai4ql7/772d+ld2gQxDCnXY9IvJA/XT8wcoxGEzOx4AdLmD5XV6M7tAb3xjWVvfmDBdnZmiK1nWBqAHUX4AE2wqKNd9y7Ype3+ZJCklOlS/mzlc00cmsswDgM+rc7n17tbCtmVtrd89hAfZNHN0kq7OTNWENJa1Aeh5lB/AJIZhaOnGQ1q0YoeKKuslSecMiNU9s0doeBLnKgDfYhiGsveX6V8sawPgxSg/gMlqXU165uM9em71XrmaPLJapB+c1U+3XzJE0eFBZscDgFM6WF6nJesL9EZ2QdvGLpKUGhOqq8el6spxfZQaw7I2AN6B8gN4ifzSWi16Z7tWbC6SJDlDHfrl1MH6wdn95LBZTU4HAF+rc7n13tbm3do+3VPStqwtLMjWfBPSzBRNSIthW38AXofyA3iZdXtK9N/LtmlHUZUkaXDvCN07e6TOGxxncjIAgax1Wdsb2QVavqn9srZzBny9rC08mGVtALwX5QfwQk1uj179Kl8Pv79TZbWNkqRLRiTodzOHq19suMnpAASSQ+V1enN9gf69/qDySmranmdZGwBfRPkBvFh5rUuPrsrVC5/vl9tjKMhm1fzz++sXkwcpgp+uAugmdS633t/WvKxt7e72y9oua1nWNpFlbQB8EOUH8AG5h6v038u3aU1uiSSpd2Sw7rp0mK4Y24dvPgB0CcMwtP5Ay7K2jYWqOmZZ29kDYnR1ZqpmsKwNgI+j/AA+wjAMrdperPvf3tZ2o8CM1F76w+wRGts32uR0AHzVofI6LdlwUG9kF7Rb1pYSHaqrM1N01bgUlrUB8BuUH8DHNDS59fdP9+mJD3JV43JLkq4c20d3zRimhKgQk9MB8AX1jV/v1sayNgCBhPID+Kjiyno99N5OvZFdIKn5m5ZfTB6k+ef1V4jDZnI6AN6meVlbecuytkPtlrWd1T9GV2em6LL0JJa1AfBrlB/Ax23ML9cflm3VhgPlkpp3YPrtZSM0fWSCLBZ+agsEusKKOr25/qD+nV2gvd9Y1nbVuOZlbX1jWdYGIDBQfgA/4PEY+s/Gg/rjOzt0uLJBknTuoFjdM2ukhiZGmpwOQE872bK2UMfXy9rO6s+yNgCBh/ID+JGahiY9/fFu/XVNnlxNHtmsFl01ro8uGBKvCWkxXBME+DHDMLQhv1z/yirQ8k2HVFV//LK2GelJbJMPIKBRfgA/dOBorR5YsV3vbi1q93xKdKgmpMUos1+0JqTFaHDvCH7yC/i4oop6vbmhQG9kF2jvka+XtfXpFaqrMlN01bg+3BwZAFpQfgA/9vneo3pnc6G+2lemHUWV8nzjd3BUiF2Z/aI1Pi1G4/tFKyO1F5slAD6gvtGt97cdbl7Wlnuk7fd2qMOmGemJujozRWf3j+WHGwDwDZQfIEBU1Tdqw4FyZe0rVdb+Mm04UK66Rne7Yxw2i0b1cbZNh8b3i1ZsRLBJiQEcq3VZ2xvZBVq2sf2ytonH7NbGsjYAODnKDxCgGt0ebS+s1Ff7ypS9v1Rf7SvTkaqG444bEBeu8WlfT4f6x4WzixzQg1jWBgBdh/IDQFLzT5XzS+v0VctkKGtfqXKLq487LjY8qO2aocy0aI1KdirIbjUhMeC/6hvdWtmyrG3NMcvaQhxWXTaqebe2swewrA0AOoryA+Ckymtdyt5f1jYd2lhQIVeTp90xwXarMlJ7aUJatMb3i9G4ftFyhjpMSgz4LsMwlHPMsrbKY5e1pbXu1paoyBB+fwFAZ1F+AJy2hia3thys0Ff7ypTVUojKahvbHWOxSEMTIr+eDvWLVkp0KEvlgG+ob3Rr75Ea5RZXadfhKr27pUh7vrmsbVwfXTkuRWlxLGsDgK5A+QHQaYZhaM+RmrZNFLL2lWrf0drjjkuMClFmWrQmtOwsNywxUnYbS+UQGGpdTdpT3FxycourlXu4WruLq3SgtPa4HRhZ1gYA3atby8/q1av1pz/9SdnZ2SosLNSSJUt0+eWXt71uGIbuu+8+/eUvf1FZWZnOOussPfXUUxo5cmTbMQ0NDbrjjjv0yiuvqK6uTlOmTNHTTz+tlJSULv8CAZy5I1UNbRsoZO0v09aDFWr6xnd44UE2je0brfFpzdOhMam9FM4OVfBxlfWN2l1crd2Hq9sVnYPldSd9jzPUocG9IzQ4IUJjU6NZ1gYA3awj3aDD35nU1NQoIyNDP/nJT3TVVVcd9/pDDz2kP//5z1q8eLGGDBmi+++/X5dccol27typyMhISdKCBQu0bNkyvfrqq4qNjdXChQs1a9YsZWdny2bjfiSAt4mPDNalo5J06agkSVKdy62c/K+32F6/v0xVDU1au7tEa3eXSJJsVotGJEW1LZUbnxathKgQM78M4KTKalzNxaa4qrnstJScosr6k74nLiJIg3pHaHDvSA1OiNCg+AgNSohQfEQwS0IBwEud0bI3i8XSbvJjGIaSk5O1YMEC3XXXXZKapzwJCQl68MEHdf3116uiokLx8fF64YUXNG/ePEnSoUOHlJqaqhUrVmj69Onf+u9l8gN4F7fH0K7DVcraV9qykULZCX8ynhoTqvH9movQ+H4xGtw7giVA6DGGYaik2tVWcHIPf112SqpdJ31fYlSIBvWOaC46Cc1lZ1DvCMWEB/VgegDAyXTr5OdU8vLyVFRUpGnTprU9FxwcrAsvvFDr1q3T9ddfr+zsbDU2NrY7Jjk5WaNGjdK6detOWH4aGhrU0PD1vUoqKyu7MjaAM2SzWjQ8KUrDk6J07TlpkqRD5XVt1wxl7SvTjqJK5ZfWKb/0oJZsOChJigqxa3zLBgoT0mI0OsWpEAfTX5wZwzBUVFnfUm6ar8Vp/XVFXeNJ39enV2hLuWkpOAnNhSeKJWsA4De6tPwUFRVJkhISEto9n5CQoP3797cdExQUpOjo6OOOaX3/Ny1atEj33XdfV0YF0M2Se4VqTq9QzclIliRV1Tdqw4Gvl8ptOFCuyvomfbijWB/uKJYkOWwWpfdxtt18NbNftGIjgs38MuDFPB5DB8vrmq/FOdyyVK1lyVp1Q9MJ32OxSP1iwjSoZalaa9EZEB/ONWoAEAC65U/6b651NgzjW9c/n+qYu+++W7fffnvbx5WVlUpNTT3zoAB6TGSIQxcMidcFQ+IlSY1uj7YXVrbdb+irfWU6UtWg9QfKtf5Auf7S8r4B8eEa37Kj3IS0GKXFhnE9RYBpcnuUX1an3MNVbeWmdblafaPnhO+xWy1KiwvX4JblaoOOKTlMFwEgcHVp+UlMTJTUPN1JSkpqe764uLhtGpSYmCiXy6WysrJ205/i4mJNmjTphJ83ODhYwcH89BfwJw6bVaNTeml0Si/NP6+/DMPQgdJaZe0rU9b+5qVyucXV2nukRnuP1Oj1rAJJUmx4UNs1Q+PTojUy2akgO1ts+wNXk0f7j9a07ajWWnD2ltQcdyPeVkE2qwbEh7fbeGBw7wj1iw3nvAAAHKdLy0///v2VmJiolStXauzYsZIkl8ulTz75RA8++KAkKTMzUw6HQytXrtTcuXMlSYWFhdqyZYseeuihrowDwIdYLBb1iw1Xv9hwXZXZvO19WY1L6w+UtU2HNuZX6GiNS+9tPaz3th6WJAXbrRqT2qu5EKXFaFzfaDlDuUbDmx17I9C2ndWKq7WvpOa4LdRbhTisbQWn+Z/N05y+MWHcXwoAcNo6XH6qq6u1e/futo/z8vKUk5OjmJgY9e3bVwsWLNADDzygwYMHa/DgwXrggQcUFhama665RpLkdDo1f/58LVy4ULGxsYqJidEdd9yh9PR0TZ06teu+MgA+Lzo8SFOGJ2jK8ObJcUOTW1sOVjTfb6ilEJXVNuqLvFJ9kVcqaY8sFmloQmS7Lbb79AplqZwJOnIj0FYRwfZ25aZ1d7U+vULZGRAAcMY6vNX1xx9/rMmTJx/3/HXXXafFixe33eT0ueeea3eT01GjRrUdW19frzvvvFMvv/xyu5ucnu51PGx1DUBqvlZwz5GaY7bYLtW+o7XHHZcYFaLxadFtN1512Kxy2CyyW5v/2fyxVXabpe1ju9WqIHvzMXabRUE2q+w26zGvW2SzWihVOvMbgQ7qHdn268SoEP6bAgA6pCPd4Izu82MWyg+Akymuqtf6/c1L5bL2l2nrwYqTLqU6UxaL5GgpUO2Kkc3S8nxroTqmbNmtclgtx79mszYXLGvrr1s/Z+t7LS3vtcphb1/c7LaWz2lvfv+xZS7o2H+Ptf2/s6Ml49gbgeYertaeI524EWjLr+Migig5AIAuYdp9fgDAbL0jQ3TpqCRdOqp505U6l1s5+c1bbO8oqlJDk1uNbkONbo+a3IYaPZ6vf+32qNFtqMntkcttqMnT/LzL3XzMN39UZBiSy+2Ryy1J7h7/Ws9Uc9FqKWrtilP74mWxWHSwrPZbbwTaWm6OvTaHG4ECALwJ5QeAXwsNsumcgbE6Z2DsGX8ut6elNHkMNTZ5WopTc1k6rlA1NR/nanmuuVAdU7I8re870Xubi9exZaztGE9rSTvxa64mT7vS1nTMa9/U5DHU5DFUL4/UcIIv+AS4ESgAwJdRfgDgNNmsFtmsLfeI8bHd9w3DOKY4Gd+YdnnavXZsUWtqKXjJzlBuBAoA8Hn8LQYAAcBi+XozBwAAAhV/CwIAAAAICJQfAAAAAAGB8gMAAAAgIFB+AAAAAAQEyg8AAACAgED5AQAAABAQKD8AAAAAAgLlBwAAAEBAoPwAAAAACAiUHwAAAAABgfIDAAAAICBQfgAAAAAEBMoPAAAAgIBA+QEAAAAQECg/AAAAAAIC5QcAAABAQKD8AAAAAAgIdrMDdIZhGJKkyspKk5MAAAAAMFNrJ2jtCKfik+WnqqpKkpSammpyEgAAAADeoKqqSk6n85THWIzTqUhexuPx6NChQ4qMjJTFYjE7jiorK5Wamqr8/HxFRUWZHQd+jvMNPY1zDj2J8w09jXPO9xmGoaqqKiUnJ8tqPfVVPT45+bFarUpJSTE7xnGioqL4TYMew/mGnsY5h57E+Yaexjnn275t4tOKDQ8AAAAABATKDwAAAICAQPnpAsHBwbr33nsVHBxsdhQEAM439DTOOfQkzjf0NM65wOKTGx4AAAAAQEcx+QEAAAAQECg/AAAAAAIC5QcAAABAQKD8AAAAAAgIlB8AAAAAAYHycxqefvpp9e/fXyEhIcrMzNSaNWtOefwnn3yizMxMhYSEaMCAAXr22Wd7KCn8RUfOuTfffFOXXHKJ4uPjFRUVpXPOOUfvvfdeD6aFP+jon3OtPv30U9ntdo0ZM6Z7A8KvdPR8a2ho0G9/+1v169dPwcHBGjhwoP72t7/1UFr4g46ecy+99JIyMjIUFhampKQk/eQnP9HRo0d7KC26lYFTevXVVw2Hw2H89a9/NbZt22bcdtttRnh4uLF///4THr93714jLCzMuO2224xt27YZf/3rXw2Hw2G88cYbPZwcvqqj59xtt91mPPjgg8aXX35p7Nq1y7j77rsNh8NhrF+/voeTw1d19JxrVV5ebgwYMMCYNm2akZGR0TNh4fM6c77NmTPHOOuss4yVK1caeXl5xhdffGF8+umnPZgavqyj59yaNWsMq9VqPPbYY8bevXuNNWvWGCNHjjQuv/zyHk6O7kD5+RYTJ040brjhhnbPDRs2zPj1r399wuN/9atfGcOGDWv33PXXX2+cffbZ3ZYR/qWj59yJjBgxwrjvvvu6Ohr8VGfPuXnz5hm/+93vjHvvvZfyg9PW0fPtnXfeMZxOp3H06NGeiAc/1NFz7k9/+pMxYMCAds89/vjjRkpKSrdlRM9h2dspuFwuZWdna9q0ae2enzZtmtatW3fC93z22WfHHT99+nRlZWWpsbGx27LCP3TmnPsmj8ejqqoqxcTEdEdE+JnOnnN///vftWfPHt17773dHRF+pDPn29KlSzV+/Hg99NBD6tOnj4YMGaI77rhDdXV1PREZPq4z59ykSZNUUFCgFStWyDAMHT58WG+88YZmzpzZE5HRzexmB/BmJSUlcrvdSkhIaPd8QkKCioqKTvieoqKiEx7f1NSkkpISJSUldVte+L7OnHPf9PDDD6umpkZz587tjojwM50553Jzc/XrX/9aa9askd3OXyM4fZ053/bu3au1a9cqJCRES5YsUUlJiW666SaVlpZy3Q++VWfOuUmTJumll17SvHnzVF9fr6amJs2ZM0dPPPFET0RGN2PycxosFku7jw3DOO65bzv+RM8DJ9PRc67VK6+8oj/84Q967bXX1Lt37+6KBz90uuec2+3WNddco/vuu09DhgzpqXjwMx35M87j8chiseill17SxIkTddlll+nPf/6zFi9ezPQHp60j59y2bdt066236p577lF2drbeffdd5eXl6YYbbuiJqOhm/MjuFOLi4mSz2Y77yUBxcfFxP0FolZiYeMLj7Xa7YmNjuy0r/ENnzrlWr732mubPn69//etfmjp1anfGhB/p6DlXVVWlrKwsbdiwQTfffLOk5m9ODcOQ3W7X+++/r4svvrhHssP3dObPuKSkJPXp00dOp7PtueHDh8swDBUUFGjw4MHdmhm+rTPn3KJFi3TuuefqzjvvlCSNHj1a4eHhOv/883X//fezisfHMfk5haCgIGVmZmrlypXtnl+5cqUmTZp0wvecc845xx3//vvva/z48XI4HN2WFf6hM+ec1Dzx+fGPf6yXX36ZNcnokI6ec1FRUdq8ebNycnLaHjfccIOGDh2qnJwcnXXWWT0VHT6oM3/GnXvuuTp06JCqq6vbntu1a5esVqtSUlK6NS98X2fOudraWlmt7b9Fttlskr5ezQMfZtZOC76idXvE559/3ti2bZuxYMECIzw83Ni3b59hGIbx61//2rj22mvbjm/d6vqXv/ylsW3bNuP5559nq2t0SEfPuZdfftmw2+3GU089ZRQWFrY9ysvLzfoS4GM6es59E7u9oSM6er5VVVUZKSkpxtVXX21s3brV+OSTT4zBgwcbP/3pT836EuBjOnrO/f3vfzfsdrvx9NNPG3v27DHWrl1rjB8/3pg4caJZXwK6EOXnNDz11FNGv379jKCgIGPcuHHGJ5980vbaddddZ1x44YXtjv/444+NsWPHGkFBQUZaWprxzDPP9HBi+LqOnHMXXnihIem4x3XXXdfzweGzOvrn3LEoP+iojp5v27dvN6ZOnWqEhoYaKSkpxu23327U1tb2cGr4so6ec48//rgxYsQIIzQ01EhKSjJ+8IMfGAUFBT2cGt3BYhjM7wAAAAD4P675AQAAABAQKD8AAAAAAgLlBwAAAEBAoPwAAAAACAiUHwAAAAABgfIDAAAAICBQfgAAAAAEBMoPAAAAgIBA+QEAAAAQECg/AAAAAAIC5QcAAABAQPj/UN04f44T4pAAAAAASUVORK5CYII=",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"alphas = np.arange(0,1.1,0.1)\n",
"perplexities = [perplexity(InterpolatedLM(bigram,unigram,alpha),oov_test) \n",
" for alpha in alphas]\n",
"plt.plot(alphas,perplexities)"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Backoff \n",
"* When we have counts for an event, trust these counts and not the simpler model\n",
" * use $\\prob(\\text{bigly}|\\text{win})$ if you have seen $(\\text{win, bigly})$, not $\\prob(\\text{bigly})$\n",
"* **back-off** only when no counts for a given event are available."
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Stupid Backoff\n",
"Let \\\\(w\\\\) be a word and \\\\(h_{m}\\\\) an n-gram of length \\\\(m\\\\): \n",
"\n",
"$$\n",
"\\prob_{\\mbox{Stupid}}(w|h_{m}) = \n",
"\\begin{cases}\n",
"\\frac{\\counts{\\train}{h_{m},w}}{\\counts{\\train}{h_{m}}} &= \\mbox{if }\\counts{\\train}{h_{m},w} > 0 \\\\\\\\\n",
"\\prob_{\\mbox{Stupid}}(w|h_{m-1}) & \\mbox{otherwise}\n",
"\\end{cases}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"What is the problem with this model?"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1.0684727180010114"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stupid = StupidBackoff(bigram, unigram, 0.1)\n",
"sum([stupid.probability(word, 'the') for word in stupid.vocab])"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Discuss with your neighbour and enter your answer here:\n",
"## [tinyurl.com/diku-nlp-backoff](https://tinyurl.com/diku-nlp-backoff)\n",
"([Responses](https://docs.google.com/forms/d/1UMmtDqpzf7pXxWqqsgK7pH3sA5EVXXWzfRaXHe9LICM/edit#responses))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Solution\n",
"\n",
"The score is not a probability distribution (probabilities do not sum to 1). Sampling thus requires further normalisation."
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"run_control": {
"frozen": false,
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Exercise\n",
"\n",
"How can we check whether a language model provides a valid probability distribution? Solve [Task 2](../exercises/language_models.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Absolute Discounting\n",
"Recall that in test data, a constant probability mass is taken away for each non-zero count event. Can this be captured in a smoothing algorithm?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Yes: subtract (tunable) constant $d$ from each non-zero probability:\n",
"\n",
"$$\n",
"\\prob_{\\mbox{Absolute}}(w|h_{m}) = \n",
"\\begin{cases}\n",
"\\frac{\\counts{\\train}{h_{m},w}-d}{\\counts{\\train}{h_{m}}} &= \\mbox{if }\\counts{\\train}{h_{m},w} > 0 \\\\\\\\\n",
"\\alpha(h_{m-1})\\cdot\\prob_{\\mbox{Absolute}}(w|h_{m-1}) & \\mbox{otherwise}\n",
"\\end{cases}\n",
"$$\n",
"\n",
"$\\alpha(h_{m-1})$ is a normaliser"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Unigram Backoff\n",
"\n",
"Assume, for example:\n",
"* *Mos Def* is a rapper name that appears often in the data\n",
"* *glasses* appears slightly less often\n",
"* neither *Def* nor *glasses* have been seen in the context of the word *reading*"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Then the final-backoff unigram model might assign a higher probability to\n",
"\n",
"> I can't see without my reading Def\n",
"\n",
"than\n",
"\n",
"> I can't see without my reading glasses\n",
"\n",
"because $\\prob(\\text{Def}) > \\prob(\\text{glasses})$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"But *Def* never follows anything but *Mos*, and we can determine this by looking at the training data!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Kneser Ney Smoothing\n",
"\n",
"Absolute Discounting, but as final backoff probability, use the probability that a word appears after (any) word in the training set: \n",
"\n",
"$$\n",
"\\prob_{\\mbox{KN}}(w) = \\frac{\\left|\\{w_{-1}:\\counts{\\train}{w_{-1},w}> 1\\} \\right|}\n",
"{\\sum_{w'}\\left|\\{w_{-1}:\\counts{\\train}{w_{-1},w'}\\} > 1 \\right|} \n",
"$$\n",
"\n",
"This is the *continuation probability*"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Modified Kneser Ney Smoothing\n",
"\n",
"Rather than using a single discount $d$:\n",
" use three different discounts $d_1$, $d_2$, $d_3$\n",
" for 1-grams, 2-grams and n-grams with count 3 or more\n",
"\n",
"See [Chen and Goodman 1998, p. 19](https://dash.harvard.edu/bitstream/handle/1/25104739/tr-10-98.pdf?sequence=1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"### Interpolation vs. Backoff\n",
"\n",
"* Both combine information from higher- and lower-order models, e.g. 2-gram and 1-gram\n",
"* Both use lower-order models to determine probability of n-grams with zero counts\n",
"* Difference: \n",
" * Interpolated models use lower-order models also for n-grams with **non-zero** counts\n",
" * Backoff models only do it for n-grams with **zero** counts"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Summary\n",
"\n",
"* LMs model probability of sequences of words \n",
"* Defined in terms of \"next-word\" distributions conditioned on history\n",
"* N-gram models truncate history representation\n",
"* Often trained by maximising log-likelihood of training data and ...\n",
"* smoothing to deal with sparsity"
]
},
{
"cell_type": "markdown",
"metadata": {
"hideCode": false,
"hidePrompt": false,
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Background Reading\n",
"\n",
"* Jurafsky & Martin, [Speech and Language Processing (Third Edition)](https://web.stanford.edu/~jurafsky/slp3/ed3book.pdf): Chapter 3, N-Gram Language Models.\n",
"* Bill MacCartney, Stanford NLP Lunch Tutorial: [Smoothing](http://nlp.stanford.edu/~wcmac/papers/20050421-smoothing-tutorial.pdf)\n",
"* Chen, Stanley F. and Joshua Goodman. 1998. [An Empirical Study of Smoothing Techniques for Language Modeling.](https://dash.harvard.edu/bitstream/handle/1/25104739/tr-10-98.pdf?sequence=1) Harvard Computer Science Group Technical Report TR-10-98.\n",
"* [Sampling from language models](https://towardsdatascience.com/how-to-sample-from-language-models-682bceb97277), a practical guide\n",
"* [Interpretation of Perplexity](https://towardsdatascience.com/perplexity-in-language-models-87a196019a94)"
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"hide_code_all_hidden": false,
"hide_input": false,
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 1
}
| word | train count | MLE | Laplace | Same Denominator |
|---|---|---|---|---|
| smally | 0 | 0/3 | 1/6 | 0.5/3 |
| bigly | 1 | 1/3 | 2/6 | 1/3 |
| tremendously | 2 | 2/3 | 3/6 | 1.5/3 |