{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%%bash\n", "DATASETS_DIR=\"utils/datasets\"\n", "mkdir -p $DATASETS_DIR\n", "cd $DATASETS_DIR\n", "\n", "# Get Stanford Sentiment Treebank\n", "if hash wget 2>/dev/null; then\n", " wget http://nlp.stanford.edu/~socherr/stanfordSentimentTreebank.zip\n", "else\n", " curl -L http://nlp.stanford.edu/~socherr/stanfordSentimentTreebank.zip -o stanfordSentimentTreebank.zip\n", "fi\n", "unzip stanfordSentimentTreebank.zip\n", "rm stanfordSentimentTreebank.zip" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# word2vec using `numpy`\n", "\n", "In this notebook, I'll walk you through how to implement the popular and flexible word2vec model using `numpy`.\n", "\n", "As well as showing how word2vec works, I also want to present to you a workflow that facilitates experimentation and ease of use that we'll carry through into all of our lessons on neural nets and deep learning. There are off-the-shelf implementations of this algorithm, but writing our own will help us better understand it, `numpy` and Python programming more generally.\n", "\n", "* First, we'll need to work with the unique challenges of text data. We will develop some Python helper objects that will help us to convert our textual sources into tensors which can be mathematically manipulated.\n", "* Next, we'll examine the word2vec Continuous Bag of Words (CBoW) and Skipgram architectures and how they work. In doing, we'll build out the `numpy` modules needed to turn these architectures from theory to practice.\n", "* Last, we'll create a standard training loop which we can alter and experiment with.\n", "\n", "The learning objectives for this notebook are as follows:\n", "* Understand the advantages and disadvantages to neural approaches in NLP, and how this relates to our previous use of word2vec.\n", "* Train and interpret their own word2vec model using a non-English language.\n", "* Study the basics of the mathematical underpinnings of deep learning including backpropagation.\n", "* Learn the ways to efficiently run deep learning models.\n", "\n", "## Motivation\n", "\n", "Before we dive into how it works, let's first take a look at what the goal of word2vec is. As the name implies, this very simple neural net seeks to transform words into numbers. A **vector**, in this sense, refers to a list of numbers whose values represent the meaning of a given word.\n", "\n", "This probably sounds a little funky... Why do we need to convert words we know the meaning of into list of numbers whose meaning is hard to grasp? Ultimately, we want to give our computer a way of understanding text it hasn't seen before and unlike us a computer can't use text to learn meaning. *It can only use numbers*. What we really want is a some black-box that we can give a word and it will spit out the meaning of that word to the computer, a list of numbers. In fact, we want to *model* word meaning. This is what word2vec does.\n", "\n", "As we will see, each unique word in our text will have an associated vector attached to it. This vector can be manipulated like any other vector, allowing us to apply complex mathematical operations to word meaning and sense.\n", "\n", "In deep learning, this is called *feature extraction* because we are teaching a model how to extract the linguistic features from a word (though it could be anything, including images or audio). Feature extraction is rarely the end point in analysis. Instead, we can use these extracted features as the inputs to another model which will do some analysis. Before we get there though, let's look at how we can harness the power of word2vec.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dataset\n", "\n", "For this example, we will be using the Stanford Sentiment Treebank. This dataset has a lot of excerpts from English newspapers. They have been marked for sentiment value by human annotators, but we won't be using that data for this lesson. Let's take a look at what some of the data looks like. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "path = \"utils/datasets/stanfordSentimentTreebank\"\n", "with open(f\"{path}/datasetSentences.txt\", \"r\") as f:\n", " sentences = f.readlines()\n", "\n", "for sentence in sentences[:6]:\n", " print(sentence)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These sources are in English (obviously), but the word2vec method is not tied to a particular language or dialect. What makes this framework so successful is that it is flexible and not language dependent. To that end, you will be apply this framework to a non-English language of your choice for your assignment." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Tokenization\n", "\n", "We need to do some processing to make this sentences usable and then we need to do some tokenization. We've talked a bit about tokenization before, but in this case we need to do it ourselves. We'll also need to skip the first line because it is just the column headings.\n", "\n", "In the data below, we used \"whitespace tokenization\", that is, we split the sentence up on the space character (the default value for `.split` is `\" \"`). This strategy is very easy and works well for English, but may not work as well for other languages. We'll revisit multi-lingual tokenization later." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"Before Tokenization: \", sentences[6])\n", "print(\n", " \"After Tokenization: \", sentences[6].strip().split()[1:]\n", ") # \"whitespace tokenization\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "path = \"utils/datasets/stanfordSentimentTreebank\"\n", "\n", "\n", "def get_sentences():\n", " sentences = []\n", " with open(f\"{path}/datasetSentences.txt\", \"r\") as f:\n", " first = True\n", " for line in f:\n", " if first:\n", " first = False\n", " continue\n", " split = line.strip().split()[1:]\n", " sentences += [[w.lower() for w in split]]\n", " sent_lens = np.array([len(s) for s in sentences])\n", " cum_sent_lens = np.cumsum(sent_lens)\n", " return sentences, sent_lens, cum_sent_lens\n", "\n", "\n", "sentences, sent_lens, cum_sent_lens = get_sentences()\n", "\n", "for sent in sentences[:3]:\n", " print(sent)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "len(sentences), len(sentences[0]) # a list of list of strings (word/tokens)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Creating our training dataset: Collation\n", "\n", "We have done a good job in getting our data from the downloaded files and then tokenizing them, but unfortunately our dataset is far from usable to train a model. As I mentioned above, computers can't work directly with string or text data. Instead we will somehow need to convert our text into numbers, and not just that, we'll also need to arrange these numbers so that all of the lists of words are the same length. This means that even though we have a bunch of different sentences with different sizes, we need to standardize them to a single size. This process is called **collation**.\n", "\n", "This size experts call `block_size` or `context_size` or `context_window`. You can think about it as the memory of the model. When the model is making predictions about what word will come next, it will only be able to use this context. As a result, we want `block_size` to be as high as possible, but we are limited by computational resources.\n", "\n", "We will choose an arbitrary word as a *center* word. Then get all `block_size` words before and after the center word. From the `block_size` context, we want our model to predict the center word. This is how the model will learn (more on this in a bit). We will end up comparing the correct center word and the predicted center word and adjusting our model according to how similar or dissimilar they are.\n", "\n", "\n", "Below is a diagram of this process using a `block_size` size of 2 (taken from: http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/).\n", "\n", "![training_data.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAA3YAAAIRCAMAAAFG8u9/AAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAADkUExURQAAAEFwmyE4TU2DtEl9rEFxnEV3pS0tLXp6ehsuPwAAAMjIyAAAAAAAABUkMQAAAEJwmwAAABAbJj1njg8PD1xcXKqqqliX0EFwnD9vmkJxnTs7OwAAACxKZgAAAAAAAIqKij90nz9vmwAAAEp/rtjY2P///0d6pwAAAAAAAAAAAAAAAAAAAB0dHQAAAAAAAAAAAAAAAGxsbLm5uQAAAAAAAAoSGDdegQAAADFUcwUJDQAAAAAAAEtLSwAAAFub1QAAAAAAAEFxm5ubm+jo6AAAACdCWlONwgAAAEh8qgAAAAAAAMNWCuwAAABMdFJOUwCf///////////L/7hk/+7/Rv///////9cwcP/w/3Yi/xhA0v////8XWLTiJ/9VlsQv//9KN///k///3HX/o/88/4D//4X//2f/qBM/t5u1AAAACXBIWXMAABcRAAAXEQHKJvM/AABWlElEQVR4Xu29DWPauLf169u5c0Ib0jSdpOd/Hyj0PLmhkJeSNk3bKU2CnsJ0bvv9v89da+/tNzBgCCFA9y/ElmVZtry9JFmW5chxCgg2nwtu1I3CflfdP+eIJCR7LL/Re5kGm0cNnTlR9MzmKyNEjTmMfW9CeNbl/vCfXji/CXdKKybYHFiI5TJtfxNP/a3NlSkWGl8lewvj+8Ocq08lELc74LxtERzIPETXdEfRNy79iYg4h39fdhSi5oT9rcn53BSS8xmFbke9nC3BrkW7TCFF80iwcMvCYrW9rWB/oVVp7bTuwh8hIJ8JoRVqtcOa6DBUuD8UKcPrEA1xdQPmZSHau+S2x/SJovODqC5xxYSG6IEunWWQNEj6njN5Ly19hzKX/TFTC21ETt5xch0dyP6Ms+Po3JwKCj9qD3+sauVhtID7Eh76fPIcTcXCzUNP0ldF3P2o2jfPB6TXiUIzQk7Go+1XzXd7yFwlK0kcL07dZ9OLhwfGVJ0QTPfAfBJsi/thcSVk9zeS19gWoHR9cByJKRNxvD/MuXgjngxwxf1Nqw+y6vU/4uD12evijhEZ6KggNL6UxzyfI9gW6wfPZ7WH89mPeubl3IPQiXq4oUYBuJpWjW3PpFGs88oM8j9X7rMYVt42UJFJaoa/GVb5K8Ays0ymbpvcC4sKsZoHGMlFl7Q/3YFFtZz9ZW6iJ9XPEM2AcQ1sf7eYZ/aHfZ1k9yeNIzHXbXPEIH/B5pTDROlbVCs4n4pFtZz99VecoTG/Rl03V9HeKjLpQiofHJxP3PXJ9bnQ/eNCrPK2L0nUah5a4HyK2VZ2LoFWBP2hjOOQ0Oij8lMtnZ+hovoMYRGe0/esOdmaUgTb337prULE/Smyr7n293uwolPyS6Y0/UpuV7APsTfAdWaP038TrLklqVtmsBDLBfv7nN/flc1n7m/2lVBQNwt87BDuQo272cFf66pmjWZxhLhXGF7KE416dBDszgHr1E+hLw77T13CalwyUskerfEm5zNJVoKFELKPN8pSWKl/cPutpkqP091ljWm2jZfN6vf4W2EXpl6lRJdTlnz+V7+/WuvDEfb3gjtDXiPCP2nVcCChdRNqgXnHeWBewmaId9h/uL1lBnBprfRn0VncbP8fnUk7HcAd4Kjoub/WBfb35O3d3dtP2N8H7O9Cko1M52gX+3uH/Oz4nI9rb6Nr5lya2yA/2+NT1vOofax7jvRxALTH2pX+jbDy8zkTCzgXHWbYuKfmdMkHXIicyNDvRJ0xAzoLYBfmtjYvrRGm9xSTPdDlNIBtcT8Q3XeLT9GMlOjy5P2VE/JIKMk/EWdSH7x78fzuqe5PdiU1t0qtdYj9zawP/rcuseKp+5FumVmSw4/rg7IrQZc1AA5q/vMp+xpL3wi2M6DLaQDbYm5Gk/gA9OP2M7hWl4HanrYwl2kwVbw7CtYvxbkXkED6CGkFguhiH7qXfmPBKtBmo1W/Qiw3S1nG6bGogHkAzUWXvj+pnFtUIH10yS4+0/ZX0Ibwv2w+DWzWjlpXF4ip9gb7qx9E7Wt2K+f+nmjLRaV2hNVvrk5YbiX7uz47lnuYKDo90KIw3l9VXn/QFpFC5MAF8wByOpd/PgWLCpgHeMj9LZnQ44OjgBPa2dr8epU3Rnr3t/qifVuNZ0XQGirHcRynAGRazLcaUR83QSHio+iuZWRLYz/6aa5R0h09UK6JaH9hwk7IvFmQ7rNL31Xo/uLrtRYvZ9ynOGVWfbDkFfBs2XWIEJCaMIw+Bu23I1eMJe8jF/i3uvRtL/s23wa673mhyJXyMbxXZ/QL065dRRtPn7lKRuU65XzrcHET61RgjN8xZxqRM9jG68/2Jy88v7t7/c/dk5eSvHB1giQxUUEefsB1xecgtdbhCTxq0oaG7UI0PIUCpF2Jzz2wfH7N8q4+pFebusffuyjI+2wBs9u96DJ+uhwdHzAOyx3OzqODs6hdzykq6T8j6BspGjx0OGv0QlNu1KdA68mrxHefzHpHrV0+P2ntti74TAdefCZOLlrhUBLO5EXR8IBPxCWWg+jdKTzCZfs4OpdXjzlBut5dxy1w10jSQdzKxlk92sNU31M+P4uO29HxOZIsy8Jo8nD7z/b2KuopncCUskgokbwUOfY8BV6bdHEuhG28SrqpofKtONvRphNYd9YT2+XgNUhsv9npRp0Zl6fjOI9BPt+38iFLYcGQ5TGy0dLo0cd9QSxJWRAg7kORI0l26eRl3sYf26Z0JGnAUpvwKKWS0mJtizWYuJ8L6mj8l+QxRPpGf2YGT+5GayaotWBat2oKOxYeICdPnhsymBWZCBewXqs88ebfYkf8SOy/426ABBuy2sIINA6dzij17DANRpp041HyAQrQ3ShW53ogFijAx5M3wlzJe3jiveUL89Uew0OAFMjFaXcN0qGTaWz0+it9f/HhmHxxbr71itmaVyTjizNpA2cNeyXvC6+KgotzW69Kh8wu1qz8y2HrhKIYLPLHZ/uTxwa/yofW0Y4c2VhDIKppfEHu+d3XP56jThqYXqwIrcoNVsuggAGVbiyf7LLeelhh8pbQEJi86SKgONeRaZpsdWFBLnmptFFMhunQKjX7spHRhsC7u3/UZHef7sJX7U/H1LQqVwxLFyrdr1C5roTaYKd1gtO0lIbA5MUaAWnDOqRFhoeSnl2Sl3ZmJm8qG35xPggW+TKZXCND2b75pTtEhiuyx46GqEnz4myw3sJadXNrqmZby3hr7UNI4NFAYpDCEFV7FJrknOx3XzTuq7MB5C7OTb9hR2Lkva+e9HvnxdmDV6Mv3wJobEl7RIakrMtZ0dlarMqYpdD0VvUUCuqcY15rcv3Y0WRZ7+SVqY7ZXQrgQ4M38SHhfyBH9kW+IKHjAauQkShN2xNNnj5kwQ2RuiR5uEN6s4s5fSx5yeMG7hH/x7gnSsdZvD4YecZw9//YIkGdE9mmjmyORMnbLr0569I8rJHnQXNZT+8c57Ee7/lSRseULIBRpTabHHERdjRZ5kqeMUfyHAUXZzXq8hGD3Al1UfmEu9/dkjpn3OZQJjNx1g1cnM2oKe0cfUzokBFGtkTWXVyebAVEydBn6xiEJ9/62Lq69FaibbjyxiqHw+91OYD79tCTznFVNo3hokTaNr/xz3Ecx3F+Q7apdjIOUsdxHVkn47QfNTgY9sM8JF09lgpWMelE6tRPGpWWRbChqMdJd7PUHcZI6qSSaYmS1I19rOt+9JA4vqgKeIngx9dXuYg0hfCr/ytevWQkzv3wM5+6ZY9N1pTYuQNx8DVdbfboRx91fw9ju0JwJ8sjWSqSOr5/n6SOSOqwtMrULRtmUu956Wn2hVnuygz/Rr/0E7yOMxl5bXU70JEGc2xRoxilHEIz+hieMd+qQu4cvSQW/aaz/wwTLc37koNFVRS9IaL3FsBUjaUObEPy9CJMUvcs/JIrU2oP28bm1hccB9hzcMOeeM9iY3RsyTLs6GfhqVsLNFVxj307+larIlPtpDHeewOpq6f9eViwliENNR4+G1sx2CZX0dSFGXuWRL3g2yNMYav1aoevkDBFlR2dt1o3r1php3XC4VhC5WiXqWMRGqK9PYmdRWp0Gerh4Posap9JvGcHe+EyXPPdZhlv2Ird5GiwBh57B/pCN85VaGfG6Bdy75kwdA9x8MEdJ4GlejRrmC5JHVKGBCJ5YpkaUmX9pGRKpEPRDcKIU47xEgcev3uNm5FLux/R1LEP1tk1jig2iqaMdQuF5wVb79nr6pe5lOlB5d7cZt8ONjPI9h04ql3GOOMppUaE1N39eM3UwU5XmrrKqzh13y+YpAv2IYN/nLo2e0TFyWtr6i4TA7SP2WPqWLqbkdtzpq6dLktwdUfHbelBxmnmEs0nDglB6hpVpIdfWeBrlnCVsl2MpmYmkroM+qLPIuS7jE2LJ94n53EXndR3ApYsw45+FjPiXB8sWYYd/SweI3UL7RM6XwDbeJU0JVdRp82VGRnLhqCpY2bC9Oi9XdTcluEEUtuxT1UjqnaQNPxmZJubQfy4IE6i4ziO48yB1RyV+BY9i63Kkbtbt4jWEjtExVNHNix1drhp6nCfDrg8khYBPof2cpOkrtw9QxpqPHzmlnwCaccN2doqZDP2LAd4xfYS/u7u/noZAtIG1+uXMsfq8VYjGT8vtL5/xwy7eJhWo/xAvqgtN3k70OvJDVgvqnKW3qUXIqnDgSKBMtAKeI5U6bB4tKAGGGk1Uq+rFl+2k2iW22r0p+w9/Yy5EDR1cPAOCLbrYXHGzR2PU1LXGlSYuqd/IWWSutd/xakbbzXiNgOO8YjkSTQP0WqUT1wTqeoiMUG+UCapQ4wzbu54nAlquzy2KoekLgaRrKjVqMBQM27u7BCVRVO3ttghKuuculiw5ip3Rw6d3xOL6OEJkqtUuzo6gn5CAj49vvorATaZNM/khLZD8mT4B/PaaLr6iiHKOyZSu2U2on6Pqdt42yFhSZ65+ab6vdhue6VFuaRz2xKbzzO3bSAnpK7XZx8qKWJRlQ64S5hxj7AxwErJxVmuouI4jrN07CZNyd23GXabl6MoXJa1KWrteBRPHdmw1Nnhpked9vHTNts88E9ba8FoaotTl/qOr880hU1AxjbKM/skytEkrbUFffyQmKd/3YWXd39wpOXw+slbpi7TWgsHllu1cBiudi9agwtJ3fJba3Eb3m2w81uzwTtyaTPhgGPTKmOSOhycttbKQr6Pn1pLvjv3FGHEKeHi1lqh0qpZlzlN3QO01vbit0D5FQyplEmEU5s09ZDi1tqCPn7Yy+dPTNKnu7sfbMWNUxe31goDTV1t0DrEDLtdemstWxc4+FbUY2e/Js8SUze9sV2OLUZtl0dPY57RcDpAegp3XY75+/jNhR2PsmjqRlnoSB4COx5lnVO3UJzMeZaPRb5MmhNb9XDnt/m36Eme2dM8s6Ej9SKnkQ7gG04v6iN1najTgRmRur6mDqUgP6Gw4YxcfCzwNv/pgbMFdCZch1tyefZYZeZokzoUKkAm00ibATebHnN/0OzCjJKmBhO4HakbqSwnF6RnnM7j0t3uSxCpY+cwVMWqcUL5YUre0epg5xtNWouGGTWnROoaSNgW1KKbqDMjGeykgoRqywNshtR1o8bGX7Vj5sl5bM0zWMfZMqzNZz6sHWwqFv/jUnSktipH7rmJhZuKbfe4eOrIY6Ru8erIgW06mjo++NA1eRZIHfYw7fgyD0cS/o/Nleb405CyCQ7RQT26ttRlnnAdxamTvX+rhzNxSuq+3v3N50KauvQJF58B6bMh8bixdxY0dfX4E0MJ8jmg8+hSng2dcwIKn3BJ6ljTDPKNC1Q1Q7NcHQWpe8cZjwdHlaTOXjdoM0nXUfsdBwaMU/ecacNPQl5p6rDZm9aJ+Axagxo/fyQwXUzdF8YmyFeATqM9SdCX6PKA6UYSM6nP246p01uBnqYONc75+oktqrvkIeUkbLtZxLYrImulxW541jlXuT+eOvIYqUu/taz3sDFb0iCR5CpVPvhp4u68V63KfBsQ27HfqfQNIJ1uNepvV2vtaH653U1lzvrD9yaVXO1rWzqAd+Q5OUCCAr/Rn3nWtflItqIVTOnw10M1Wpa3AdwBBZQAna5UnyV1SNxiNc71I7VS7BIhbovxtpoijW1JLYyEaq/XlQRJMqWnLR3bQZJn8qPuoRca29A9LKETVTnCA7+xKTS3KXVFKdki3TmO4ziO4ziO42wiDeulZIuGfs9B2aY2he3DjbO5iO3CvrhVc/z6DbXIt33YIaUR/oXHT/wzgIZbS5iF2NCopahKpvMgr8+uBjlymQwtIWI7PvWAW20HNwenDd21zkNnfXGpCOksNUKR33oiB5pMptlu7dO0H/b5eU/mHb8kr6AnJ5Kt7GPSbEQ9PkcN8cfTJU3hfRT9C0cvSPayObYrj9jw/XonrBtfYjxYcXCSODgTkm4p8LUaG5aG4r+NtvslScQ1uqawC8YznHdq5xczDjqkA4MYg+JrdkV+Kao7Woyfh69KP4BfW2g7x3Gc3x2WYDM/up5taHHWhXJWcdutJb204sgaGXuS9lld5q14n8Pnyz05G1twv8T7g+TOyFkDZKAbqf6bwjCXurPe56gvDKohYOJcJdt5LGgq+RR0k60SY7aD7uSGibrj3RNCQX7r3C7mKNvYvvC74LZznA1H6zqrwXbpLInc29UjFL2hPU65UMBtt2TcdpuL225zUdsFfvbgxehHOmZYxUbD0VA63sxUxHaLfxu2JHqFFF4nReMLjVAiCPmPzYvod6JOP5o9iIEc4r2u59hc8m0OLPx4e/cPXE9lESecNrmQ7w+LrcREXNjRIYKA2u6w1drFytoRx/zZxcJAgh3Jev08RHqwPENnUXR9HdmXO5QDfrCZa4fn0SlCXsIDAbBJOiAQXO2D6LotEWA9FqIDOGUoIaJnA9N3eqHId5+V2DCcX0d7GofsUvgC38voAN46CtGpDLqU8GeW/5psPeyatsNM3mbV42FrS4/f7MOvGvXZg0fWimtRRm0H9XGkKYFW4cBLb0Zsp9bCMowaL33AP8LKh3QQnpMP31uvsIz14puxHb+xQnPcwnoZUtvRAdupHziPhzyS8DivXJ345s6x7IBT+Ko7gfG1EYPMdaOzzNXD2C4ZOXeD1ee5ePO2+/N/zHcc7NR0l30Tmb6J7WRYh+XZrgiz0Yz8MA41kzQhE0i0Y8Q6eUim7SNvuyyTLScmyhN7jK0AM8/JNMrYbjrLs50zH267zcVtt3S6RfXMdOSicfyiXhdgCalnNvvdqCHVE2Jff5MKaLXT7PIzRo0mfLH+XhUWZ4mY7UbqmdRdj8v0gh1pO0yavB2Ux7XOGkArBVpHLBUa+l32rnQPpuGqMgqaWlFtNy0/dVYKDTQXubH7HMdxHMdxHOeRsW5Aj4sdizMfU1ojpzV1ZijfnmnzMdx2i+G221zcdktnnuTcqxVaT2hgt4SrkbM7y3avdaYbTX+2LkhA7bqSZ6m208gKoyzxHL7so/opnY0KWyfT47FWTeNerdCxuaRLCRYGu3HXE7XdC/x/0u4stBUXZeEll8V6GkOZvkbJhGsuEGaX6+Fnx3Kw1n2NynY2wq7xgwX5lhb+xDxpfUxt15NGzC4HuFgcPfOp7SAg6UEExHbsMPb3iO1MkK+1V5LGUKavUTLhR/IY6AjWA3G6UtutY1+jsp2NsFP+mrBPn7br9sUzPhZd3bPeK0V9WEqjZ76QJM8Ug01kSgx5JgaMk7U5fY2mdjYSKRXknEVlW5z0hShju+ksz3bOfLjtNhe33bJhJ4YxkiRO65vCrhLOYwIz8ZfUMxtSV2myowPgS8vwbUoNU1YH2KxftWXnUVHbpfcIYrTQj20H3UmlswF5hohWgznpK8GdR0Wr/UV36HKnN4V73TA4juNsJrlmLivC0pIsV6Z5AbdewB6NBjuwW10FlRV2iI7NhDlqlvzwIiqgXsKtF2KcTD1TjMbB/BRt4GQg6PNeTdHO0mENMwRMu4GfguZCQ2aciNU6fKogzxNm1TydFSMmKrpHGOdej14dx3Ec57fAerduBHbIjjHt+Z3NZ1DyMd+UB31ld2SH7Bhuu83Fbbe56Hkr7ltr80nE4/iJYab3JRMkvsK+tTafQTnbaajCsCX6nZXtmjalb22/o49bp4HDyxzhzOATiM9b3D8z27eWXuzvPGMcPzHM17u7t7Df8yd3PzgW4N3bH9Kn8wlMJh1xgcQnE0aQ7VvLCUDkjLHWqpzgAHA9wUM750qPT0ntRvSt7XVsZBVYpdNodtl2KeOrxG1gWCVr+w02aS7aqhmft9h22b61nJQYx08MYwM3ynCAf+vkn893f2EZ68U3Y7vRvrWcgNR2dEheoDtsnZxggtRuSN9amAxWkbZoPi3vNWEdUWPDWsrgj19X+7Lc23YFJKv0/E1CbVeCibuKVwxsHiPXU8qIJZbDtExyxHZZpvStnfFcpyCDvG+eWcCUVVmWZ7sZPIjtNhm33ebitls6HCisNB0t6+SRkT+IfWxwifGj3lpjYd8GFICoeKLKYk9fJUyQgeGkpol5s9vsWNXGeUTUaqg7mjFopA7ft4Ov1TOpssR2OlScfOTJbffIwDCwC/I/2oT9HcQmYijaTuwDCWIp8AOGuMMLgRuFhe8VnKVRTj2w3SguO8dZGHt9ZBr8pmiCy21tgOFQ3mHaZd8+FGkoy/Br9OHLIhDwOTJLOZpN6qHOegB7wHD5eqaM6Q3ftD2TBqPlWD0xizqPDnUnd3IwCe684YDi+Oqk2o7mFKtFfa5ECNfd+iDWmUTByqnhHccpxX105Hfnj4q0qyyMZ6CPCc4+bIeKiNUzq1jssbKpdRWBi5j0G/aTJTGb1zkfE9qhw94MMAPMhVpkl18RFTXmbCfDOyS2o+WwkRjQeSymllkdsd6oulKLue4cx3EcZ/3QN7SWgMXnTOtClqX0GZvYoazcjmaHctsluO02F7fdRiClxcHITX3RyZI3fwxz60ZT+u7HiO1eF7zsZTuaYZyStqvrvmQ6wrR3D4wSQYTpY31P7fBlhyazwsOckzMe9HkUbvnaU/s2OuDbT3qyblqvjkbeAxp8aF1hJZb5Cpbu/8tem2ft8sv1UN6dwo8vR31DNENZA4fYiZMff9/98Vm+u/BE/BgpSN8D2tm9GFy0aheDwU6rdbE74ItDGgoHgh/3C7+LE65vXe2+4ScZ9Ej0cMI3GhHH8i59z0cNE97J4eBawyLf4dKDA8fn7TP46Q8Lt1PfA/pf5jsGDqDT4cPWwAetZp1Ol9/HxoJ27oN9saq5pMeumi78p+qTk2XvUeVsZ+8/ViqZrxswnZpqeceKk8v2kCcG68U3Yzu+00X9PZEPLBTYjg59h0vhHiWUvIhHq9F8cjAgnsuR6OFgiiPKvHtH5DDq5/Janq07S1KrOcelmhKXHLiP7RhtkBGGBcy1sZK2q7JdLFRht6X0yESWuRftBSQF8b8LuGzhJyfkVeArjK3Dw5PQOmHWeoLLPuwM5GQG/sv2B6fhnUQTzqHgOs4QT0y9HV2G4TniZRiaCWD2OjyF7MJnLOdt17oIVwG7QeThe20Q+IZfpRZoUg01QADOdWkn3HCTEChEPZJ2HSm5RQ7ClHwL9T16klvuG9dUuL0M0YEu4KBknXJWP0fBcRDO2oymLrarqxlHmZJndlVOIXRppG6nL/YJgcP2hY7orhrY1x2/B2u9jE8pUmmuQrKpn4pIrgiJPoiBslwFNZMx9SCE0keSYAYsghfzYkyIUt+TzPNg44nNPlnCkmw3k4ew3dbitlsMHMaYnKdljg9x2CwSNgs78MeF9UiUZ73Q40NXlH4E5RuOrgf/KhwoD/HrN+CrT2ed9QA2SuqZzfhyou6sfsJ/1Fj46By+/BaJP29dF1RJ8tZkkxOpZ1blTg8/3PchAP/xU9u57taHWGsGTTWVkfCO4yzAfDpy1a0R1q5SGq+prA8QktUze1G1ao0paWOm/tiQaQ3VLrz1QW0HNUmfWbPMmO1kSf4thLMOjDwbENvEHaJj0gcIo2scx3F+K/rSWFkCr2CuHSjfrK4ig9WqJ2YygG2jyUewcXOns2ao7WiYXtRr2NNVLlbtj3Dqtls7RjPMouflgknScRzHcRzHcRzHcRzHcRzHcRzHcZwHw14nyz9YbWQX468kOGuIG2dzcdttLmK70OfQDsw9scSxOhrVfc1K+Vk1rpVvkjCA23p9UNuF97rE7utiu/AvfH/in7aDRwf/z3pR1N3XgM4aoLZLxJTYDu4qJqo7XUE3bbiudJktmLsUko9scE6SsZ0kZIrtOqH5S/LO9eRX+IUDt4WyMH2jFPmtJanteswOp9mu19gPa/y6OY97brbEdjIEB9I/Oc9EGbjOsHwmP5l/UINJIlgVw2LQJEruYoidevB5BjfWPtuX7EfyobUntV0Tx7yPVE20nVREuWJNgVU4HGOHdnuWSwSrYr84oYWw9meSCqZPPqwZPjKEjFMi9twypDK6xgWe1FZwhCIaOFLb0cc+fTqUmbqBXJsf4agiDATLrGUrbSeT9c44YSY99cgs8rajQ2a53ENsJ+gNbOy3bTxjEpHrrDM4+1rswQp521k+qbpLENvFl+Ozfdl2G2235lSRpTdhBzEZy7uP+H+f5KJNLe+k2Iv4L9BOpkiExQ+lYVzncVbGkNkCrcRqo5iDc1pSfOXWHTVJVjdD0jokGmP7H0xKdw/B//WGP8dxHMfZLKwe5qwV+ca9Sbjt1hE2Vc5+NOC2W0fKWcVtt47ETVzMOnHfGgXewP7Cvao8y/uFBXuoJ+2A4gaYOY/Oe22DFWgSeYzFB6xsOZKHYLLAgpFrh9rg5KwHDbEQYdlHy0ijrbTRSnsRxAYPeTIGw3XkYZ6zJjAPlBY9s51IK7GdtMMzENHHzvR21gJYR58cF9qO9qLt0rb1ZvARUNeAxkf2Bfgp4no/bjs4fpmvlnO/2GlA+0A4j8xHywg1SxyzHSudYiz8y4PXf+VBS/IAxVlbvGDbXNx2m4vbznEcx3Gc3wXeHa4K26WzJCZ+t5os69vVittuybjtNhe33ebitttc3Habi9tuc8nZLrwwh1FglYzXRU3n9KqUMKDabhjqbXGMMTwwxxIouk4upX/IdJZxfWlHIz7Bm4DupM9W6Xu9rKy2g81e38E523ZZMrYrIz495HcyfUDkCii+DGbbbnYI5X9sXgTSid8U2yliu3sZb8R2n75i6UcIr8VbDLITrkIlVFo1LF0F8RpchO/fabsLLopX2A07nFVehUGrdRSO4MYK/IeBrIEbu9vTe/T2WcDZhSu9YdcVZ5d8Afbssr53eRaF4alI5TbcnmogMAxwh7Anm16GS3iF0K7v6droXOM5aNfPsHQdQvZaEct8CceYMtiBxJEewjDcMoTudBiGEnkxf04xXo+Rc1qVYRzMtxm6gV+9sw8uB/0Ks2lwMZI8U6z1FPZSpyzSKhcwFeYVk5kYCgstsR0sZF5ht9U6xBz/u+ZgqNaH1hVCvqFTD1MU8Q3mg+MsuhU/gwFwunDm6pjTuPAYyhaJ7Xg6YRWsgbVoBJooXEfXXCnIDg6wh7q4uZ8YsZ3OsRm3RiSJgbgW8TJCXEG6kOHPPBONp18uj3pNWIpue90TXqntGHO/gSDiWpS87aA/ePCaFH9a5YpnPW87epGdG5mp7fD/Cv9iME7wf3JzNDiR0OKrh8lTiRMrp3bkyLmktrvEHwLaCbyl1AyeaazBOcf2cqDwyEUjtuIkRAdcn9jGbHcZjmVOG3HyhXPCWLCGm17KQi7a6E+ekYT/+o95j8G8EFsiz2w0begYoBbN2U5HQZC1i1Fku8/iAWgQnvYR2+0iVyS1XYgtYzszWatFm+K/cnGIxQLbiUhgj1s9gTEMkLMdTztNnEkiF2n6y/Z56ps7ARnbnSNMFrsWZE7Vgb1U+YwaB8XY67KQi3ZEdxNNl+iOtuuk75TAbKO6Y7++/D7mo8h2Tz7f/cFyT2z34URKtYvWK+aEaqjDwaAGs9Va32lFtd1h6ztzRrHS7vfWd+ahu6+wrsB20XGb546nLWs8BqhH1/Ay2335RlVcDqN2cobbyENZtt1ywzaMS0nmTsBxtHdstouO30XXqWbVZufndcxpOi6igE24jb4h8N5BNGxzj7eM9jIXd8Jk04nVsJHYjg4p1uhVRRnXZWc+FIbNqLvE8q4IsQrPus2Lmb42ZeZhjgXgyX1gpu1iwfM6tlnsURSflYYLsUa2ayclT8wKbJfLtPNcL7h7FmNZkt5FBSdgNOxclLLddJamO2c+3Habi9tuc3HbLZ3mvOPQ6h3g/Ljtlg7Sid+oQaakvrlgX2m2PKwK2+W2M7ftpq5zVom0oHDwOjFi116sC7wV5zt5uC+3VZx37FbeWQey7ZkdGM4EKKbinTgc3Waj2ew3tclFf846kGuLTt9mFS/ajiv6UbcbdTWg226NsDyTtmO7tCEmMt3xh/zSXPJz1gJYosFnr2yL7piBMGFZR9uJzaIqdKdGjgM4a8CYJWY1Wi56j+AsnZXdmzuO4ziO4ziO4ziO4ziO4zjOQ2PdgB4ZOxhnLqZ10Jva/y+ldB8/m4/jtlsIt93m4rbbXNx2m4vbbnNx2y2defqr3CvluRMa4hEclCLbZfw+Pdc5oyg1rpFMK+HQhhpI0RRsy7hGuTia2pEo7WRb1d63Rn/efklZ9ITCZhWe29m2y5Kx3RRRJWgQDuQxyjLOWIJcAcWXwWzblX5NecrYOEWpmWS7e10sI7a74GAOgxB0YAYxzcvwIrwOr++eY/GFjrvy41P4/Jm2+8RFtV2JcY3w/5134jIwEnbJlboxD0Ru0TdlXKNpAxtJl1nEinjhrHLeb/T71pOPtpM3TKoyCkSy8wWQc0fEWjdyhunkv9jpE8eokiE8RGbix/E8xHZPxItblhnXiBOVNpYHcFzowEix7jjD6cKZW8dxjcoObARV6SsJ2FxsR6M1OnEnTNOdmFR/C5O3HcWAH8GS2OkFrZO3Hb3Iy6cyU9vhf9a4RpzIopiSBlavcdut47hGZQc2gmU4JM6I7aA1JWs7MLKPubCzl7MdhCIkGhux3dsfdMHj7VvOJApOzGQTxzXiRBZlOCQEOOJoZcASwFnOdjztHGAok0QuPs64RqUHNhKDNeWNBMSgRmr0G9az/YFtd/S9dSKqoGX++UNKtU93f+lQR5x8/fHjOcz2/O4zrai2KzGuESey2NoZtFAGMsMU41kCONuQcY2mDWyELboBtkO2AHvBVsgbOBJVEyUcV3NEI/VGBWZC9KVIbFeA2IkkjkKmRZFlcjhLwFg6eHIfmGm7WPC86mYFGxd4LeEeoZgV225bxjXSe/Nyhi8XagKlbDedZdnOmRO33ebitttc3HZLJ/ea61h75rS0znpBdgS33dIpSk052815HqRp4tGxg9kOoLRO6KTtKvH9na4N/dDArQGHr5XhcvjrRQiP2mncbuY8Ejo2O+7NY9vRaGmbmJiKS/jhLr0f9WwAaS7LzbvzaBS3Z1JWAnwbfbaswAEzV6N+FeUcFhAszVmdRwEGUdPkbJfVXbdptsOM+aZYmsFcd48NjADDoYzrsFFT8syOlHfSnhlQuIlxux2u6SIcZmo7Wtl5TGCHZJqjwCvPzADOA6N3aeN2mN0Hac77O8dxHMd5ROboW+uVkzUjZ5Cxtujc/fe9Hps7y6dITKnFcLuewYW3XrD1mffmsEvcnpnvW9tgG3RfVrjt1or+zL61Ykz5HKzbbr2AWWb0rYWz2ZWmMLfdmiEGm9a3Fh7dZhRYjXHbrRc0zeS+tViGhzyKlS+UOOuE2qPAKuNefo+wZszRt9Zl5ziO4ziO4ziO4zibjL3MsRHYITvG1He4bD6Dkq96TXnXq9yO3HYjuO02F7fd5uK221zcdpuL225zyZ220XFrbZ4l43dR0zlt97qEAXXTwnFrZVrJ732MeWxXFHZV49Z2y71Ix84PSmPBVyb1tOGsFY1ba/NJZGw3Y9gqQaMrHLfW5tMpeV6TcfzGmW270sNQTR+3dpbt2O8otV3WOQ8jtsuPW8tJaydchQo8alyv48wOLsL377TdBRfVdm/DS85e/xV+3N09CU/gxgr8hx+yRm03Ydxa/ssKaLkSMD38XrtohcqNHMhROOKojmq79R+3Fobr9RixjAjAf/tV4131Q6jakk7Ed27k3BGx1si4tfS6oC1lWWQmflwptpNhZ812d3ccpBH/b83BkTfv/rl78fnu7m86dVci7dFxa2UqM+wEsR9iTuPCoyJbJLbj6YRV4F7XcWs5zgO2DPIeuXTjC/JWggwIYFFSd3Dy9eWM77zYaVN72PniNUl/WcczB0fWdvQiOzyj8BLD4P8v/IvBOMH/H0+f/PhDRrkVX4lONh4btzadqe1qajseEzyPguxIUsgzDWus97i1scnM3Wh2m83YV7A8E2EkASM7KoudtpztknFrObHzl7XdrlU2arsyAG1iOzPZ3R3HIsb/609fsVhgu7Fxa2Uqs5ztuEeaWFdJCtd/3FrqLrGdarAb+Cu0nSya77zYacvZLhm3ll4fTqRUu2i9krMofoeDQQ3nv9b6Tiuq7b7efWbOKFZ6+/nuM/PQt39hXYHtxsat5URnh61deJntPrxpfcBCpTVgUEnhBoxbSxP19VUR/DdpI+SXmIntunwjiJ3exXbVTsai82KnrZBk3bRAWEvDlGByLLZmLIBcTwkLpnA6tN8kFj2lNi8GphqjyK8E08ySrJsWCGvNNrOYHIuuGUBjeVZgOyn1ill03FpmiJNBuTfK/e7viplusoSl6W4GD2K7TcZtt7m47TYXt93Smecbajk6c5Z7brulg+Oco+JoqZLZnCnkjf2mYIe87sxnO2MR2zlLhzfd/WbPmqF1AFuxZ2iynUWCcNgHbYCRu3eGQRBs6Twm2fZMbZeush2l31dfQUwZ205EKrlKbtwcZ/VkbdcRd7PTizpxm5iQs534ue3WAmmoNJuouXqageZshx/0SNvpcLbq4TwuNIKWdcg0RU+hE/ViNUpbdBRgToQS3cGuHH5YC0bnUZlugXgtbDeG2+6xKXdvXmC7ee/NHcdxHOcRkdu2GUj101j00auzfGCWWbbLfzzGb+vWBhhudt/aBtZ0o2rf7uSdtUDbMPGb1rdWRl9s8JbcbbdGlOpbqyNnVuVDeG67tUGbmM12qsHxvrViO4QMXYjTPJ3Hhyaa0bcWttPB2rMZqfP4TDcFDDhKgZfzOCCfnALKvRH8/s5xHMfZRBbuW0u83vKooJ45ywKTq6Juu0elhO0mw7cqnUeDN+Mz+tYmHfxwB8+b+EaPzdKY+EOFR6VM39q0c6b+2DFTNkhCOI9Bmb61xbZj21kcwnkUmGfyRyuoucb61sJlHWv116iKMbngeeZjQgPYI9dJfWtpu7hjLX+NvmyAf6+rPCq01mRkLWyXI30RYXSNs1Jm35vzgVAOt53jOI7jOI7jOI7zyNjYN/fGonOWd0pnY6NOTWdmKLddStnxxCz4LCaPO+a2Wzpuu83Fbbe5uO02F7fd5uK2W4g5+tYu44jl4yuISL7pkVB0srJ+8qESO2UljkJtp991yqORzvyGms0noscgXwbKJyRm9qD5Cw6rnwOHMfVs6Ep2SYr6S+jhgKQOGeds22VZyHb8TMkoM60ilLSdpOHBbfenzQvAYZQ4G2K7MgFngWt1yE/gHLfPbzG9jk7b8JWT9eGktQNH9ntArZ0TfugFHvLlINl/qEd7/CrS8DI6ja4PogPEQf/j6OC4PZTv8mRs91x+b9/e3T3holmFM/0eUDgJR0et1tGb1odBa3DT+s59S6jBm9YJ9spvzLxq7VZar+RrMzsD+QYO92K2w373oujsvG3f/RHEMrfRN/2UENbz6zQHTKrwRb8pcx59S78pk8E+BBRjvuPE/cTwC2YiunsyLkBDutA2Med7r/wtAUkX0o3YmOvIt4x4svhtEDiytjuJv+XE82anjBPaTgzGySkie/cOZ4fnUiJPbQebycee3r4V043bLvctJ5hLkFC0EZaxBj9b0DV2IGY7/AfNPuWIlFhVmlba7ExTKsz8lpMca8z/O8l4tBa2hJ3YL8ziiDvZqu3o2W9wOrKLBcnYLv56lZwSFkJwZG0Xl0vBvqIlYfGfWIkT/L8L9XcZ39R28jk8fiTvqVhxou3susHVQoGLiwfB/X+n9HT/tsYOJGs7cWbgYXzZi845vxbDYiH5Vhc3xxpuVPwNtTzmO4bajr3XKUDrO6SeK7Bd/I0cOSU4P/x24QfklHJ+OOGHe+TKVy8Ji1PBa1WioQP/l19uLwttR+P9gOOJZJs52+nnucx29KjodwvtX2xHk8kHKeMPCMXbcy8RLpdzs11Wc4SHAV9+6KdtOeaZbkRsLVOffrvwXbo+x5TyjiazX6PTsxeSqUEZ3iG1XV/87s9Qqpn43ws49tNwmZR38s1QfuzziF/xJDDmRUBWdRF/M1S2v+anOPe4Hou3gZ+VQ0waqeYctN0TrP8Ew30KMB0/KMp51na74aYSLsJJrYa9Vo5oops3Ib1sWhX9kCG/tIYMMxxCkXpQse2+8OCxRzmGY35h1GCw26gd6ufhXBZon72MNvnNUMSRfjMUs0m2mwK24EZMtPwkhoaNctTR1xKkIKxybJwHwk5pfNYmUXb/qrsiLP6x3VBbKdOPAixyIuI8pogFT+zoZlZbKYpuGfcIxcQnyz7dO4nl2O4iyLcRs5icYh7Adia+Ii6ZAS3EpHvzgsOb/4jLMvNkKcux3WwewHbbi9tuc3HbbS5uu4XAnV0HtwJ5phzbg4xr5LZbCBzG+JFMOzbcEC4d3gNtFHbcjwzuveXeTm1oBxWqcMjYfql/0PFt4yDOo6NNl/rrdK1NTBer8Sr4yi8O56wH2nRJC7JxLM4P1XZw4L/b7Hc6UaffN8O57dYF1R2HPKW0YrsktoMnV/WiHmZuuzUD1lGDME+08Wuj0GnK0De2KsB25pKfsx6MmmKmaWBsZz1AnpllZHEcH7fWcRzH2UTmG7cWd3nO2lBY659c2ZxZDXVWR6HtJuO2WyMy7SXZvrXwbvSj0GxUm50OW6RD1OlHTXYec9YEbc+Uhi84YlWlnTP1B/9Ghx9y8lEX1wi13Ujf2iLbwWhNnTnrAk1mv7Rvbdqx1mzXZDg2XHueuUao4dJnrFwQl3WsVdv1A2WnYZx1YdQYUlsZ9UyX3XZrRNG9ObLIPInF/N7ccRzH2UxwZzfet7YAr6SsH7BJKbPgXsFZM3DzJvdtasPYjLYIg4mrH7xBZf0o7ltLm6mfTmA3BnTWisK+tfTsRY1+s0FRWluLrXPWhsK+tWyahrNKc3KZE9fd+iHZI398WpD0rRVrSlHXxAL9vLxbP8RWGUaXY+Ki0FkfRrLCiTnjJJs6juM4juM4juM4juM4juM4juM4juM4juM4juM4juM4juM4juM4zu/Gv3zLNGXfvIv4GMK/5swzcYXjOEW8bwgh9GQ+TT5QV/F7qBNXOI4zhZB8ycxxnBWRym4/9KPGfuj1UQGtPmPFs2pF2fsQPnL+L8L+avRCeDZrRRT1f+5L5TWEn+bjOI6Ryg6iCaHbgHLe7/9s9Pv9f6EjkVE/BBkZuBEgperHPsSpI/FNXNGB2ppQIiLs+2DdjjNCVnbhvTljquEZZ6m64hYUFIqcTVxh/rz58/GeF6DfRZbX6z7YufupFZEYr5Csmqzs0ru85rBqdUQuZdRlF0J1xoqe6pXmlbkzD0NI7t9+f9jLWGS5fJRmtC5MLg65U5jM+31vsF4yRbL7lzdpv+CYpa6JK1DKKc8YjTMXOKtDcz4ssflmUTacU5oi2SWuRWUHf110FgBnb3TwSal07v+MG6z+TR6z/rRqRaY9zEI/a1iO1xzinn3/pxkoS0ZOv/6F5eI2NNRRNDSKuWGEMlHxqujyKJIdTnS3GTXlfHN5btn9shpqtfpwtydbDOsK+7FqAE4qK51s4lKR4XzLPDEEjBe3h7E5a7+BKuq+2AYmeoY65HtIaawITWQHe+2jetNEvLID1HK5AovYtNlH7afb73vb2BLZD/GYsczZjF+4rWB2ablq+pxg3079zxkrnoX9j2wLhe39gfoCaJa3r6KAoOzsNk0WRbKL28OgOt0s+gXhph0aoLFRS8Sy+wVZiQfjERfWVBH3vko/kaez1jxLCk7Y0esmi9FkcyOUkr3orfpXJLv4jMc+CpZSRrUTx4zoUjQeqa/EUbrsNgPk1T9ZDL7n7YY3qiwKSiFIaER2LNTmkp25CsjIbvReAPUYlLZmOpfdptD5iWpq6CWNAM4CoE5JMaHgsesfHlJ3gE6kch/9wlkWRyo73IjFGkHVNK1yFhDLyfaTATvoULKqRpeds/3gcu91Gw3WMeVOjhW+uElF78Ho8/Njf4gCaUx2bA/ZH0qTCgPzRZMu7rM73fhzWSmJnFi2VTv9/sfhM1EajoB3kxCf3u5jx41+x6XnbDPvh7juIT0t0YA272d7rbz/uR/2u++TRwmZ9jBWNaDG6r9xEckHCOHZz3g5BWqLayO2h2qDcos7O1CXemfeQRRpf1vHcRzHcRzHcRzH+d2x7npLuFcea4J2HKeIj9rS/C+kZz6L47JznFLYY6Gl4LJznFKEpIut8vEnn92kb4zwZZKPP0Po0YO9o/d/Wnfb93xa1EHoXtdiSGUnD42SOHRMleQZkuP87jQhCL7hE7NfbbA7A9SkfSHYB2K/0e9QN+wVIRKUNX0Iix0nPlJ5oqhYdvBoNKNf2EbeSUBA7uBj1Xs4OI7xi2MOQRn5sqhhfQBjSfHNE2116diYKUnvBXZ0EL3ZDGLkDFTFFUflOE4WDu8Vd/X7t8oOzEB6IcUlGMWjjrgTXzwHKN4407Dwz0B/vjemA0Q4jpMFpRl0hoJr/1/WDKGyxWU3Xpv8SOmprh3HidG3R0xAJWVnlcyPpigL20ve0cqBUGkvXsf5jYGY9n82Gl3c3knzB27cnr23273ZssONX6ffgWA1jM35/hffUek3qhIS3p0+X1AZHZPHcX5Tmv9yMMz9n8mtFx+c97pN1DblQUHyMkkyUBXWxE0qDR18PR4/MX3xRB4g7FeHWrzJ84P0cYLjOIsSl3qO46wMl53jrBxUNpM3nx3HcRzHcRzHcRxnmfBx4jZiyXOcdSSEu8UIobU0lhmX4LJz1hqXneOsHJed46wcl53jrByXneOsHJed46wcl52z/jTHPqu7HB6tn3RWdi/smRd4gUWZTKScVCoTQlVq5hAycYUrc9yLjOyGxwfmmoNhWGCjh6J+bY4oOiifnVxmvme0MMNLcyyH/7H53MiL4R19p7W3yIuoveyIf/1Ebf0HkvNM8rLD5PlrTJYmu0msTnbrJKDFyKRgw2X3538WE15XRHMf2eVIZRdVH6lalJXd20+YiOy+/oFJePnkx90fL59w1Y+XT95Cl09f/uASSaTy4eak1Xq1cyTLtYr42azVukoENdj5gHBXtSCrRHbfj+gEWdl9OPzeGnw//KCLtcqH2m6rcgPn7g4VebWzi+lNHP+bHUyuwk5lMKgcIn6jUHbty2+Ynl/uceH6TMqQ21tOC7DN7LqT2TAcn1+Hs9v27RmWLm/PvrWj9pfjNhbaZ6fXUXuvPn6V5nYa763+DpPrs+F51H53bH4H4fr4W7udKdpicrI7RnQHdUtCLoIRUtmF23dR+1v9XBcksj050D2mAxzUmYYcx18Q9bezUw13yW2/XUpKj2+x5vY2c1Bj/DmFhYSn4zDEsuNYtX0p/xosrLr50U/6DFztcY1qqsH14qxSvd2Gyk5HvO08UnE3dm8nshOstJPZV4iOvP2q81R2sQLeTJfdSRiYS6jUBkex6EZkp/MPVBoi0hl4E7tu3iDaQyg9vGq1Lr7Dx3aS7LRYdtd1c3w7lRmEN1F0yWY52XHCq1nKnEtdg2sWk3ad4ipgZKeqBVHi6OFAdjIfJye7dDYawQijpV1m+UCyCqC6K1CdaTQS2Z3GaWOWUNeDOZ8uO7tGxvnv/1pAeFY65Uq7BlRjHtVc8RdLdFx23ERAfHGls/lII4WVlF1g8ZcjlkrNaoV67U+U3RWLpZRKqFyw2FKysouj01poKqWkgJOir/ZqECqHrVeQX1nZfTOdqFDA7amWeIXMll18Gae7Oj+WUijL6E7PEELFfmBFTczk+uME2Y1GMEJyfF/qexDR+XG8bOW8QN2dB9NYSnIskmRTGqKE/uI102U3kUVUN1F2IqgRTEdFspPCjiC+qpVyay67vz4ltUsjlsrVhcwGF7JckcJqsDMmu1bNirE3oidWMnd34gIwK7tDUePgUOWXSmmgK1q7h9zqVe3mQ+voSFeXk50WMqwQio9c/NlLMI9tdnAss9sC2VmIW17OViAUXMH5nUbtcG5Kjr7kC6nJspMqKSLHf1Z2oxGMEMvuOkhZhhqpLLY1azi1DGLvDEekzizDLzK7DjzWgzMtDSULGepOT+PT+q4e4sJwNgvWMbMlWFZ2hZpRrUklU28JZXQx+nbiWzrKuK9DhK1HJfO1tmN+hvMz5rjXsxmE9xSu53+P39vhvi6E2pVd+98Pw+HRSS1AjCeMSpCbrsHRRQg7b0RqF4Hiw7JulMRVCeFq9wbBUH9EXLq1bd86OZK4xd26oNoPpeZaQ4iK7E1zABDL7lY2D0ELhvbwLIRTuV7gCLjyuM6unxFi72vZZBjCOTc5h9oucdVj28thG7HbxXw6/HYZQlKgZMnslODm0Fy4jo9DqKsAGDkpqvW2v9RDuNzDtc/kIITNchHkiJMtodqnCHR7juODvnDoSnyoexPSj6PGRkg3Vx8girOhiq89rIf6MDk/c8luwRYV0w+kRrumsqNqAMXUVGUS+nVUTuY02XEqw/Vp6SkFnvqvnrHSriyZEkpIy7X5GY3r3mRKu8W4nhlBUonbbFjrXYBzLUNXxcyqYG8kQMlSbC0eIMxFXirMdbSNchHWSnYseJCdT0dLjeKCYmOQNCTlXllQbIYFxbowcz8uLym7uNq5cpZW2t2H9SvtHOchcdk5zspx2TnOynHZOetPN2PPGZ3DrNVzXpJn6avBZeesPdrgmHtcPpEFZRf1kicQq0Bbs7YPS56zDYjSYrtiIflqlnxHKy8zyI5fh6RntYeNGJAe9Imf5nHKh3coRPkoD0ul2z4d5zch6fClpZ1KCmIx//RJOemKp3SVrup660PGbimi355M2ZOzK1LT9Y/VTcxx1pPJfTIV8YixSiZDWRcU3UDUxdpqB6VlBy5EpmHtmXlevY7zmzNS2iWyK6wXmuwoolh2OpMVXdEclFdllFnZeWnnODlUaSaMVHaQjXSuxCTtk4n7OCzLDVvc4dIWVI6yeU+lmJWd39s5To7Zkri/aKwq6jiOkX1uV0RjxvrZrPi5neM4juM4juM4juM4juM4juM4juM4juM4juM4juM4juM4juM4zmzsvXjHRz1yVseCY+UtPM5fIQ8wYJ85yuOyc1aHy85w2Tmrw2VnuOyc1eGyM1x2zupw2RkuO2d1uOwMl90aM3kIo2ZucFobALoAG+J2hFlDIz0Y2Qv0ylrSAT/YL5MJlJXd6wnhXj83h5A5iGk7LU8mwspOuRhzshuu04da69fm4EdkzTGbpXzkeXhpjmWx2MfLbdzm2RTJjqOuT5Ld7K8zPxB52WFS46eQlya7SaxOdmUjXN/SLpMFbLzs/vzPIsKzMSw7KA86HY6sp4PRyvCzsTNQQSK7TnZYdW7DVZAdv1Oi8uUo7hrl5OLxYcnKbvcCE5Hd4QkmYedo0DrZOeKqwc7RLnR5szPgEi9SU8zd3T9P/7i7++vlE/F5/lr8bHZ39yIJ9+PlPwj34nmQVSK7z0/oBFmVfDj83hp8P/ygi7XKh9puq3ID564UW1c7OI7WTfyZ9Dc7mFyFncpgUJGDVgplN6i9wfSk9p0LuxeMp3UkqSMjsrNr3a47mQ3D8fl1OLtt355h6fL27Fs7an855rfz22en11F7rz5+lbYvv2F6fikf+7695RTl1ztMrs+G51H73bH5HYTr42/tdqZoi8nJ7hjRHdQltpEIRkhlF27fRe1v9XNdkMj25ED3mA5wUGcachx/QdTfzk413CW3/XYpKT2+xZrb2+nVgT+nML/wsp8Yacqne0Zkl4gHjnytE8SlnW6NmHQoWy3+JhSCD05WdoLITrALVmaHcpHiaj3UeSq7p6awv6fL7o/ww1zC6+c/nsSiG5Gdzj9QaTganYE3sesG4rnCYbwKr1qtC2pISunskRfKLj70OCYILxUdN7EzohTJjhNezVLmXOoaXLOYtOsUVwHXXEu+nXKqWhAljqyh7GQ+Tk526Ww0ghFGS7vM8oFkFUB1V6A602gksjuN08Ysoa4Hcz5LdmbZcf77v+YWnmrDBn6WAdRHZJeM6MxibLQ+mqtk8it2LBkJtfxYXz4oKbuQliRCKrvnL3SuApsouxcvzaG8Dq8/vTV3YSXzqiaz9GiSAk6KvtqrQagctl6JlMrJ7o3GqJolRzda4ilzyy6+jNPtzo+lFMryzcSp6oyiM4TQMu/AipqYyfXHCbIbjWCE5Pi+1PcgovPjePn6LNU3dXceTGMpybFIkk1piBL6i9fMkt1E5ledacOEM0N2/f6k0i6RnX75QFnz0u7VhdUujVR2Lz7J7Mcn8Xn9jyy8HJPd3XNZg1JR7upYyXz7Mi4AsyrRcnVwqDtPj2ZgBe7uIY/kVe3mA2qIurqc7FpSx0REF+IjJZ1VNUmx7A6OZXZbIDsLccvL2QqEgitYSjbWQjV0O5ybkqMv+UJqsuykSorI8Z+V3WgEI8Syuw5SlqFGKottzRpOLYPYO8MRqTPL8IvMrgOP9eBMS0PJQoa609NYdu/qIS4My7BIHTOWlXyNDqUURNOAE9VNngbKTiuWvY7WNqsMZ18aAVoDzcgu6omPTJLq6YrJy64ipW9gze075rjXsxku9Bu4am/G7+1wXxfC8xcmsM9fw9cnfzwPEOMfjErATR20+ORTCC//Fql9ChQflnWj5CCw/6td7GgH9Ufdt6BF7cnRYTg8smL3ggd1GHg4NYSotE4wlQMlcYRHsnm8YlC5COFGRAcHU8l1Jsti2eFyDeH0YBjCORy4Qi9xJR6EsIfLun0bgl3Mp8NvlyEkBUqW9lBisCVcyWkh9e04hLoKgJGTovu09pd6CJd7uPaxQ4awWS6CHAwgMFT7FIFuz3F80BcOXYkPdW9CsYWjxkZIN1cfIIqzoYqvPayH+jA5P3PKbqEWlbh+KWTLqiloeTiTksGWTl52pcnKTknLtflZ8CAms0CEedld50VYQFKJ22xY612Acy1DV0Xm+Vop2TXH7vCKWYvndnMwKjvJQeOa5dyslexY8CA7n46WGsUFxcYgaUjKvbKg2AwLitWJWZLs7sdayc5xHhyXneGyc1aHy85w2a0xZe/Vlod0hnk4XHaGy26NmfxQe2ZX6EWfzD1sa4vLznDZrS8lHxosVXYP239FW7McYGfEWTv06VqDAgo9SlA90q7Q+ri8L7Ib6abSl17Psi3WpBFJh2mJASEwbcITLnh2VbuyznF+V7TAsmKrqHOY9v8CjdDJiy6zGQUpTnv4ziVqLao2qph2sZ0FiMX5OB1YHGctUDVM6QqdSA1Skc5jGUxKWg6K00ozqUU2Anz5a9LTZec4CaoymeqLP9JJUyuH9DUhqVQa+ZsyDSVbmKrsrk1vGIMUddVul5HnZOeVTOf3xppUurgBb6rbnHCZJAEkoyUUlZl0he7zzdgg/qYqFpzmI05MrYzMyu6xXglynHUhIwGT4AxQebwnj9Zd03HWhMzj8nKyuzcP/LjccRzHcRzHcRznN2Ry+0aJ4Wmr8eh8o3irieNM5n7D004Wlz8jcJyJ2Mhgiw9PC9X2OedjOenUqVEWFo6O4wB7ci1qWmB4WoZKeqYgYDd0bDF5fu44zgiqjoWHp2UoE6bKDSWgys17ojjOJFQdVjTNkF3B8LQqO1GjxIHoqqpCL+0cZyIqqwWHpxXZ6cYdykwm8sqdBnccp4iHGp62VCDH+U3JPGErJbtyQx75czvHcRzHcRzHcRzHcRzHcRzHcRzHcRzHcRxnq+HLf87ysdPrOEUs/KEtcyyF5X62Cyz0oS1zLAOXnTMVl53hsnNWh8vOcNk5q8NlZ7jsnNXhsjNcds7qcNkZLrs1ptxrq/eht9rBjLJX25U1foMrLMpkAmUv0sqEcJWaOYSM7MILc9yLzOFVdqYkI0MuRZVpaS/BUmVXvzZHFB2Uj/dyaI77MLw0x7L4H5vPiYxhlAxUtCj2NnnhUA7yOeXVkZcdJrUKJkuT3SRWJ7uyArpvinIsVXbhwBxbILs//7OI8HQghweVXbnBIpZG9mrbvcBEZHd4gknYORq0TnaOuGqwc7QLXd7sDLiUu0g/3CDwq50j8ZGtk5kpWRjsfEC4q1qQVSK77xI1yMrun6+f7358/vqPLj5//c/zt3evn8L59iUV+eLlW0yfvuZK8PdLTF6El69//Hj99Q/1A4WyG9TeYHpS+86F3Qukp9U6ig9hVHa2mWUPMquEnZPdcHE0OJLzdHTxZtAafJAzMri42W0Nvh/GmUkqu/blN0zPL/e4cHvLKcqvd5hcnw3Po/a7Y/M7CNfH39rtTNEWk5PdMaI7qEtsIxGMkMou3L6L2t/q57ogke2JnPbOOGV8bXWkHH9B1N/OTjXcJbf9dslQ7eNbrLm9zRxUAX9OYQHhqVB6/AKrDhIWenKC+1zR5MnWQY56Mq0iBMI2sTpfc4xlpxuwdJPhanWQsdUO3jeWySeKia88mR3KRYqr9VDn6WY3Fv6N+EyU3UkwwSqV2iC94vOy0/k/VBpkpzPwd+x6+jeE9vXu7q/w193dp8/weaGbP4+1WCy7+NBbb25kBuFlDqGM7DhhyrRWYBK7YrSDQyo6JZHddd0c3045VS2IEkfWUHYyH2e8tJPZaAQjjJZ2meWDY5OZ6q5AdabRSGR3ysMlzBLqejDns2Rnhhjnv/9rbuGZIrS0Ey2pDuPRZblErXV6HUz7lJKGbeRLsFxpxwVbr98qV+8VUVJ2gcVfhnSzml3WKrCJsrvaMYdSCRUtboSCSuaL5zJLpZQUcFL0Pf/rR3j99e4vyK+s7N7ERZEIBRzdZA5hftnFSUy3O9mRghQksvsW19IOVCRnKKe0zDuwoiZmcv1xguxGIxghkdmX+h5EdH4cL1+fpfqm7s6DaSwlORapZJrSNLuI1yxc2s2vurzsRGsqES2xdAUbXXryq6b3gbNkl6tYrqPsXl3kCqvMRXrFGherWeJT+SALO2Oya9VkTXz18xLejWusOdl9ZSXy7sdXlV8qpR+64u7t1x+Y/vX86T93T57o6nKya0kdk0cqPlLSWVWTFMvOcoujAtlZiCMm9UajPolzp7SSKSUb6mZnepm2w3l8v/QlX0hNlp1USSEP/GdlNxrBCLHsroOUZaiRymL7WCqopzKl7nBE6swy/CKz68BjPTjT0lCykKHu9DSW3bt6iAvDMixUxzRFaBVShpQ1iai4tILZlaKuE/oipQmyk8VUdtmK5WNWMivajslM+zvmUJTNILwbuGq4nRGym73awYorE9j3w3B4dFLjNieMSpCLEbdEIexoBBeBlzCWdaNEdq9DePH2aQgvUX+8u/usW4egN21/PPkavj6xG7hPnzD5GijB5wjx+u4PTOknxId3JJtbClqDCvZ4I2rhrpFKrjNZFssOwuQmOC8n3OQEaqtBdti2Vhkg9gvNX24qb2pIXJpjpRpqD89COE3KhuuQFlLfjkOoqwAQRii6T2t/qYdwuYdr/1ZD2CwXQQ4GEBiqfYpAt+eXgfo6sBUhLvv2JhRbOGpsNAyy+gBRnA1VfO1hPdSHSWk3p+wWalExvaAuiAOXemVcMnFk6Fgu+vWDXrZkFNnJ/ZtSDdwwlR1DAG4Xa3JFjFxtZRnfLC3X5idT2i2HBVKV32R3ZgRpraCAjOzWHNZ6F+Bcy9BVMdI2Mg8lv/3/iA8Q5mB0M2Ya2ka5CGslO5Zqh7OSoo84rUQcZzNkJ2lIyr2yoNgMC4p1Ybb6cfkcLLjZBNavtLsnm1PaOY+Cy85w2Tmrw2VnuOyc1eGyM1x2a4w0O2rr5LLp5Jpr0vbMe7TilMBlZ7js1pe+Pht4ENnlSWXXSZ87PADamuUsGzu9zjJQwWHaC/qJ5NDt6/M6nmo+hlO56JQP1PUZnz3dS+jCr9lFDNatjPHGXWCwCg6JoSFrV6Fyx1lbYpFImSdfIbdH3KoM9hGTIM0gjwHo7IkA9fvJMSqwDoU7KrukkIND+lerU+aO81sSF0giskyfzLg/F1ewQ0q328S0kd4H5juHmY64alR2SbnI8tAql/5hc+e3JiOSnEziF3tkqSea63ajzH1gXnamoxmya3ZswUs75/dGRSTv22kV0JQhrZBNXehLDRP1TFnKyC7tk8maJ+4JuYqe6hTZWax91VpPttAoHOd3Rd8xWJBR+ZSU07326ThbgL0ptwh2/5dSUnZWgXUcx3Ecx3Ecx3GWxUO/b7fit+0cZxOQ9o17t+hPbpxc8bvljrMB6JPre8tuygNwfzbuOCPoA/ElDE9Lbckz9r72zMREt4z7mTmOo5gmtLS71/C0WLTIdNte0CGh4xgdxzFyshO9qEjmH54Wi/IGA5AoOsnLQS47x8mjmljS8LS6rUTDnpn6aqRXMh1nBNXLvYen1WggMaBhuVhVAeYE6jjOfTpIlhqe1h8gOM4Y/rjccRzHcRzHcRxn81nO8LQLDKOoI3Q6zm/I6oanHeMe77U7zkajgsP0fsPTMprcmGGdDgL12VfFNmzyM5PymK8KB+dxBzTH+c2IpSJl3uLD047LjrLU8fmkp0tDnDISWfocT/fhOL8bk/pkxj26uIIdUmYMTyueOdlx88zUBtKkWFkA0j0mXcf5TchIxQQSy078dWn28LRlZafbxlXWeMlxfjP00r//8LT0HBmYNjvFjR2ikEFsGVKCm0wd57dj8mgMJUiLq9RVjJV2ObyPtPPbspThabVcm0KB7Py5neM4juM4juM4juM4juM4juM4juM4juM8NsF5aOxMO05CCK0lsvRrLIS7eVlmipYQl8vOGcdlNw2XnfMguOym4bJzHgSX3TRcds6D4LKbhsvOeRBcdtNw2TkLshfCgTkLKHthVYrDXYSauYTkGhtO3Wl5srJ7/TWEr89/2NJEcimqhCtzLcRDye62rBgvQwhDc9+DEC7N9cjoa646vN4C5E5b+rbrmoyBecDDuKS55OJfhuwmUSmW3fSdlicju5d/mWMGS5BKwnJllzklYqFyiB3vy3DZsvs//8scc6HveN9raIeUzEvm6zFOypjshmeh/oVroqiNnDYcJ6bMXlivdkLYuboKoXKCf3jUdNaCVybcoHKBcN9r37kgssOyrs5dY9en2NE7WUCmPYzeHYfLNpfOb+uhfnuu/roF5pcsInl0x9fiJcSy+8wjILL04/WnEJ6+iFd8ptbCc1mVkZ2ED1rcaalcCZzBXTk8/H5SCxe7TFpl9yaEC0koEnd0GC6OKje6lD07kuwbxvad0SL1OD0SYJeO2isJxVPFSA7l7ID4lJwzMLnl0gFSWg9ne7IquuZ5uNRTNUYqu+svxzg7pl2NTCoVqM+InWlZXZmBpr89N9kdwCRnQzFC1B7CCkPEM02R/3sS/9effy4gPBkERQ5bxgjDnB5dkeHIYCf8ZmRDPl+uI+3JQA06iAqHnoVDZNeUJBcNnvJIpOYKp5y2Ay/nL+Z7avP0wrq6kNngQnxqehnajJeTORKvnUR2lSPxAFnZ1UU913W9TC7rvNza8GvrCqyB+ZNc+Ja5wkGQ6/D4G6dCprQLIjPy/G+Z/fgkPm8/vb27e/JEvEhWKsBqmVYqy6xyeIJkQFmSqJqFOGK6LJlvxmVXeyOzwQVD74YBF77LKdvR7XUNo4CaEURC5E+JKQYcBEnjuzqnpqT2Wbo+w2hpZ8tnPIt7xyoh0+9oUJxfzWyvRVsHZxr6GxeGclFEp5mDKuDPP/+/Sfzf8wvPRu/S0k7VJGP1ceCwkWGJdFHqoiOySwo5OnT02tTv8cnITs+szJjTKOKXkV1Nrxq78ibK7mrHHEplZ8cuUVJwjb1TYaVHEwteDR/OYflb5Aks/Kzqlbl6imT3d1yuvfiq87fhqTqEErLjhClT2cVJlO2ktJMyjaRxvdHtsc0hpyK43UNKS6oCggZJzpQySXbp7MA2n1DupGdjj4XiMUoo41qkJ4juJOvKkdRlJXuzHBBRQvPxmlXKztQhsosH0BNRoczSkftiLKRobUR2SanI8tAql2s0Gl+x7OJ6TUx6Yd3Y5fdGfCbKzjL6GFzCu5K7C9lrzK4By1XTo/mmHtAfM/wvw72zqP5OS71ysntrarv7W9WGkk5KPGNu2ZmgVE/KSUB5CNK4duO1VhAijoEGisPGzC27c8lyJhKfDa2tZJbj6qYAu95K9TVP3aI+5fmVE05Y3zANnk+XnVUpx1mokpkt7WxUTC3Wer1GvryykDNk18D1sRmlXXR7toeqxvlQqje8ru3yaLU+3OD6eXVxJD5X1NKr2uGY7HABVgatwauaik0u4e87BTWqL3UofO/MTJ2R0rVIf0+z6nYdV9O7uh5bOdnd/Xj5+gfKupe4p0uql6nwimU3OMS91+7NRYHsPtTeIEEfpBRHgnESBjtWbc7ENdhBslHWx/dsR0cX5hzsyH3d7o0KcrLsbnHXer53eQxnVnYQkNzXXZ/GGVKO5Gwc43YYdrPS7nikXnl2XFhWcqP2tzORHeqkOM3todRM28e3bdxlX8ayQ0laGMEEFmtS0aqjVjJtfFr4iAJlMR4emiqDkGQcW/VUp2qUUut2VWsN2UI0uUmMXKRg5LKZi8w1thwysivLqOxyhXMBSYFewPjZmZuln5IJJHfJczK9tFsys9owR+VTVk4jVdT1Z8tlN9j5YK6JbIfsUFVfhOu0TXslTH/C1pXCMENJ2W3et+uWcGFlWMPS7l5sjuycjcJlNw2XnfMguOym4bJzHgSX3TRcdkumOaNN5b7IV2A3AJfdNFx2S0aa+8s83NaHdXPTXJ8HeFOR3hHOQ2Jn2okfdc96jEAWlF36MN1xHEWfr6nsmtINWrqZMGsa6WhSDQwkeVa1p48RZIFuLS279qC8ybD0lLjXqL+K46wFpgmVnT3ilo4n1VAdeUKnpZ1oyQo+7eEiS9RaM/RFsYhRA3RMnJv25NxxHpas7OJ+YKIZ/QZ5FtNaKru4D6fUIntd9g7Dr6Gi5QqXneMUoprQ0k7FYh0rO/ErPDFVUaiENAXqXZtWMCExK/DSmFR2Xsl0nBHyTSpsb6KIquLLl13TrtDVHns/i0pNdryvS94PqkrAbjaAys6bVBxnlERWxdy7qNqUBwiOs0L8cbnjOI7jOI7jOM7mU3p4Wh3Ebz56/sjOccZZ6vC0Y2jsjuPkkA5efFwnD9ymDU8rwznoAzlxoiRD6K5szWcEzdBoqocWniK45Amf4zgx2QH7TCOThqcdk52IUsfno2ahOTr5pD0dgaXk0CuO8zuR7ZMZv3Qn0hobnnZcdqKtdJpVcFzYmZ4dx8mQ1cr04WnLyi4u31TQ8ZLjOCkqGy2UZg1PCwWNDkybkx1fv9NBbLFaBacydRwny6xaYFpczSq44jpqFn/7wHGKKD08rZZrkymSnT+3cxzHcRzHcRzHWQlLft/OX69znNlIQ0hRc8hi+MvkjjOT/FgqS8CHTnGcWWjPFJXd9OFp5el5Ux+J8wmerO7x8YNuJk5/VOc4MzGRqOxUgvqAbmx42rgeykAaAhP+W8XSNs44HMcpJCu76cPTdqwU035gDSyjUMw8QnfZOU5ZVCRa2mkHSlFiwfC0KjENCc3JPNNhLFabVzIdZxblh6flfZ2+0ApQB40dgIFjD29ScZyZzHh0MG/Z5Q8QHGc2/rjccRzHcRzHcRzHcRzHcRzHcZxtJor+f3ssb58vHzDyAAAAAElFTkSuQmCC)\n", "\n", "\n", "\n", "So first, we need to standardize our sentences so that they all have the same context size. We will set a center token and then retrieve C words before and after it." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def get_random_context(C=5):\n", " sent_id = random.randint(0, len(sentences) - 1)\n", " sent = sentences[sent_id]\n", " word_id = random.randint(0, len(sent) - 1)\n", "\n", " context = sent[max(0, word_id - C) : word_id]\n", " if word_id + 1 < len(sent):\n", " context += sent[word_id + 1 : min(len(sent), word_id + C + 1)]\n", "\n", " center = sent[word_id]\n", " context = [w for w in context if w != center]\n", "\n", " if len(context) > 0:\n", " return center, context\n", " else:\n", " return get_random_context(C)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "center, context = get_random_context()\n", "center, context # we will use the context words to predict the center word" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"But,\" you may be asking yourself, \"this doesn't solve the problem about computers not being able to read text at all! We still have strings! What gives, Peter >:(\"\n", "\n", "Good point! That part is a bit easier: Because our center word is picked randomly, we can assign each word in our text a number somewhat at random. In fact, we will go sequentially and assign a *token id* to each word that we haven't seen before. We will create two dictionaries: one with keys that are each word and values are their token id, and another with keys that are the token ids and the values are their words. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def get_tokens():\n", " tokens = {}\n", " tok_freq = {}\n", " word_count = 0\n", " rev_tokens = []\n", " idx = 0\n", "\n", " for sent in sentences:\n", " for w in sent:\n", " word_count += 1\n", " if w not in tokens:\n", " tokens[w] = idx\n", " rev_tokens += [w]\n", " idx += 1\n", " tok_freq[w] = 1\n", " else:\n", " tok_freq[w] += 1\n", "\n", " tokens[\"UNK\"] = idx\n", " rev_tokens += [\"UNK\"]\n", " tok_freq[\"UNK\"] = 1\n", " word_count += 1\n", " return tokens, tok_freq, rev_tokens, word_count\n", "\n", "\n", "tokens, tok_freq, rev_tokens, word_count = get_tokens()\n", "len(tokens), len(tok_freq), len(rev_tokens), word_count" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"Center word: *\", center, \"* Center word token id: \", tokens[center])\n", "for i in range(len(context)):\n", " print(\n", " \"Context word: *\", context[i], \"* Context word token id: \", tokens[context[i]]\n", " )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Negative Sampling\n", "\n", "We'll come back to this if we have time" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# the data came with some splits in our data\n", "# we can apply them with this function\n", "def dataset_split():\n", " split = [[] for _ in range(3)]\n", " with open(f\"{path}/datasetSplit.txt\", \"r\") as f:\n", " first = True\n", " for line in f:\n", " if first:\n", " first = False\n", " continue\n", " split = line.strip().split(\",\")\n", " split[int(split[1]) - 1] += [int(split[0]) - 1]\n", " return split\n", "\n", "\n", "split = dataset_split()\n", "len(split), len(split[0]), len(split[1]), len(split[2])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "table_size = 1e8\n", "\n", "\n", "def sampleTable():\n", " tokens_num = len(tokens)\n", " sampling_freq = np.zeros((tokens_num,))\n", "\n", " i = 0\n", " for w in range(tokens_num):\n", " w = rev_tokens[i]\n", " if w in tok_freq:\n", " freq = 1.0 * tok_freq[w]\n", " freq = freq**0.75\n", " else:\n", " freq = 0.0\n", " sampling_freq[i] = freq\n", " i += 1\n", "\n", " sampling_freq /= np.sum(sampling_freq)\n", " sampling_freq = np.cumsum(sampling_freq) * table_size\n", "\n", " sample_table = np.zeros((int(table_size),))\n", "\n", " j = 0\n", " for i in range(int(table_size)):\n", " while i > sampling_freq[j]:\n", " j += 1\n", " sample_table[i] = j\n", "\n", " return sample_table\n", "\n", "\n", "sample_table = sampleTable()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def reject_prob():\n", " threshold = 1e-5 * word_count\n", " reject_prob = np.zeros((len(tokens),))\n", " for i in range(len(tokens)):\n", " w = rev_tokens[i]\n", " freq = 1.0 * tok_freq[w]\n", " reject_prob[i] = max(0, 1 - np.sqrt(threshold / freq))\n", " return reject_prob\n", "\n", "\n", "reject_prob = reject_prob()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Our complete dataset object\n", "\n", "Now that we have coded out the data specific functions, we can compile it all into a single class from which we can call these functions." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class StanfordSentiment:\n", " \"\"\"\n", " Class for reading and loading Stanford Sentiment Treebank. We ignore the sentiment component of the treebank and extract just the text.\n", " \"\"\"\n", "\n", " def __init__(self, path=None, table_size=1000000):\n", " if not path:\n", " path = \"utils/datasets/stanfordSentimentTreebank\"\n", "\n", " self.path = path\n", " self.table_size = table_size\n", "\n", " self.get_sentences()\n", " self.get_tokens()\n", " self.get_all_sentences()\n", " self.dataset_split()\n", " self.sampleTable()\n", "\n", " def get_tokens(self):\n", " if hasattr(self, \"tokens\") and self.tokens:\n", " return self.tokens\n", "\n", " tokens = {}\n", " tok_freq = {}\n", " word_count = 0\n", " rev_tokens = []\n", " idx = 0\n", "\n", " for sent in self.sentences:\n", " for w in sent:\n", " word_count += 1\n", " if w not in tokens:\n", " tokens[w] = idx\n", " rev_tokens += [w]\n", " idx += 1\n", " tok_freq[w] = 1\n", " else:\n", " tok_freq[w] += 1\n", "\n", " tokens[\"UNK\"] = idx\n", " rev_tokens += [\"UNK\"]\n", " tok_freq[\"UNK\"] = 1\n", " word_count += 1\n", "\n", " self.tokens = tokens\n", " self.tok_freq = tok_freq\n", " self.rev_tokens = rev_tokens\n", " self.word_count = word_count\n", " return self.tokens\n", "\n", " def get_sentences(self):\n", " if hasattr(self, \"sentences\") and self.sentences:\n", " return self.sentences\n", "\n", " sentences = []\n", " with open(f\"{self.path}/datasetSentences.txt\", \"r\") as f:\n", " first = True\n", " for line in f:\n", " if first:\n", " first = False\n", " continue\n", " split = line.strip().split()[1:]\n", " sentences += [[w.lower() for w in split]]\n", " sent_lens = np.array([len(s) for s in sentences])\n", " cum_sent_lens = np.cumsum(sent_lens)\n", "\n", " self.sentences = sentences\n", " self.sent_lens = sent_lens\n", " self.cum_sent_lens = cum_sent_lens\n", " return sentences\n", "\n", " def get_reject_prob(self):\n", " if hasattr(self, \"reject_prob\") and self.reject_prob:\n", " return self.reject_prob\n", "\n", " threshold = 1e-5 * self.word_count\n", " reject_prob = np.zeros((len(self.tokens),))\n", " n_tokens = len(self.tokens)\n", " for i in range(n_tokens):\n", " w = self.rev_tokens[i]\n", " freq = 1.0 * self.tok_freq[w]\n", " reject_prob[i] = max(0, 1 - np.sqrt(threshold / freq))\n", " self.reject_prob = reject_prob\n", " return reject_prob\n", "\n", " def get_all_sentences(self):\n", " if hasattr(self, \"all_sentences\") and self.all_sentences:\n", " return self.all_sentences\n", "\n", " sentences = self.get_sentences()\n", " reject_prob = self.get_reject_prob()\n", " tokens = self.get_tokens()\n", " all_sentences = [\n", " [\n", " w\n", " for w in s\n", " if 0 >= reject_prob[tokens[w]]\n", " or random.random() >= reject_prob[tokens[w]]\n", " ]\n", " for s in sentences * 30\n", " ]\n", " all_sentences = [s for s in all_sentences if len(s) > 1]\n", " self.all_sentences = all_sentences\n", " return all_sentences\n", "\n", " def get_random_context(self, C=5):\n", " sentences = self.get_all_sentences()\n", " sent_id = random.randint(0, len(sentences) - 1)\n", " sent = sentences[sent_id]\n", " word_id = random.randint(0, len(sent) - 1)\n", "\n", " context = sent[max(0, word_id - C) : word_id]\n", " if word_id + 1 < len(sent):\n", " context += sent[word_id + 1 : min(len(sent), word_id + C + 1)]\n", "\n", " center = sent[word_id]\n", " context = [w for w in context if w != center]\n", "\n", " if len(context) > 0:\n", " return center, context\n", " else:\n", " return self.get_random_context(C)\n", "\n", " def dataset_split(self):\n", " if hasattr(self, \"split\") and self.split:\n", " return self.split\n", "\n", " split = [[] for _ in range(3)]\n", " with open(f\"{self.path}/datasetSplit.txt\", \"r\") as f:\n", " first = True\n", " for line in f:\n", " if first:\n", " first = False\n", " continue\n", " split = line.strip().split(\",\")\n", " split[int(split[1]) - 1] += [int(split[0]) - 1]\n", " self.split = split\n", " return split\n", "\n", " def sampleTable(self):\n", " if hasattr(self, \"sample_table\") and self.sample_table:\n", " return self.sample_table\n", "\n", " tokens_num = len(self.tokens)\n", " sampling_freq = np.zeros((tokens_num,))\n", "\n", " i = 0\n", " for w in range(tokens_num):\n", " w = self.rev_tokens[i]\n", " if w in self.tok_freq:\n", " freq = 1.0 * self.tok_freq[w]\n", " freq = freq**0.75\n", " else:\n", " freq = 0.0\n", " sampling_freq[i] = freq\n", " i += 1\n", "\n", " sampling_freq /= np.sum(sampling_freq)\n", " sampling_freq = np.cumsum(sampling_freq) * self.table_size\n", "\n", " self.sample_table = np.zeros((int(self.table_size),))\n", "\n", " j = 0\n", " for i in range(int(self.table_size)):\n", " while i > sampling_freq[j]:\n", " j += 1\n", " self.sample_table[i] = j\n", "\n", " return self.sample_table\n", "\n", " def get_random_train_sentence(self):\n", " split = self.dataset_split()\n", " sent_id = random.choice(split[0])\n", " return self.all_sentences[sent_id]\n", "\n", " def get_split_sentences(self, split=0):\n", " split = self.dataset_split()\n", " sentences = [self.all_sentences[i] for i in split[split]]\n", " return sentences\n", "\n", " def get_train_sentences(self):\n", " return self.get_split_sentences(0)\n", "\n", " def get_test_sentences(self):\n", " return self.get_split_sentences(1)\n", "\n", " def get_val_sentences(self):\n", " return self.get_split_sentences(2)\n", "\n", " def sampleTokenIdx(self):\n", " return self.sample_table[random.randint(0, self.table_size - 1)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dataset = StanfordSentiment() # takes about 45sec" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tokens = dataset.tokens\n", "num_words = len(tokens)\n", "print(num_words)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Model\n", "\n", "As I mentioned in the motivation, we are trying to create a model that gives us a vector for each word that represents the meaning of that word. How could we do this?\n", "\n", "It may not seem like it but the problem is of the shape: $y = Ax$, where $x$ is our inputs, in our case the context words, $y$ is our expected outputs, in our case the center word. Like I said, we are going to have our model predict a center word from the context words and then compare that prediction to the actual center word. Based on how close we were, we can then adjust the model so that it does a better job on another training example. This leaves two major questions:\n", "\n", "1. How can we measure similarity between words mathematically?\n", "2. How can we \"adjust\" our model? What does that even mean?\n", "\n", "### Stochastic Gradient Descent\n", "Luckily, there is a single process which will answer both of this questions.\n", "\n", "> Before we discuss this topic, realize that no one just woke up one day and \"discovered\" this process. It took decades of mathematical and computational experimentation to develop. To that end, I do not expect you to *just* understand it, instead I want you to compile questions that you have. Pay close attention to what are you confused about and where you stop understanding.\n", "\n", "It is called Stochastic Gradient Descent or SGD and it will allow us both to create a quantitative similarity metric and to \"learn\" from what it tells us. As I posited above, this problem can be simiplied to the following: $y = Ax$, where $x$ is our inputs, in our case the context words, $y$ is our expected outputs, in our case the center word. In that case, what is $A$? $A$ will be matrix of \"weights\" which when multiplied by our $x$s will product our $y$s.\n", "\n", "We don't know need to figure out $A$. It will start out as completely random and then we will learn its value through training. Importantly, each row in the $A$ matrix is a single vector representing a word, so it will be as long as our entire vocabulary. So for each word in our text, we will have a initially random vector, whose size we will called `embedding_dim` or embedding dimension.\n", "\n", "Now that each word has a (random) vector associated with it, we can directly compare them. Using the **the scaled dot product**, we can determine how similar two vectors are. The scaled dot product ($x \\cdot y$) between two vectors will produce a number between -1 and 1, representing how similar or dissimilar a vector is from any other. This answers our first question above.\n", "\n", "Before we attack the second question, let's first take a look at what we just described looks like in code." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "vector_dim = 10\n", "word_vecs = np.concatenate(\n", " (\n", " (np.random.rand(num_words, vector_dim) - 0.5) / vector_dim,\n", " np.zeros(\n", " (num_words, vector_dim)\n", " ), # for simplicity's sake, we will have a separate set of vectors for each context word as well as for each center word\n", " ),\n", " axis=0,\n", ")\n", "\n", "word_vecs.shape # 2*num_words (one for the context vector and another for the center vector) x vector_dim\n", "# initially random vectors" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# getting center word vecs and context word vecs\n", "# each word will have two word vectors: center and context, we will only care about the center word vectors\n", "center_word_vecs = word_vecs[:num_words, :]\n", "outside_word_vecs = word_vecs[num_words:, :]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "block_size = 5\n", "center_word, context = dataset.get_random_context(block_size)\n", "center_word, context # get a center word and context" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# find index of center word\n", "center_word_idx = dataset.tokens[center_word]\n", "center_word_idx" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# getting the random word vec for this index/word\n", "center_word_vec = center_word_vecs[center_word_idx]\n", "center_word_vec # still random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we are able to get the center word vector, we can get the vectors for the outside words in the same way. For each one, we are going to take the similarity (dot product) between it and and the center word vector." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# example with just one outside word\n", "outside_word_idx = dataset.tokens[context[1]]\n", "outside_word_idx" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "outside_word_vec = outside_word_vecs[outside_word_idx]\n", "outside_word_vec # start as zeros" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dot_products = np.dot(\n", " outside_word_vecs, center_word_vec\n", ") # take the dot product between all outside words and the center word\n", "dot_products.shape" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# let's see what this dot product produces\n", "import matplotlib.pyplot as plt\n", "\n", "plt.plot(dot_products)\n", "plt.show() # it's all zeros because all of the outside word vectors are zero" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How can we take these numbers and get a prediction for word? Remember what we want to do: compare a predicted word to the actually correct center word. But right now all we have an array of zeros. How can we turn this into a prediction?\n", "\n", "We will be using something called the **softmax** function, which is defined as: $\\sigma(x_i) = \\dfrac{e^{x_i}}{\\sum_{j=1}^{K}e^{x_j}}$. This might look really scary, but don't worry. All this function does is turn a set of numbers into a probability distribution. See below." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def softmax(x):\n", " orig_shape = x.shape\n", "\n", " if len(x.shape) > 1:\n", " # Matrix\n", " tmp = np.max(x, axis=1)\n", " x -= tmp.reshape((x.shape[0], 1))\n", " x = np.exp(x)\n", " tmp = np.sum(x, axis=1)\n", " x /= tmp.reshape((x.shape[0], 1))\n", " else:\n", " # Vector\n", " tmp = np.max(x)\n", " x -= tmp\n", " x = np.exp(x)\n", " tmp = np.sum(x)\n", " x /= tmp\n", "\n", " assert x.shape == orig_shape\n", " return x" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "softmax_probs = softmax(dot_products)\n", "softmax_probs.shape" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "softmax_probs[0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# let's see what this looks like\n", "plt.hist(softmax_probs)\n", "plt.show() # probabilities are even, at zero, as you might expect" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this case, all of the words have the same probability: zero or almost zero (~5e-5), as softmax cannot output a value of zero. As a result, we can pick any word and compare it to our center word. To do so, we introduce a value called *loss* which represents how close we are to the true word for a given training example. There are many ways to calculate a loss, but because we are picking individual words, we are going to use **negative log likelihood**: $Loss = -y_{o,c}\\ln(p_{o,c})$.\n", "\n", "This also probably looks scary, but all it says is that we take the predicted word and the correct word and from their dot product can calculate a single number." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "loss = -np.log(softmax_probs[outside_word_idx]) # nll in code\n", "loss\n", "# this number represents how good our prediction is\n", "# zero is the lowest number that we can predict" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Stochastic Gradient Descent continued\n", "\n", "We have completed one half of our model! What we just did was called the **forward pass**. We are now going to investigate the **backwards pass**.\n", "\n", "It is called a backward pass because we are going to go backwards through all of the steps in the forward pass to figure out what we need to do to make the prediction better. This process is also called *back propagation* or *backprop*.\n", "\n", "So we need to figure out what elements of our $A$ matrix (our word vectors) we need to change, and how to change them, so that we **minimize our loss**. This is an *optimization* problem, meaning we need to determine the *most optimal* values for each cell of $A$ such that the loss between the predicted $y$s and the actual $y$s is the lowest we can make it. Thus, when our loss has reached the lowest it will go, we will have trained our word vectors so that they actually represent the meaning of their respective words. We will be able to show this by the end.\n", "\n", "But how do we optimize? Well, it involves some calculus. We want to see how much we need to change each and every element of $A$, so we use a *derivative*, which will tell us how far away we are from reaching the lowest point in our loss function.\n", "\n", "Thankfully, the derivatives we will need to calculate are fairly simple. All we have done is some multiplication and addition, which are very easy to take the derivative of. Don't worry about this though, the derivatives will be provided below.\n", "\n", "Once we have the derivative, we can take a small step in that direction by multiplying it by a small number (called a step size or learning rate) and subtract it from our values of $A$.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# let's see an example in code\n", "loss # need to differential with respect to all of the values of A" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "current_grad_center_vec = -outside_word_vecs[outside_word_idx] + np.dot(\n", " softmax_probs, outside_word_vecs\n", ") # derivative of dot product for the center word vec\n", "current_grad_center_vec" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "current_grad_outside_vecs = np.outer(\n", " softmax_probs, center_word_vec\n", ") # derivative of dot product for the outer word vecs\n", "current_grad_outside_vecs[outside_word_idx] -= center_word_vec\n", "current_grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "grad_center_vecs = np.zeros(center_word_vecs.shape) # holder for our derivative values\n", "grad_outside_vecs = np.zeros(\n", " outside_word_vecs.shape\n", ") # holder for our derivative values\n", "\n", "grad_center_vecs[center_word_idx] += current_grad_center_vec\n", "grad_outside_vecs += current_grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# now that we've calculated our derivatives we can take a step\n", "step = 1\n", "center_word_vecs -= step * grad_center_vecs\n", "outside_word_vecs -= step * grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# and then run another forward pass\n", "dot_products = np.dot(outside_word_vecs, center_word_vec)\n", "dot_products # longer zero!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "softmax_probs = softmax(dot_products)\n", "softmax_probs # a bit more variation!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "loss = -np.log(softmax_probs[outside_word_idx])\n", "loss # slight lower!!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Negative Sampling\n", "\n", "We just saw how using softmax and ggradient descent can reduce our loss, meaning that we can learn word meaning and represent that meaning with vectors! That's great, but it takes too long. Softmax is a very expensive operation. We'll use it in later lessons, but here, we're going to use a similar technique, but a different activation function: **sigmoid**. Additionally, instead of applying softmax to every context word vector. We are only going to sample a small subset and estimate the loss based on that sample. This process is called *negative sampling*.\n", "\n", "Sigmoid is defined as follows: $\\frac{1}{1+e^{-x}}$\n", "\n", "Like softmax, sigmoid, transforms a set of numbers into probability distribution by not allowing any numbers greater than 1 or less than 0.\n", "\n", "Let's run through an example of negative sampling in code now." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# new example copying from above\n", "vector_dim = 10\n", "word_vecs = np.concatenate(\n", " (\n", " (np.random.rand(num_words, vector_dim) - 0.5) / vector_dim,\n", " np.zeros(\n", " (num_words, vector_dim)\n", " ), # for simplicity's sake, we will have a separate set of vectors for each context word as well as for each center word\n", " ),\n", " axis=0,\n", ")\n", "\n", "block_size = 5\n", "center_word, context = dataset.get_random_context(block_size)\n", "\n", "center_word_idx = dataset.tokens[center_word]\n", "center_word_vec = word_vecs[center_word_idx]\n", "\n", "outside_word_idxs = [dataset.tokens[w] for w in context]\n", "\n", "center_word_vecs = word_vecs[:num_words, :]\n", "outside_word_vecs = word_vecs[num_words:, :]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# first we need a data structure from which we can easily sample from\n", "# we can use a table of values\n", "table_size = 1e8\n", "\n", "\n", "def sampleTable():\n", " tokens_num = len(tokens)\n", " sampling_freq = np.zeros((tokens_num,))\n", "\n", " i = 0\n", " for w in range(tokens_num):\n", " w = rev_tokens[i]\n", " if w in tok_freq:\n", " freq = 1.0 * tok_freq[w]\n", " freq = freq**0.75\n", " else:\n", " freq = 0.0\n", " sampling_freq[i] = freq\n", " i += 1\n", "\n", " sampling_freq /= np.sum(sampling_freq)\n", " sampling_freq = np.cumsum(sampling_freq) * table_size\n", "\n", " sample_table = np.zeros((int(table_size),))\n", "\n", " j = 0\n", " for i in range(int(table_size)):\n", " while i > sampling_freq[j]:\n", " j += 1\n", " sample_table[i] = j\n", "\n", " return sample_table\n", "\n", "\n", "sample_table = sampleTable()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "sample_table[random.randint(0, table_size - 1)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "negSampleWordIndices = [None] * 5\n", "for k in range(5):\n", " newidx = sample_table[random.randint(0, table_size - 1)]\n", " print(newidx)\n", " negSampleWordIndices[k] = newidx\n", "[int(n) for n in negSampleWordIndices]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# function version\n", "def get_negative_samples(outsideWordIdx, dataset, K):\n", " negSampleWordIndices = [None] * K\n", " for k in range(K):\n", " newidx = dataset.sampleTokenIdx()\n", " while newidx == outsideWordIdx:\n", " newidx = dataset.sampleTokenIdx()\n", " negSampleWordIndices[k] = newidx\n", " return [int(n) for n in negSampleWordIndices]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "outside_word_idx = outside_word_idxs[0]\n", "\n", "neg_samples = get_negative_samples(outside_word_idx, dataset, 5)\n", "neg_samples # neg samples" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "grad_center_vec = np.zeros(center_word_vec.shape)\n", "grad_outside_vecs = np.zeros(outside_word_vecs.shape)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "u_0 = outside_word_vecs[outside_word_idx]\n", "u_0 # vector for the true context word" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "z_0 = np.dot(u_0, center_word_vec)\n", "z_0 # dot product as before" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def sigmoid(x):\n", " return 1 / (1 + np.exp(-x))\n", "\n", "\n", "p_0 = sigmoid(z_0)\n", "p_0 # new sigmoid transformation" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "loss = -np.log(p_0) # loss for just this part\n", "loss" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# derivatives for this part\n", "grad_center_vec += (p_0 - 1) * u_0\n", "grad_outside_vecs[outside_word_idx] += (p_0 - 1) * center_word_vec" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for k in neg_samples: # loop through neg sample idxs\n", " u_k = outside_word_vecs[k] # find the correct context vector for a sample idx\n", " z_k = np.dot(u_k, center_word_vec) # take the dot product as above\n", " p_k = sigmoid(-z_k) # activate using sigmoid\n", " loss -= np.log(p_k) # calculate the loss\n", "\n", " # derivatives for this negative sample\n", " grad_center_vec -= (p_k - 1) * u_k\n", " grad_outside_vecs[k] -= (p_k - 1) * center_word_vec" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "loss # new loss about neg sampling" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# example backwards pass\n", "step = 1\n", "center_word_vecs -= step * grad_center_vecs\n", "outside_word_vecs -= step * grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# checking if our grad descent worked like last time\n", "loss = 0.0\n", "u_0 = outside_word_vecs[outside_word_idx]\n", "z_0 = np.dot(u_0, center_word_vec)\n", "p_0 = sigmoid(z_0)\n", "loss = -np.log(p_0)\n", "\n", "for k in neg_samples:\n", " u_k = outside_word_vecs[k]\n", " z_k = np.dot(u_k, center_word_vec)\n", " p_k = sigmoid(-z_k)\n", " loss -= np.log(p_k)\n", "\n", "loss # went down slightly!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Running the model\n", "\n", "We have covered *A LOT* this lesson, so I have assembled the functions that we will need to train the model below. You have seen all of the code in them, though the presentation/order might be a little weird." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def w2v_wrapper(model, w2i, word_vecs, dataset, block_size, loss_and_grad):\n", " batch_size = 50\n", " loss = 0.0\n", " grad = np.zeros(word_vecs.shape)\n", " N = word_vecs.shape[0]\n", " center_word_vecs = word_vecs[: int(N / 2), :]\n", " outside_word_vecs = word_vecs[int(N / 2) :, :]\n", " for i in range(batch_size):\n", " block_size1 = random.randint(1, block_size)\n", " center_word, context = dataset.get_random_context(block_size1)\n", "\n", " c, grad_in, grad_out = model(\n", " center_word,\n", " block_size1,\n", " context,\n", " w2i,\n", " center_word_vecs,\n", " outside_word_vecs,\n", " dataset,\n", " loss_and_grad,\n", " )\n", " loss += c / batch_size\n", " grad[: int(N / 2), :] += grad_in / batch_size\n", " grad[int(N / 2) :, :] += grad_out / batch_size\n", "\n", " return loss, grad" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def sigmoid(x):\n", " return 1 / (1 + np.exp(-x))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def softmax(x):\n", " \"\"\"Compute the softmax function for each row of the input x.\n", " It is crucial that this function is optimized for speed because\n", " it will be used frequently in later code.\n", "\n", " Arguments:\n", " x -- A D dimensional vector or N x D dimensional numpy matrix.\n", " Return:\n", " x -- You are allowed to modify x in-place\n", " \"\"\"\n", " orig_shape = x.shape\n", "\n", " if len(x.shape) > 1:\n", " # Matrix\n", " tmp = np.max(x, axis=1)\n", " x -= tmp.reshape((x.shape[0], 1))\n", " x = np.exp(x)\n", " tmp = np.sum(x, axis=1)\n", " x /= tmp.reshape((x.shape[0], 1))\n", " else:\n", " # Vector\n", " tmp = np.max(x)\n", " x -= tmp\n", " x = np.exp(x)\n", " tmp = np.sum(x)\n", " x /= tmp\n", "\n", " assert x.shape == orig_shape\n", " return x" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# normal softmax\n", "def softmaxloss_gradient(center_word_vec, outside_word_idx, outside_word_vecs, dataset):\n", " dot_products = np.dot(outside_word_vecs, center_word_vec)\n", " softmax_probs = softmax(dot_products)\n", " loss = -np.log(softmax_probs[outside_word_idx])\n", "\n", " grad_center_vec = -outside_word_vecs[outside_word_idx] + np.dot(\n", " softmax_probs, outside_word_vecs\n", " )\n", " grad_outside_vecs = np.outer(softmax_probs, center_word_vec)\n", " grad_outside_vecs[outside_word_idx] -= center_word_vec\n", "\n", " return loss, grad_center_vec, grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def get_negative_samples(outsideWordIdx, dataset, K):\n", " \"\"\"Samples K indexes which are not the outsideWordIdx\"\"\"\n", "\n", " negSampleWordIndices = [None] * K\n", " for k in range(K):\n", " newidx = dataset.sampleTokenIdx()\n", " while newidx == outsideWordIdx:\n", " newidx = dataset.sampleTokenIdx()\n", " negSampleWordIndices[k] = newidx\n", " return [int(n) for n in negSampleWordIndices]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# negative sampling\n", "def negative_samplingloss_gradient(\n", " center_word_vec, outside_word_idx, outside_word_vecs, dataset, K=10\n", "):\n", " neg_samples = get_negative_samples(outside_word_idx, dataset, K)\n", "\n", " grad_center_vec = np.zeros(center_word_vec.shape)\n", " grad_outside_vecs = np.zeros(outside_word_vecs.shape)\n", "\n", " u_0 = outside_word_vecs[outside_word_idx]\n", " z_0 = np.dot(u_0, center_word_vec)\n", " p_0 = sigmoid(z_0)\n", " loss = -np.log(p_0)\n", "\n", " grad_center_vec += (p_0 - 1) * u_0\n", " grad_outside_vecs[outside_word_idx] += (p_0 - 1) * center_word_vec\n", "\n", " for k in neg_samples:\n", " u_k = outside_word_vecs[k]\n", " z_k = np.dot(u_k, center_word_vec)\n", " p_k = sigmoid(-z_k)\n", " loss -= np.log(p_k)\n", "\n", " grad_center_vec -= (p_k - 1) * u_k\n", " grad_outside_vecs[k] -= (p_k - 1) * center_word_vec\n", "\n", " return loss, grad_center_vec, grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def skipgram(\n", " current_center_word,\n", " block_size1,\n", " outside_words,\n", " w2i,\n", " center_word_vecs,\n", " outside_word_vecs,\n", " dataset,\n", " loss_and_grad,\n", "):\n", " loss = 0.0\n", " grad_center_vecs = np.zeros(center_word_vecs.shape)\n", " grad_outside_vecs = np.zeros(outside_word_vecs.shape)\n", "\n", " center_word_idx = w2i[current_center_word]\n", " center_word_vec = center_word_vecs[center_word_idx]\n", "\n", " for outside_word in outside_words:\n", " outside_word_idx = w2i[outside_word]\n", " current_loss, current_grad_center_vec, current_grad_outside_vecs = (\n", " loss_and_grad(center_word_vec, outside_word_idx, outside_word_vecs, dataset)\n", " )\n", " loss += current_loss\n", " grad_center_vecs[center_word_idx] += current_grad_center_vec\n", " grad_outside_vecs += current_grad_outside_vecs\n", "\n", " return loss, grad_center_vecs, grad_outside_vecs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import pickle\n", "import glob\n", "import random\n", "import numpy as np\n", "import os.path as op\n", "\n", "SAVE_PARAMS_EVERY = 2000\n", "\n", "\n", "def load_saved_params():\n", " \"\"\"\n", " A helper function that loads previously saved parameters and resets\n", " iteration start.\n", " \"\"\"\n", " st = 0\n", " for f in glob.glob(\"saved_params_*.npy\"):\n", " iter = int(op.splitext(op.basename(f))[0].split(\"_\")[2])\n", " if iter > st:\n", " st = iter\n", "\n", " if st > 0:\n", " params_file = \"saved_params_%d.npy\" % st\n", " state_file = \"saved_state_%d.pickle\" % st\n", " params = np.load(params_file)\n", " with open(state_file, \"rb\") as f:\n", " state = pickle.load(f)\n", " return st, params, state\n", " else:\n", " return st, None, None\n", "\n", "\n", "def save_params(iter, params):\n", " params_file = \"saved_params_%d.npy\" % iter\n", " np.save(params_file, params)\n", " with open(\"saved_state_%d.pickle\" % iter, \"wb\") as f:\n", " pickle.dump(random.getstate(), f)\n", "\n", "\n", "losses = []\n", "\n", "\n", "def sgd(f, x0, step, iterations, use_saved=False, PRINT_EVERY=10):\n", " ANNEAL_EVERY = 5000\n", " if use_saved:\n", " start_iter, oldx, state = load_saved_params()\n", " if start_iter > 0:\n", " x0 = oldx\n", " step = 0.0\n", " if state:\n", " random.setstate(state)\n", " else:\n", " start_iter = 0\n", "\n", " x = x0\n", " exploss = None\n", "\n", " for iter in range(start_iter + 1, iterations + 1):\n", " loss = None\n", " loss, gradient = f(x)\n", " x -= step * gradient\n", "\n", " if exploss is None:\n", " exploss = loss\n", " else:\n", " exploss = 0.95 * exploss + 0.05 * loss\n", "\n", " if iter % PRINT_EVERY == 0:\n", " if not exploss:\n", " exploss = loss\n", " else:\n", " exploss = 0.95 * exploss + 0.05 * loss\n", " print(\"iter %d: %f\" % (iter, exploss))\n", " losses.append(exploss)\n", "\n", " if iter % SAVE_PARAMS_EVERY == 0 and use_saved:\n", " save_params(iter, x)\n", "\n", " if iter % ANNEAL_EVERY == 0:\n", " step *= 0.5\n", "\n", " return x" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Training loop\n", "\n", "Now that we have all of these functions and utilities we can finally put everything together and train a word2vec model. Training with these parameters will take about 20 minutes, so plan accordingly." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "import matplotlib.pyplot as plt\n", "\n", "random.seed(314)\n", "dataset = StanfordSentiment()\n", "tokens = dataset.tokens\n", "num_words = len(tokens)\n", "\n", "vector_dim = 10\n", "C = 5\n", "\n", "random.seed(31415)\n", "np.random.seed(9265)\n", "\n", "start_time = time.time()\n", "word_vecs = np.concatenate(\n", " (\n", " (np.random.rand(num_words, vector_dim) - 0.5) / vector_dim,\n", " np.zeros((num_words, vector_dim)),\n", " ),\n", " axis=0,\n", ")\n", "word_vecs = sgd(\n", " lambda vec: w2v_wrapper(\n", " skipgram, tokens, vec, dataset, C, negative_samplingloss_gradient\n", " ),\n", " word_vecs,\n", " step=1, # was .01\n", " iterations=10000,\n", " use_saved=True,\n", " PRINT_EVERY=10,\n", ")\n", "\n", "print(\"training took %d seconds\" % (time.time() - start_time))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Evaluation\n", "\n", "Now that our model is trained let's make sure that our word vectors make sense and reflect underlying word meaning. these types of evaluations are difficult because word meaning is inherently qualitative, not quantitative. But we can still make some interpretations." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from logging import makeLogRecord\n", "\n", "plt.plot(losses, label=\"Loss\")\n", "plt.xlabel(\"Iterations\")\n", "plt.ylabel(\"Loss\")\n", "plt.title(\"Loss vs. Iterations\")\n", "plt.legend()\n", "plt.show()\n", "makeLogRecord" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "trained_word_vectors = np.concatenate(\n", " (word_vecs[:num_words, :], word_vecs[num_words:, :]), axis=0\n", ") # put all of center word vecs together" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# visualize_words = [\n", "# \"great\", \"cool\", \"brilliant\", \"wonderful\", \"well\", \"amazing\",\n", "# \"worth\", \"sweet\", \"enjoyable\", \"boring\", \"bad\", \"dumb\",\n", "# \"annoying\", \"female\", \"male\", \"queen\", \"king\", \"man\", \"woman\", \"rain\", \"snow\",\n", "# \"hail\", \"coffee\", \"tea\"]\n", "\n", "visualize_words = [\"Paris\", \"London\", \"England\", \"France\"] # analogies" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "visualize_idx = [tokens[word.lower()] for word in visualize_words]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# dimension reduction for visualization\n", "visualize_vecs = trained_word_vectors[visualize_idx, :]\n", "temp = visualize_vecs - np.mean(visualize_vecs, axis=0)\n", "covariance = 1.0 / len(visualize_idx) * temp.T.dot(temp)\n", "U, S, V = np.linalg.svd(covariance)\n", "coord = temp.dot(U[:, 0:2])\n", "full_piece = temp.dot(U[:, 0:2])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "for i in range(len(visualize_words)):\n", " plt.text(\n", " coord[i, 0],\n", " coord[i, 1],\n", " visualize_words[i],\n", " bbox=dict(facecolor=\"green\", alpha=0.1),\n", " )\n", "\n", "plt.xlim((np.min(coord[:, 0]), np.max(coord[:, 0])))\n", "plt.ylim((np.min(coord[:, 1]), np.max(coord[:, 1])))\n", "plt.show()\n", "makeLogRecord" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conluding remarks\n", "\n", "Implementing anything from scratch as we did in the notebook is **not** easy. External libraries can be incredibly helpful, but challenging ourselves to not use them can give us a lot of insight into the inner workings of these libraries." ] } ], "metadata": { "colab": { "provenance": [] }, "kernelspec": { "display_name": "Python 3", "name": "python3" }, "language_info": { "name": "python" }, "mystnb": { "execution_mode": "off" } }, "nbformat": 4, "nbformat_minor": 0 }