docs/notebooks/WMD_tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finding similar documents with Word2Vec and WMD \n",
    "\n",
    "Word Mover's Distance is a promising new tool in machine learning that allows us to submit a query and return the most relevant documents. For example, in a blog post [OpenTable](http://tech.opentable.com/2015/08/11/navigating-themes-in-restaurant-reviews-with-word-movers-distance/) use WMD on restaurant reviews. Using this approach, they are able to mine different aspects of the reviews. In **part 2** of this tutorial, we show how you can use Gensim's `WmdSimilarity` to do something similar to what OpenTable did. In **part 1** shows how you can compute the WMD distance between two documents using `wmdistance`. Part 1 is optional if you want use `WmdSimilarity`, but is also useful in it's own merit.\n",
    "\n",
    "First, however, we go through the basics of what WMD is.\n",
    "\n",
    "## Word Mover's Distance basics\n",
    "\n",
    "WMD is a method that allows us to assess the \"distance\" between two documents in a meaningful way, even when they have no words in common. It uses [word2vec](http://rare-technologies.com/word2vec-tutorial/) [4] vector embeddings of words. It been shown to outperform many of the state-of-the-art methods in *k*-nearest neighbors classification [3].\n",
    "\n",
    "WMD is illustrated below for two very similar sentences (illustration taken from [Vlad Niculae's blog](http://vene.ro/blog/word-movers-distance-in-python.html)). The sentences have no words in common, but by matching the relevant words, WMD is able to accurately measure the (dis)similarity between the two sentences. The method also uses the bag-of-words representation of the documents (simply put, the word's frequencies in the documents), noted as $d$ in the figure below. The intution behind the method is that we find the minimum \"traveling distance\" between documents, in other words the most efficient way to \"move\" the distribution of document 1 to the distribution of document 2.\n",
    "\n",
    "<img src='https://vene.ro/images/wmd-obama.png' height='600' width='600'>\n",
    "\n",
    "\n",
    "This method was introduced in the article \"From Word Embeddings To Document Distances\" by Matt Kusner et al. ([link to PDF](http://jmlr.org/proceedings/papers/v37/kusnerb15.pdf)). It is inspired by the \"Earth Mover's Distance\", and employs a solver of the \"transportation problem\".\n",
    "\n",
    "In this tutorial, we will learn how to use Gensim's WMD functionality, which consists of the `wmdistance` method for distance computation, and the `WmdSimilarity` class for corpus based similarity queries.\n",
    "\n",
    "> **Note**:\n",
    ">\n",
    "> If you use this software, please consider citing [1], [2] and [3].\n",
    ">\n",
    "\n",
    "## Running this notebook\n",
    "\n",
    "You can download this [iPython Notebook](http://ipython.org/notebook.html), and run it on your own computer, provided you have installed Gensim, PyEMD, NLTK, and downloaded the necessary data.\n",
    "\n",
    "The notebook was run on an Ubuntu machine with an Intel core i7-4770 CPU 3.40GHz (8 cores) and 32 GB memory. Running the entire notebook on this machine takes about 3 minutes.\n",
    "\n",
    "## Part 1: Computing the Word Mover's Distance\n",
    "\n",
    "To use WMD, we need some word embeddings first of all. You could train a word2vec (see tutorial [here](http://rare-technologies.com/word2vec-tutorial/)) model on some corpus, but we will start by downloading some pre-trained word2vec embeddings. Download the GoogleNews-vectors-negative300.bin.gz embeddings [here](https://code.google.com/archive/p/word2vec/) (warning: 1.5 GB, file is not needed for part 2). Training your own embeddings can be beneficial, but to simplify this tutorial, we will be using pre-trained embeddings at first.\n",
    "\n",
    "Let's take some sentences to compute the distance between."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time\n",
    "start_nb = time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize logging.\n",
    "import logging\n",
    "logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s')\n",
    "\n",
    "sentence_obama = 'Obama speaks to the media in Illinois'\n",
    "sentence_president = 'The president greets the press in Chicago'\n",
    "sentence_obama = sentence_obama.lower().split()\n",
    "sentence_president = sentence_president.lower().split()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These sentences have very similar content, and as such the WMD should be low. Before we compute the WMD, we want to remove stopwords (\"the\", \"to\", etc.), as these do not contribute a lot to the information in the sentences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package stopwords to /home/lev/nltk_data...\n",
      "[nltk_data]   Package stopwords is already up-to-date!\n"
     ]
    }
   ],
   "source": [
    "# Import and download stopwords from NLTK.\n",
    "from nltk.corpus import stopwords\n",
    "from nltk import download\n",
    "download('stopwords')  # Download stopwords list.\n",
    "\n",
    "# Remove stopwords.\n",
    "stop_words = stopwords.words('english')\n",
    "sentence_obama = [w for w in sentence_obama if w not in stop_words]\n",
    "sentence_president = [w for w in sentence_president if w not in stop_words]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, as mentioned earlier, we will be using some downloaded pre-trained embeddings. We load these into a Gensim Word2Vec model class. Note that the embeddings we have chosen here require a lot of memory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cell took 259.69 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "start = time()\n",
    "import os\n",
    "\n",
    "from gensim.models import KeyedVectors\n",
    "if not os.path.exists('/data/w2v_googlenews/GoogleNews-vectors-negative300.bin.gz'):\n",
    "    raise ValueError(\"SKIP: You need to download the google news model\")\n",
    "    \n",
    "model = KeyedVectors.load_word2vec_format('/data/w2v_googlenews/GoogleNews-vectors-negative300.bin.gz', binary=True)\n",
    "\n",
    "print('Cell took %.2f seconds to run.' % (time() - start))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's compute WMD using the `wmdistance` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "distance = 3.3741\n"
     ]
    }
   ],
   "source": [
    "distance = model.wmdistance(sentence_obama, sentence_president)\n",
    "print 'distance = %.4f' % distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try the same thing with two completely unrelated sentences. Notice that the distance is larger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "distance = 4.3802\n"
     ]
    }
   ],
   "source": [
    "sentence_orange = 'Oranges are my favorite fruit'\n",
    "sentence_orange = sentence_orange.lower().split()\n",
    "sentence_orange = [w for w in sentence_orange if w not in stop_words]\n",
    "\n",
    "distance = model.wmdistance(sentence_obama, sentence_orange)\n",
    "print 'distance = %.4f' % distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Normalizing word2vec vectors\n",
    "\n",
    "When using the `wmdistance` method, it is beneficial to normalize the word2vec vectors first, so they all have equal length. To do this, simply call `model.init_sims(replace=True)` and Gensim will take care of that for you.\n",
    "\n",
    "Usually, one measures the distance between two word2vec vectors using the cosine distance (see [cosine similarity](https://en.wikipedia.org/wiki/Cosine_similarity)), which measures the angle between vectors. WMD, on the other hand, uses the Euclidean distance. The Euclidean distance between two vectors might be large because their lengths differ, but the cosine distance is small because the angle between them is small; we can mitigate some of this by normalizing the vectors.\n",
    "\n",
    "Note that normalizing the vectors can take some time, especially if you have a large vocabulary and/or large vectors.\n",
    "\n",
    "Usage is illustrated in the example below. It just so happens that the vectors we have downloaded are already normalized, so it won't do any difference in this case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cell took 32.01 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "# Normalizing word2vec vectors.\n",
    "start = time()\n",
    "\n",
    "model.init_sims(replace=True)  # Normalizes the vectors in the word2vec class.\n",
    "\n",
    "distance = model.wmdistance(sentence_obama, sentence_president)  # Compute WMD as normal.\n",
    "\n",
    "print 'Cell took %.2f seconds to run.' %(time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Similarity queries using `WmdSimilarity`\n",
    "\n",
    "You can use WMD to get the most similar documents to a query, using the `WmdSimilarity` class. Its interface is similar to what is described in the [Similarity Queries](https://radimrehurek.com/gensim/tut3.html) Gensim tutorial.\n",
    "\n",
    "> **Important note:**\n",
    ">\n",
    "> WMD is a measure of *distance*. The similarities in `WmdSimilarity` are simply the *negative distance*. Be careful not to confuse distances and similarities. Two similar documents will have a *high* similarity score and a small distance; two very different documents will have *low* similarity score, and a large distance.\n",
    "\n",
    "### Yelp data\n",
    "\n",
    "Let's try similarity queries using some real world data. For that we'll be using Yelp reviews, available at http://www.yelp.com/dataset_challenge. Specifically, we will be using reviews of a single restaurant, namely the [Mon Ami Gabi](http://en.yelp.be/biz/mon-ami-gabi-las-vegas-2).\n",
    "\n",
    "To get the Yelp data, you need to register by name and email address. The data is 775 MB.\n",
    "\n",
    "This time around, we are going to train the Word2Vec embeddings on the data ourselves. One restaurant is not enough to train Word2Vec properly, so we use 6 restaurants for that, but only run queries against one of them. In addition to the Mon Ami Gabi, mentioned above, we will be using:\n",
    "\n",
    "* [Earl of Sandwich](http://en.yelp.be/biz/earl-of-sandwich-las-vegas).\n",
    "* [Wicked Spoon](http://en.yelp.be/biz/wicked-spoon-las-vegas).\n",
    "* [Serendipity 3](http://en.yelp.be/biz/serendipity-3-las-vegas).\n",
    "* [Bacchanal Buffet](http://en.yelp.be/biz/bacchanal-buffet-las-vegas-7).\n",
    "* [The Buffet](http://en.yelp.be/biz/the-buffet-las-vegas-6).\n",
    "\n",
    "The restaurants we chose were those with the highest number of reviews in the Yelp dataset. Incidentally, they all are on the Las Vegas Boulevard. The corpus we trained Word2Vec on has 18957 documents (reviews), and the corpus we used for `WmdSimilarity` has 4137 documents.\n",
    "\n",
    "Below a JSON file with Yelp reviews is read line by line, the text is extracted, tokenized, and stopwords and punctuation are removed.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package punkt to /home/lev/nltk_data...\n",
      "[nltk_data]   Package punkt is already up-to-date!\n"
     ]
    }
   ],
   "source": [
    "# Pre-processing a document.\n",
    "\n",
    "from nltk import word_tokenize\n",
    "download('punkt')  # Download data for tokenizer.\n",
    "\n",
    "def preprocess(doc):\n",
    "    doc = doc.lower()  # Lower the text.\n",
    "    doc = word_tokenize(doc)  # Split into words.\n",
    "    doc = [w for w in doc if not w in stop_words]  # Remove stopwords.\n",
    "    doc = [w for w in doc if w.isalpha()]  # Remove numbers and punctuation.\n",
    "    return doc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cell took 114.53 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "start = time()\n",
    "\n",
    "import json\n",
    "\n",
    "# Business IDs of the restaurants.\n",
    "ids = ['4bEjOyTaDG24SY5TxsaUNQ', '2e2e7WgqU1BnpxmQL5jbfw', 'zt1TpTuJ6y9n551sw9TaEg',\n",
    "      'Xhg93cMdemu5pAMkDoEdtQ', 'sIyHTizqAiGu12XMLX3N3g', 'YNQgak-ZLtYJQxlDwN-qIg']\n",
    "\n",
    "w2v_corpus = []  # Documents to train word2vec on (all 6 restaurants).\n",
    "wmd_corpus = []  # Documents to run queries against (only one restaurant).\n",
    "documents = []  # wmd_corpus, with no pre-processing (so we can see the original documents).\n",
    "with open('/data/yelp_academic_dataset_review.json') as data_file:\n",
    "    for line in data_file:\n",
    "        json_line = json.loads(line)\n",
    "        \n",
    "        if json_line['business_id'] not in ids:\n",
    "            # Not one of the 6 restaurants.\n",
    "            continue\n",
    "        \n",
    "        # Pre-process document.\n",
    "        text = json_line['text']  # Extract text from JSON object.\n",
    "        text = preprocess(text)\n",
    "        \n",
    "        # Add to corpus for training Word2Vec.\n",
    "        w2v_corpus.append(text)\n",
    "        \n",
    "        if json_line['business_id'] == ids[0]:\n",
    "            # Add to corpus for similarity queries.\n",
    "            wmd_corpus.append(text)\n",
    "            documents.append(json_line['text'])\n",
    "\n",
    "print 'Cell took %.2f seconds to run.' %(time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is a plot with a histogram of document lengths and includes the average document length as well. Note that these are the pre-processed documents, meaning stopwords are removed, punctuation is removed, etc. Document lengths have a high impact on the running time of WMD, so when comparing running times with this experiment, the number of documents in query corpus (about 4000) and the length of the documents (about 62 words on average) should be taken into account."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/lev/Dropbox/raretech/os/wmd/wmd_env/lib/python2.7/site-packages/matplotlib/__init__.py:872: UserWarning: axes.color_cycle is deprecated and replaced with axes.prop_cycle; please use the latter.\n",
      "  warnings.warn(self.msg_depr % (key, alt_key))\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgEAAAGVCAYAAABn+SKpAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xm8VVX9//HXW9Bw6CqSgICKOIUUzl+cvZRTVuaUqYWY\nXzVTi8zKob4omD+H1BwbNC3TcsgxLQccbigqJs7zgBMyJokgoAif3x9r3+vmcO7lXtiXey/7/Xw8\nzgPO2uusvdbeB877rD0cRQRmZmZWPiu0dQfMzMysbTgEmJmZlZRDgJmZWUk5BJiZmZWUQ4CZmVlJ\nOQSYmZmVlEOAFU7Sm5KubOt+LO8kdZN0vaRpkuZL+uEStLFA0vDW6F/ZSPqTpDfauh+LI2m9bL//\nrK37Ym3PIcCaJGlo9h/G/zSy/A5J4yuKFwAtugGFpO0knSqpZkn7WkJnA1/N/hwC3NW23Vm+SDpY\n0rAWvCRo4fu+NS1B/62EOrd1B6xDaOo/tmrLNiEFgZbYHhgO/BH4oIWvLatdgLsj4ty27shy6hBg\nAHBhW3dkCXX0/tsy4BBghYuIeUvwMhXekZasXFoRWBAR89uyHy3UHZjR1p0ws47LhwOscNXOCZB0\njKRnJM2S9L6kJyUdmS07FTgnq/pmdvhhvqSdc68/WtKzkuZImiTpd5K6Vln3sZJelzRb0qOSdpJU\nJ+n+XJ1dsnUcIuk0SW8Bs4HeklaUNELSY5KmZ+2MlfSNKutaIOk3kvaX9FxunZtly4+U9ErW5zpJ\n6zdz+62XHev/T9bmY/n11x+iAVYDDqvfXotpcyVJv5Y0VdIHkm6V1LuRugMl/VPSjGx/PSBpxyr1\naiT9KtvecyVNkPQXSWtny+v7tm7F6+q3f37/1kl6QdIXsr9/mLV7YLZ8R0mPZNvjJUm7V+lPT0l/\nyN4fc7P2jm5k3QdJOkXSO9n+uVfSBrl6D5AOtfTN6i92Gzcme589lvV9uqQbJPWtqFM//v6S7s/G\nP0HST6u0t66kv2f7Zkq2X3fPb9Pm9l/SEZJey7bXY5K2rljePdumb2d1Jmfvjf5Lsi2s/fFMgDXX\n6pK6VZQJWLFK3YUOEUj6X+AS4Abg4uw1A0iHAC4HbgY2Bg4ChgHvZS99MXv9L4CRwL3A74ANgOOA\n/5E0qH7mQdL3s/ZHA+cD6wG3AtOBd6r08xRgPnBBNpZZQA1wJHAdcCXQhTSterOkvSLi7oo2diD9\nZ3tpNu5TgNslnQH8APgNsAZwEulQR22VfuS31VrAI8CqpGnc/wDfydZ/SERcD/wrK7sCGAtc1lSb\nmSuycfwla78W+AeL7qvPAw8BM0nnGnyUbY97Je0aEQ9l9VYhbedNs3GNA7oBewEbApNo+hh5ZXmQ\nttMdpPfJDcDRwDWSRNpHvwH+CvwUuEHSOhExM7fdxpL246XAVODLwG8krRkR/69ifT8DPgF+BawO\nnAhcA2yXLf9lVt4b+BFLOFMl6STgjGw8VwJdSe/dhyRtFhH17/X68f8TuAW4HjgAOEvSM/Xvu2y7\nPwD0zLbJJODbwGAW3qbN6f9BpPfZ77LXngjcJKlfbkbsJtK/1YuBN4G1SIehNib792kdXET44Uej\nD2Ao6fh+U4/xFa95A7gy9/xm4JnFrOcE0gfyuhXlnwPmAncDqtKvY7LnKwLTgH8DnXL1hmT17s+V\n7ZKVvQl0qVifgBUryjoDzwL3VJQvyPrWN1d2ZFY+GVgtV35GNr5+i9kO52f1dsqVdQGeB96tGNvM\n/HZuos2BWZ8urii/KlvX8Ip9NTffT9KH+zTgsVzZadlr91vMe6faPt0lK985V/ZAVnZIrmzjrN+f\nANvmynfLyg/PlV0GTATWrFjXZWThrmLfP1+xLX+QrX/TXNntle/txWznP+brA+sAHwM/r6i3PjAH\n+GWV8X87V7ZiNqYbcmU/zurtkytbCXihyjat2n9SOF5ACko1ufKvZ23slT1fPav34+ZuAz863sOH\nA6w5gvTtZdcqj7HNeP0MoE/lVGMz7Ur6z/DCyP5nylwNTCF9CwfYhvRhdXksfFz/r8B/G2n7qoiY\nmy+IpH5mYUWlQw5rkL71blWljfsj4s3c8/rtcVNEzKpS3q+RvtTbC3giIh7M9Wku6VtwT2DLxby+\nsTaD9A057yJy3xAlrQDsDvw9Ihqu+Ij0bfVPwFbZN26A/YHnI+LmJehPY+ZExF9z630FeB94JSIe\nzdWrti33J81sSOnSyW7ZzNUoYBVgUMW6rqp4nzxI2haL2z8tsT/QiTRrke/TTFKoHFxRf05E/KX+\nSfY+fKyiT3sAkyPi1ly9j0kzai11Y0TkT8Kt3AZzSCGmVlUOvdnywYcDrLkej4jHKgsl/QfosZjX\nng18CXhM6XLCUcD1EVHXjPWul/35Sr4wIhZIehXomxWtS/qge72i3nxJbzbSduWljUA6TkqaQu3P\nwtOo1a54qDzMUH+i3oQq5SJNBzdlPdIUbKUXs9f3Jc12tMR6pG3zWkX5KxXP1yJ9YFaW16+fbP3T\nSIdkbq1Sb2m8W6VsBhXbOCI+SEcI0rbMgklX4HDgf6u0EaSTKPMq91t9UCzyw24j0j57uZE+Vb7/\nqo3/v8AXc8/Xq/I6WHTfNkfldn0/v10j4mNJJ5IOmUyRNJZ0uOLqiKh8f1sH5RBgrS4iXpK0Cekb\n6R6kb+/fk3RpRPygDbs2p7JA0rdJU8i3AWeRpkw/IX3AHFyljcZOFmusvE2vgljGGjsfoFMj5Uu6\nLetnNK8lHXev5vkWtlmEFUjbYM9G1lf5/lvW75nFri8iLpR0K/AN0mGYXwCnSPpqRIxupX7ZMuQQ\nYMtENqV9M+kEtxVIx6OPkfT/IqL+JLJq3iL9p7QJuW872cliGwFPVNTbELgvV68T6dvr083s6gHA\n6xGxb74wO7lxWXiLNNZK/Unb6M0lbLN+27yUK69czzTSVRKNrZ/c+l8HvrCY9dZ/u14DeDtX3ncx\nr2upaaQp9s4Rcf/iKrfA0t74p35W6p2IeKnJms33FtW3+0ZVygq5cVFEvEU6dHSRpF6kf0s/Jx0i\nsw7O5wRYq5O0Zv55RCwAnsuerpH9+WH2Z+V07CjScckfZh/89b5DOgxxe/b8cdJVBUdmH/z5ei2Z\n4q12GVU/YJ8WtLE07gC2lLRDbv2fAb5POtlw3BK0eScpBBxXUf4Dch8U2X65C/i6cpczZvvvUODf\nETEtK74RGCBp/ybW+3q23vylgCsARy3BGBqV9ftGYB9JAyuXS/rcEjb9IZ++P5fETaRDSFVvy1zl\napvmuBvoKakhpErqQjohtdJS9V/SylnbDSJiIml2bI1cvZ6SNqn4d2cdhGcCrDmWdjryHklTSZee\nTSZ9azkOeDoi6o81P56t5yxJfyV98N8XEf+RdDrpEsF7sqnJDYBjgSdJl74REfMknUb6xvKApBtI\nx0+/S5pBaO63or8D+0m6Pft7H9IH8EvA5ku+CZrtbNJhh39Kuoj0LXcI8HnSmfMtvRMjEfG0pGuB\n70taAxhDOimt/ph13i9I075jJF1KukTwCNKZ4ifk6v2KdOLbtZL+RAonXUlT3/8XEQ9GxAuSHiXt\n026kSzUPonW+fJxEOvP/EUmXk6b/uwJbkKayV1mCNh8HDpR0AelkxAWRLtFsloh4I7tE8JzsvgC3\nkk50XD/r03Wk93VL/J70b+ea7P0xkXSJYP2hhfz7fKn6T7o6435JfyNtz49Ih/I+z8LvhbNIIbEv\nC8/4WEfQnEsIgJ1Ix0gnkJLtoU3U/T1VLishXcZyMek/tVlZe70r6qxBOuv7/ezxZ2D1tr6EoswP\nPr3M638aWX47afo8XzYeuCL3/AjgftLZ/HNI3xB/DXyu4nU/I003z2PRy52OIp1RPYd0bfRvga5V\n+nNstv7ZpP/4diCdSPePXJ36S9QObGRMJ5CCw2zgGdL19acC8yvqzQcurShbLyv/aUV5k+us0sZ1\npHsEzCadIb53lXof5LfzYtpcKdvmU7PX3QL0yvr0fxV1v0iakZhBmma/H9ihSpurZ22+Rbqs8O3s\n32zPXJ2+pG+vs0kfWCNJJ4lWu0Tw+SrrGJ/fd4vZ9t1I186/kfVnIunQ0NGL2w+5/XZormxl0mV/\n00jnhcyv7EdFG3+k4t9CVv71bHz12/NF0n0z+jdj/Iu0mfX176T/R6cA5wH7Zf3fZnH9b+w9mtuu\n/5f9fU3SvSqey/r+fvZeHFqlj59QcSmoHx3joWwnNknSV0j/mT6R/SM/JiL+XKXeAaSbpawF/Doi\nzs8t+232j+FQ0jeCX5M+9LeMrBOS7iR98/pf0jeUK7J/AIvcrc2sObJDCNNIl+x9r637Y9YaJP2I\nFAb6RDrHxqxZmnU4ICLuJB1XRNJV1epIWo/0wb4rFb9mpvTLcIeTEuT9WdkQ0jeIXYFR2W0o9wC2\nj+xSNEnfAx6UtFFEvNry4VmZSPpMRHxUUTyU9I3mgTboklnhJHWJ3P0tsuP23wNedQCwlirknIDs\nhJC/AqdHxMsLn78FpJusdCad5AVAREyQ9CLp1rGjgG2BmZG7KUhEjJH0YVbHIcAWZ1tJvwb+RjpJ\ncCtS+HyGdOKY2fLgZklvA0+RZlO/Qzp+f0ib9so6pKJODBwJTI2Ixu5h3pN0POq9ivIp2bL6OtNY\n1NRcHbOmvEk6Lv0D0rf/6aQ73Z0cEZ+0XbfMCnUX6TybQ0j3XHgB+FZEOOhaiy11CJBUS5py3Wyp\ne2O2FCJdz7ysLuUzaxMRcRHpKhizpVbETMAupG/qk3OHATqRLov5UUSsS7osrJOkbhWzAT349IYT\nk0knFFbqni1bhKRCboZhZmbWUUREYXeRLOJ63UtJv1K2We4xkfRraF/O6owjXUKyW/2LJPUh3YVs\nTFb0CLCapG1zdbYnXd/7cGMrb+vLK5b2ceqppzar3oRefZjQq0+b93dpx9HeH8vDOJaHMSwv41ge\nxuBxtK9H0Zo1EyBpVdItR0UKDutK2gyYHhHvkK5nztefR/qlq1eh4Qc/riDNDkwjHas9j3Riy31Z\nnZck3Q38PrsqQKTfub49fGWAmZlZ4Zo7E7A16e5s40i/bT6CdM+AEY3UrxZXhpFuUHId6ScrPyDd\nACVf92DSfanvIl2S+CTpvgJmZmZWsObeJ+BftODQQUQs8pvckX4be1j2aOx1MyjZh35tbW1bd6EQ\nHkf7sTyMAZaPcSwPYwCPY3nWrDsGtleSoiP3vyXe7b0OAL3frfwZdDMzKwtJRDs7MdDMzMw6IIcA\nMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIMDMzKymHADMzs5Jy\nCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OScggwMzMr\nKYcAMzOzknIIMDMzKymHADMzs5JyCKjQq8+6SCrs0avPum09JDMzs6o6t3UH2ptJ777DoOF3Fdbe\n2JF7FtaWmZlZkTwTYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIO\nAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJdWsECBpJ0m3SZogaYGkQ3PLOks6W9LTkmZJ\nmijpL5LWqWhjJUkXS5qW1btNUu+KOmtIulrS+9njz5JWL2aoZmZmltfcmYDVgGeBHwKzK5atAmwO\nnA5sAewNrAPcKSnf/oXAvsC3gB2BGuAOScrVuTZra3dgD2BL4M8tGI+ZmZk1U7N+Sjgi7gTuBJB0\nVcWyD0gf2A0kfQ94HugPPC+pBjgcGBoR92d1hgBvAbsCoyT1z9rZPiIey7XzoKSNIuLVJR6lmZmZ\nLaK1zglYHQjgv9nzrUiBY1R9hYiYALwIbJ8VbQvMjIhHc3XGAB/m6piZmVlBCg8BklYEzgP+HhET\ns+KewPyIeK+i+pRsWX2daVWanJqrY2ZmZgVp1uGA5pLUCfgL6Xj/14ps28zMzIpVWAjIAsB1wABg\nl4j4b27xZKCTpG4VswE9gNG5OmtVabp7tqyq0047reHvtbW11NbWLkn3zczM2p26ujrq6uparX1F\nRMteIM0Ejo2IP+fKOgPXA5uSAsDUitfUkKb6h0bEdVlZH9KJgXtExL2SPk86mXCH+vMCJG0PPAh8\nvtqJgZKipf1vxvgYNPyuwtobO3JPiujju73TFZe9331nqdsyM7OOSRIRocXXbJ5mzQRIWhXYEBDp\nPIJ1JW0GTAcmAjeSTv77eqquHtlLZ0TE3Ij4QNIVwDmSpmWvOw94CrgPICJeknQ38PvsqgABvwNu\n95UBZmZmxWvuiYFbA08C44AuwAjgiezPPqR7A/TKlk/MPQ7MtTEMuIV0yOBB4ANg74qv8gcDTwN3\nkS5JfBI4FDMzMytcc+8T8C+aDgyLDRMRMY8UBIY1UWcG/tA3MzNbJvzbAWZmZiXlEGBmZlZSDgFm\nZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJeUQ\nYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZS\nDgFmZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZm\nJdW5rTuwtE455eeFtdWnT5/C2jIzM2vvOnwIuPqRCYW1NXH02YW1ZWZm1t51+BDQe+dDCmtr8pjr\nWLBgfmHtmZmZtWc+J8DMzKykHALMzMxKyiHAzMyspBwCzMzMSsohwMzMrKSaFQIk7STpNkkTJC2Q\ndGiVOqdJelfSbEkPSNq0YvlKki6WNE3SrKy93hV11pB0taT3s8efJa2+dEM0MzOzapo7E7Aa8Czw\nQ2B25UJJJwLHA8cCWwNTgVGSVs1VuxDYF/gWsCNQA9whSbk61wKbA7sDewBbAn9uwXjMzMysmZp1\nn4CIuBO4E0DSVVWqDAPOjIhbszpDSUHgEOBySTXA4cDQiLg/qzMEeAvYlRQY+pM++LePiMeyOt8D\nHpS0UUS8uuTDNDMzs0pLfU6ApPWBnsCo+rKImAuMBrbPirYmBY58nQnAi7k62wIzI+LRXJ0xwIe5\nOmZmZlaQIk4M7AkEMKWifEq2DKAHMD8i3muiTk9gWpX2p+bqmJmZWUF8dYCZmVlJFfHbAZMBkb7t\n53/Np0e2rL5OJ0ndKmYDepAOG9TXWatK+91z7SxiQt3VDX+v6TuQmr6btbT/ZmZm7VJdXR11dXWt\n1v5Sh4CIeEPSZGA3YByApC7ATsAJWbVxwCdZneuyOn2A/sCYrM4jwGqStq0/L0DS9sAqwMONrb9P\n7ZClHYKZmVm7VFtbS21tbcPzESNGFNp+s0JAdqnfhqRv/CsA60raDJgeEe8AFwAnS3oZeBX4BTCT\ndMkfEfGBpCuAcyRNA6YD5wFPAfdldV6SdDfw++yqAAG/A273lQFmZmbFa+5MwNbAA6QTAAFGZI+r\ngMMj4pzs2/8lQFdgLLB7RHyYa2MYMI80E7AycC8wJCIiV+dg4GLgruz5bcAPWjooMzMzW7zm3ifg\nXyzmJMKIGAmMbGL5PFIQGNZEnRnAIncjNDMzs+L56gAzM7OScggwMzMrKYcAMzOzknIIMDMzKymH\nADMzs5JyCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OS\ncggwMzMrKYcAMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIaGXq\ntCKSlvrR0J5Erz7rtuGIzMxsedG5rTuwvIv58xg0/K6lb+gPRwAwaPhdjB2559K3Z2ZmpeeZADMz\ns5JyCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OScggw\nMzMrKYcAs6V0zTXXsMUWW7Dyyiuz1lprcdhhhy20/LnnnqO2tpZVVlmFddZZh9NPP32xbR511FFs\nuOGGrLLKKnTv3p199tmHl156qWH5v/71L1ZYYQU6derECiussNDjpptuKnqIZrac8m8HmC2Fiy66\niLPPPptzzz2XQYMGMWfOHF555ZWG5TNnzmS33XajtraWcePG8eKLL3LYYYex2mqrcfzxxzfa7jbb\nbMPQoUNZZ511mD59Oqeeeiq77bYbb775Jp06dWKHHXZg8uTJC73mwgsv5JJLLuErX/lKq43XzJYv\nngmwwgwePJhjjjmGn/zkJ3Tr1o3u3btz8cUX8/HHH3PcccfRtWtX1ltvPa655pqFXjdx4kQOOugg\n1lxzTdZcc02+9rWv8dprrzUsHz9+PPvssw9rr702q622GltttRX/+Mc/Fmpj/fXX54wzzuDoo49m\n9dVXZ5111uHcc89t1fHOmDGDU045hauvvpqDDz6Yfv36MWDAAPbdd9+GOtdccw1z5szhqquuon//\n/uy3336ceOKJnH/++U22feSRR7LDDjuw7rrrsvnmm/PLX/6Sd999l/HjxwPQuXNnunfvvtDjxhtv\n5JBDDmGVVVZp1XGb2fLDIcAK9de//pWamhoee+wxTj75ZIYNG8Y+++zDJptswrhx4xg6dChHHHEE\nU6ZMAWDOnDkMHjyYVVddlQcffJBHH32UXr16seuuuzJ37lwAZs2axV577cV9993HM888wwEHHMD+\n+++/0DdugAsuuICBAwfy5JNPcuKJJ/Kzn/2MsWPHNtrXhx56iM9+9rONPmpqajjrrLMaff0999zD\nggULmDRpEgMGDKBPnz7st99+vPHGGw11Hn30UXbaaSdWWmmlhrI99tiDiRMn8tZbbzVrm3744Ydc\neeWV9O3bl759+1atU1dXx2uvvcZRRx3VrDbNzKCgECBpBUmnSxovaU725+mSVqiod5qkdyXNlvSA\npE0rlq8k6WJJ0yTNknSbpN5F9NGWjQEDBjB8+HA22GADjj/+eD73uc+x0kor8YMf/IB+/foxfPhw\nIoIxY8YAcO211wJwxRVXMGDAADbeeGN++9vfMmvWLO644w4ABg4cyFFHHcWmm25Kv379OPnkk9li\niy248cYbF1r37rvvzjHHHEO/fv047rjj2HDDDbnvvvsa7es222zD008/3ejjqaee4uijj2709ePH\nj2f+/PmcccYZXHDBBdx6663MmzePwYMHNwSYyZMn06NHj4Ve16NHDyJiken8Sr/97W8bAsndd9/N\nvffey4orrli17mWXXcbmm2/OFlts0WSbZmZ5RZ0TcBLwfeBQ4DlgIHAVMBc4A0DSicDxwFDgFeBU\nYJSkjSPiw6ydC4GvA98CpgO/Bu6QtGVEREF9tVY0cODAhZ53796dL37xiw3PO3fuTNeuXZk6dSoA\nTzzxBOPHj+ezn/3sQq+bM2cOr7/+OgCzZ8/mtNNO4x//+AeTJk1i3rx5fPTRR2y22WZNrrtXr14N\n66nmM5/5DP369Wv5IDMLFizgk08+4eKLL+bLX/4yAH/5y1/o2bMnt99+O9/85jeXuG2A73znO+y+\n++5MmjSJc889lwMOOICHH36YLl26LFRv+vTp3HLLLVxwwQVLtT4zK5+iQsB2wO0R8c/s+duSbgcG\n5eoMA86MiFsBJA0FpgKHAJdLqgEOB4ZGxP1ZnSHAW8CuwKiC+mqtqPKbqqSqZQsWLADSB+kWW2zB\n9ddfT2XOW3PNNQE44YQTuOeeezjvvPMazpgfMmQIH3/88WLXXb+eah566KEmT6KTxCmnnMJJJ51U\ndfnaa68NQP/+/RvKampq6NWrF2+//TYAPXv2bDj0UW/KlClIomfPno2uG2iYBdhggw0YNGgQXbt2\n5aabbuLb3/72QvWuuuoqOnfuzCGHHNJke2ZmlYoKAQ8B35e0SUS8nE3zf4lPZwHWB3qS+yCPiLmS\nRgPbA5cDW2f9ydeZIOnFrI5DwHJoyy235LrrrqNbt27U1NRUrTNmzBgOPfRQ9tlnHwDmzp3L66+/\nziabbLJU664/HNCU+iBSzQ477ADAyy+/TK9evYB0/sKkSZMajt1vt912nHTSSXz88ccN5wXcc889\n9OrVi/XWW6/ZfV2wYAERwUcffbTIsiuuuIIDDzxwkdkUM7PFKeScgIg4G7gGeEHSx8CzwJ8i4vdZ\nlZ5AAFMqXjolWwbQA5gfEe81UceWM9/+9rfp0aMH3/jGNxg9ejRvvvkmo0eP5ic/+UnD4YCNN96Y\nW265hSeffJJnn32WIUOGVP0wbKn6wwFNPdZYY41GX7/RRhux9957M2zYMB5++GFeeOEFvvvd79Kj\nRw+++tWvAjScrX/YYYfx/PPPc/PNN3P22WdzwgknNLTz73//m/79+/P4448D8Prrr3POOefwxBNP\n8M477/Dwww/zzW9+ky5duvC1r31toT489NBDvPDCCxx55JFLvT3MrHwKmQmQdBAwBDgIeAHYHLhI\n0hsR8cci1tGYCXVXN/y9pu9Aavpu1kRta02SWly28sorM3r0aE466SQOPPBAZsyYQa9evRg8eDBd\nu3YF4Pzzz+eII45g5513pmvXrvzoRz9aJAQ0d91Fu+aaa/jxj3/M3nvvTUSw4447ct999zUct6+p\nqWHUqFEce+yxbLPNNnTt2pWf/vSn/OhHP2poY/bs2bzyyivMnj0bSOGkrq6O888/n/fff58ePXqw\n884788gjj9C9e/eF1v+HP/yBAQMGsO2227b6WM1s2aurq6Ourq7V2lcR59tJehs4JyIuyZX9nHR8\nf+PscMDrwDYRMS5X5w5gWkR8V9Jg4F6ge342QNJzwN8iYkSV9cag4Xctdf/rjTtzbz6Z9zFFtjl2\n5J6FtHfTH44AYP8j/sDYkXsucvzczMyWf5KIiMK+4RR1n4BVgMozsBbUtx8RbwCTgd3qF0rqAuwE\njMmKxgGfVNTpA/TP1TEzM7OCFHVi4O3ASZLeBJ4HtiRdDvinXJ0LgJMlvQy8CvwCmAlcCxARH0i6\nAjhH0jQRsD8RAAAU7klEQVTSJYLnAU8BjV/sbWZmZkukqBBwHHA6cCnQHZgE/D4rAyAizsm+/V8C\ndAXGArvn7hEA6TLCecB1wMqkwwNDfI8AMzOz4hUSArIP8h9nj6bqjQRGNrF8HikIDCuiX2ZmZtY4\n/3aAmZlZSTkEmJmZlZRDgJmZWUk5BJiZmZWUQ4CZmVlJOQSYmZmVlEOAmZlZSTkEmJmZlZRDgJmZ\nWUk5BJiZmZWUQ4CZmVlJOQSYmZmVlEOAmZlZSTkEmJmZlZRDgJmZWUk5BJiZmZWUQ4CZmVlJOQSY\nmZmVlEOAmZlZSTkEmJmZlZRDgJmZWUk5BJiZmZWUQ4CZmVlJOQSYmZmVlEOAmZlZSTkEmJmZlZRD\ngJmZWUk5BJiZmZWUQ4CZmVlJOQSYmZmVlEOAmZlZSTkEmJmZlZRDgJmZWUk5BJiZmZWUQ4CZmVlJ\nOQSYmZmVlEOAmZlZSRUWAiT1lPQnSVMlzZH0nKSdKuqcJuldSbMlPSBp04rlK0m6WNI0SbMk3Sap\nd1F9NDMzs08VEgIkrQ6MAQL4CvB54AfA1FydE4HjgWOBrbNloyStmmvqQmBf4FvAjkANcIckFdFP\nMzMz+1Tngto5EZgYEd/Nlb1VUWcYcGZE3AogaSgpCBwCXC6pBjgcGBoR92d1hmTt7AqMKqivHZ46\nrUjRuWjt3uswccLbhbZpZmbtW1Eh4BvAnZKuAwYDE4E/RMSlAJLWB3qS+yCPiLmSRgPbA5eTZgc6\nV9SZIOnFrI5DQCbmz2PQ8LsKbXPsyD0Lbc/MzNq/os4J6AccA7wO7A5cAJwl6ZhseU/SoYIpFa+b\nki0D6AHMj4j3mqhjZmZmBSlqJmAF4LGI+Hn2/GlJG5OO//+moHVUNaHu6oa/1/QdSE3fzVpzdWZm\nZstMXV0ddXV1rdZ+USFgEvBiRdmLwA+zv08GRPq2PyFXp0e2rL5OJ0ndKmYDegCjG1txn9ohS9Ft\nMzOz9qu2tpba2tqG5yNGjCi0/aIOB4wBNqko24Ts5MCIeIP0Ib9b/UJJXYCdstcCjAM+qajTB+if\nq2NmZmYFKWom4NfAGEmnANcDW5IuETwpV+cC4GRJLwOvAr8AZgLXAkTEB5KuAM6RNA2YDpwHPAXc\nV1A/zczMLFNICIiIxyXtA5xJ+nB/G/h5RPwuV+ec7Nv/JUBXYCywe0R8mGtqGDAPuA5YGbgXGBIR\nUUQ/zczM7FNFzQQQEXcCdy6mzkhgZBPL55GCwLCi+mVmZmbV+bcDzMzMSsohwMzMrKQcAszMzErK\nIcDMzKykHALMzMxKyiHAzMyspBwCzMzMSsohwMzMrKQcAszMzErKIcDMzKykHALMzMxKyiHAzMys\npBwCzMzMSsohwMzMrKQcAszMzErKIcDMzKykHALMzMxKyiHAzMyspBwCzMzMSsohwMzMrKQcAszM\nzErKIcDMzKykHALMzMxKyiHAzMyspBwCzMzMSsohwMzMrKQcAszMzErKIcDMzKykHALMzMxKyiHA\nzMyspBwCzMzMSsohwMzMrKQcAszMzErKIcDMzKykHALMzMxKyiHAzMyspFolBEg6WdICSRdVlJ8m\n6V1JsyU9IGnTiuUrSbpY0jRJsyTdJql3a/TRzMys7AoPAZK2BY4Enq4oPxE4HjgW2BqYCoyStGqu\n2oXAvsC3gB2BGuAOSSq6n2ZmZmVXaAiQtDpwDfBd4P2KxcOAMyPi1oh4ARgKfBY4JHttDXA48JOI\nuD8ingKGAAOBXYvsp5mZmRU/E3AZcENE/CtfKGl9oCcwqr4sIuYCo4Hts6Ktgc4VdSYAL+bqmJmZ\nWUE6F9WQpCOBfsDBVRb3BAKYUlE+BeiV/b0HMD8i3qtSp2dR/TQzM7OkkBAgaWPgDGCHiFhQRJtm\nZmbWuoqaCdgO6Aa8kDuHrxOws6SjgS8AIn3bn5B7XQ9gcvb3yUAnSd0qZgN6kA4bVDWh7uqGv9f0\nHUhN382WbiQlpU4rUvT5l2v3XoeJE94utE0zszKpq6ujrq6u1dovKgTcAvy7ouxPwCvAGRHxiqTJ\nwG7AOABJXYCdgBOy+uOAT7I612V1+gD9gTGNrbhP7ZCChlBuMX8eg4bfVWibY0fuWWh7ZmZlU1tb\nS21tbcPzESNGFNp+ISEgIj4AXsiXSfoQmB4RL2ZFFwAnS3oZeBX4BTATuLa+DUlXAOdImgZMB84D\nngLuK6KfZmZm9qnCTgysIhZ6EnFO9u3/EqArMBbYPSI+zFUbBswjzQSsDNwLDImIhdoyMzOzpddq\nISAivlSlbCQwsonXzCMFgWGt1S8zMzNL/NsBZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl\n5RBgZmZWUg4BZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJeUQYGZm\nVlIOAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIOAWZmZiXlEGBmZlZSDgFm\nZmYl5RBgZmZWUg4B1mrUaUUkFfro1Wfdth6Wmdlyo3Nbd8CWXzF/HoOG31Vom2NH7lloe2ZmZeaZ\nADMzs5JyCDAzMysphwAzM7OScggwMzMrKYcAMzOzknIIMDMzKymHADMzs5JyCDAzMysphwAzM7OS\ncggwMzMrKYcAMzOzkiokBEg6WdJjkmZImirp75IGVKl3mqR3Jc2W9ICkTSuWryTpYknTJM2SdJuk\n3kX00czMzBZW1EzAzsAlwHbAYOAT4F5Ja9RXkHQicDxwLLA1MBUYJWnVXDsXAvsC3wJ2BGqAOySp\noH6amZlZppBfEYyIr+SfSxoCzAB2AP6RFQ8DzoyIW7M6Q0lB4BDgckk1wOHA0Ii4P9fOW8CuwKgi\n+mpmZmZJa50TUJO1/V8ASesDPcl9kEfEXGA0sH1WtDUplOTrTABezNUxMzOzgrRWCLgQeAJ4JHve\nEwhgSkW9KdkygB7A/Ih4r4k6ZmZmVpBCDgfkSTqf9M19h4iIots3MzOzYhQaAiT9GjgQqI2It3KL\nJgMifdufkCvvkS2rr9NJUreK2YAepMMGVU2ou7rh7zV9B1LTd7OlGoOZmVl7UVdXR11dXau1X1gI\nkHQh8E1SAHg1vywi3pA0GdgNGJfV7wLsBJyQVRtHuqpgN+C6rE4foD8wprH19qkdUtQQzMzM2pXa\n2lpqa2sbno8YMaLQ9gsJAZIuBb4DfAOYIalHtmhWRHyY/f0C4GRJLwOvAr8AZgLXAkTEB5KuAM6R\nNA2YDpwHPAXcV0Q/zczM7FNFzQR8n3TiX+WH9QhgJEBEnJN9+78E6AqMBXbPhQRIlxHOI80ErAzc\nCwzxuQVmZmbFK+o+Ac26yiAiRpKFgkaWzyMFgWFF9MvMzMwa598OMDMzKymHADMzs5JyCDAzMysp\nhwDrUNRpRSQV+ujVZ922HpaZWZso/I6BZq0p5s9j0PC7Cm1z7Mg9C23PzKyj8EyAmZlZSTkEmJmZ\nlZRDgJmZWUk5BJiZmZWUQ4CZmVlJOQSYmZmVlEOAmZlZSTkEmJmZlZRDgJVe0Xch9B0Izayj8B0D\nrfSKvguh70BoZh2FZwLMzMxKyiHAzMyspBwCzMzMSsohwMzMrKQcAszMzErKIcDMzKykHALMzMxK\nyiHArGBF33zINyAys9bimwWZFazomw+Bb0BkZq3DMwFmZmYl5RBgZmZWUg4BZmZmJeUQYGZmVlIO\nAWZmZiXlEGBmZlZSDgFmZmYl5RBgZmZWUg4BZh2A70JoZq3Bdww06wBa4y6Ej53xdSQV2ubavddh\n4oS3C23TzFqPQ4BZSfn2xmbmwwFmZmYl5RBgZmZWUu0yBEg6RtJ4SXMkPS5px7buk5ktnk9gNOtY\n2t05AZK+BVwAHA2MAY4F7pTUPyImtGnnzKxJPs/ArGNpjzMBxwNXRsSVEfFyRPwQmAR8v4371So+\nePPptu5CITyO9mN5GAMsH+Ooq6tr6y4UwuNYfrWrECBpRWArYFTFonuA7Zd9j1rfB28+09ZdKITH\n0X4sD2OAT8fRGocYOn9m5WVyyGJ5+dDxOJZf7e1wwOeATsCUivIpwJeXfXfMrK211iGGItts6p4L\nI0aMWKI2fc8FWxbaWwhosXdvOb2wtiKisLbMrDwaCyoT6q6mT+2QJWrTN3MqVq8+6zLp3XeWOJRV\nWl62pdrTB192OGA2cFBE3JQrvwQYEBGDK+q3n86bmZktAxFRWDpsVzMBETFP0jhgN+Cm3KLdgL9V\nqV9sTDYzMyuRdhUCMucDf5b0b9Ilgt8H1gZ+36a9MjMzW860uxAQETdIWhP4OenD/zngKxHxTtv2\nzMzMbPnSrs4JMDMzs2WnXd0noLk60m2FJZ0qaUHFY2JFndMkvStptqQHJG3aVv3N9WknSbdJmpD1\n+dAqdZrst6SVJF0saZqkWVl7vZfdKBY/Dkl/rLJ/Hm5P45B0sqTHJM2QNFXS3yUNqFKv3e6P5oyh\ng+yLYyQ9nY1jhqSHJe1VUafd7ofmjqMj7ItK2XtsgaSLKsrb/f7I9WWRMbT2vuhwIUCf3lb4l8Dm\nwMOk2wr3adOONe0loAfQM3t8sX6BpBNJd0k8FtgamAqMkrRqG/QzbzXgWeCHpCs2FtLMfl8I7At8\nC9gRqAHukAq+7qlpTY4jM4qF989eFcvbehw7A5cA2wGDgU+AeyWtUV+hA+yPxY4h0973xTvAz4At\nSDc2ux+4VdIXoEPsh3pNjiPT3vdFA0nbAkcCT1eUd5T90egYMq23LyKiQz2AR4HfVZS9ApzR1n1r\npL+nAs80sXwicFLueRfgA+DItu57rk8zgUNb0u/sTfgR6XLP+jp9gPnAbu1oHH8E/t7Ea9rjOFYl\nfYh+taPuj0bG0OH2RdaH93LbuUPthybG0WH2BbA68BqwC/AAcFFuWYfYH4sZQ6vuiw41E6COe1vh\nftl01HhJ10paHyD7sye58UTEXGA07Xg8zez31qQTT/N1JgAv0v7GtqOkKZJelnSZpLVyy7ai/Y2j\nhjSL91/osPtjoTHkdJh9IWkFSQeRAs2YDrofFhlHblFH2ReXATdExL/yhR1sf1QdQ06r7Yt2d3XA\nYnTE2wo/ChxGOiTQHfg/0n8YA0hv0KD6eHotwz62VHP63QOYHxHvVanTs3W71yJ3ku5J8QbQFzgD\nuF/SlhExj9TX9jaOC4EngEey5x1xf1SOATrIvsimzB8hfaucCewbES9I2o4OtB8aG0e2uKPsiyOB\nfsDBVRZ3iH8XixkDtPK+6GghoMOJiLvzzyU9StqZQ4GxbdIpaxARN+SePi/pCeAt4KvArW3Tq8ZJ\nOp+U7neIbN6vo2lsDB1oX7wEbEaawj2AdF+TXdq2S0uk6jgi4oWOsC8kbUz6QNwhIha0dX+WRHPG\n0Nr7okMdDgD+QzrO0aOivAcwedl3p+UiYjbwPLARqc+i442nOf2eDHSS1K2JOu1OREwCJpD2D7Sj\ncUj6NenEn8ER8VZuUYfZH02MYRHtdV9ExCcRMT4inoyInwNPkU4+6zD7AZocR7W67XFfbAd0A16Q\nNE/SPNIx9WMlfUw6x6G9748mx5AdAl9I0fuiQ4WAbOqj/rbCebux8LGsdktSF+DzwMSIeIO0k3ar\nWL4T7Xg8zez3ONKJX/k6fYD+tOOxZcfaegOTsqJ2MQ5JF/Lph+er+WUdZX80NYZG6rfLfVHFCsBn\nOsp+aMIKwGeqLWin++IW0pVWm+UejwPXAptFxCu0//2xuDHMq3xB4ftiWZ39WOBZlAcCc4H/JX2Y\nXkg623Odtu5bI/39FenyqL7AIOAO4P36/pIu0/kv6fKOLwDXkVLeqm3c71WzN+TmwIfAL7Lnze43\n8BvgbdL5GluQLkMaR3aTqrYeR7bsV8C2wHpALemS07fa0ziAS4EZWf965B75Prbr/bG4MXSgfXEm\n6RKs9bLtfCbpP+DdO8J+aM44Osq+aGRclWfWd4j90dgYlsW+aJMdVcBGOhoYD8wB/k06ntLm/Wqk\nr9dmb7q5pGtz/wZ8vqLOcOBd0nXsDwCbtoN+7wIsIB1+yT+ubG6/gRVJIW0aMIt0/Kp3exkH6YSo\nu0jfFuaSztW4orKPbT2ORvo/HxjekvdRW45jcWPoQPvij1nf5mR9vQfYtaPsh+aMo6Psi0bGdT+5\nENBR9kdjY1gW+8K3DTYzMyupDnVOgJmZmRXHIcDMzKykHALMzMxKyiHAzMyspBwCzMzMSsohwMzM\nrKQcAszMzErKIcDMlilJ60laIGnLtu6LWdk5BJgtpyT9UdLf22kffJcys3bAIcDM2oLaugNm5hBg\nVkqSaiRdJmmKpA8kPSBpq9zyoZJmSvqSpGclzZJ0v6T1Kto5WdJkSTMkXSHp/yS9kS07FRgKfDWb\n/p8vaefcy/tKukfSh5Kel7TrMhm8mTVwCDArp38CPYG9SL+wOBq4T1L+t9c/A5wEHEb6FbM1gN/V\nL5R0EOnHWU4GtgJeBX7Mp1P95wI3APeSfjFwbdIvoNX7JXABMJD0Q2DXSlqlwDGa2WI4BJiVjKQv\nkT54vxkR4yJifEScSvqFsiG5qp2AY7I6z5E+1Gtzy39I+lXJP0bEaxFxFvBY/cKI+JD0K3UfRcS0\niJgaEZ/kXn9+RPwzIl4HTgG6kQKJmS0jDgFm5bMl6XfK/5NN+c+UNBMYAGyQq/dRRLyWez4RWEnS\nGtnzz5O+weeNbUE/nq3/S0RMzP7avQWvN7Ol1LmtO2Bmy9wKpN8n35FFT9D7IPf3TyqW1U/zF/Xl\nYV6VMn8xMVuGHALMyucJ0jH6iIg3lqKdl4BtgD/lygZV1PmYdFjBzNohhwCz5VuNpM0qyl4DxgC3\nSTqR9GG+NrAHMCoixjTRXn7m4ELgSkmPAw8C+wH/A0zP1XkT2FPSxsB7wIylGIuZFcwhwGz5thPp\nm3/eTaSrAn4JXEY6Dj+FFAyuWkx7DTf5iYjrJa0PnAmsAtxMunpg71z9y4FdgMdJ5yEMBt6i+s2C\nfAMhs2VMEf53Z2bFkHQz0CkivtHWfTGzxfNMgJktEUkrA98H7gLmA/uTZgH2a8t+mVnzeSbAzJaI\npC7A7aRr+1cm3SzorIi4vk07ZmbN5hBgZmZWUr4m18zMrKQcAszMzErKIcDMzKykHALMzMxKyiHA\nzMyspBwCzMzMSur/Azfki/ehAvQDAAAAAElFTkSuQmCC\n"
     },
     "output_type": "display_data",
     "metadata": {}
    }
   ],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Document lengths.\n",
    "lens = [len(doc) for doc in wmd_corpus]\n",
    "\n",
    "# Plot.\n",
    "plt.rc('figure', figsize=(8,6))\n",
    "plt.rc('font', size=14)\n",
    "plt.rc('lines', linewidth=2)\n",
    "plt.rc('axes', color_cycle=('#377eb8','#e41a1c','#4daf4a',\n",
    "                            '#984ea3','#ff7f00','#ffff33'))\n",
    "# Histogram.\n",
    "plt.hist(lens, bins=20)\n",
    "plt.hold(True)\n",
    "# Average length.\n",
    "avg_len = sum(lens) / float(len(lens))\n",
    "plt.axvline(avg_len, color='#e41a1c')\n",
    "plt.hold(False)\n",
    "plt.title('Histogram of document lengths.')\n",
    "plt.xlabel('Length')\n",
    "plt.text(100, 800, 'mean = %.2f' % avg_len)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we want to initialize the similarity class with a corpus and a word2vec model (which provides the embeddings and the `wmdistance` method itself)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Train Word2Vec on all the restaurants.\n",
    "model = Word2Vec(w2v_corpus, workers=3, size=100)\n",
    "\n",
    "# Initialize WmdSimilarity.\n",
    "from gensim.similarities import WmdSimilarity\n",
    "num_best = 10\n",
    "instance = WmdSimilarity(wmd_corpus, model, num_best=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `num_best` parameter decides how many results the queries return. Now let's try making a query. The output is a list of indeces and similarities of documents in the corpus, sorted by similarity.\n",
    "\n",
    "Note that the output format is slightly different when `num_best` is `None` (i.e. not assigned). In this case, you get an array of similarities, corresponding to each of the documents in the corpus.\n",
    "\n",
    "The query below is taken directly from one of the reviews in the corpus. Let's see if there are other reviews that are similar to this one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cell took 51.17 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "start = time()\n",
    "\n",
    "sent = 'Very good, you should seat outdoor.'\n",
    "query = preprocess(sent)\n",
    "\n",
    "sims = instance[query]  # A query is simply a \"look-up\" in the similarity class.\n",
    "\n",
    "print 'Cell took %.2f seconds to run.' %(time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The query and the most similar documents, together with the similarities, are printed below. We see that the retrieved documents are discussing the same thing as the query, although using different words. The query talks about getting a seat \"outdoor\", while the results talk about sitting \"outside\", and one of them says the restaurant has a \"nice view\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Query:\n",
      "Very good, you should seat outdoor.\n",
      "\n",
      "sim = 1.0000\n",
      "Very good, you should seat outdoor.\n",
      "\n",
      "sim = 0.5998\n",
      "It's a great place if you can sit outside in good weather.\n",
      "\n",
      "sim = 0.5798\n",
      "It was good I like the outside\n",
      "\n",
      "sim = 0.5495\n",
      "Always a good bet.\n",
      "\n",
      "sim = 0.5478\n",
      "Sat outside under heat lamps.  Good service and good food.  Wonderful place\n",
      "\n",
      "sim = 0.5474\n",
      "Patio is awesome but can get crowded.\n",
      "\n",
      "sim = 0.5464\n",
      "The steak was good. Prices reasonable for the strip and it was a great view with the outdoor seating.\n",
      "\n",
      "sim = 0.5453\n",
      "Best seat in the house with view of water fountain, good wine, good food n good service.\n",
      "\n",
      "sim = 0.5443\n",
      "nice view, good service\n",
      "\n",
      "sim = 0.5403\n",
      "Good value restaurant on strip! \n",
      "Great view take outside seat good food!\n",
      "However, be sure you make reservation!\n"
     ]
    }
   ],
   "source": [
    "# Print the query and the retrieved documents, together with their similarities.\n",
    "print 'Query:'\n",
    "print sent\n",
    "for i in range(num_best):\n",
    "    print\n",
    "    print 'sim = %.4f' % sims[i][1]\n",
    "    print documents[sims[i][0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try a different query, also taken directly from one of the reviews in the corpus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Query:\n",
      "I felt that the prices were extremely reasonable for the Strip\n",
      "\n",
      "sim = 0.5691\n",
      "Reasonable prices. Makes for a nice dinner out in the town.\n",
      "\n",
      "sim = 0.5485\n",
      "The steak was good. Prices reasonable for the strip and it was a great view with the outdoor seating.\n",
      "\n",
      "sim = 0.5457\n",
      "Exceptional food at reasonable prices.  Reservations are a must.\n",
      "\n",
      "sim = 0.5378\n",
      "Good food, great atmosphere, reasonable prices.  Right in the middle of the Strip.  Nothing not to like here.\n",
      "\n",
      "sim = 0.5376\n",
      "Incredible restaurant on the strip! Very reasonable prices, outstanding service, an breathtaking views. Bar none, my favorite meal on the Strip.\n",
      "\n",
      "sim = 0.5346\n",
      "don't let the tourist location throw you. terrific French food on the strip without the strip prices.\n",
      "\n",
      "sim = 0.5334\n",
      "Had lunch here, food price was very reasonable for vegas and the atmosphere was great.\n",
      "\n",
      "sim = 0.5278\n",
      "Nice place to take a date at a reasonable price.\n",
      "\n",
      "sim = 0.5264\n",
      "Really good food at decent prices (for being on the strip).  Not a traditional steakhouse but just as good as many of them.  Sitting out on the strip is very nice at nighttime.\n",
      "\n",
      "sim = 0.5253\n",
      "Great value on the strip and good quality food.\n",
      "\n",
      "Cell took 62.98 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "start = time()\n",
    "\n",
    "sent = 'I felt that the prices were extremely reasonable for the Strip'\n",
    "query = preprocess(sent)\n",
    "\n",
    "sims = instance[query]  # A query is simply a \"look-up\" in the similarity class.\n",
    "\n",
    "print 'Query:'\n",
    "print sent\n",
    "for i in range(num_best):\n",
    "    print\n",
    "    print 'sim = %.4f' % sims[i][1]\n",
    "    print documents[sims[i][0]]\n",
    "\n",
    "print '\\nCell took %.2f seconds to run.' %(time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This time around, the results are more straight forward; the retrieved documents basically contain the same words as the query.\n",
    "\n",
    "`WmdSimilarity` normalizes the word embeddings by default (using `init_sims()`, as explained before), but you can overwrite this behaviour by calling `WmdSimilarity` with `normalize_w2v_and_replace=False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Notebook took 181.05 seconds to run.\n"
     ]
    }
   ],
   "source": [
    "print 'Notebook took %.2f seconds to run.' %(time() - start_nb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "1. Ofir Pele and Michael Werman, *A linear time histogram metric for improved SIFT matching*, 2008.\n",
    "* Ofir Pele and Michael Werman, *Fast and robust earth mover's distances*, 2009.\n",
    "* Matt Kusner et al. *From Embeddings To Document Distances*, 2015.\n",
    "* Thomas Mikolov et al. *Efficient Estimation of Word Representations in Vector Space*, 2013."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}