{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem Set 1: Text Classification\n",
    "=============\n",
    "\n",
    "In this problem set, you will build a system for automatically classifying reddit comments by subreddit. You will:\n",
    "\n",
    "- Do some basic text processing, tokenizing your input and converting it into a bag-of-words representation\n",
    "- Build a machine learning classifier based on the generative model, using Naive Bayes\n",
    "- Evaluate your classifiers and examine what they have learned\n",
    "- Build a machine learning classifier based on the discriminative model, using Perceptron\n",
    "- Build more stable discriminative classifier, using the averaged perceptron\n",
    "- Build the logistic regression classifier (See instructions within the section)\n",
    "- Implement techniques to improve your classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 0. Setup\n",
    "\n",
    "In order to develop this assignment, you will need the following libraries. Many of these are part of [anaconda](https://www.continuum.io/downloads), so a good starting point would be to install that.\n",
    "\n",
    "- [python 2.7](https://www.python.org/downloads/release/python-2710/) (and not Python 3, although if somebody wants to try that and tell us what goes wrong, that would be appreciated...)\n",
    "- [jupyter notebook](http://jupyter.readthedocs.org/en/latest/install.html)\n",
    "- [scipy](http://www.scipy.org/install.html)\n",
    "- numpy (This will come if you install scipy like above, but if not install separately)\n",
    "- [nltk](http://www.nltk.org/install.html) (tested on NLTK 3.0.4)\n",
    "- [matplotlib](http://matplotlib.org/users/installing.html)\n",
    "- [nosetests](https://nose.readthedocs.org/en/latest/)\n",
    "- [pandas](http://pandas.pydata.org/) Dataframes\n",
    "\n",
    "Here is some help on installing packages in python: https://packaging.python.org/installing/\n",
    "\n",
    "I generally use ```pip --user``` for everything."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## About this assignment\n",
    "\n",
    "- This is a Jupyter notebook. You can execute cell blocks by pressing control-enter.\n",
    "- Most of your coding will be in the python source files in the directory ```gtnlplib```.\n",
    "- **To submit this assignment, run the script ```make-submission.sh```, and submit the tarball ```pset1-submission.tgz``` on T-square.**\n",
    "\n",
    "Grading will be mostly based on automated unit testing.\n",
    "\n",
    "- The directory ```tests``` contains unit tests that are very similar to the tests that will be used to grade your assignment --- but not the same! \n",
    "- You should run these tests as you work on the assignment to see that you're on the right track. If you pass them in a non-adversarial way (i.e., you didn't write functions that target these tests directly), you will pass the tests that we use for grading. \n",
    "- Parts 1 and 2 are the foundation for the rest of the assignment. Don't even try to work on the later parts of the assignment until your code passes all tests for parts 1 and 2.\n",
    "- The same is largely true within each part: for example, do not move on to deliverable 4.2 until your code passes the test for deliverable 4.1.\n",
    "- You are free to look at the source code of the unit tests -- though most of the relevant code is also here in this notebook. Learn more about running unit tests at http://pythontesting.net/framework/nose/nose-introduction/\n",
    "- You may want to add more tests, but that is completely optional.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Preprocessing\n",
    "\n",
    "Total: 1 point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "df_tr = pd.read_csv('reddit-train.csv',encoding='utf-8') # read the training data into a data frame\n",
    "df_dv = pd.read_csv('reddit-dev.csv',encoding='utf-8') # read the dev data into a data frame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A dataframe is a structured representation of your data. You can preview your dataframes using ```head()```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>subreddit</th>\n",
       "      <th>text</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>science</td>\n",
       "      <td>Why don't you bother instead and respond prope...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>iama</td>\n",
       "      <td>AAIA's ACES is the database standard (http://w...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>iama</td>\n",
       "      <td>So many.  I needed to perform a maintenance ru...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>worldnews</td>\n",
       "      <td>Ukraine used to be part of Russia in the Sovie...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>worldnews</td>\n",
       "      <td>This wiki article goes into how contentious th...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   subreddit                                               text\n",
       "0    science  Why don't you bother instead and respond prope...\n",
       "1       iama  AAIA's ACES is the database standard (http://w...\n",
       "2       iama  So many.  I needed to perform a maintenance ru...\n",
       "3  worldnews  Ukraine used to be part of Russia in the Sovie...\n",
       "4  worldnews  This wiki article goes into how contentious th..."
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_tr.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your first task is to convert the text to a bag-of-words representation. There are three steps:\n",
    "\n",
    "- Break each input into sentences\n",
    "- Break each sentence into word \"tokens\"\n",
    "- Downcase each token, and add it to a Counter\n",
    "\n",
    "You should use NLTK to complete the tokenization step, and collections.Counter for the bag of words representation. For more about NLTK tokenization, see http://www.nltk.org/book/ch03.html\n",
    "\n",
    "**Deliverable 1.1** Complete the function ```gtnlplib.preproc.tokenize_and_downcase```. (0.5 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib import preproc\n",
    "reload(preproc); #terminal semicolon suppresses output\n",
    "\n",
    "# when you edit gtnlplib/preproc.py, you will need to reload it into the notebook, using the line above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# this will not work until you implement it\n",
    "y_tr,x_tr = preproc.read_data('reddit-train.csv', #filename\n",
    "                                       'subreddit', #label field\n",
    "                                       preprocessor=preproc.tokenize_and_downcase) #your preprocessor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "y_dv,x_dv = preproc.read_data('reddit-dev.csv', #filename\n",
    "                                       'subreddit', #label field\n",
    "                                       preprocessor=preproc.tokenize_and_downcase) #your preprocessor\n",
    "y_te,x_te = preproc.read_data('reddit-test.csv', #filename\n",
    "                                       'subreddit', #label field\n",
    "                                       preprocessor=preproc.tokenize_and_downcase) #your preprocessor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Each element in the list ```x_tr``` is a counter, which corresponds to a bag of words.\n",
    "- Each element in the list ```y_tr``` is a string, corresponding to a label."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ORIGINAL TEXT:  I saw an article recently stating that there was a link between angiotensin converting enzymes and Alzheimer's. It said that ACE was partially responsible for the break down of the protein fibers and plaques that form in Alzheimer's. To your knowledge, is there any truth to this and if so, is there a correlation between the prevalence of Alzheimer's and the use of ACE inhibitors in the last few decades?\n",
      "\n",
      "Thank you for the work that you do! I am glad there are much smarter people than I working on research for these cognitive issues. \n",
      "\n",
      "\n",
      "EDIT: I'm really sad I missed this AMA. \n",
      "\n",
      "BAG OF WORDS:  Counter({u'the': 6, u'i': 5, u'and': 4, u'there': 4, u'.': 4, u'that': 4, u'alzheimer': 3, u'for': 3, u'of': 3, u\"'s\": 3, u'this': 2, u'is': 2, u'in': 2, u',': 2, u'to': 2, u'between': 2, u'you': 2, u'was': 2, u'a': 2, u'ace': 2, u'responsible': 1, u'few': 1, u'prevalence': 1, u'edit': 1, u'am': 1, u'it': 1, u'an': 1, u'down': 1, u'really': 1, u'ama': 1, u'are': 1, u'research': 1, u'converting': 1, u'protein': 1, u'inhibitors': 1, u'saw': 1, u'your': 1, u'issues': 1, u'if': 1, u'!': 1, u'people': 1, u'use': 1, u'said': 1, u'knowledge': 1, u'angiotensin': 1, u'fibers': 1, u'plaques': 1, u'much': 1, u':': 1, u'?': 1, u'missed': 1, u'do': 1, u'working': 1, u'recently': 1, u'cognitive': 1, u'form': 1, u'any': 1, u'smarter': 1, u'break': 1, u'article': 1, u\"'m\": 1, u'sad': 1, u'than': 1, u'glad': 1, u'partially': 1, u'on': 1, u'last': 1, u'work': 1, u'enzymes': 1, u'so': 1, u'these': 1, u'truth': 1, u'correlation': 1, u'thank': 1, u'link': 1, u'stating': 1, u'decades': 1})\n"
     ]
    }
   ],
   "source": [
    "i = 100\n",
    "print 'ORIGINAL TEXT: ',df_tr.loc[i]['text']\n",
    "print \n",
    "print 'BAG OF WORDS: ',x_tr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should now be able to pass the first test, ```test_preproc_d1_1```. \n",
    "Try this by running the following code on the command line:\n",
    "\n",
    "```nosetests -v tests/test_pset1_preproc.py```\n",
    "\n",
    "Now let's aggregate these counts, by running the code block below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "corpus_counts = preproc.get_corpus_counts(x_tr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This makes it possible to see the top K most common terms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(u'.', 22920),\n",
       " (u'the', 20303),\n",
       " (u',', 19036),\n",
       " (u'to', 13252),\n",
       " (u'and', 11552)]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "corpus_counts.most_common(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Word count distributions are said to follow [power law](https://en.wikipedia.org/wiki/Power_law) distributions. In practice, this means that a plot of the log-frequency against the log-rank is nearly linear. Let's see if this holds for our data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5.1\n"
     ]
    }
   ],
   "source": [
    "# you need matplotlib version 1.4 or above\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "print matplotlib.__version__\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAETCAYAAAAlCTHcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHp1JREFUeJzt3XeUVeW5x/HvQ1FElChBk0u3IBaKRsECcRCk2FDBgr1G\nSQSvmAvGZRyIJmK86jVqFCJLowa5aNRoQIWFjgZNEAuiSL0YmogQDRGwjPDcP94zycnIzOw5bZ89\n5/dZa6+Z/Z6yH94lPL7d3B0REZG6NIo7ABERSQYlDBERiUQJQ0REIlHCEBGRSJQwREQkEiUMERGJ\nRAlDREQiyXvCMLPJZrbezBZUKx9kZovNbKmZjU0rP9bMXjGz+8zs+/mOT0REoilEC+NBYGB6gZk1\nAu5JlR8MDDezLqmXHfgM2BlYU4D4REQkgrwnDHefA3xarbgnsMzdV7p7JTAVGJJ6/yvufiJwHfCz\nfMcnIiLRxDWG0QZYnXa/JlWW7u/ATgWLSEREatUk7gCqM7PTCF1VLQndViIiUgTiShhrgfZp921T\nZbj7U8BTtX3YzLRjoohIBtzdMv1sobqkLHVVmQfsZ2YdzGwn4Gzgmfp8obvn9SovLy/IZ+t6b02v\n16e8elld90mtz0zrUvVZmPrMpKwQdZnNc5L2dz1bhZhWOwV4DehsZqvM7GJ33waMBGYCC4Gp7r6o\nPt87btw4Kioqch5vlbKysoJ8tq731vR6fcqrl2XzZ8tUIeoz07qs7TXVZ2avR6m3+pTlW6bPTMrf\n9YqKCsaNG1fr86OwXGSdQjMzT2LcxWrcuHE5+Y9JAtVn7qguc8vM8AR0SUkRi+P/6Boy1WfuqC6L\nS2JbGOXl5ZSVlek/KBGROlRUVFBRUcH48eOzamEkNmEkMW4RkTiVbJdUvge9RUQaCg16JzBuEZE4\nlWwLQ0RECiuxCUNdUiIi0ahLKoFxi4jESV1SIiJSEEoYIiISSWIThsYwRESi0RhGAuMWEYmTxjBE\nRKQglDBERCSSxCYMjWGIiESjMYwExi0iEieNYYiISEEoYYiISCRKGCIiEokShoiIRJLYhKFZUiIi\n0WiWVALjFhGJk2ZJiYhIQShhiIhIJEoYIiISiRKGiIhE0iTuADI1Zw7stlu4WrQIP5s1A8t4OEdE\nRGqT2FlSRx3lfPYZbN4Mn30Wrm3b/j2BVP+9Pq+1bBkSkIhIQ5HtLKnEtjAGDBhHWVkZZWVl/yz7\n6qt/JZD0RLKj3zdurP09W7bAuefCmDGw777x/TlFRLJVUVGRk3VriW1h5DvuDRvgV7+C++6DgQPh\nuuuga9e8PlJEJK+0DiNPWreGm26CFSugWzc4/ngYMgTmzo07MhGReChh1GH33WHsWPjgAxgwAM48\nE/r1g9mzIYGNMxGRjKlLqp4qK2HKFJgwISST66+Hk0+GRkq9IlLksu2SUsLI0Pbt8PTT8POfw5df\nwk9+AmedBU0SO41ARBo6JYyYucPMmfCLX8Dq1aH76sILNSVXRIqPEkYRefXVkDjmzIE+faBv33B1\n7w6NG8cdnYiUuqKfJWVmk81svZktqFY+yMwWm9lSMxtb7bXmZjbPzE7Id3y5dMwxMH06LF8OF10E\n//d/YS1H69Zw6qlw113w7ruhO0tEJGny3sIws97AZuBhd++WKmsELAX6AR8C84Cz3X1x6vXxwGfA\n++4+YwffWZQtjJqsWwcVFfDii/DSS7BpE5SVwbHHwl57wc477/hq1gw6dVLrRERyIxFdUmbWAXg2\nLWEcCZS7++DU/XWAu/utZtYfaAU0Aza6+/QdfF+iEkZ1q1eHxDFnDnz6aRg039G1ZUu4TjoprAEZ\nMACaN487ehFJqqRuDdIGWJ12vwbomfq9DGgOHAxsBb6RMJKuXTu44IJw1eWvf4VnnoG77w7v79s3\ndG/17w+77hqm86Zfu+yiDRhFJD+KbhKou98AYGYXABtjDid2HTvCqFHh+uQTmDED/vCHsFVJZWUY\nD6m6Kith8GB4/HFo2jTuyEWkoYkrYawF2qfdt02V/ZO7P1zbF6QfaF59E8KGas894bzzwrUjX30F\nQ4fC+efD736nsQ+RUperTQerFGoMoyNhDKNr6r4xsIQw6L0OeB0Y7u6LIn5foscw8umLL8KYR7t2\nMHmyVqCLyL8kYVrtFOA1oLOZrTKzi919GzASmAksBKZGTRZVxo0bl9PM2VA0axa6rJYtg6uv1n5X\nIhJaGum9MpnSwr0GatOmsEli//5wyy0aCBeRBLQw8kUtjNq1bAkvvBAGyXv0gJEj4X//F9aurfuz\nItKwqIWRwLjjUFkJb70Ff/pTuObMCdNxDz00XIcdBvvsA3vsEQbVd9kl7ohFJF8SsXAv15QwMrd9\ne9iyZP58ePvtcK1aFRYQfvJJ2G23Sxc45BA44gi48krNthJpKJK6cC9r48Z980xvqVujRrD//uE6\n44xvvr5pEyxaBO+9B7/8JXTuHE4bFJHk0pneCYw7af7nf0IL5Le/jTsSEckFdUlJ3nz0UeieWrs2\njHuISLJplpTkzXe+A0ceGfayEpHk0iypBMadRI8+Co89Fs75EJFkU5eU5NXmzdC2LSxdGs7uEJHk\nUpeU5FWLFmFvqmnT4o5ERDKlLqkExp1Uzz8P5eUwd27ckYhINkq2hSGF078/fPZZ2P1WREqXWhgS\nyeLF0KcPPPccHH543NGISCbUwpCC6NIF7r8fhg2DjSV/DqJIadLWIBLZ0KEwbx707AmnnBK2T2/b\nNizqa9dOGxeKFCttDZLAuBsCd3jjDZg1Cyoq4OOPw9Tbf/wDRoyAq66C1q3jjlJEdkTrMKQoLFkC\nd9wBv/89jBkTTvvbeee4oxKRdEoYUlSWLYPRo8PZG3vsEQ5y6tQJDj44zLY6/PCwtkNECk8JQ4rS\n+vWwdWs4Z2PFinCI0+zZ8O67YcyjUydo0waaN4d99w17VvXrp1aJSD6VbMIoLy/XoHcCuYdk8sEH\n8OGHIaksXRrGQ959Nwye9+gBF10UNj886CCdRy6SrapB7/Hjx5dmwkhi3FK7jRtDEpk1C554Atas\nCcnjxhvDz6ZN445QJNlKtoWRxLilfr76CiZMgKlTQ2tj1iwdFyuSDSUMafC2bYMBA8KA+YQJ6qIS\nyZQShpSE9eth0CA46ij49a/jjkYkmZQwpGRs3gwHHAAzZkD37nFHI5I82ktKSkaLFmFB4C9/GXck\nIqVJCUMS5YorYM4cmDQp7khESk9iE4ZO3CtNLVuGBYD//d/Qu3fYiuSNN6CyMu7IRIqXTtxLYNyS\nO19/HdZqTJ4cBsSXLw+bHrZuHY6ULS/XbCqR6jToLQJs2QIbNoTkcdVV0KQJHHggnHceHH00NGsW\nd4Qi8VPCEKnm88/D5ofvvw8PPRR20j3pJHjggdClJVKqlDBE6rB1K4waBe+9B2PHwmmnxR2RSDw0\nrVakDs2bw8SJcNllobvq+efjjkgkmdTCkJIya1aYmvvyy2FnXJFSohaGSD0cf3xIGD17hjM6RCQ6\ntTCkJD31FPzgB3DOOXDmmeEAJ+2EKw1d0bcwzGyyma03swXVygeZ2WIzW2pmY9PKu5jZfWY2zcyu\nzHd8UppOOw3mzg3HyP7oR7D33nDppWF8Q4sARXYs7y0MM+sNbAYedvduqbJGwFKgH/AhMA84290X\np33OgN+6+wU7+E61MCSnVq0Kq8Yff/xf03CPPBIuuCAcKSvSEBR9C8Pd5wCfVivuCSxz95XuXglM\nBYZUvWhmJwN/BGbkOz4RgPbt4Zpr4LXXYP78kCxmzQqL/j7+OO7oRIpDnQnDzFrl4bltgNVp92tS\nZQC4+7PufiJwXh6eLVKrdu1gxIjQ4jjpJOjXDzZtijsqkfhFaWH8xcweN7MTUt1EeWVmx5rZXWZ2\nPzA9388TqYkZ3HwzdO0KbdvCD3+oxCGlrUmE93QG+gOXAL8ys2nAQ+6+NIvnrgXap923TZXh7i8D\nL9f1Bek7L5aVlVFWVpZFOCI7ZgZTpsC6dTBmDHTrFrqu+vULiUSkmFVUVOR0V+96DXqbWV/gUWBX\n4B3gOnf/c4TPdQSedfeuqfvGwBLCoPc64HVguLsvihiHBr0lFnPnwj33hNlUo0eHleO77RZ3VCLR\n5H3Q28xamdnVZvYG8GNgJPBt4FpgSoTPTwFeAzqb2Sozu9jdt6W+ZyawEJgaNVlU0XkYEodeveCR\nR+C552DBgnBk7Jo1cUclUruCnYdhZkuBR4AH3X1NtdfGuvutWUdRT2phSLG4/Xa48cZwqFOvXjqD\nQ4pbti2MKGMYB9T0r3McyaLKuHHjNHYhsbv22nDW+AknhPGNM84ICwFFikmuxjKitDBmAWe4+99T\n93sQupAGZv30DKmFIcWmsjKcADh+PJx7Lvz0p3FHJPJNhVi417oqWQC4+6fAXpk+MFc0hiHFpGlT\nGD4cZs4MhzYdcwxs3Bh3VCJBIccw3gROc/dVqfsOwFPufljWT8+QWhhSzD7/PHRV/e53oaXx4x/H\nHZFIkPcT98xsEDCJsDbCgD7AD9z9hUwfmi0lDEmCJUvCFiM33RSm34rELe+D3u7+vJkdBhyZKvpP\nd4+9sa1Bbyl2BxwAL70EffqE3XHbtKn7MyL5ULBBbwAzawN0IC3BuPsrWT89Q2phSJJcf31Y7Lff\nfmFQ/PjjoVmzuKOSUlSILqlbgbMIC+y2p4rd3U/J9KHZUsKQpPn883Bo0z33wNq18OKLsO++cUcl\npaYQCWMJ0M3dv8z0IbmmhCFJdv/9YTB8woRwaJNIoRRiWu0KoGmmD8gXTauVpLrySnjllTB7SlNv\npRAKOa3290B3YDbwz1aGu4/K+ukZUgtDGoJLLw274D7yCLTKx6kzItUUooXxDHATYQPBN9MuEcnC\nLbeEw5p69AgtDpFiF3WW1C5Ae3dfkv+Q6qYWhjQkTz4Jl1wSzteYPBk6d447ImmoCrG9+cnAfOD5\n1H0PM3sm0wfmisYwpKE4/fQwljFoEPTtC3/6U9wRSUNT6K1BjgMq3P3QVNl77n5I1k/PkFoY0lBN\nnw5XXAH77BO2Tj/iiLgjkoakEGMYle5e/STj7Tt8p4hk5cQT4YMP4Jxz4LjjwkI//b+RFIsoCWOh\nmZ0DNDaz/c3sbsIAuIjkQdOmYertggWhxTF4MLymv3FSBKIkjJHAwYQptY8B/wD+M59BiQh06hRm\nTw0eHMY5Ro2CL76IOyopZZFmSRUbjWFIqVm/PoxtvPNO6KY66yzYeee4o5KkKcTWIC8B33iTux+X\n6UOzZWZeXl6u3Wql5FRUQHl5SCCvvw677x53RJIEVbvVjh8/Pu8J43tpt82AocDX7j4m04dmSy0M\nKWXucNFFsHAhTJoEh8V2lJkkTd5bGDU89HV375npQ7OlhCGlbvt2uPde+NnP4IQT4LbbYK/YD06W\nYleIhXt7pl3fNrOBQMtMHygi2WvUCEaOhOXLYdddw/Yijz0WEolIvkTpkvqAMIZhwNfAB8DP3H1O\n/sOrMSa1METSvPIKXH01HHgg3HxzWPgnUl3eWxju3snd90n93N/dB8SZLETkm77//XAc7Le/Dd27\nww9/CH//e9xRSUMTpYVxem2vu/uTOY0oArUwRGq2ciWMGQNz58KUKXD00XFHJMWiENNqpwNHAy+m\nivoSVnpvIBzVekmmD8+UEoZI3Z5+GkaMgIEDw9GwLVrEHZHErRB7STUFDnL3oe4+lLDqu6m7XxxH\nsqii3WpFanfqqbBkCZhB+/Zhu5H16+OOSuJQyN1qF7n7gWn3jYCF6WWFphaGSP2sXAk33hj2prrz\nzrC5YePGcUclhVaILql7gP0J+0gBnAUsd/eRmT40W0oYIpmZNy9sMbJ1KyxaFFofUjoKsnDPzE4D\nvp+6fcXdn8r0gbmghCGSOXdo0gRatgxjHJdeqmm4paIQYxgAbwHT3f0a4AUz2y3TB4pIvMygshJm\nzYK//Q0OPRRGj9ZOuFK3KCu9LweeACamitoAT+czKBHJr0aN4Hvfg/vvDzvgLlsWzhSfoxVWUoso\nLYwfAccQzsHA3ZcB2rVGpIHo2BGeeQauvx5OPhkOPzzshCtSXZSE8aW7f1V1Y2ZN2MF25yKSXGZw\n8cWwdm3YCXfwYHjuOR0PK/8uSsJ42cyuB3Yxs+OBx4Fn6/MQM5tsZuvNbEG18kFmttjMlprZ2LTy\nIWY2ycweSz1TRAqgeXO46iqYOBEuvBD22CPsUfW3v8UdmRSDKNNqGwGXAgMIGxC+ADxQn2lKZtYb\n2Aw87O7d0r53KdAP+BCYB5zt7ovTPvct4DZ3v7za92mWlEieucPbb4euqsWL4YknQneVJFdeZ0mZ\nWWPgEXf/jbuf4e7DUr/X61/r1GaFn1Yr7gksc/eV7l4JTAWGVHvPDcC99XmWiOSGWTic6bnn4Npr\nw55UZ50Fb70Vd2QSl1oThrtvAzqY2U55eHYbYHXa/ZpUGQBmNgGY4e7z8/BsEYnILJy9sWxZWK/R\np09IIFu2xB2ZFFqUMYwVwKtm9lMzG1115TMoMxtJ6KoaZmY/yOezRCSaDh3glltCN9X8+WEzw2HD\nYM2auCOTQmlS0wtm9oi7nw+cAtxJSC65XLC3Fmifdt82VYa73w3cXduH0zfSKisro6ysLIehiUhN\nOneG2bNDoigvD62Oyy8Px8Q2bx53dJKuoqIip5u01jjobWbvA/2B54Gy6q+7+yf1epBZR+BZd++a\num8MLCG0JNYBrwPD3X1RhO/SoLdIkXjrLbjmmvBz4sSwsaEUp3wOet8PzAY6A2+kXW+mftYnyCmE\nMzQ6m9kqM7s4NT4yEpgJLASmRkkWVbS9uUhxOOwwePllmDQJLrssrOF45524o5J0hdze/D53H5H1\nk3JILQyR4rRhA9xwQ0gep58ODzwQ1nJIcSjEmd5FlSxEpHi1bh26pdauhc2b4cAD4c9/jjsqyZWo\nu9UWHXVJiRSv//gPeOEFuO66sH7j0kth3bq4oypdBeuSKkbqkhJJjtWrw/GwM2bASSfBTTdBjx5x\nR1WaCnUeRtFRC0MkGdq1C0fDrlwJbdqE8zf69Amn/0lhqIWRwLhFBD75BG6+OZwt3qtXGPPo3j3u\nqEpDybYwRCSZ9twT7rgDPv00JIwePWD4cPjrX+OOTOqS2IShLimRZPvWt+Cuu8JOuJ9/Dp06hUSy\nbVvckTU86pJKYNwiUrMXXghrNxo1gl/8IpzLYRl3nsiOqEtKRBqEgQPD2o077wxncLRoERb+bd8e\nd2RSRS0MESk627bBvffC+PHQuDFMmwbaXzR7JdvC0BiGSMPVuDGMGhVWjI8YAX37wtCh2ko9UxrD\nSGDcIpKZxYvDmMbs2TB2bNivqkWLuKNKnmxbGEoYIpIYf/hDWDX+0Ufwl7+EabkSXcl2SYlI6Rky\nBFatgvPPhyOPDFuNfPRR3FGVjsQmDI1hiJSmpk3h4YfDMbFr1sB3vxuOjlWnQ800hpHAuEUk955+\nGk47DQ45BJ54Ag44IO6Iipe6pESkpJ16KmzcCK1aQZcucPjhsHx53FE1TEoYIpJ4rVrBSy/BihXw\n9dew//7h1L+vvoo7soZFCUNEGgSzsB/VvHnwk5/AFVdA796wfn3ckTUcShgi0qA0bRr2olq0CDZt\ngu98Bx58UFuM5EJiE4ZmSYlIbbp0gYULwxYj//VfYSru5s1xRxUPzZJKYNwiEo+5c0MX1ebNYfHf\nQQeV5k64miUlIlKHXr3g1VfhsMPC7zfcAB9/HHdUyaMWhoiUlCeeCEfEtmgBY8bAKafEHVHhaC8p\nEZF6WrEC7r47rBg/9FCYMQN22inuqPJPCUNEJANffx22FznnHNiwASZOhGHDwol/DZXGMEREMtCk\nSVgV/s478NOfhsRx0UWlO5MqisQmDE2rFZFc2GUXGD0a3n47nCu+995hB9xt2+KOLHc0rTaBcYtI\n8evdOySPMWPCivGGNLahMQwRkRx78kk499ywOvzDD8NeVQ2BEoaISJ4cdVTYYqRVK1iyJIx7JJkS\nhohInnzxBWzZAl27ho0N+/YNaziSKtuEkfB8KSKSP82ahWv2bHjjDbj22tDKGDgwtD5KjVoYIiIR\nVFbC7bfD66+H+5tvhn32CQklKdQlJSJSQG++CRdcEBb7jRoV9qVKCiUMEZEY/PrXcOut4Qzxq6+G\nE0+MO6K6Ff1KbzObbGbrzWxBtfJBZrbYzJaa2di08k5m9oCZTct3bCIimTr/fPjNb8Jg+OOPw7vv\nwsqVcUeVX3lvYZhZb2Az8LC7d0uVNQKWAv2AD4F5wNnuvjjtc9Pc/cwavlMtDBEpCi++GFoYAMuX\nw9atxXvWRtHPknL3OWbWoVpxT2CZu68EMLOpwBBgcfXPi4gUs+OOC60LgN13hxtvDKvDzz03DIo3\nJHHtJdUGWJ12vyZVlq5Ic7SIyI7dfnv4OX16ONmvoSm6dRhmtifwc6CHmY1191vjjklEJIrLLw8/\nmzSBhx4KM6r22gvuuCPWsHImroSxFmifdt82VYa7fwKMqOsL0ndeLCsro6ysLKcBiohk6rLLYN99\nw+8XXgi33QaNGxc+joqKipzu6l2QabVm1hF41t27pu4bA0sIg97rgNeB4e6+KOL3adBbRBKhZUsY\nOjTsfLv//vHGkoRptVOA14DOZrbKzC52923ASGAmsBCYGjVZVNF5GCKSBI8+Cr16hTPE46LzMBIY\nt4hInIq+hZEvamGIiESjFkYC4xYRiVPJtjBERKSwEpsw1CUlIhKNuqQSGLeISJzUJSUiIgWR2ISh\nLikRkWjUJZXAuEVE4qQuKRERKYjEJgx1SYmIRKMuqQTGLSISJ3VJiYhIQShhiIhIJEoYIiISSWIT\nhga9RUSi0aB3AuMWEYmTBr1FRKQglDBERCQSJQwREYkksQlDg94iItFo0DuBcYuIxEmD3iIiUhBK\nGCIiEokShoiIRKKEISIikShhiIhIJEoYIiISSWIThtZhiIhEo3UYCYxbRCROWochIiIFoYQhIiKR\nKGGIiEgkShgiIhKJEoaIiESihCEiIpEoYYiISCR5TxhmNtnM1pvZgmrlg8xssZktNbOxaeXNzewh\nM5toZufkOz4REYmmEC2MB4GB6QVm1gi4J1V+MDDczLqkXj4deNzdrwBOKUB8JU8r5nNL9Zk7qsvi\nkveE4e5zgE+rFfcElrn7SnevBKYCQ1KvtQVWp37flu/4RH8pc031mTuqy+IS1xhGG/6VFADWpMqq\nfm+b+j3jJezZyuY/1Pp8tq731vR6fcqrl8Xxl7AQ9ZlpXdb2muozs9ej1Ft9yvIt02eW2t/1Yhz0\nfhIYZmb3As/GFYQSRm4l8R+4mspVn3W/roRR//cm4e96QTYfNLMOwLPu3i11fyQwzt0Hpe6vA9zd\nb434fdp5UEQkA9lsPtgkl4HUwvj37qV5wH6pRLIOOBsYHvXLsvkDi4hIZgoxrXYK8BrQ2cxWmdnF\n7r4NGAnMBBYCU919Ub5jERGRzCXyPAwRESm8Yhz0FhGRIlS0CUMrxHMrg/rsZGYPmNm0wkdb3DKo\nyyFmNsnMHjOz4wsfcXHLoD67mNl9ZjbNzK4sfMTFrb71mXqtuZnNM7MTav1ydy/KC+gN9AAWpJU1\nApYDHYCmwHygS+q184ATU79PjTv+YrvqW59p75kWd+zFdmVRl98CfhN3/MV2ZVGfBjwcd/zFdmVS\nn8B44MfACbV9d9G2MFwrxHMqg/qUGmRRlzcA9xYgxETJpD7N7GTgj8CMggWaEPWtTzPrD7wPbKCO\nxdJFmzBqUPQrxBOmtvqsorqMpta6NLMJwAx3n1/owBKq1vp092fd/URCz4LUrbb6LAN6AecAl9X2\nJYVah1EITwL3mNmJxLhCvKEwsz2BnwM9zGysR1xUKd9kZiOBfsDuZrafu0+KO6YkM7NjCZuU7gxM\njzmcxHP3GwDM7AJgY23vTVrCWAu0T7tvmyrD3bcCl8QRVILVVp+fACPiCCqhaqvLu4G74wgqwWqr\nz5eBl+MIKsFqrM8q7v5wXV9S7F1SNa4QN7OdCCvEn4klsmRSfeaO6jK3VJ+5lZf6LNqEoRXiuaX6\nzB3VZW6pPnMrn/Wpld4iIhJJ0bYwRESkuChhiIhIJEoYIiISiRKGiIhEooQhIiKRKGGIiEgkShgi\nIhKJEoZIAZhZuZmNjjsOkWwoYYhkwMy0i6+UHCUMkQhSe/AsNrPfmtm7wAOpE8reNbPytPd9YGbj\nzOxNM3vHzDrv4LsuN7PpZrZzQf8QIllSwhCJbj/gHnfvClzr7kcA3YEyMzsk7X0fu/v3gPsJp5hV\nMTP7EXACcKq7f1mowEVyQQlDJLqV7j4v9fvZZvYm8DZwUOqq8lTq55tAx7TyC4BBwLDUqWciiaKE\nIRLdFgAz6whcC/R19+6EY0Kbpb2vquWwjX8/c2YBIYG0y3OcInmhhCESXdVA9+7AZuAzM9sbGBzx\n828DVwDPmNl38xCfSF4pYYhE5wDuvgCYDywCHgXmVH9PjV/g/hphXOOPqWNwRRJD52GIiEgkamGI\niEgkShgiIhKJEoaIiESihCEiIpEoYYiISCRKGCIiEokShoiIRKKEISIikfw/jgaNNS0bxPEAAAAA\nSUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b382806d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.loglog([val for word,val in corpus_counts.most_common(4000)])\n",
    "plt.xlabel('rank')\n",
    "plt.ylabel('frequency');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.2** Now let's compute some statistics about the training and dev data.\n",
    "\n",
    "- Print the token/type ratio for the training data.\n",
    "  You will have to implement ```gtnlplib.preproc_metrics.get_token_type_ratio``` (0.1 points)\n",
    "\n",
    "- Print the number of types which appear exactly once in the training data.\n",
    "  You will have to implement ```gtnlplib.preproc_metrics.type_frequency``` (0.1 points)\n",
    "\n",
    "- Print the number of types that appear in the dev data but not the training data (hint: use [sets](https://docs.python.org/2/library/sets.html) for this)\n",
    "  You will have to implement ```gtnlplib.preproc_metrics.unseen_types``` (0.1 points)\n",
    "  \n",
    "(0.3 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from gtnlplib.preproc_metrics import get_token_type_ratio,type_frequency,unseen_types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19.67109394737792"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_token_type_ratio(corpus_counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14134\n",
      "263\n"
     ]
    }
   ],
   "source": [
    "print type_frequency(corpus_counts,1)\n",
    "print type_frequency(corpus_counts,10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Words that appear exactly once are called [hapax-legomena](https://en.wikipedia.org/wiki/Hapax_legomenon).\n",
    "\n",
    "Now let's look at the dev data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.0507739212\n"
     ]
    }
   ],
   "source": [
    "y_dv,x_dv = preproc.read_data('reddit-dev.csv', #filename\n",
    "                                       'subreddit', #label field\n",
    "                                       preprocessor=preproc.tokenize_and_downcase) #your preprocessor\n",
    "corpus_counts_dv = preproc.get_corpus_counts(x_dv)\n",
    "print get_token_type_ratio(corpus_counts_dv)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, let's compute the number of word types in the dev data, which do not appear in the training data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1737"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unseen_types(corpus_counts,corpus_counts_dv)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, you can test your code by running ```nosetests -v tests/test_pset1_preproc.py```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.3** \n",
    "\n",
    "Why do you think the type-token ratio is lower for the dev data as compared to the training data?\n",
    "\n",
    "Yes the dev set is smaller; why does this impact the type-token ratio? (0.2 pts)\n",
    "\n",
    "*Please put your answer in the file gtnlplib/text-answers.md*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pruning the vocabulary\n",
    "\n",
    "Now let's prune the vocabulary to words that have appeared more than ten times. \n",
    "\n",
    "Please run the following two code blocks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3600\n",
      "86\n"
     ]
    }
   ],
   "source": [
    "vocab = [word for word,count in corpus_counts.iteritems() if count > 10]\n",
    "print len(vocab)\n",
    "print len(x_tr[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This cutoff is chosen mainly for reasons of speed; in the bakeoff, you may want to have a larger vocabulary, assuming your classifiers are fast enough.\n",
    "\n",
    "Run the code below to prune the data to this vocabulary. It will take a minute or two to complete."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x_tr = [{key:val for key,val in x_i.iteritems() if key in vocab} for x_i in x_tr]\n",
    "x_dv = [{key:val for key,val in x_i.iteritems() if key in vocab} for x_i in x_dv]\n",
    "x_te = [{key:val for key,val in x_i.iteritems() if key in vocab} for x_i in x_te]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "68\n"
     ]
    }
   ],
   "source": [
    "print len(x_tr[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Linear classification\n",
    "\n",
    "Now you'll implement the linear classification rule, $\\hat{y} = \\text{argmax}_y \\theta^{\\top} f(x,y)$.\n",
    "\n",
    "You will use these functions in all classifiers in this assignment.\n",
    "\n",
    "Total: 1 point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 294,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib import clf_base\n",
    "reload(clf_base)\n",
    "\n",
    "from gtnlplib import constants\n",
    "reload(constants);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.1** \n",
    "\n",
    "Recall from class and the reading that the feature function vector $f(x,y)$ can be viewed as a dict, in which the values are counts, and the keys are tuples $(y,x_j)$, where $y$ is a label and $x_j$ is a base feature.\n",
    "\n",
    "Implement the function ```make_feature_vector``` in ```clf_base.py```. Desired output is shown below:\n",
    "\n",
    "Note that you must also include the offset feature, ```gtnlplib.constants.OFFSET```.\n",
    "\n",
    "(0.2 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "fv = clf_base.make_feature_vector({'test':1,'case':2},'iama')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('iama', '**OFFSET**'): 1, ('iama', 'case'): 2, ('iama', 'test'): 1}\n"
     ]
    }
   ],
   "source": [
    "print fv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute the entire set of labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set([u'worldnews', u'science', u'askreddit', u'iama', u'todayilearned'])\n"
     ]
    }
   ],
   "source": [
    "labels = set(y_tr) #figure out all possible labels\n",
    "print labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.2**\n",
    "\n",
    "Now implement the prediction rule, $\\hat{y} = \\text{argmax}_y \\theta^{\\top} f(x,y)$.\n",
    "\n",
    "Specifically, implement the function ```predict``` in ```clf_base.py```. The output should be:\n",
    "\n",
    "- A predicted label\n",
    "- The scores of all labels\n",
    "\n",
    "This function will be called **a lot**, so try to make it fast. You don't need to do anything crazy, but avoid making your code do silly extra work.\n",
    "\n",
    "(0.4 points)\n",
    "\n",
    "You can test this function using these simple hand-crafted weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict,Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# weight vectors must be defaultdicts\n",
    "theta_hand = defaultdict(float,\n",
    "                         {('worldnews','worldnews'):1.,\n",
    "                          ('worldnews','news'):.5,\n",
    "                          ('worldnews','world'):.5,\n",
    "                          ('science','science'):1.,\n",
    "                          ('askreddit','askreddit'):1.,\n",
    "                          ('askreddit','ask'):0.5,\n",
    "                          ('iama','iama'):1,\n",
    "                          ('todayilearned','til'):1.,\n",
    "                          ('todayilearned','todayilearned'):1.,\n",
    "                          ('iama',constants.OFFSET):0.1\n",
    "                         })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(u'science',\n",
       " {u'askreddit': 0.0,\n",
       "  u'iama': 0.1,\n",
       "  u'science': 5.0,\n",
       "  u'todayilearned': 0.0,\n",
       "  u'worldnews': 0.0})"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_base.predict(x_tr[5],theta_hand,labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's see how good these weights are, by evaluating on the dev set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from gtnlplib import evaluation\n",
    "reload(evaluation);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.394\n"
     ]
    }
   ],
   "source": [
    "# this applies your predict function to all the instances in ```x_dv```\n",
    "y_hat = clf_base.predict_all(x_dv,theta_hand,labels)\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.3**\n",
    "\n",
    "Now modify ```theta_hand``` in ```gtnlplib/hand_weights.py``` to get accuracy above 41%\n",
    "\n",
    "You can look at the training set to see how best to do this.\n",
    "\n",
    "(0.4 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib import hand_weights\n",
    "reload(evaluation)\n",
    "reload(hand_weights);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.42\n"
     ]
    }
   ],
   "source": [
    "# currently showing the accuracy for my weights\n",
    "y_hat = clf_base.predict_all(x_dv,hand_weights.theta_hand,labels)\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run this block to output predictions on the test set\n",
    "y_hat_te = clf_base.predict_all(x_te,hand_weights.theta_hand,labels)\n",
    "evaluation.write_predictions(y_hat_te,'hand-test.preds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Naive Bayes\n",
    "\n",
    "You'll now implement a Naive Bayes classifier, as described in chapter 1 of the notes.\n",
    "\n",
    "Total: 2 points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from gtnlplib import naive_bayes\n",
    "reload(naive_bayes);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.1** (warmup) implement ```get_corpus_counts``` in ```naive_bayes.py```. This function should compute the word counts for a given label.\n",
    "\n",
    "(.2 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17.0\n",
      "255.0\n"
     ]
    }
   ],
   "source": [
    "iama_counts = naive_bayes.get_corpus_counts(x_tr,y_tr,unicode('iama'));\n",
    "print iama_counts['four']\n",
    "print iama_counts['am']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.2** Now implement ```estimate_pxy``` in ```naive_bayes.py```. This function should compute the *smoothed* multinomial distribution $\\log P(x \\mid y)$ for a given label $y$.\n",
    "\n",
    "Hint: note that this function takes the vocabulary as an argument. You have to assign a probability even for words that do not appear in documents with label $y$, if they are in the vocabulary.\n",
    "\n",
    "You can use ```get_corpus_counts``` in this function if you want to, but you don't have to.\n",
    "\n",
    "(.5 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "log_pxy = naive_bayes.estimate_pxy(x_tr,y_tr,unicode('iama'),0.1,vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probabilities must sum to one!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.99999999999991929"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(np.exp(log_pxy.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the log-probabilities of the words from the hand-tuned weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'todayilearned': 0.0, 'science': -8.5404041994450584, 'iama': 0.0, 'til': -11.41208382432907, 'worldnews': 0.0, 'askreddit': 0.0, '**OFFSET**': 0.0, 'ask': -7.7101941334791189, 'world': -7.3656964399725098, 'news': -8.8920858547297996}\n"
     ]
    }
   ],
   "source": [
    "print({word:log_pxy[word] for (_,word),weight in theta_hand.iteritems() if weight>0})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.3** Now you are ready to implement ```estimate_nb``` in ```naive_bayes.py```.\n",
    "\n",
    "- The goal is that the score given by ```clf_base.predict``` is equal to the joint probability $P(x,y)$, as described in the notes.\n",
    "- Don't forget the offset feature, whose weights should be set to the prior $\\log P(y)$.\n",
    "- The log-probabilities for the offset feature should not be smoothed.\n",
    "- You can call the functions you have defined above, but you don't have to.\n",
    "\n",
    "(0.8 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_nb = naive_bayes.estimate_nb(x_tr,y_tr,0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(u'science',\n",
       " {u'askreddit': -1007.9847188388546,\n",
       "  u'iama': -975.84461062677099,\n",
       "  u'science': -949.40658879134492,\n",
       "  u'todayilearned': -976.50222647175656,\n",
       "  u'worldnews': -1004.6447250798952})"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_base.predict(x_tr[55],theta_nb,labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(u'science',\n",
       " {u'askreddit': -1078.6362701511371,\n",
       "  u'iama': -1040.9001474598663,\n",
       "  u'science': -976.34200102283444,\n",
       "  u'todayilearned': -983.32655052451435,\n",
       "  u'worldnews': -1029.2493890460514})"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_base.predict(x_dv[48],theta_nb,labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 440,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.728\n"
     ]
    }
   ],
   "source": [
    "y_hat = clf_base.predict_all(x_dv,theta_nb,labels)\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# execute this block to write predictions for the test set\n",
    "y_hat = clf_base.predict_all(x_te,theta_nb,labels)\n",
    "evaluation.write_predictions(y_hat,'nb-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y_hat_te = evaluation.read_predictions('nb-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.70799999999999996"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluation.acc(y_hat_te,y_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.4** Write a function in ```naive_bayes.py``` called ```find_best_smoother```, which finds the smoothing value that gives best performance on the dev data. \n",
    "\n",
    "Your function should trying at least the following values: [1e-3,1e-2,1e-1,1]. \n",
    "\n",
    "Then, using this smoothing value, run your Naive Bayes classifier on the test set, and output the results. (0.3 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "best_smoother, scores = naive_bayes.find_best_smoother(x_tr,y_tr,x_dv,y_dv,[1e-3,1e-2,1e-1,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's load the test data. Note that the ```y_te``` labels are all meaningless."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_nb = naive_bayes.estimate_nb(x_tr,y_tr,best_smoother)\n",
    "y_hat = clf_base.predict_all(x_te,theta_nb,labels)\n",
    "evaluation.write_predictions(y_hat,'nb-best-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.708\n"
     ]
    }
   ],
   "source": [
    "y_hat = evaluation.read_predictions('nb-best-test.preds')\n",
    "print evaluation.acc(y_hat,y_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.5** Run the code below to compare the learned weights using smoothing of $.001$ and $10.$\n",
    "\n",
    "Explain the resulting figure as best you can, in the text file ```text-answers.md```.\n",
    "\n",
    "(0.2 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_nb_001 = naive_bayes.estimate_nb(x_tr,y_tr,.001)\n",
    "theta_nb_10 = naive_bayes.estimate_nb(x_tr,y_tr,10.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQkAAAD7CAYAAAB5RWHCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF1JJREFUeJzt3XtwnXWdx/H3N20SSluuvdJAwlVwEGyhiLLCKdpuQVe8\ny213WSuiIKuruIgIzTrurAIyg9oKYsYRhbTOMOwiwygtEFgZa2tp7QIByiVtKb2cQoFW0zSX3/7x\nPac5SU6eJs0553nOyec1k0lyrr8n5+RzfvfHQgiIiAymKu4CiEiyKSREJJJCQkQiKSREJJJCQkQi\nKSREJNLYuAtgZhqDFYlJCMH2d5tE1CRCCBX7tXDhwtjLoOPT8eX7GqpEhISIJJdCQkQiKSSKLJVK\nxV2EotLxVT4bTtukKAUwC3GXQWQ0MjNCuXRcikhyKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQi\nKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSRE\nJJJCQkQiKSREJJJCQkQiFf2EwWbWBrwN9ACdIYSziv2cIlI4pTireA+QCiHsLMFziUiBlaK5YSV6\nHhEpglL88wbg92a2ysyuLMHziUgBlaK5cU4IYYuZTQaWmVlrCOEPuTdobGzc93MqldJJWkWKoKWl\nhZaWlmHfr6QnDDazhcCuEMLtOZfphMEiMUjECYPN7GAzm5D5eTwwD3immM8pIoVV7ObGVOABMwuZ\n57o3hPBIkZ9TRAqopM2NvAVQc0MkFolobohI+VNIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJI\niEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgk\nhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSI\nRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJI\niEikooeEmc03s+fN7EUzu77YzycihWUhhOI9uFkV8CLwIeB1YBVwcQjh+ZzbhGKWQUTyMzNCCLa/\n2xW7JnEWsD6EsCGE0AksAS4q8nOKSAEVOyRmAJtyfn8tc5mIlAl1XIpIpLFFfvzNwDE5v9dlLuuj\nsbFx38+pVIpUKlXkYomMPi0tLbS0tAz7fsXuuBwDvIB3XG4BVgKXhBBac26jjkuRGAy147KoNYkQ\nQreZfQV4BG/aNOUGhIgkX1FrEkMqgGoSIrFIyhCoiJQ5hYSIRFJIiEgkhYSIRFJIiFSIdDrNqlWr\nSKfTBX1chYRIBWhuXkp9/cnMnfsl6utPprl5acEeW0OgImUunU5TX38y7e2PA6cB6xg3bg4bNjzP\n5MmTB72fhkBFRom2tjZqahrwgAA4jerqetra2gry+AoJkTLX0NDA3r1twLrMJevo7NxAQ0NDQR5f\nISFS5iZPnkxT02LGjZvDIYfMYty4OTQ1LY5sagyH+iREylA6naatrY2GhoZ9YZDvsihD7ZNQSIiU\nmebmpSxYcDU1Nd7MaGpazCWXfG7Yj6OQEKlAra2tzJx5Nh0d/wOkGOpIRj4a3RCpMM3NS5k58wN0\ndEwDPgUspdAjGfkUe2cqESmAdDrNggVX09HxBNm5EDAHmFrQkYx8VJMQKQP55kLAkdTWXlTQkYx8\nVJMQSbDsiMWECRNy5kJ4TaK2Ns2aNSs45ZRTiloGhYRIQvUfxViw4HKamuZQXV1PZ+cGmpruLHpA\ngEY3RBJpsPUYq1f/gd27dw95LkSURGyEKyIHJtsH0d7edz3G7t27mT17dknLoo5LkYTI3Q+i2Osx\nhkMhIZIA/feDWL78saKuxxgO9UmIxCxqPwhgWOsxhkN9EiJlYrD+h7a2NmbPnh1L7SGXmhsiMUtS\n/0M+CgmRmBV7P4iRUp+ESEIMdz+IkdJScRGJpKXiIlIQCgmREirWCXSKSSEhUiLNzUs55piTSKUu\np67uBO666+64izQk6pMQKYGnnnqKc8/9ED091cBUYCuwlzvvXMRVV10ZS5nUcSmSENde+zV+8pOf\nAUcBrwM9wNHAZsaMCWzZsjGe6dbquBSJX2trayYgVgAvZb6PAxYBD9PdXcWaNWviLOJ+aVq2SBGt\nXLkSqKP/tnPwr0AamBhTyYZOISFSBK2traxcuZKxY8cCr5G77Zw3OVYDncDZHH300fEVdAgUEiIF\n9oUvfJGmpnuAGcAWvHkxB6gHNuAdl7uB2dTWHsvu3btjK+tQqE9CpIBuu+12mpp+DZwMvAU0Au1A\nE3AXcD/wNtAArKOqamtiFnINRqMbIgWSTqeZPv04urufou+5MQ7FmxjvBl4BuoFpjB27jXvuufuA\nTtFXCNpPQqSE0uk0S5Ysobt7Kn07KeuAF/BK+3XAXOBZxoz5COvW/bkku12PlEJCZISam5fy+c9/\niT17DNiD1yCmA8uAF4Eu4FzgWnyuxMssWnRHWQQEqLkhMiLpdJqjjjqWrq4xwBS8ozL7fp4ObAe+\nAzQyfnw9XV2vc8cdt8U2yzKXJlOJFNlTTz3FvHl/T1dXF96UeBD4Oh4Sf8QnT/0B+AHjxx/PokXf\nYtOmlxIREMOhmoTIAZg370KWLWvBW+xd+DTrTXin5CnA2pxbn0Zt7QY2bXopMbtNgWoSIkXz0EMP\nZQLiPjwgVuCdkyuAMfhciN79KuEl7rjjtkQFxHCo41JkGJqbl3L55VcAk4FVDJxyPQOYiQ991gHr\nufXW75VdEyOXmhsiQ9Ta2sp73nMm3d1j8ZDYiH/OrqB3XsTZQOCggxoIITmdlPnEvlTczBYCV+Ld\nuwDfDiH8Ls/tFBKSeM3NS7niii+yd28X3il5GtCCz3uoxmsNrwGd3H33Tzn99NNLtqHtgUpKSOwK\nIdy+n9spJCTRWltbmTnzA3R0LAJ+iC/OyjoW2AEcDLyNGWzbtinR4ZCVlI7L/RZAJMluu+12Tj31\nTDo6DgHewIc1czsl3wF+ha/H6OHee39ZFgExHMWuSfwz/lf8M/CNEMLbeW6nmoQk0ic/+VkeeOBB\n4Dzgf/Fhzo34Eu/j8SHPyWT3hfjRj77DtddeG1dxh60kzQ0zW4ave913ET6T5Ea8N2dHCCGY2feA\n6SGEBXkeQyEhiXPmme9j9erVwHg8FFYArcCXgSPwJsbNwAeBK4CXee65NWUz1RpKtMArhDB3iDe9\nG/jtYFc2Njbu+zmVSpFKpUZSLJERGT/+MP72t714f8Nm4DB8ivUcvLMyd4Xn/cCrXHLJZxIfEC0t\nLbS0tAz7fsVsbkwLIWzN/PxvwOwQwqV5bqeahCRGff1xbNy4lYHDmrfjn3W5nZYnApu49NLPcO+9\nvyp5WUcqCUvFbzGz9+JbA7cBVxXxuURGbObMM9i48VV8Q5gOvK/hNHzl5lfxf5febehqatI89tij\nnHPOOTGVuDSKFhIhhH8q1mOLFNo111zL2rX/h3erbQH+JfP9enzDmEXA00AKOJLa2h384hd3VXxA\ngKZli3DZZf/Ifff9JvPbQcBJ+MjF9fj2c13AJGAx8Fmqq/+BNWtWJr4PolAUEjKqXXrpZTQ334eH\nQzW+tDu3Y/J44E3gYqCOqqqt/PKXTaMmIEAhIaPYpEnTeOONt/BwGA8czsCt517Fh0Bh/vwTueee\nP1bcZKn90QIvGZWmTp3G9u3b8T6Isfjk43H0HeI8G29q1GG2jW3b2ioqIJIwuiGSSDU1B9PZCXAc\n3jnZgy/x/k+8iXEMvj/EHnyOxFa+/OUFFRUQw6GahIwqkyZN5Y03dtF3HsR5eCD8id4NbL+QuUcP\nkycfzvbtW+IoblHFvgp0qBQSUio1NePp7OzAawqv5FwzC99NqhuvXbQBfwV6OPfcD/LEE4+Vuqgl\nkZRVoCKJMGZMDZ2dAZ8otRW4BZ8sdR/wMn6WrT349iftQBcLF95UsQExHKpJSEVLp9NMmTINqAUe\nxkcx/gpcmLnFUfhkqePwsOgCurj11h9y3XVfj6HEpaOahIx6jY3fZcqUKfgQ51TgU8CXMt8PAX6O\n7w+xAm9+dAI93Hnnzyo+IIZDoxtSkWbOPIO1a/+CD3FOAbYxcNHWzMytfQPbqqpX2bp166gdxRiM\nahJScU499XTWrl2DD22OwXeUOo6+E6WOAtZkfl8HbObJJ59QQOShkJCKct555/Pss89kfjsI3xOi\nB29O5G479zqwAF/ufTbz5qVGxWKtA6GOS6kYM2fOzqzkBP/8y21ezMZDYzIeEJ8A7qe2topHH102\nKgNC8yRkVJk7dz7Llz+Bj2J8A/g1Pmsy6yT8rN7fx+dDvMPEibW8887Okpc1KTS6IaPGRz/6MZYv\nX46PYkwAzseXeuc2L17DN7Ldic+P2DuqA2I4VJOQsnbeeefz5JMt+EDdWLxD8k189KIFX5OxGagB\n9gJ7mThxogICNTdkFJg+vY6tW1/H+xpm4KMYP8XP6v1+vFnRlXMP48gjD2fHju0DHms00ipQqWhH\nHDGFnTt34gGR20E5B3geqAfWZ64/GHiTI488gh07tsVU4vKlPgkpO2PH1rJz55v4KV6Oou/8h3p8\nFWcbcA3wELCLm276tgLiAKm5IWXFbAweDjXARGAXsJLemsT78VmWB2du8wap1Ad4/PFH4ylwgml0\nQyqOmdE7i7IKP5NWFXAGPsX6/fgIx6eA3cBmFi68QQExQuqTkLJgVoXXDIyBE6XOxk+39wp+vowl\nwF62b9+uadYFoOaGJJ7XIA7CP9P+nYETpU7EN42pwoc5A3pP7Z+aG1L2br755kxAVANH4su9P83A\niVKbgRvInq9aAVFYam5IIlVV1RJCJ73rLbbjn2mdwJV4EyN3otQtmHXT06OAKDTVJCRxzMZkAqI6\n83UYPlrRQ++ZvbMrO9uBt1m8+HZ6evbGU+AKp5qEJIo3L6C3g/I4vHnxLeA/8BmVxwKfxfshUPOi\nyBQSkhgeEGPx2kN2DcYN+DTrOfgOU4fhKz23of6H0tDohsTOw8HwvoX+w5vZadYfxkc0puMB0a6A\nGCGNbkhZ6G1e1ABfw5dz55tmvR5fsNXGRRfNU0CUkGoSUnK9wQC9zYs6vIbQSd+aRHY1ZwcTJkxg\n165dJS5t5dJScUmc3mZFdvZkHb4ZzCeAe/FQeF/mNtnhzXZAnZPFoOaGxM7M+nx5rSG7OGsF8GLm\n+wNAK157qMP3gHgVaGfatGkKiJhpdEMKpm8zYgweBtX46fOq8RrC4fgIRW6/Qx2+krMTrz10Aqo9\nJIWaG3LA8odCHT6vYQ8+W3I6vjt1AFbhYXEGAxdoTQJ2oOZF6ai5ISPWt6nQ/7qxwDh8cdU4fAbk\nw8AVeBAcj4dGGjgZD5E/4XMestOqT8p834P3TbRz0003KSASZtTUJHLf6HEfcznwEMjtXNxDCD2Z\n6wwPhv61AfAmxR9zLk/h8xu2AOfiQ5lb8A7KLnL3oNTrUlqqSeTo/6nnexPIYDwE+ncuHtSvVjGD\ngafNmwO8q9/lDfhWcqfhTYrs5jDdeBMEZs2apYBIsIr/b4l6w0tffUOgjr7/7IfhQXtC5vtG+i7X\n3gI8Cbzc7/I2PCiyp9bbDFyHNz+6CSGwevXqoh2TjFzFNjf6hsCJeEDk/v6SPr1yDGxedAO/B8bj\n/9iXMrB5UY0v436T3q3sz8nc90Q8ILro7bysxgfU2tG06viN6ubGwE61Vxm4SYn07ZjsX9saA1wA\nXIYHxCH0rVnMwMNgN75d3PmZy6fjnZgv4BvF9OBhcQE+tPkmU6ZMVECUkYoJieg3fDVwFtkzSHsn\n3Oh+k/YN0lry9zE00fs3fAffxwE8aN8Evp65/Jv4CMYteC3E8ADZgofEUfjIh9cetm3T1vblpCKa\nG32ryq/gexAMbF5kxX3McRs4OtECXMjANRNteHMC4D14jWw6HhDfx/d4eJy+TZAzge8AXyRbc/Ah\nTv3dk2bUNDd6p/s+jAdDE/5pNrB5EYL2H/BAraVvx2QKOBT/Jz8BH6rswmsC0Nvp+Ht8otT9wHsZ\nuGJzBj7CMQ3fbu51srW20f53L2dlXZPoW4N4A1gMfA4/s3QPvYuEesf4R7PeGsTD+Lkp+tcC2vF/\n/NXAjfiu1NnNX7Idk7Pxz5bpwFYGdmYejp+5WzMnk67izwWaf0LPHHxH5R78TepNDL1Rc9XhNYfF\n+N/rCLJB6rYDP8ZrC8fiHZDVeBMiu65iHF6T+At9N6RtR+FQeUbU3DCzT5vZM2bWbWaz+l13g5mt\nN7NWM5s3smIOpv9Y/hHAfHKruHqz9pdtin0OD4JN+D92Ff7PXwfcBlwPPAs8jU96OhT4Id4c+Qjw\nO7yDsgsP43b9zSvUiJobZvYu/GP7LuC6EMLTmctPAe7D66Z1wHLgxHztigNtbgw+NVjj71n5pqL7\nbNOD6P30PwR4G/+Hz7dt3GR8jcWN+GzJs/GXvDtzH63YLFcl6bgMIbwQQliPv1tyXQQsCSF0hRDa\n8An7Z43kufovNvI35R78Tauhzf4Gm4rufTPt+IzJh/F+hSYGnp27Dh/dWIfXPm6mt9+iA69BdKrm\nMAoUa3RjBl6PzdqcueyA7P8Nn63uqnMShjoVvR7vmwCYi49k5I4IrcebJNlg2Ej/JoXCYXTYb8el\nmS3DewP3XYQ3Um8MIfy2EIVobGzc93MqlSKVSuU+P/maFZmqkt6og+rfXzOD3LkivX0Tp+EB0cXA\nTshXATUlKkVLSwstLS3Dvl9BhkDN7HHgGzl9Et8CQgjhB5nffwcsDCH8Kc99I/skPCS09mI4htJf\nM7BvYg/ZVZmgYBgN4phMlftkDwIXm1mNmR2Ld4mvPPCHzj85SvIbSn9NvqaamhGSz0hHNz6OD6pP\nAt4C1oYQLshcdwOwAO/+/moI4ZFBHmO/oxv5PvXU/7B/2mhHolTclvp6w4sUVsXNuFQwiMSj7Bd4\niUhxKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQiKSREJJJCQkQi\nKSSK7EC2CysnOr7Kp5Aoskp/k+n4Kp9CQkQiKSREJFIitq+LtQAio1hZ7HEpIsmm5oaIRFJIiEik\n2ELCzG4xs1YzW2tm95vZITnX3WBm6zPXz4urjCNhZp82s2fMrNvMZuVcXm9mfzOzpzNfi+Ms54EY\n7Ngy15X9a5fLzBaa2Ws5r9f8uMtUCGY238yeN7MXzez6yBv3PwFsqb6ADwNVmZ+/D/xX5ud3A2vw\n7f4b8FNMWVzlHMHxvQs/fdZjwKycy+uBdXGXr0jHdkolvHb9jnUh8PW4y1HgY6rKvDb1QDWwFjh5\nsNvHVpMIISwPvafhWoGf4RbgY8CSEEJXCKENP731WTEUcURCCC+EENbT9/SHWfvtUU6yiGO7iAp4\n7fIo69crj7OA9SGEDSGETmAJ/trllZQ+ic8DD2d+ngFsyrluc+ayStJgZqvN7HEz+7u4C1NAlfra\nXZNpFv/czA6NuzAF0P91eo2I16moZ/Ays2XA1NyL8FNX3xhC+G3mNjcCnSGE5mKWpRiGcnx5vA4c\nE0LYmWnP/7eZvTuEsLvIxR2WAzy2shR1rMBi4LshhGBm3wNux89xO2oUNSRCCHOjrjezK4ALgfNz\nLt4MHJ3zex0JPY34/o5vkPt0AjszPz9tZi8DJwFPF7h4I3Igx0YZvXa5hnGsdwOVEJCbgWNyfo98\nneIc3ZgPfBP4WAihI+eqB4GLzazGzI4FTgBWxlHGAtrXpjWzSeanScfMjsOP75W4ClYAue31invt\nzGxazq+fBJ6JqywFtAo4ITPSVgNcjL92ecV5wuAfAzXAsswZw1eEEK4OITxnZr8BngM6gatDpku2\nnJjZx/FjnAQ8ZGZrQwgXAOcC3zWzvUAPcFUI4a0Yizpsgx1bpbx2/dxiZu/FX6s24Kp4izNyIYRu\nM/sK8AheUWgKIbQOdntNyxaRSEkZ3RCRhFJIiEgkhYSIRFJIiEgkhYSIRFJIiEgkhYSIRFJIiEik\n/wcQnUBwqY4yWAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b3478b650>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(theta_nb_001.values(),theta_nb_10.values());\n",
    "plt.axis('square');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Perceptron \n",
    "\n",
    "Total: 2 points\n",
    "\n",
    "The perceptron update is,\n",
    "\n",
    "\\begin{align}\n",
    "\\hat{y} = & \\text{argmax}_y \\theta^\\top f(x,y)\\\\\n",
    "\\theta \\gets & \\theta + f(x,y) - f(x,\\hat{y})\n",
    "\\end{align}\n",
    "\n",
    "You will now implement this classifier, using the file ```gtnlplib/perceptron.py```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<module 'gtnlplib.perceptron' from 'gtnlplib/perceptron.pyc'>"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from gtnlplib import perceptron\n",
    "reload(perceptron)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 4.1 **\n",
    "\n",
    "Implement the perceptron *update*, $f(x,y) - f(x,\\hat{y})$, in the function ```perceptron_update``` in ```perceptron.py```. (0.5 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_perc = hand_weights.theta_hand_original.copy() #let's start with the hand-set weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# no update when the prediction is correct\n",
    "update = perceptron.perceptron_update(x_tr[110],y_tr[110],theta_perc,labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<type 'float'>, {})\n"
     ]
    }
   ],
   "source": [
    "print update"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((u'science', u'and'), 2), ((u'iama', u'200'), -1.0), ((u'iama', u'genes'), -3.0), ((u'iama', u'now'), -1.0), ((u'science', u'years'), 1)]\n",
      "146\n"
     ]
    }
   ],
   "source": [
    "# update when the prediction is incorrect\n",
    "i=20\n",
    "update =perceptron.perceptron_update(x_tr[i],y_tr[i],theta_perc,labels)\n",
    "print update.items()[:5]\n",
    "print len(update)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 4b **\n",
    "\n",
    "Now implement the perceptron algorithm. Your implementation should take as inputs:\n",
    "\n",
    "- The training instances $x$\n",
    "- The training labels $y$\n",
    "- The number of iterations to train\n",
    "\n",
    "It should use your ```update``` function, and it should return:\n",
    "\n",
    "- weights $\\theta$\n",
    "- a list of the weights at each iteration\n",
    "\n",
    "Specifically, you should implement ```estimate_perceptron``` in ```perceptron.py``` (0.5 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(perceptron);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_perc,theta_perc_history = perceptron.estimate_perceptron(x_tr[:10],y_tr[:10],3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n",
      "4.0\n"
     ]
    }
   ],
   "source": [
    "print theta_perc[('science','its')]\n",
    "print theta_perc[('science','what')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'm including the running time (on my lenovo X1 carbon laptop) for reference:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 15.4 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "theta_perc,theta_perc_history = perceptron.estimate_perceptron(x_tr,y_tr,20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_perc,theta_perc_history = perceptron.estimate_perceptron(x_tr,y_tr,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run this to plot the accuracy over iterations\n",
    "def plot_accs(weight_history,x_tr=x_tr,y_tr=y_tr,x_dv=x_dv,y_dv=y_dv):\n",
    "    tr_accs = []\n",
    "    dv_accs = []\n",
    "    for theta in weight_history:\n",
    "        tr_accs.append(evaluation.acc(clf_base.predict_all(x_tr,theta,labels),y_tr))\n",
    "        dv_accs.append(evaluation.acc(clf_base.predict_all(x_dv,theta,labels),y_dv))\n",
    "    plt.plot(tr_accs,'--')\n",
    "    plt.plot(dv_accs)\n",
    "    plt.xlabel('iteration')\n",
    "    plt.ylabel('accuracy');\n",
    "    plt.legend(['training','dev'],loc='lower right');\n",
    "    return tr_accs,dv_accs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.646\n"
     ]
    }
   ],
   "source": [
    "y_hat = clf_base.predict_all(x_dv,theta_perc,labels)\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAEPCAYAAABGP2P1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XmcTfX/wPHXm6KU7CRrEgnhqyyVTOkbbSrFFwmVlm9K\nq1K/lqm+RZRsLWRPUpYkikSTlC1bdlL23VjGDGa5798f5w6z3Jm5d+aeuXNn3s/H4z5m7jmfc857\nDnPfcz6rqCrGGGNMskKhDsAYY0zeYonBGGNMKpYYjDHGpGKJwRhjTCqWGIwxxqRiicEYY0wqriYG\nERklIvtF5M9MygwRkS0iskpEGroZjzHGmKy5/cQwBmid0U4RuRW4TFUvBx4DPnU5HmOMMVlwNTGo\n6kLgSCZF7gLGe8suAUqISAU3YzLGGJO5ULcxVAJ2pni/27vNGGNMiIQ6MRhjjMljzgnx9XcDVVK8\nr+zdlo6I2KROxhiTDaoqgZTPjScG8b58mQF0BRCRZsBRVd2f0YlU1V6qvPHGGyGPIa+87F7YvbB7\nkfkrO1x9YhCRiUAEUEZEdgBvAEUAVdURqvq9iNwmIn8BscCDbsZjjAlvqrB4MYwdCxdcAAMHhjqi\n/MnVxKCqnf0o86SbMRhj8oevvoLXXwcReOABGDAA+vSB8uX9P0dcHBQr5l6M+UWo2xhMNkRERIQ6\nhDzD7sVZ+f1eVKsG48ZB06ZOcrjgAjhyxHdi8HUvjh+H6tVhyhS46SbXww1rkt06qNwmIhousRpj\nAnP6NKxcCYsWQVISvPBC8K/x8cfQty907QrvvBP88+eG+++H1auhcGE455yzX8ePh5o1fR8jImiA\njc+WGIwxIfXUUzB6NNSqBc2bw7//DffcE9xrqEK9ejBsGNx4Y3DPnZu2bYMTJyAx0UmgyV8bNHCe\noHzJTmKwqiRjTFCoOh9U557r/zGzZ8P338OePVCihHux/fKLE1+417ZVr54717EBbsYUULt3w4sv\nBudcr78OJUtCuXKwcaP/x1Ws6FSDuJkUwIlr0CCnbSJcnDwZumtbVZIxeUhCAgwdCo89lnHVQLC8\n+Sa8/TYcO5bza+3dC0WLOg27H33kdCk9//zgxOkPVfc+9JOSnPOfk836lVOnnHaBpUudryNGQKFM\n/iRXhX794LffYObM7F0zpexUJdkTgzF5yKBBzgd2r17uXicpyanXL10aVqzw/7i4OJg4Mf32ihWd\ncz3yCFxxBTz3XPBizcrChdCxY/aOjY3NfP+xY9CihdMOEoiTJ+GZZ+Dqq5378vjjsGYNNGvmVLel\ndfSos9/jgeefd+7xiBGBXTOoQj0qL4DRe2pMfhcXp7pnj2qtWqqff+7edZYtU73mGtWNG1VjYvw/\nbsEC1SZNMi9z9KjqffepxsbmLEZ/nTihWqqUc98CcfCgasWKqtHRvvcfPqx69dWqDz6oWrKk6oED\n/p/b41GdNUv199+df9OsLFqkWrWqaoUKqtdem3FM2eH97Azo89aqkozJg1avhptvdqoTatVy5xrx\n8VCkSGDHDBgAO3fCkCHuxJRdPXpA7drQu3fgx5Ur53RjTSkuDq67Dlq1cn7mhQvhmmvgvPOCF3Na\nqs5Tw+WXB7cazrqrGpOPjBjhfFg89lioIznrvvugXTvonOWcBr4dPOi0awweHNw2gYUL4dFHYd26\n1Ofdvx8qZLLCy65dTlfPNWvgkktS75s3zxkIF04N1r5YYjDGuKpKFYiKgssuy97x3bs7de7BnuNI\n1Xmy+uILaNLE2bZ+PdxyC2zf7gwEy0jv3hATA5/m0/UjrfHZmDBy/LjTQBkfn/1znDoVvHiysnu3\nc70aNbJ3fFQUzJ8Pb70V1LAA56/6xx+HtWvPbvv4Y3joocyTAsDLL8PUqbB5c/DjCleWGIwJgcRE\n6NDB6Z4ayICwZCdPwv/+59RHnziR83j8eRhXhXffDbxqRdWp5nnkEadt4sILsxdjVp5/3kkE4DwB\nTJzoXDcrpUs7czAFI66xY532iXBnicGYEEieJTTQunZVmDTJ6RK6apUzojeQD7TRo52qlZSiouCO\nO7I+tnJl58M9UCJQt64z+d3ddwd+fHZMmOBMfVG5sn/lb7stfRuDLwkJzkhtX5Ytc/5ds5Po8xpr\nYzAmlyUkQKVKziCwQKplVqxw6syrVoUPP4SWLdOXmTcPvv4ahg9Pvy8mxjl2wwa4+OKz2/fvhzp1\n4PDh8G9oBSd5XnWVk3SDPYtqfDxcein88INzjZTuuw+uv96pHsxLrI3BmDAwb56TEAKtq7/0Uqen\n0rJlvpMCOH+Vz57t1OWn9dVXzlxBKZMCOL12LroItmwJLJ686tQpaN/encnyihSBJ59M33i+ZYvz\n9NajR/CvGQr2xGBMLps2zamH7tLFnfPPmOH0tPnzT2eaimTNm8Orr8Ltt6c/pkMHaNvWvZjyk+ho\np1fW+vXOiG9wuhRXqOBOw3pO2RODCVtTpvieKiA/atfO3Q/gtm3hyiud+XaSrVsHO3ZA69a+j2na\n1JnLx2StdGlnXYRhw5z30dEweXLg02bkZZYYTMjt3es8+qfsamhyZsgQZzK+5C6Yo0fDgw9mPBFc\nkyaZVyUNGGCJI6Wnn3aq9WJjnUSxZo0zgjq/sKokE3KqzmRjr74anAVaEhOdxteYGOeXtVw5Z3qJ\ngrbW7/Tp0LChM4d/dLRzn8uU8V02+Vcro8bnOnWc3lANGrgSalhautT5f5vZTKl5gS3UY8KSiNOY\n+tdfOT/Xvn3QqZNzzmuucf5iPnAArr224CWGlF1DS5fOvGxmvZGOHHGmjqhbNzhx5RfJI6zzI0sM\nJk+oWdOZOC6nfv7ZSTKvvZb1iFePJ+//tZcXLFsGjRtnfz0CE37s18LkCVdeGZwP6U6dIDIy66QA\nzijZjz7K+TX99dRTTk+WcLN4sdM4bQoOa2MwBdY//8Ctt8Kdd8J772UvMa1ZA9WqOeMAMnPwoDN9\nxe7d7q/MFmy33+70zw9G+4/JfdZd1YSVf/4J7cRll14Kv//u/EXcsWPgE9LFx8O998KiRVmXnTLF\nSUJ5PSmsX59+rp/+/Z11CUzBYYnBhMzAgU5Pl+x66y1nMFdOlC4Nc+c6ja833+wsseivTz5xBjpl\nNDYgpS+/dKq58ronnnAWB0qpbt2sn4hM/mKJwYREYqIzp092F3wBZ9qHYPQ0Ou8854O7e3f//6KP\njoZ33oH338+67M6dzgAzfxJIqDVpAkuWhDoKE2qWGExIzJvn9K+vWTP751i/PnhdKAsVcurR/Z0Z\n8+23nWqklNdXhWefdRJBSrNnO/XzKaenyKuaNLGBbCYXEoOItBGRjSKyWURe8rG/qoj8JCKrRWS+\niPgx+a0Jd198kf5pITra+cvaHwcPOrOUpp0QLjfs2+dM6/zmm6m3izgDyB5+OPX6Bo88cnb6hLwu\neWoM6+dRsLmaGESkEDAMaA3UBTqJyBVpir0PjFXVBsBbQD9MrlB1euO8807uXjcuzmkb+M9/Um9f\nsgSee86/c6xf73RxDcU00Rdf7PRGKl8+/b4+fZx2irTTXru5iHwwVa7s3NMdO5z/H5YgCia3nxia\nAFtUdbuqJgCTgLvSlLkS+BlAVaN87Dcu6dcPRo50PsRy8wMgIcGZKz/tX/s1a/o/9XMwq5EycuyY\ns/ymLxk9qZxzjrMa2Kuvwtat7sXmFhGnSu34cae31a23hjoiEwpuJ4ZKQMoa113ebSmtAtoBiEg7\n4EIRKeVyXAbo1g2WL3fq1zdsyL3rlijhXDutatWcfv7+rIHcpYv7UxwPHOgMggs0adapA6+84kxa\n5/G4E5ub3n4b6td3uvFedlmoozGhkBcan3sDESKyHGgB7AaSQhtSwXDJJU43xDZtnAbSnEpMdKaj\niI3N3vFFijhVGdu2ZV22eHH32xdeecVZBjPtoiz+ePppZ+Dc6dPBjyu3LFkCzZqFOgoTCm7PfrIb\nqJrifWXvtjNUdS9wL4CIXADcq6o+H+AjIyPPfB8REUFERERwo80njhxx1gH2t4fNI49k/8M8pV9/\ndc6T3OVT1ZkG4vnnncFk/qhZ05lMr1atnMeTU0WLOgPTmjZ1JuS74Qb/jy1c2FksJ5wtXuw8PZjw\nEhUVRVRUVI7O4eqUGCJSGNgEtAL2AkuBTqq6IUWZMkC0qqqI/A9IVNVIH+eyKTH81Lev037QooUz\naKtVKzj/fGcpSTcnjXvqKWdFq1deObvt44+dWObOhdq1sz7Hhx86bQe33OJenIGaPdupa//ss/yz\ndGNW9u51/h3yyzrQBVl2psRwfa4kEWkDDMapthqlqv1E5E1gmarOFJF7gb6AB1gA9PQ2VKc9jyWG\nABw65Mw0+tNPzmvvXqdqoH59d67n8TgLzf/0E1yRpt/ZmDHwf/8HM2dCo0bh+UEzdaozdXfyUo75\n3bx5TpKeOTPUkZicypOJIVgsMfiWkOBflVF8vFOH75YlS5zG1oxmD500Cbp2daqV+vbN2bVUwzO5\nhBubljx/sEn0ChhVeOABGD8+67JuJgWAX35x1jLOSMeOztPEo4/m/FrPPussq2jcZUmh4LKlN8LY\niBFON9MxY0IdCbz4ovP0kplAGm8zs3at05PKGOMOSwxhatUqZxDVwoVOw3IwfPABlCzpTOmQHf72\ngsqpdeucUc/GGHfYw2IYOn4cOnSAIUP86+njr0qV4Ntvg3e+7PrtN2etBl+io50usVWq5G5MxhQk\nlhjC0Ntvw403Bn9+/3//22krCPWgrM8/h++/971v/XpnZLE1PhvjHqtKCkNvvOHfmsaBKlPG+dD9\n7Te46abgn99fyYPcfPn7b/fnSDKmoLMnhjB04YXBa1dIK9DpMTKr9smuzBJD167OQDNjjHssMZhU\n2rRxGrT91bu3/zOi+iuzxADuPC0ZY86yAW4mFY8HkpL862G0Zw/Uq+csXBPMcRJxcc5azLGxlgSM\nySkb4BaG/v7bWRQlK/5MRR0MhQr53+10+nS4447gD54rVgx69oSTJ4N7XmOMfywxhNj06c6o4MwG\nh82fnzcXkp82zVnL2A0ffOC0pRhjcp8lhly0fj28lGbV62eecQaVvfaa72OSkpwpIJ580v34AnH4\nMCxblrsJKzraqWYyxrjLEkMu2bjRGSeQdnbTQoWcpSAnTPDdG2jkSCdxZDYPUSiIwKhRTrVPbnn7\nbRg2LPeuZ0xBZYkhF2ze7KyL8O67zpKUaZUrB198Ad27Ow26yY4dc8YsDBqU+wO6Dh+GlSsz3l+6\nNNx3X+7FA7mzzrMxxhKD67ZudRbKeest3+scJ2vZ0lkOctGis9vefttp3G3UyP0401qzBh57LPev\nm5n1622OJGNyg3VXdVnPnlChArz+euDHzp4NDRu6v7axL/HxzpPMqFGwYIEzo+m8ebn35KIK773n\nzNpaqJAzP9QllzhfbTpoY/xnC/XkQapOA/I5YTj5SI8ezrTet9/uvK66KnertCpWhD/+cCb3W7LE\nSbJ//JF71zcmP8hOYgjDj6vwIhKeSQGchu9QSh4BXakSHD0KERGhjceYgsIeyk2eVbPm2ek2WreG\n998PbTzGFBSWGEyeldWcScYYd1hiMHmWJQZjQiNMa7/zPo8HNm1y1jcw2dO0adbrSBtjgs96Jblk\n3Tq4++7gT0ltjDGBsNlV85DFi6FZs1BHkT9s3eq8jDG5wxKDSxYtssQQLJ9+Cl9/HeoojCk4LDG4\nZPFiaN481FHkDzZHkjG5yxKDC44dg23b0s+karJn3TqbI8mY3GSJwQUHDzozpfq7EprJ2KJFsH07\nXHppqCMxpuCwXkkmT/vlF2cqDPunNyZ78mSvJBFpIyIbRWSziLzkY38VEZkvIitEZJWI3Op2TCZ8\ntGxpScGY3ObqE4OIFAI2A62APcAyoKOqbkxRZjiwQlWHi0gd4HtVTVdxYE8MxhgTuLz4xNAE2KKq\n21U1AZgE3JWmjAe4yPt9SWC3yzEZY4zJhNtTYlQCdqZ4vwsnWaT0JvCjiPQCigE3uxyTMcaYTOSF\nuZI6AWNU9UMRaQZMAHz2Wo+MjDzzfUREBBF5cIL+b76BevXg8stDHYkxpiCKiooiKioqR+dwu42h\nGRCpqm287/sAqqrvpSizFmitqru977cCTVX1UJpzhUUbQ6NG8MknNurZGJM35MU2hmVATRGpJiJF\ngI7AjDRltuOtPvI2PhdNmxTCxYkTsHmzkxyMMSZcuZoYVDUJeBL4EVgHTFLVDSLypojc4S32AvCI\niKwCvgC6uRmTm/74w1kXuWjRUEdijDHZZwPcgqhvX2fU88CBoY7EGGMcebEqqUCxqbaNMfmBJYYg\n6tzZmb7BGGPCmVUlGWNMPmZVSS6JioLDh8++V4UFC0IWjjHGuMoSQxa2b4f27WHXrrPbjh6FHj3g\ntddsgjdjTP5jiSETHo+zrsILL0CDBme3lyoFCxfC7Nnw6KOQmBiyEI0xJugsMWRi0CDnQ/+FF9Lv\nK18efv4ZduyAe++FkydzPz5jjHGDNT5nYO1auPFGWLIEatTIuFx8PLRrB4UKwYy0Y7qNMSbEstP4\nbIkhA4MHQ/Hi8NBDWZdVdZ4YihVzPy5jjAmEJQZjjDGpWHdVY4wxOWaJwRhjTCp+JQYRmSYit3vX\ncDbGGJOP+ftB/zHQGdgiIv1EpLaLMYWMNWEYY4yfiUFVf1LV+4F/AduAn0TkdxF5UETOdTPA3PT7\n79C6daijMMaY0PK7akhEygDdgR7ASmAwTqKY60pkIbBmDVSpEuoojDEmtM7xp5CIfAPUBj4H7lTV\nvd5dX4nIH24Fl9v+/NNZgc0YYwoyvxIDMERVf/a1Q1WvDmI8IfXnn86EecYYU5D5W5V0pYiUTH4j\nIqVE5AmXYgoJVacqqX79UEdijDGh5W9ieERVjya/UdUjwCPuhBQae/c6s6aWLRvqSIwxJrT8TQyF\nReTMkGoRKQwUcSek0LjkEti6NdRRGGNM6PnbxjAbp6F5uPf9Y95t+UrhwqGOwBhjQs+vSfS8I54f\nA1p5N80FRqpqkouxpY0hoEn0jh+HkSPh2WdBApo+yhhj8g+bXdXr1Cm47TZnIZ2//oLLLnM5OGOM\nyaNcSwwicjnQF7gSOC95u6pmsoRNcPmbGBITnS6nRYpAxYrQti3cdFMuBGiMMXlQdhKDv20MY4A3\ngA+BG4EHyaMzs44cCXFx8NVXTnLwR0yMsxJbmTLuxmaMMeHA3yeG5araWETWqGr9lNtcj/BsDH49\nMSQlwenTga2mNm4c/PgjfPFFDgI0xpg8yM0nhtPeBugtIvIksBu4MNAAc0PhwoEvsfnnnzawzRhj\nkvlbHfQ0UAzoBTQGugDd/DlQRNqIyEYR2SwiL/nYP1BEVorIChHZJCLR/gYfLDZHkjHGnJVlVZJ3\nMNt7qvpCwCd3njI243Rz3QMsAzqq6sYMyj8JNFTVHj72ubbm88UXwx9/QOXKrpzeGGNCxpU1n71j\nFa7PZkxNgC2qul1VE4BJwF2ZlO8EfBnIBV56yemSmhFV+OQTp7eSL/v3O20SlSoFclVjjMm//K1K\nWikiM0TkARFpl/zy47hKwM4U73d5t6UjIlWB6sB8P2MC4OuvMx/AJgIffwwrV/ref+CA06XVBsEZ\nY4zD38bn84DDQMoRAQpMC2IsHYEpmdUXRUZGnvk+IiKCli0j2LPHGa+QmVatYN48uOaa9Pvq13d6\nJRljTH4QFRVFVFRUjs7h6shnEWkGRKpqG+/7PoCq6ns+yq4AnlDVxRmcK13OOHwYataEI0cyj2PG\nDBg2zOmSaowxBYlr3VVFZAzOE0IqqvpQFocuA2qKSDVgL85TQScf578CKJlRUsjInj3OrKhZueEG\nuP9+py2haNFArmCMMQWPv20MM4FZ3tc84CLgRFYHeRuunwR+BNYBk1R1g4i8KSJ3pCj6H5yG6YD4\nmxhKloQrr4QlSwK9gjHGFDzZqkrydkNdqKrXBj+kDK+Zripp3z7Yvh2aNs36+B9/hBo1nKonY4wp\nKHJtdlURqQ3MUtVc+5h1YxzDli1O9VK9ekE9rTHG5BlutjHEkLqNYR+QbhRzuBk3zplCwxKDMcac\n5VdiUNXibgcSCmvWQNeuoY7CFESRUZGcTDhJZEQk5597fqjDCcjpxNMUPcd6ceRnfjU+i8g9IlIi\nxfuSInK3e2HlDpsjyYTC6cTTDFkyhA2HNtBoeCMW7wqoM15IqSrXfHYNz8x+hnBZ5MsEzt9eSW+o\n6rHkN6p6FGd9hrB1/Lgz6rlGri01ZIxj9l+zqV+hPjM6zeDtG9/m7kl30/vH3pxMOBnq0LK0ct9K\nYuJj+G3nbzw751lLDvmUv4nBVzl/R027IikJ2rQBj8f/Y1ShZUuIjoa1a6FuXaeNwZjc9OXaL+lU\nzxnO075ue9b8dw3bj20Pi6eHCX9OoOtVXZn7wFxLDvmYv4nhD+/02Jd5XwOB5W4GlpWDB2HFCigU\nwDpyIs5aDVFRzkC3Bx90LTxjfIqNj+WHv37gvivvO7Ot3AXl+Lr912eeHl6c+yIeDeAvHmDjoY38\nFZ3JbJI+nIg/wYLtC/wun+hJ5Mu1X3L/VfdT8rySrieHmNMxfLfpO0s8IeDvx+pTQDzwFc5AtFNA\nT7eC8oe/g9vSuukmmD8fGjeG//43+HEZk5kZm2ZwbZVrKVusbLp9yU8PC7YvYPDiwX6f89ipY7SZ\n0IZmI5sxZf0Uv47ZdGgTTUc2pfWE1uyJ2ePXMfP/mU/VElWpVaYWgGvJYcexHbzw4wtUH1ydR2c+\nyqDFg4JyXuM/vxKDqsaqah9VvVpVr1HVV1Q11u3gMpPTxGBMKExaN+lMNZIv5S4ox8R7J/LuwndZ\nd2CdX+d8evbTtL6sNXO6zKH33N48P+d5EpISMiw/df1Urh9zPc80fYaHGz3MsKXD/LrO539+Tpf6\nXVJtC2ZyWLp7KR2ndKTR8EaoKssfXc6ihxfR77d+LNnl37QFSZ4kuk/vzsXvX+zzVW1QNSaumZjt\nGIMhPimemNMxIY0hS6qa5QuYizOXUfL7UsAcf44N1ssJ9azhw1UfflgDlpioWqqU6p49gR9r8ret\n0Vt17f61rp0/Oi5aL+p7kR47dSzLsp8t/0wbftpQTyeezrTctPXT9LLBl2nM6RhVVT0cd1hvnXCr\nthjdQvfG7E1VNiEpQV+Y84JW+7CaLtu9TFVV/zr8l5Z5r8yZ4zMSczpGS/QtoftP7Pe5/8jJI3r1\niKu156yeejLhZJY/XzKPx6MzNs7Q60Zdp9UHVdcPF32Y7v5M3zBdq31YTQ/HHc7yXD1n9dSIsRG6\n69gu3RuzN91r0c5Fetngy/Sp75/K8t664WDsQW02sple8sEl+tuO33Llmt7PzsA+b/0qBCv92ebm\nK21iiIxUfe217N2oe+5R/frr7B1r8qffd/yuZfuX1cbDG7t2jZHLR2q7r9r5Vdbj8eidE+/UV356\nJcMye2P2aoUBFdJ9wCR5kjTy50it9EElXbBtgaqq7ovZpxFjI/SWz2/Rg7EHU5Vv91U7HbJ4SKbx\nTFg9QW/74rZMyxw5eUTvnnS3Vvuwmk78c6ImeZIyLb9011K9YcwNWu/jejp53WRNSErIsOyzs5/V\ntl+2VY/Hk2GZdxa8ow0+aaBHTx7NMs47J96pzUc2113HdmVaNpi2Rm/VWkNraZ+5ffS7Td9p+QHl\ndcjiIZn+TMHgZmJYDlRN8b46sCLQi+XklTYx/POP6rZt2btRJ06ouvxvYcLINxu+0bL9y+rMTTO1\n+qDqZ/6aDrabx9+sk9dN9rv8vph9Pj/4VZ3EccfEO/Tln17O8Pgftvyg5QeU1xd/fFErD6ysr89/\nXROTEtOV+23Hb1pjcA2f+5K1mdBGv1zzpV9xR/0TpY2HN9ZrRlxzJjGl9M+Rf7TTlE56yQeX6Mjl\nIzO9brLTiae1yWdNdODvA33uH7VilFYfVF33HPevKiDJk6TvLHhHK75fUef/Pd+vY3Ji+Z7leskH\nl+iwJcPObNsavVUbftpQO03ppCdOn3Dt2m4mhjbADuBzYAKwHWgd6MVy8kqbGEz4WbFnhf51+K9Q\nh5HKx0s/1orvVzyTDN5d8K4+NP0hv49PrgrJ6q++vTF7tUTfEhoXHxdQfGmripKN+GOEX1VN/xz5\nR++ceKfO3DQz03LNRjbTKeum+Ny3L2afluxXUmPjY/2OO8mTpBNWT9CqH1bVeybdo5sObdIjJ4/o\niz++qKXfK61v/PxGltVXvn6W8gPK6+Kdi1Nt/27Td1phQAXdeHBjQOdTVZ27da5WGFBB31v4nmt/\nuc/eMlvL9S+n09ZPS7cvLj5Ou0/vrnU/qqubDm1y5fquJQbn3JQHXgVuB+4Dbgj0Yjl5FaTEsOnQ\nJu00pZM+OetJ7fdrP52weoL+su0X3Rq9VU8lnAp1eNkSGx+rVQZW0Us+uEQ3HNwQ6nDU4/HoKz+9\nopcPuVy3Rm89s33/if1asl9JjY6L9us80zdMVyLRwYsHZ1puyOIh2mVal2zF2n16d310xqNn3ie3\nCwSzPWTyusnafGRzn/sGLRqk3b7plq3zxsXHad9f+2qZ98po2f5l9eFvH9bdx3dnO8607Q2Ldi7S\nsv3LpksWgdhxdIc2+ayJtv2ybYZtKNk1duVYrTCggi7cvjDDMh6PR4f/MTzD5JFT2UkMfs2uKiI9\ngKeBysAqoBmwSFVvyvTAIHJjdtW8aG/MXq4bfR1dG3Sl9Pml2XlsJ7tidrHr+C52HtvJ3hN76d6g\nO8PvHB7qUAPyzoJ3WLV/FXfWupOX573MvK7zuKLsFUE7//HTx1m6eymLdy1m0a5FLN+znColqtC8\ncnPnVaU51UpUQ0RISEqgx3c92HRoE991+o5yF5RLda5OUzvRvHJzejXtlek1VZV/jfgXXa/qSt+F\nfZnVeRbXVPKxfixw3ejreOX6V7i91u3Z+tkafNqAYbcOo03NNrQc25J2ddrxXPPnAj5XRpI8SVw+\n9HImtJvAtVVSz6Z/9Yir6XdzP26ucXO2z38w9iDHTh+jZumcT8j83Jzn2HpkK/1a9ePGcTcy+q7R\n3Hb5bTkLdy3dAAAb4UlEQVQ65+nE07wR9QZjV41lcJvBdKjbAfFjIfit0Vs5fPKwz30/bPmBsavH\n8n3n76lTrk6W51q2exntJ7fnYNxBn/sLS2EqFq9I5YsqU+WiKqm+1i5bO8N769q02yKyBrgGWKyq\nDb0rrr2rqu0CuVhOFITEcOzUMVqObUn7K9vzfzf8n88ysfGxNBnZhN7X9qZ7w+65G2A27Tuxj7of\n12Vpj6VcVvoyxq8eH5TksO7AOoYsGcKiXYvYemQrjS5udCYJNK7YmJ3Hd7Jo5yIW7XJeAM0rN+fw\nycOUKFqCSfdNoti5xdKdd8H2BTw+83HWPbEu0w+Hbzd+S+Qvkax4dAXTNkyj99zerHhsBSXPK5mq\n3Paj22k8ojF7nt9DkcJFsvWz/rLtFzpP68z99e9n2Z5lzOs6j0ISwOhOPwxdMpSo7VFM7TD1zLYN\nBzfQanwrdj67k8KF8sY0AfFJ8bQY04L1B9cz9NahQf09WLJrCQ9++yBXlruSj2//mPIXlE9XxqMe\n5vw1h4GLB7Jm/xqqlqjq81wVLqzAiDtGULF4FovSp5DoSeR04mmf+xI8Cew7sc/5Y/H4LnYeP/u1\nfvn69P93f5/HZScx+FuNs8z7dRVQ1Pv9ukAfT3LyIp9XJZ1KOKU3jr1Re87qmWVd59r9a7Vs/7J+\nVyX8Hf23dp/e3bU6zKz0+LaHvjDnhVTbxq0al+Nqpdu+uE17fd9Ll+xakmVdu8fj0X+O/KMT/5yo\nQ5cMzbQHjMfj0Ss/ulJ//ufnTMs0/LShTt8w/cy2p75/Su+ZdE+6f7/3Fr6Xqioou56f87xe1Pci\n3XZkW47P5UvM6Rgt816ZVO1A/zfv//T5Oc+7cr2c2HF0h3691p2uhScTTupLc1/SCgMq6KQ1k878\ne8bFx+mIP0ZonWF1tMEnDXTcqnFhUbWLi43P3wAlgUhgAfAt8H2gF8vJK2ViWL06e2MY8qokT5J2\nmNxB7/3qXr96aKiqjlk5RusMq5Nlb4a/o//Wah9W027fdNOy/cvqB79/4Pc1gmHV3lVafkB5PXLy\nSLp9OUkO+0/s1xJ9S7jWm2PI4iHaYXKHDPdP3zBdG37aMFUSOJVwShsPb6yDFg1KVbbhpw2D0vMl\nPjFe/47+O8fnyUyfuX30yVlPqqrz/7L6oOq6au8qV6+ZVy3euVjrDKuj9351r742/zUt17+c3jHx\nDp3/93zXu5gGk2uJQVN/QLcE2gJFAj02J6+UiWH6dNW2bYN010LM4/HoU98/pS3HtAxoYJCqardv\numXaKJicFJK7yP11+C+9YcwNeu2oa3Pl6cHj8Wirca1SddFLK7vJYfDiwdluzPXH0ZNHtWS/krov\nZl+6fb6eFpJtjd6q5fqX0yW7lqiq6oaDG7Ti+xVzNRnnxO7ju7Vkv5J6OO6w/rr9V633cb2w+hAM\ntpMJJ/W1+a/pEzOfyBOdJrIjVxJDqF4pE8NHH6k+/ngwblno9f21r9b/uL7Pv6izcuL0Ca0zrI6O\nWTkm3b60SSFZkidJhyweomXeK+P608PMTTP1imFXaHxifKblkpND2oFXmblmxDU6e8vsnIaYqR7f\n9tB3FryTbruvp4WUpqybotUHVdfouGh94+c39JkfnnE1zmDr9k03fXfBu/rYd49pv1/7hTock0PZ\nSQzZWvM5FFI2Pr/6KhQpAq+/HuKgshCXEMe9X9/Lwh0L0/UiqFKiCgdjDzJ8+XB+e+g3Kl1UKVvX\nWHdgHRHjIojqFkXd8nUB+OfIP9w47kZ6X9ubnk18z3W4NXorD814iERPIqPajgpqDyGAhKQErvr0\nKt7/9/t+9cR5+NuHqV6yOq+1fC3LspsObSJiXAQ7n93JOYXcm/19+Z7ltPu6HX/3+vtMw6uq0xMp\nsmUkd11xV4bH9vqhFzuP72T9wfWMv3s8TSs3dS3OYPtz/5+0mdCG+KR4Vj62kiolqoQ6JJMD2Wl8\nDm63hlyS3Qn0clNcQhx3TbqLMueXYfsz2/m6/dc81/w5mlVuBsDvO39nye4l/HD/D9lOCgB1y9dl\nwL8H0H5ye2LjY/1KCgCXlb6Mn7v9TMe6Hbl+9PX0+qEXh+IOZTuOtEYsH0Hliyr73Y3wuebP8dGy\njziVeCrLsl+s+YJO9Tq5mhQAGl/SmAoXVGD2X7PPbJuxaQYAbWu3zfTYAf8ewM5jO0lISqBJpSau\nxhlsV1W4inrl61G/Qn1LCgVVoI8YoXqRoiqpdWvVWbNy+Hzlotj4WL15/M16/9T7c61uuds33c7M\nU5NZnb4vB04c0J6zemrZ/mW1/8L+frV1ZDYPzpGTR7T8gPK6et/qgOK4dcKtOnL5yEzLeDwevXTQ\npbp8z/KAzp1do1eM1tu/uP3MtTNqW/Bl57Gd+uv2X90MzzVbDm8J+N/P5E0UlKqkrVuhfHkoXjzE\nQfmQ/KRQ4YIKjLt7XK71/Y6Nj6XV+FZ0bdCVJ655Ilvn2HRoEy/99BKr9q2ib6u+dKzXMfkxlM2H\nNzvjAbzjAjYc2sAVZa9INYCsVplaFJJC9P6xN0dPHeWztp8FdP15f8+j1+xerP3v2gzHD/y+83d6\nzOiR5RiDYIlLiKPqh1X549E/WL1v9ZlxC7lxbWOCwbUBbnlBOAxwC1VSCLZftv3C8z8+TyEpRLkL\nyrF412KKFylOs8rNziSBuuXqsuHQhlQDyI6dOkbTyk1ZtnsZa59Yy8UXXhzQdVWVRsMb0bdVX269\n/FafZf47879UKVGFV1q8Eowf1S/PzH6G8885n9lbZ2fZtmBMXmOJIYTyS1JI5lEP0zdOB6BZ5WZc\nUjzrRp19J/axaOciyhYrS4tqLbJ13c9Xf87Y1WOZ13Veun3xSfFc8sEl/PHoH1QvWT1b58+OjYc2\n0uDTBlxZ7kp7WjBhxxJDiMTGx3L3V3fnm6QQSvFJ8dQYXIOZnWfS8OKGqfZ9u/FbBi4eyC/df8n1\nuDpP7UzXBl1pU7NNrl/bmJwoML2S8pIth7fQbFQzql5U1ZJCEBQpXIReTXvxwaIP0u2bsGZCuqUl\nc8vEeydaUjAFhuuJQUTaiMhGEdksIi9lUKaDiKwTkTUiMsHtmDITGRXJi3Nf5Oipo1mWnb5xOteN\nvo6e1/RkZNuRlhSC5NHGjzJr8yx2Hd91ZtvRU0f5ceuP3HflfSGMzJiCwdXEICKFgGFAa6Au0Mk7\nM2vKMjWBl4DmqlofeCazc44eDX37uhPvzmM7GbJkCIfiDlF7WG2GLhlKfFJ8unKJnkT6/NSHXj/0\n4rtO3/H41Y9bvXMQlTyvJF0bdGXokqFntk1dP5Wba9xMqfNLhTAyYwoGt58YmgBbVHW7qiYAk4C0\nXToeAT5S1eMAqprpKKvNm8GtpoYPFn3AQ40eYvRdo/npgZ+YtWUW9T6uxzcbvkkeS8GB2APc8vkt\nLN+7nOWPLg+rEa3h5OmmTzNq5ShiTscAoa1GMqagcTsxVAJ2pni/y7stpVpAbRFZKCK/i0jrzE7o\n1qjnQ3GHGL96/JnFT+pXqM/sLrMZeutQ3oh6gxvG3sD41eNpPKIxzSs3Z/b9s9Mt8GKC59JSl9Kq\nRitGrRzFjmM7+HP/nzlejMUY4x935xTwzzlATeAGoCqwQETqJT9BpBQZGcnChc4TQ/XqEURERAQt\niCFLhnDflfel65bZumZrbq5xM+NWj+OjZR/x0W0fZTkdggmO55s/T4fJHTgRf4L76txH0XOKhjok\nY/K8qKgooqKicnQOV7urikgzIFJV23jf98EZnv1eijKf4KwMN877/ifgJVVdnuZcqqrUqQNTpkDd\nusGLM+Z0DDWG1GDRw4uCsvSgCZ4WY1rwx54/mPvAXK6ven2owzEm7OTF7qrLgJoiUk1EigAdgRlp\nykwHbgQQkbLA5cDfGZ0wbVXS6cTT5DS5DV8+nJtr3GxJIQ966bqXqHJRlXTrEBtj3OP6ADcRaQMM\nxklCo1S1n4i8ibNc6ExvmQ+ANkAi8D9VnezjPKqqbN8OVatCciegWz6/hfIXlGf0XaOztZ7uqcRT\n1Bhcgx/u/4EGFzfI7o9pXHQ68bRVIxmTTQVy5HP5AeW5qsJVAEz7zzQuKnpRQOcd/sdwZmyewazO\ns4ISpzHG5CV5sSrJVYfjDhOfFM+cLnOoXaY2N4y5gT0xe/w+PtGTSP/f+/Py9S+7GKUxxoSXsE4M\nGw9t5IqyV1C4UGGG3TaM/9T9D9eOupYNBzf4dfzkdZOpVLySNWoaY0wKYZ0YktcEAOdx6eUWL/PW\njW8RMS6ChTsWZnqsqtJ3YV97WjDGmDTCOjFsPLSROmXrpNrWtUFXPr/nc9p91Y5JayeR5Enyeeys\nLbMoXKiwTYxmjDFphFVi6NEDpk8/+z65KimtWy67hTld5vC/Bf+jdP/S3Dz+Zl6d/yqzNs/icNzh\nM08Lfa7rY3McGWNMGnlh5LPf/voLSpQ4+37DoQ3UKVfHZ9lGFRux9om1HI47zOJdi1m0axEDFw9k\n2e5llLugHIWkkM3UaYwxPoRVYkg5uO1U4il2H9/NpSUvzfSYMsXKcHut27m91u0AJHmSWHdwHeef\nc75Nk22MMT6EbWLYfHgzNUrV4NzC5wZ0jsKFCp8Z92CMMSa9sGpjEIHixZ3vNx7amGE1kjHGmOwL\nq8RQKcWE3RsObuCKMukbno0xxuRMWCWGpUvPfr/xsD0xGGOMG8IqMVyUYhqkjLqqGmOMyZmwSgzJ\nPOph8+HN1C5TO9ShGGNMvhOWiWHHsR2UPr80xYsWD3UoxhiT74RlYthwcINVIxljjEvCMjH4miPJ\nGGNMcIRVYti2zflqDc/GGOOesEoM5cs7X1NOt22MMSa4wioxFCvmfLWqJGOMcU9YJQZwlvM8nXSa\niy+8ONShGGNMvhR2iSH5acHWUTDGGHeEXWKw9gVjjHFXWE27DdYjyZhwU716dbZv3x7qMPK9atWq\nsS2562YOhWVieORfj4Q6DGOMn7Zv346qhjqMfC+Y1etWlWSMMSaVsEoMyct51ihVI9ShGGNMvhVW\niSG7y3kaY4zxX1glBmt4NsYY97meGESkjYhsFJHNIvKSj/3dROSAiKzwvh7K6FwbDm6wEc/GmDzl\nv//9L++8807Qy4aSuNlbQEQKAZuBVsAeYBnQUVU3pijTDWisqr2yOJd2nNKR22rexgMNHnAtZmNM\ncIlInu6VdOmllzJq1ChuuummUIeSIxndZ+/2gLosuf3E0ATYoqrbVTUBmATc5aOcX0FvPGTrPBtj\nck9SUlKoQwgJtxNDJWBnive7vNvSaiciq0TkaxGpnNHJbDlPY0wwde3alR07dnDHHXdw0UUXMWDA\nAAoVKsTo0aOpVq0arVq1AqBDhw5UrFiRUqVKERERwfr168+c48EHH+T1118H4JdffqFKlSoMHDiQ\nChUqUKlSJcaOHZutstHR0dx5552UKFGCpk2b8tprr9GiRQv3bwp5o/F5BlBdVRsCPwHjMipY6rxS\ntpynMSZoxo8fT9WqVZk1axbHjx+nQ4cOACxYsICNGzcyZ84cAG677Ta2bt3KgQMH+Ne//sX999+f\n4Tn37dtHTEwMe/bsYeTIkfTs2ZNjx44FXPaJJ56gePHiHDhwgLFjxzJu3LhcmyPO7cSwG6ia4n1l\n77YzVPWIt5oJYCTQOKOTFfm1CJGRkURGRhIVFRXsWI0xIRAZCSLpX5GR/pfPqKy/UtbNiwhvvvkm\n559/PkWLFgWge/fuFCtWjHPPPZfXX3+d1atXExMT4/NcRYoU4bXXXqNw4cLceuutXHjhhWzatCmg\nsh6Ph2nTpvHWW29RtGhR6tSpQ7du3fz6WaKios58TkZm88a4PSXGMqCmiFQD9gIdgU4pC4jIxaq6\nz/v2LmA9Gbj9kduJvC3SpVCNMaEQGRnYB3ug5bOjcuWzNdoej4dXXnmFKVOmcOjQIUQEEeHQoUMU\nL56+BqNMmTIUKnT2b+5ixYpx4sQJn9fJqOzBgwdJSkpKFUeVKlX8ij0iIoKIiIgz7998802/jkvJ\n1ScGVU0CngR+BNYBk1R1g4i8KSJ3eIv1EpG1IrLSW7Z7RuezhmdjTLD5qp5JuW3ixIl89913zJ8/\nn6NHj7Jt2zZU1dWeVuXKleOcc85h165dZ7bt3LkzkyOCy/U2BlWdraq1VfVyVe3n3faGqs70fv+K\nqtZT1Uaq2kpVN2d0LhvcZowJtosvvpi///4bwOcHfkxMDEWLFqVUqVLExsby8ssvu17XX6hQIdq1\na0dkZCQnT55k48aNjB8/3tVrprp+rl0pCGxwmzEm2Pr06cPbb79N6dKlmTp1aroP/a5du1K1alUq\nVapEvXr1uPbaawM6fyBJJGXZoUOHcvToUSpWrEi3bt3o3LnzmTYPt7k6wC2YREQ9Ho+t3GZMmMnr\nA9zCRZ8+fdi/fz9jxozxuT+cBrgFlSUFY0xBsWnTJtasWQPA0qVLGTVqFO3atcuVa4fdQj3GGFMQ\nxMTE0KlTJ/bu3UuFChXo3bs3d955Z65cO6yqksIlVmPMWVaVlDsKbFWSMcYY91liMMYYk4olBmOM\nMalYYjDGGJOKJQZjjDGpWGIwxpgUUq6ZUFBZYjDGGJOKJQZjjDGpWGIwxhRoK1eupHHjxpQoUYKO\nHTty6tSpM/tmzpxJo0aNKFWqFNdff/2ZKSr69+9P+/btU53n6aef5plnnsnV2N1iicEYU2AlJCRw\nzz330K1bN6Kjo2nfvj1Tp04FYNWqVTz88MN89tlnREdH89hjj9G2bVsSEhLo2LEjP/zwA7GxsYCz\nmM/kyZMzXfIznNiUGMYYV2U1JYa8GZzJMfWNwD8ffv31Vzp16pRqQZzrrruOVq1acejQIcqVK5dq\nBbQrrriCzz77jBYtWnDDDTfw6KOP0qVLF+bOncsTTzzBli1bgvKzZEcwp8SwSfSMMSGVnQ/0YNmz\nZw+VKlVKta1atWoAbN++nXHjxjF06FDAWcQnISGBPXv2ANCpUye+/PJLunTpwpdffknnzp1zN3gX\n2RODMcZVeXkSvQULFtC5c+dUTwzXX389N910EwcPHqRq1aq8/PLLPo89dOgQ1apVY/PmzdSrV4/F\nixdTu3bt3Ao9HZtEzxhjgqB58+acc845DB06lMTERKZNm8bSpUsB6NGjB5988smZ97GxsXz//fdn\n2hXKli1Ly5YtefDBB6lRo0ZIk0KwWWIwxhRY5557LtOmTWPMmDGUKVOGyZMnc++99wLQuHFjRo4c\nyZNPPknp0qWpVasW48aNS3V8586dmTdvXr5pdE5mVUnGGFfl5aqk/MSqkowxxrjGEoMxxphULDEY\nY4xJxRKDMcaYVCwxGGOMScUSgzHGmFRsSgxjjKuqVauGSHDmQzIZS57KIxhcH8cgIm2AQThPJ6NU\n9b0Myt0LTAauVtUVPvbbOAZjjAlQnhvHICKFgGFAa6Au0ElErvBR7kKgF7DYzXjyi6ioqFCHkGfY\nvTjL7sVZdi9yxu02hibAFlXdrqoJwCTgLh/l3gb6AaddjidfsP/0Z9m9OMvuxVl2L3LG7cRQCdiZ\n4v0u77YzRKQRUFlVf3A5FmOMMX4IaeOzOC1SA4FuKTeHKBxjjDG43PgsIs2ASFVt433fB9DkBmgR\nuQj4CziBkxAuBg4DbdM2QIuItTwbY0w2BNr47HZiKAxsAloBe4GlQCdV3ZBB+Z+B51R1pWtBGWOM\nyZSrbQyqmgQ8CfwIrAMmqeoGEXlTRO7wdQhWlWSMMSEVNusxGGOMyR1hMSWGiLQRkY0isllEXgp1\nPLlJREaJyH4R+TPFtlIi8qOIbBKROSJSIpQx5gYRqSwi80VknYisEZFe3u0F8V4UFZElIrLSey/e\n8G6vLiKLvb8nX4pIgZnZQEQKicgKEZnhfV8g74WIbBOR1d7/G0u92wL+HcnzicHfQXL52Bicnz2l\nPsBPqlobmA/4Xq08f0nEaX+qCzQHenr/HxS4e6Gqp4EbVbUR0BC4VUSaAu8BH6hqLeAo8HAIw8xt\nTwPrU7wvqPfCA0SoaiNVbeLdFvDvSJ5PDPg/SC5fUtWFwJE0m+8CkhefHQfcnatBhYCq7lPVVd7v\nTwAbgMoUwHsBoKpx3m+L4nQ7V+BGYKp3+zjgnhCElutEpDJwGzAyxeabKID3AqeNNu3nesC/I+GQ\nGLIcJFcAlVfV/eB8YALlQxxPrhKR6jh/KS8GKhTEe+GtOlkJ7APmAluBo6rq8RbZBVwSqvhy2YdA\nb5zkiIiUAY4U0HuhwBwRWSYiPbzbAv4dKRD1bgVAgelB4J1XawrwtKqe8DG+pUDcC++HXiPvWKBv\ngIJUvXqGiNwO7FfVVSISkXJXiEIKtetUda+IlAN+FJFNpP+dyPJ3JByeGHYDVVO8r+zdVpDtF5EK\nACJyMXAgxPHkCm8D4hTgc1X91ru5QN6LZKp6HIjCaXcp6W2Tg4Lze3Id0FZE/ga+xKlCGgyUKID3\nAlXd6/16EJiOUxUf8O9IOCSGZUBNEakmIkWAjsCMEMeU24TUfwHNALp7v+8GfJv2gHxqNLBeVQen\n2Fbg7oWIlE3uWSIi5wP/xml4/Rlo7y1WIO6Fqr6iqlVVtQbOZ8N8Ve1CAbwXIlLM+0SNiFwA3AKs\nIRu/I2ExjsG7psNgzq7p0C/EIeUaEZkIRABlgP3AGzh/CUwGqgDbgQ6qejRUMeYGEbkOWIDzH129\nr1dwRtN/TcG6F/VxGhELeV9fqeo7InIpTueMUsBKoIu3w0aBICItgedVtW1BvBfen/kbnN+Nc4Av\nVLWfiJQmwN+RsEgMxhhjck84VCUZY4zJRZYYjDHGpGKJwRhjTCqWGIwxxqRiicEYY0wqlhiMMcak\nYonBFDgistD7tZqIdAryuV9O835hMM9vTG6wcQymwPLOrfO8qt4ZwDGFvSsTZrQ/RlWLByM+Y0LF\nnhhMgSMiMd5v+wLXexd4edo7Y2l/7yI4q0TkEW/5liKyQES+xVmiFhH5xjuD5ZrkWSxFpC9wvvd8\nn6e5FiIywFt+tYh0SHHun0VksohsSD7OmFCy2VVNQZT8mNwH7xQKAN5EcFRVm3rn5fpNRH70lm0E\n1FXVHd73D6rqURE5D1gmIlNV9WUR6amq/0p7LRG5F7hKVeuLSHnvMb94yzQErsSZQvs3EblWVX93\n6Wc3Jkv2xGDMWbcAXb3rHCwBSgOXe/ctTZEUAJ4RkVU4a0JUTlEuI9fhzP6Jqh7AmRH1mhTn3qtO\nve4qoHrOfxRjss+eGIw5S4CnVHVuqo3O5Gyxad7fBDRV1dMi8jNwXopz+HutZKdTfJ+E/V6aELMn\nBlMQJX8oxwApG4rnAE8kLxwvIpeLSDEfx5fAWSHstHfd6WYp9sWnWXg++Vq/Av/xtmOUA1rgzAxr\nTJ5jf5mYgii5jeFPwOOtOhqrqoO9y4auEBHBWdDE1/q4s4HHRWQdsAlYlGLfCOBPEVmuqg8kX0tV\nvxGRZsBqnAXbe6vqARGpk0FsxoSMdVc1xhiTilUlGWOMScUSgzHGmFQsMRhjjEnFEoMxxphULDEY\nY4xJxRKDMcaYVCwxGGOMScUSgzHGmFT+H8odJhJnVxELAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b3477add0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_accs(theta_perc_history);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# execute this code to write the predictions on the dev and training data\n",
    "y_hat_dv = clf_base.predict_all(x_dv,theta_perc,labels)\n",
    "evaluation.write_predictions(y_hat_dv,'perc-dev.preds')\n",
    "y_hat_te = clf_base.predict_all(x_te,theta_perc,labels)\n",
    "evaluation.write_predictions(y_hat_te,'perc-test.preds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Averaged Perceptron \n",
    "\n",
    "You will now implement the averaged perceptron, which often achieves better generalization than the standard perceptron. The basic idea, as described in the notes, is to average the weights across each update:\n",
    "\n",
    "\\begin{align}\n",
    "\\hat{y} \\gets & \\text{argmax}_y \\theta^{\\top}f(x,y)\\\\\n",
    "\\theta_t \\gets & f(x,y) - f(x,\\hat{y})\\\\\n",
    "m \\gets & m + \\theta_t\\\\\n",
    "\\overline{\\theta} \\gets & \\frac{m}{t}\n",
    "\\end{align}\n",
    "\n",
    "Note that during training, prediction is performed using the non-averaged weights, $\\theta$. The averaged weights are only returned at the end. They often give better generalization than the standard perceptron.\n",
    "\n",
    "However, it is too inefficient to repeatedly compute the sum $m + \\theta_t$. The reason is that we must perform an operation for every feature with non-zero weight. There are many more such features than there are non-zero features in any given example, $f(x_i, y)$. Therefore, this addition will dominate the computation.\n",
    "\n",
    "An efficient solution was pointed out by [Daume 2006](http://hal3.name/docs/daume06thesis.pdf). \n",
    "Let $\\delta_t$ indicate the update at time $t$.\n",
    "Assuming $\\theta^0 = 0$, \n",
    "\\begin{align*}\n",
    "\\theta^t = & \\theta^{t-1} + \\delta_t \\\\\n",
    "= & \\sum_{t' < t} \\delta_{t'}\n",
    "\\end{align*}\n",
    "\n",
    "We would like to compute the sum of the weight vectors,\n",
    "\\begin{align*}\n",
    "\\sum_t^T \\theta_t = & \\sum_t^T \\sum_{t' \\leq t} \\delta_{t'} = T \\delta_0 + (T-1) \\delta_1 + (T - 2) \\delta_2 + \\ldots + \\delta_T \\\\ \n",
    "= & \\sum_t^T (T - t) \\delta_t\\\\\n",
    "= & T \\sum_t^T \\delta_t - \\sum_t^T t \\delta_t \\\\\n",
    "= & T \\theta_t - \\sum_t^T t \\delta_t \\\\\n",
    "\\frac{1}{T} \\sum_t^T \\theta_t = & \\theta_T - \\frac{1}{T} \\sum_t^T t \\delta_t\n",
    "\\end{align*}\n",
    "\n",
    "This means we need to keep another running sum, $\\sum_t^T t \\delta_t$, the sum of scaled updates. \n",
    "To compute the average, we divide by the number of updates $T$ and subtract it from the current weight vector.\n",
    "\n",
    "**Deliverable 4.3**\n",
    "\n",
    "Implement ```estimate_average_perceptron``` in ```perceptron.py```. (1 point)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(perceptron);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "theta_avp,theta_avp_history = perceptron.estimate_avg_perceptron(x_tr[:10],y_tr[:10],3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 16.5 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "theta_avp,theta_avp_history = perceptron.estimate_avg_perceptron(x_tr,y_tr,20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_avp,theta_avp_history = perceptron.estimate_avg_perceptron(x_tr,y_tr,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.664\n"
     ]
    }
   ],
   "source": [
    "y_hat = clf_base.predict_all(x_dv,theta_avp,labels)\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEPCAYAAABRHfM8AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8FfW9//HXJ2yCKIRNLbsCalArrmhdolahi1pRECyK\nWFut2qpVf+JKqNertL1eW7e6UKp1YRFRQa9GgePWKijgwhJwAdlkkT0YIMnn98dM4JAEPCfJ5Jyc\nvJ+Px3kkM/Odmc8ZOOeT+W5j7o6IiMj3yUp1ACIiUjcoYYiISEKUMEREJCFKGCIikhAlDBERSYgS\nhoiIJCTShGFmo8xspZl9socyfzOzhWY228yOjFs/xMwWmFmBmV0SZZwiIvL9or7DGA302d1GM/sJ\ncJC7dweuAP4ers8G7gSOBY4HhptZi4hjFRGRPYg0Ybj7u8C6PRQ5F3gqLPsB0MLM9iNIMvnuvsHd\n1wP5QN8oYxURkT1LdRtGe2BJ3PLScF359cvCdSIikiKpThjlWaoDEBGRyjVM8fmXAR3jljuE65YB\nueXWT6vsAGamybBERKrA3ZP6I702Eoax+zuHl4GrgbFm1htY7+4rzex14O6woTsLOBMYtrsTaALF\nQF5eHnl5eakOIy3oWuyka7FTulwLdygshC1bgp9lr9JSOOGEiuU3b4YxYyqub9YMLrqo4vpvvoFB\ng+AXv4Brr608BrPkK3QiTRhm9izBnUJrM/saGA40BtzdH3P3V83sp2b2OVAIDCXYuM7M7gI+BBwY\nETZ+i4jUmi1bYPVqKCqCbduCdYcfXrHc5s3w4IOwbh2sXx+8Nm2Cpk1hwoSK5VesgO7dYe+9g1ez\nZsHPjh0rL799O/znP1D+Oz47u/KE0bIl3HEHHHRQ8u95TyJNGO5eyVupUOaa3az/J/DPGg5JROqh\nkhL45BMoKIBnn935l31pKVx/fcXya9cGX96lpdCmTfDF37gxtG0L0yqpHDcLkkR2NnTtGnxh77NP\n8LMyP/hBcP5EZWfDqFGJl99rLzj99MTLJyrVbRhSg3Jzc1MdQtrQtdgpU6/F2rUVq3W2bIGzzqr4\nl/i2bTBkCOy9dy6TJu38iz47u/JjZ2cH1TrNm1c8VmX23hvuvbf67yndWV2v/zczr+vvQUSCu4CV\nK2HZsuC1fHlQdTN8ODSs5E/b/faDRo12fvmXVe288kqwXvbMzNKy0VtE6qGCAvj22511+mWva68N\nvtzLa98++Gv+Bz8Ifv/BD+CAA6C4uPKEsXJl9O9BdqWEISIJmTQJZsyA+fNh48adVUCvvAL771+x\n/JVXBo3FLVtCixZBNU/LlsGdRGWWLYMGDaJ9D1I9qpISqefcg7/8V60KegQdfnjwBV/eddfBvvtC\nTk6wvawK6IgjggZhqVuqUiWlhCGSoQoL4fPPoXPnynvrDB0Kr70WVBs1axb0AGrXDh55JEgCktmU\nMETqsXHj4M03YeFCWLAgGBNw4IHw+OOVDwZbtChoHG7TBpo0qfVwJcWUMEQy3Pr1QSNwmzYVt40b\nF9wtdO8OPXpAhw6QlW6zxUnaUMIQySDffQezZ8P06UFj8/TpQTfT++6DX/861dFJXaeEIVLHFBYG\niaGyO4YnngjaE447Do49NngdemjlXUxFkqWEIZLGVqwI5gmaMQNmzoSvvw5GIA8dCg8/nOropL7R\nwD2RFCsqgjVrgvaD8lavDuYzOumkYPBaly7B2IQqTBoqkhK6wxCpom+/hZEjYelS+OqroNfRunVB\nQnjzzVRHJ7JnusMQqSGlpfDppxCLwZw58NhjFcs0agStWgVjFrp2De4YDjhAPZMkc+kOQyTkDg88\nEExf/fbbQUN0bm7wGjhQVUeSWXSHIVINZsGU2QMGwEMPBZPfichOusOQemP1apg4MZgO46abKh/9\nLFJfVOUOQ7WtktHWrAnaH848E7p1gylT4Pzz4eCDUx2ZSN2jKinJaC+9BFOnBlNtv/RSMMmeiFRN\n5FVSZtYXuJ/gbmaUu48st70T8A+gLfAtMNjdl4fbSoCPAQMWu/svKjm+qqRERJKUdiO9zSwLWACc\nASwHZgAD3X1+XJlxwMvu/rSZ5QKXufsl4baN7r7v95xDCaMemzsXnnwS3ngjmGtJ02aIJCYd2zCO\nAxa6+2J33w6MAc4tVyYHmAbg7rFy29WRUSoYOxauvhp69YIf/zjo3fTMM0oWIlGL+iPWHlgSt7yU\nIInEmw30Ax4ws35AczPLdvd1QBMzmw4UAyPd/aWI45U6oKAgaMC+6CI4/nglCpHakg4ftZuAB83s\nUuBtYBlQ9tTfzu6+wsy6AlPN7BN3/6r8AfLy8nb8npubS25ubtQxS4SKiuDZZ4OH/1T2T3nnnbUe\nkkidF4vFiMVi1TpG1G0YvYE8d+8bLg8DvHzDd1z5vYF57t6pkm2jgUnu/kK59WrDyBArVgTTeT/6\nKBxzDAwfHkztLSI1Lx3bMGYA3cyss5k1BgYCL8cXMLPWZjsmXbiFoMcUZtYy3AczawOcCMyNOF5J\ngTVr4JJLoGfPYEK/t9+GV15RshBJN5FWSbl7iZldA+Szs1vtPDMbAcxw98lALnCPmZUSVEldHe5+\nKPBo2LU2C7gnvneVZI599gkasP/612C6bxFJT5oaRGrNli1Bj6amTVMdiYikY5WUCMuXw803Q8eO\nwUywIlI3KWFIZObOhcsug8MOC55b/eGH8NOfpjoqEamqdOhWKxlo5swgOVxzDSxcCK1bpzoiEaku\ntWFIJNyD8RRqrxBJT2rDkFq1fTtMmhSMnyhPjdsimUcJQ5K2cCHccEPQiH3vvbByZaojEpHaoIQh\nCSsoCB4+dOKJ0LhxMMDuvffgyCNTHZmI1AY1ekvCSkvh1FOD6cSbN091NCJS29ToLSJSD6nRW6qt\npCR4tkRBQaojEZF0o4QhQNANduJE+OEP4cEHg4F2IiLx1IZRz7kHjze97bagm+y998LPfhZ0ixUR\niac2jHpu9Wo46yy45Ra44ALI0j2nSL1QlTYMJQzBXXcUIvWNGr2lSpQsRCQRShj1xJo18Je/BHcT\nIiJVoYSR4bZtg7//PZhifOnSoGFbRKQq1EsqQ5WNp8jLg+7d4dVX4aijUh2ViNRlShgZ6p//hNGj\ng9epp6Y6GhHJBJH3kjKzvsD9BNVfo9x9ZLntnYB/AG2Bb4HB7r483DYEuA1w4G53f6qS46uXVCVK\nSoIusmrQFpHKpF23WjPLAhYAZwDLgRnAQHefH1dmHPCyuz9tZrnAZe5+iZllAx8CRwEGfAQc5e4b\nyp1DCUNEJEnp2K32OGChuy929+3AGODccmVygGkA7h6L294HyHf3De6+HsgH+kYcb50zcyZMnpzq\nKESkPog6YbQHlsQtLw3XxZsN9AMws35A8/Duovy+yyrZt95yh/vvh759YevWVEcjIvVBOjR63wQ8\naGaXAm8TJIaSZA6Ql5e34/fc3Fxyc3NrLro0tHo1XHopfPstvP8+HHhgqiMSkXQXi8WIxWLVOkbU\nbRi9gTx37xsuDwO8fMN3XPm9gXnu3snMBgK57n5luO3vwDR3H1tun3rVhvHuuzBwIAweDHfdBY0a\npToiEamL0rHRuwFQQNDovQKYDgxy93lxZVoDa93dzey/gGJ3zyvX6J0V/n502J4Rf456lTBmzgzu\nLM48M9WRiEhdVpWEEWmVlLuXmNk1BA3WZd1q55nZCGCGu08GcoF7zKyUoErq6nDfdWZ2F0GicGBE\n+WRRH2nwnYikimarFRGph9KxW61U0bRpcOedqY5CRGQnJYw04x7M/3TxxdC7d6qjERHZKR261UrI\nPbirePFFmDUL2rZNdUQiIjvpDiNNxCeLqVOVLEQk/ShhpImiIliyRMlCRNKXekmJiNRD6iUlIiKR\nUcIQEZGEKGGkgDuMGQPFxamOREQkcUoYtcwdbroJRo6ETZtSHY2ISOI0DqMWucN118F778GUKZCd\nneqIREQSp4RRS0pL4Zprgtlm33wTWrZMdUQiIslRwqgl990HH38M+fmw776pjkZEJHkah1FLNm4E\nM9hnn1RHIiKShg9Qqg11JWGIiKQTDdwTEZHIKGGIiEhClDAisGkTXHstbN+e6khERGqOeknVMHe4\n6ipo3BgaNUp1NCIiNSfyOwwz62tm881sgZndXMn2jmY21cxmmtlsM/tJuL6zmW0J1880s4ejjrUm\nPPkkfPQR/O1vqY5ERKRmRdpLysyygAXAGcByYAYw0N3nx5V5FJjp7o+a2aHAq+7e1cw6A5Pc/Yjv\nOUfa9JKaNw9OOSV4Hvdhh6U6GhGR3UvHXlLHAQvdfbG7bwfGAOeWK1MKlA1lawksi9uW1JtJpe++\ngwsvhP/+byULEclMUSeM9sCSuOWl4bp4I4CLzWwJMBn4Xdy2Lmb2kZlNM7OTog21erKy4MYb4fLL\nUx2JiEg00qHRexAw2t3/18x6A08DPYEVQCd3X2dmRwEvmlmOu28uf4C8vLwdv+fm5pKbm1srgcdr\n0gQuuaTWTysikpBYLEYsFqvWMaJuw+gN5Ll733B5GODuPjKuzGdAH3dfFi5/ARzv7mvKHWsacIO7\nzyy3Pm3aMERE6op0bMOYAXQLezw1BgYCL5crsxj4MUDY6N3E3deYWZuw0RwzOxDoBnwZcbwiIrIb\nkVZJuXuJmV0D5BMkp1HuPs/MRgAz3H0ycCPwuJldT9AAPiTc/RTgj2a2LVx/hbuvjzLeZGzZEjR0\nt26d6khERGqHJh+sgtJSGDAADjooeHKeiEhdU5UqqXRo9K5z7rgDvvkGnnkm1ZGIiNQeJYwk/etf\n8Nxz8MEHQc8oEZH6QlVSSXjvPTjvvGAkd8+etXJKEZFIRNZLysxeMLOflfVaqq9iMXjqKSULEamf\nErrDMLMfA0OB3sB4goF2BRHHlhCNwxARSV7kj2g1sxYEI7NvI5jy43Hg6XCeqJRQwhARSV6kA/fM\nrDVwKXA5MAv4K3AU8EYyJxQRkbopoV5SZjYROBj4F3C2u68IN401sw+jCk5ERNJHom0Yp7n7tFqI\nJ2lRVkm5w4wZcNxxkRxeRCRloqySyjGzlnEnyjazq5KKrg565RW47LJgZLeISH2X6B3GbHc/sty6\nWe7eK7LIEhTVHUZJCRx5JNx9N5xzTo0fXkQkpaK8w2hgZjsObGYNgMbJnKiuefZZ2HdfOPvsVEci\nIpIeEp0a5DWCBu5Hw+UrwnUZaetWuPPOYJCe1ZmHxIqIRCvRKqksgiRxRrjqDeAJdy+JMLaERFEl\n9cgjMHly0IYhIpKJIh+4l46iSBiFhbB+PbQv//RxEZEMEVnCMLPuwD1ADrBX2Xp3PzDZIGuaRnqL\niCQvykbv0cAjQDFwGvAU8HRy4YmISF2WaMJo6u5TCO5IFrt7HvCz6MISEZF0k2gvqa1hw/fC8Bnd\ny4Dm0YUlIiLpJtE7jGuBZsDvgaOBwcCQRHY0s75mNt/MFpjZzZVs72hmU81sppnNNrOfxG27xcwW\nmtk8MzsrwVirZNYsePnlKM8gIlK3fe8dRjhI70J3vxHYTPBcjISEdyUPEnTHXQ7MMLOX3H1+XLHb\ngbHu/qiZHQq8CnQ1sxxgAHAo0AF408y6R9XC/Ze/wDHHRHFkEZHM8L13GOFYi5OqePzjgIVhu8d2\nYAxwbrkypcC+4e8tCaq7AM4Bxrh7sbsvAhaGx6txq1cHYy6GJHTPJCJSPyXahjHLzF4meNpeYdlK\nd3/he/ZrT/CgpTJLqfilPwLIN7PfE1R7/Thu3//ElVsWrqtx//hH8KzuVq2iOLqISGZINGHsBXwL\nnB63zoHvSxiJGETwyNf/NbPeBN11k3pqdl5e3o7fc3Nzyc3NTXjf0lJ49FEYOzaZM4qI1C2xWIxY\nLFatY0Q60jtMAHnu3jdcHga4u4+MK/MZ0Mfdl4XLXwDHEzzZD3e/N1z/GjDc3T8od45qNWvk58Ot\nt8KHegyUiNQjUY70Hk1wR7ELd7/se/ZrABQQNHqvAKYDg9x9XlyZV4Bx7v5k2Oj9hrt3CBu9nyFI\nHu0J5q+q0Ohd3YRRUgIrVkCHDlU+hIhInVOVhJFoldTkuN/3As4j6PW0R+5eEo7byCdoYB/l7vPM\nbAQww90nAzcCj5vZ9QQN4EPCfeea2ThgLrAduCqKHlINGihZiIgkokpVUmF32Xfd/cSaDynpWDSX\nlIhIkqKcS6q87kC7Ku4rIiJ1UEJVUma2iV3bML4BKozaFhGRzJVQwnD3faIOpLY9+2ww9qJp01RH\nIiJSNyRUJWVm55lZi7jllmb2i+jCitbcuXDDDUGDt4iIJCbRNozh7r6hbMHd1wPDowkpeo89Br/6\nFTRunOpIRETqjkS71VaWWBLdN62UlsLzz8OUKamORESkbkn0DuNDM7vPzA4KX/cBH0UZWFQ++gia\nN4eDD051JCIidUuiCeN3wDZgLMGMs0XA1VEFFaWXXoJf1NnWFxGR1Il0LqnakOzAvVmzoEULOPDA\nCIMSEUlzkQ3cM7M3zKxl3HK2mb2ebIDpoFcvJQsRkapItEqqTdgzCgB3X4dGeouI1CuJJoxSM+tU\ntmBmXahk9loREclciXaNvQ1418zeAgw4GfhNZFGJiEjaSbjR28zaESSJWUBTYJW7vx1hbAlJtNF7\n2zYN1BMRKRNlo/flwBTgBoLnV/wLyEs2wFS64AKYPPn7y4mISOUSbcO4FjgWWOzupwG9gPV73iV9\nbN4MsRicdFKqIxERqbsSTRhF7l4EYGZN3H0+UGfGSufnQ+/e0LLl95cVEZHKJdrovTQch/Ei8IaZ\nrQMWRxdWzXrxRY3uFhGprqRHepvZqUAL4DV33xZJVMnFs8dG7+3bYf/94eOP9exuEZEyVWn0TnrG\nWXd/K5nyZtYXuJ+g+muUu48st/0+4DSCcR17A23dvVW4rQT4mKAr72J3T/o+YckSOOMMJQsRkeqK\ndC4pM8sCFgBnAMuBGcDAsA2ksvLXAEe6++Xh8kZ33/d7zpHUXFIiIhJht9pqOA5Y6O6L3X07wUy3\n5+6h/CDgubjlpN6MiIhEJ+qE0R5YEre8NFxXQTj1SBdgatzqJmY23cz+bWZ7SjQiIhKxdHpq3kDg\n+XL1S53dfYWZdQWmmtkn7v5V+R3z8vJ2/J6bm0tubm7UsYqI1CmxWIxYLFatY0TdhtEbyHP3vuHy\nMMDLN3yH22YCV7n7+7s51mhgkru/UG692jBERJKUjm0YM4BuZtbZzBoT3EW8XL6QmR0CtIxPFmbW\nMtwHM2sDnAjMTfTEixfDQw9VN3wRESkTacJw9xLgGiAfmAOMcfd5ZjbCzH4eV/RCggbxeIcSPEt8\nFsE8VvfsrndVZfLz4f1K71VERKQqMvYRrddfD+3bw403piAoEZE0l45VUikzdy7k5KQ6ChGRzJGx\nCWPOHCUMEZGalJEJY8MGWL8eOnX6/rIiIpKYjEwYWVnwj38EP0VEpGZkbKO3iIjsnhq9RUQkMkoY\nIiKSECUMERFJiBKGiIgkJOMSxqefws03pzoKEZHMk3EJ46OPYPnyVEchIpJ5Mi5haEoQEZFoKGGI\niEhClDBERCQhGTXSu7AQ2raFTZugQYMUByYiksbq/Ujvxo3hrbeULEREopBRdxgiIpKYen+HISIi\n0VHCEBGRhESeMMysr5nNN7MFZlZhDLaZ3Wdms8xsppkVmNnauG1Dwv0KzOySqGMVEZHdi7QNw8yy\ngAXAGcByYAYw0N3n76b8NcCR7n65mWUDHwJHAQZ8BBzl7hvK7aM2DBGRJKVjG8ZxwEJ3X+zu24Ex\nwLl7KD8IeC78vQ+Q7+4b3H09kA/03d2On3wC5+7pyCIiUi1RJ4z2wJK45aXhugrMrBPQBZi6m32X\n7W5fgM8+g732qk6oIiKyJw1THUCcgcDzValfysvLY8oUaNgQYrFccnNzaz46EZE6LBaLEYvFqnWM\nqNswegN57t43XB4GuLuPrKTsTOAqd38/XB4I5Lr7leHy34Fp7j623H7u7px3Hvzyl3DBBZG9HRGR\njJGObRgzgG5m1tnMGhPcRbxcvpCZHQK0LEsWodeBM82sRdgAfma4rlKaQ0pEJFqRVkm5e0nY8ymf\nIDmNcvd5ZjYCmOHuk8OiFxI0iMfvu87M7iLoKeXAiLDxu4KtW+Hrr6Fbt8jeiohIvZcxU4OsWwfZ\n2amORkSkbqhKlVTGJAwREUlcOrZhiIhIhlDCEBGRhKTTOAwRqUe6dOnC4sWLUx1GxuvcuTOLFi2q\nkWNlRBtGUZHTpEmqIxGRZIR16KkOI+Pt7jrX2zaMXr1SHYGISObLiIRxyCGpjkBEJPNlRMLQCG8R\nkehlRMLo2TPVEYiIZL6M6CWVjncY7s7YOWP5w+t/YO/Ge9OzbU9y2ubs+HlIm0No2qhpjZ937Xdr\nmbt6LnNWzQl+rp7DnNVzWLl5ZdLHapjVkG6tutGzXc9d4u/eujuNshqxYvMK5qwKjl92rrmr57Kh\naMP3HzwJPVr3oH9Of/r37M/h7Q7HLLF2um+3fBu8/1W7xre9dDs5bXPIaZOzy3vbv/n+CR/7i7Vf\nMH7ueMbNGceqwlX0O7Qf/XP686NOPyLLMuLvsCpxd5ZsXLLj/2DZNZ+/Zv4u/45dWnZJdaiR++1v\nf0uHDh247bbbarRsKmVEL6ktW5ymNf/dW2UrN6/kt6/8loJvC3ji7CdouVfLCl+qn6/9nMPaHcbD\nP32YY9sfW63zbdy6kQc+eIBHPnyEjVs3Bl+G4Zd7z3bBl2H7fdon/GVYZmvxVhauXVghKXy94Wsa\nN2hMkwZNKiSTnLY5tG7WulrvJ567M3PFTMbNGcf4ueNp0rAJA3IG7JI8KksMc1bPoai4aJfYyq5F\no6xGu/xblO1b6qW7lC2fSOKTxPJNy3ckif2b78+EeRMYP3c8qwtXc0HOBbskj01bNzFvzbwd17Hs\nGp7S6RQG9BzAKZ1PoUFWgxq5XqsLV1e4FuuL1vPzHj+nf05/jtjviD3+P5izag7j547npYKXWPfd\nuqTPv/a7tTRv3LzCNT+49cF8vPJjxs0Zx8T5E+nSsgsf/ubDtO4l1bVrV0aNGsXpp5+e6lCqpSZ7\nSWVEwqip9/Dlui+5Y9odnNPjHC7IuSDpD7G7M+azMVz3+nVcduRlDM8dzl4NK3+q0/aS7Tw/9/kd\nZfNy82jSMLm+wWWJ4v4P7qdvt77c/KOb6dm2Z9KJIVlFxUUUbius0cSQCHdnxvIZjJ8znvFzx5Nl\nWWzZvoXvir/b+QVVjSS5qnBVheRYlkja7t2WDUUbdiSJ3X3JF6wpYPzcIL5Vhato3KAxqwtXc0ib\nQ4K4wrua9vu0540v32D83PEs3biUfof0Syp5lCWG8n/JbyvZtiPZlSW8Zo2a8VLBS4ybM47GDRoz\noOeAXZJHWZIYP3c8G4o20D+nP+fnnE+HfTsk9e8D0KJJC7Kb7nlSt+LSYmKLYpx50Jl1NmGUlJTQ\noEHNJPmoKWHEqamE8c7idxjw/ACGHjmUqV9NZdO2Tdx5yp0JJ474u4p/nvvPhO8aqrJf+URx+8m3\nc3CbgxM6X6Zwdz5b9RnZTbOrdPeUzHlWFa5i+ablHLHfEUn9EfH52s8B6Nqy6x73+3zt5zw/93nG\nzRnHsk3LOLXzqTRq0KjSWJZvWr6jWq38nV3Pdj05oPkBu70W7s6Hyz/ccbfWuEFjGjVotCNJ9O/Z\nn94detdalVo6j8O45JJLeOaZZ2jSpAkNGzbkjjvu4Oabb+aJJ55gxIgRdO3alVgsxoABA3jnnXco\nKirihz/8IQ8//DA5YR350KFD6dixI3/84x956623GDx4MNdffz0jR46kYcOG3H333Vx66aVJl127\ndi1Dhgzh7bff5pBDDuGss84iFovxzjvvVPpeajJh4O51+hW8heoZNXOUt/tzO8//PN/d3UtLS/21\nha/58Y8f7zkP5fiYT8d4cUnxLvuUlJb4F2u/8Jfnv+x3vXWXt/tzO7/lzVu8aHtR0ucvLS315z59\nztv9uZ0Pe2NYhWNsLd7qn638zMd+Ntb/X/7/8zZ/auODXxjs81fPr/qblrS08NuF/swnz/jTHz9d\n6Sv/83xftnGZl5aWVus8paWlPn3pdP/31//2ktKSGoo+OTXx2Y1Sly5dfOrUqe7uvmjRIjczHzJk\niG/ZssWLioLP6OjRo72wsNC3bdvm119/vR955JE79r/00kv9jjvucHf3WCzmDRs29Ly8PC8uLvZX\nX33VmzVr5uvXr0+67IUXXuiDBg3yoqIinzt3rnfs2NFPPvnk3b6P3V3ncH1y37fJ7pBur+r8pysu\nKfY/vPYH7/a3bj5v9bwK28snjuHThvvFL1zsRz16lDe7u5l3vK+j9326r//htT/4jGUzqhxHmW82\nfePnjTnPcx7K8Tum3uEXjLvAD33wUN/rv/byHg/08PPGnOe3T7ldiUIyQiKf3eHDg2+p8q/hwxMr\nv7tyiejSpYtPmTLF3YOEkZWV5YsWLdpt+XXr1rmZ+caNG929YhJo1qyZl5TsTM7t2rXzDz74IKmy\nJSUl3qhRI1+4cOGObbfffnutJYyM6CVVFRu3bmTQhEEUFRfxweUf0KppqwplzIw+3fpw1kFnkf9F\nPlO/mkpul1yuOvYqctrmsG+TfWs0pv2a78eEAROYMG8Cs7+ZTb9D+nHHKXfQo3WP3baFiGSyvLzg\nFVX5ZHXosLNdp7S0lFtvvZXnn3+eNWvWYGaYGWvWrGGfffapsG/r1q3JytpZ3desWTM2b95c6Xl2\nV3b16tWUlJTsEkfHjh1r4q0lpF4mjK/WfcXZz53NyZ1O5m8/+Vul9cXxyhJHn259Io/NzLgg5wIu\nyNHDyUVSqbK2oPh1zz77LJMmTWLq1Kl06tSJDRs2kJ2dXVbzEYm2bdvSsGFDli5dSrfwEaNLliyJ\n7Hzl1bsO4wVrCjh59MlccfQVPPyzh783WYhI/bT//vvz5ZdfAsRXge+wadMmmjRpQnZ2NoWFhdxy\nyy2R91DMysqiX79+5OXl8d133zF//nyeeuqpSM+5y/mjPoGZ9TWz+Wa2wMxu3k2ZAWY2x8w+NbOn\n49aXmNnVKmkFAAAMCklEQVRMM5tlZi9WN5aCNQWc8dQZ/PG0P/K7438X+T+uiNRdw4YN46677qJV\nq1ZMmDChwvfFJZdcQqdOnWjfvj2HHXYYJ554YlLHT+b7J77sAw88wPr16znggAMYMmQIF110EU1q\nabruSLvVmlkWsAA4A1gOzAAGuvv8uDLdgLHAae6+0czauPuacNtGd99jQ0Gi3Wrjk8VlvS6r+psS\nkRqRzt1q65Jhw4axcuVKRo8eXen2ujS9+XHAQndf7O7bgTHAueXK/Bp4yN03ApQli1CN3AIoWYhI\npigoKODTTz8FYPr06YwaNYp+/frVyrmjbvRuD8S3yCwlSCLxegCY2bsECWyEu78ebmtiZtOBYmCk\nu7+UbABKFiKSSTZt2sSgQYNYsWIF++23HzfddBNnn312rZw7HXpJNQS6AacAnYC3zeyw8I6js7uv\nMLOuwFQz+8Tdv0r0wEoWIpJpjjnmGBYuXJiSc0edMJYRJIEyHcJ18ZYC77t7KbDIzBYA3YGP3H0F\ngLt/ZWYxoBdQIWHkxXW8zs3NJTc3l0XrFylZiIiEYrEYsVisWseIutG7AVBA0Oi9ApgODHL3eXFl\n+oTrLjWzNsBHwJGAA1vcfVu4/j3g3PgG83D/Shu9b51yK1uLt/I/ff4noncnItWhRu/aUWcavd29\nBLgGyAfmAGPcfZ6ZjTCzn4dlXge+NbM5wBTgRndfBxwKfGhms8L195RPFnsyacEkDX4TEalBGTlb\n7aL1izju8eNYccOKGnvOgIjULN1h1I46c4eRKpMKJvHT7j9VshARqUEZmTAmL5zM2T1qp5uZiNQP\nQ4cO5c4770x1GCmVcQlj09ZN/GfJfzjroLNSHYqISEbJuISR/0U+J3Q8gX2aVJxeWEREqi7jEsak\nBZNUHSUi1TZr1iyOPvpoWrRowcCBAykqKtqxbfLkyfTq1Yvs7GxOOumkHVN1/OlPf6J///67HOfa\na6/luuuuq9XYo5JRCaOktIRXF77Kz3v8PNWhiEgdtn37ds477zyGDBnC2rVr6d+/PxMmTABg9uzZ\n/OpXv+Lxxx9n7dq1XHHFFZxzzjls376dgQMH8n//938UFhYCwUOWxo8fzy9/+ctUvp0akw5Tg9SY\n6cums1/z/ejSskuqQxGRGmAjqj//qA9Pvuvu+++/T3FxMb///e8BOP/88zn22GMBeOyxx7jyyis5\n5phjALj44ou5++67ef/99zn55JM56qijmDhxIoMHD2bKlCnsvffeO/at6zIqYag6SiSzVOXLviYs\nX76c9u3b77Kuc+fOACxevJgnn3ySBx54AAgerrR9+3aWL18OwKBBg3juuecYPHgwzz33HBdddFHt\nBh+hjKqSUsIQkZpwwAEHsGzZrtPeff311wB06tSJ22+/nbVr17J27VrWrVvH5s2bufDCCwHo378/\nsViMZcuWMXHiRCWMdLRo/SJWFa7iuPblZ08XEUnOCSecQMOGDXnggQcoLi7mhRdeYPr06QBcfvnl\nPPLIIzuWCwsLefXVV3e0W7Rp04ZTTz2VoUOHcuCBB3LwwQen7H3UtIxJGBrdLSI1pVGjRrzwwguM\nHj2a1q1bM378eM4//3wAjj76aJ544gmuueYaWrVqRY8ePXjyySd32f+iiy5iypQpGdPYXSZj5pLq\n83QffnPUbzg/5/xUhyQiCdBcUrVDc0mVo9HdIiLRy4iEodHdIiLRy4iEod5RIiLRy4iE8erCV5Uw\nREQilhEJY//m+9O5ZedUhyEiktEyImFo7igRkehlxNQgqo4SqXs6d+6MWfXnipI9K5vSpCZEPg7D\nzPoC9xPczYxy95GVlBkADAdKgY/dfXC4fghwG+DA3e7+VCX7enFJsQbsiYgkIe3GYZhZFvAg0Afo\nCQwys0PKlekG3Ayc4O6HA9eF67OBO4FjgeOB4WbWorLzKFkEYrFYqkNIG7oWO+la7KRrUT1Rt2Ec\nByx098Xuvh0YA5xbrsyvgYfcfSOAu68J1/cB8t19g7uvB/KBvhHHW6fpw7CTrsVOuhY76VpUT9QJ\noz2wJG55abguXg/gYDN718z+bWZ9drPvskr2FRGRWpIOjd4NgW7AKUAn4G0zOyy1IYmISHmRNnqb\nWW8gz937hsvDAI9v+DazR4D33f3JcPlNgjaN7kCuu18Zrv87MM3dx5Y7h2YvExGpgmQbvaNOGA2A\nAuAMYAUwHRjk7vPiyvQJ111qZm2Aj4Ajw80fAkcRVJ19CBwdtmeIiEgti7RKyt1LzOwaggbrsm61\n88xsBDDD3Se7++tmdpaZzQGKgRvdfR2Amd1FkCgcGKFkISKSOnX+eRgiIlI76vTUIGbW18zmm9kC\nM7s51fHUJjMbZWYrzeyTuHXZZpZvZgVm9vruxq1kGjPrYGZTzWyOmX1qZr8P19e762FmTczsAzOb\nFV6L4eH6Lmb2fvhZec7M0qHDS+TMLMvMZprZy+FyvbwOAGa2yMw+Dv9vTA/XJfUZqbMJI5FBgRlu\nNMF7jzcMeNPdDwamArfUelSpUQz8wd17AicAV4f/F+rd9XD3rcBp7t6LoC3wJ2Z2PDAS+B937wGs\nB36VwjBr07XA3Ljl+nodIJhJI9fde7n7ceG6pD4jdTZhkNigwIzl7u8C68qtPhcoe7jwk8AvajWo\nFHH3b9x9dvj7ZmAe0IH6ez22hL82IWindOA0YEK4/kngvBSEVqvMrAPwU+CJuNWnU8+uQxyj4nd+\nUp+RupwwEhkUWN+0c/eVEHyJAu1SHE+tM7MuBH9Zvw/sVx+vR1gNMwv4BngD+AJY7+6lYZGlwA9S\nFV8t+l/gJoKEiZm1BtbVw+tQxoHXzWyGmV0erkvqM1Jv6u/qqXrVo8HMmgPPA9e6++ZKxujUi+sR\nfiH2MrN9gYlAfaqqBcDMfgasdPfZZpYbvylFIaWDH7n7CjNrC+SbWQEVPxN7/IzU5TuMZQQjw8t0\nCNfVZyvNbD8AM9sfWJXieGpN2Hj5PPAvd38pXF1vrwdAOD9bjKBdp2XY7gf147PyI+AcM/sSeI6g\nKuqvQIt6dh12cPcV4c/VwIsE1fpJfUbqcsKYAXQzs85m1hgYCLyc4phqm7HrX0wvA5eGvw8BXiq/\nQwb7BzDX3f8at67eXQ8za1PW08XMmgJnEjT6TgP6h8Uy/lq4+63u3sndDyT4bpgaPjahXl2HMmbW\nLLwDx8z2Bs4CPiXJz0idHocRPmvjr+wcFHhvikOqNWb2LJALtAZWEjxP5EVgPNARWAwMqA+DHc3s\nR8DbBB8AD1+3EswsMI56dD3M7HCCxsus8DXW3e82s64EHUOygVnA4LCzSMYzs1OBG9z9nPp6HcL3\nPZHgs9EQeMbd7zWzViTxGanTCUNERGpPXa6SEhGRWqSEISIiCVHCEBGRhChhiIhIQpQwREQkIUoY\nIiKSECUMkThm9m74s7OZDarhY99Sbvndmjy+SNQ0DkOkEuH8Qze4+9lJ7NPA3Uv2sH2Tu+9TE/GJ\npILuMETimNmm8Nd7gJPCh+9cG84A+6fw4USzzezXYflTzextM3sJmBOumxjOCPpp2aygZnYP0DQ8\n3r/KnQsz+3NY/mMzGxB37GlmNt7M5pXtJ5Iqmq1WZFdlt9zDCKeTAAgTxHp3Pz6cu+w9M8sPy/YC\nerr71+HyUHdfb2Z7ATPMbIK732JmV7v7UeXPZWbnA0e4++Fm1i7c562wzJFADsFU5e+Z2Ynu/u+I\n3rvIHukOQyQxZwGXhM+Z+ABoBXQPt02PSxYA15nZbIJncnSIK7c7PyKYURV3X0Uww+yxccde4UHd\n8WygS/XfikjV6A5DJDEG/M7d39hlZTCxXWG55dOB4919q5lNA/aKO0ai5yqzNe73EvSZlRTSHYbI\nrsq+rDcB8Q3UrwNXhc/dwMy6m1mzSvZvQfBUt63hc8V7x23bVrZ/uXO9A1wYtpO0BU4mmGlXJK3o\nrxWRXZW1YXwClIZVUP9097+Gj3+daWZG8KCZyp5//BpwpZnNAQqA/8Rtewz4xMw+cveLy87l7hPN\nrDfwMVAK3OTuq8zs0N3EJpIS6lYrIiIJUZWUiIgkRAlDREQSooQhIiIJUcIQEZGEKGGIiEhClDBE\nRCQhShgiIpIQJQwREUnI/weRdOcNC8653gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b34720a50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_accs(theta_avp_history);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# execute this code to write the predictions on the dev and training data\n",
    "y_hat_dv = clf_base.predict_all(x_dv,theta_avp,labels)\n",
    "evaluation.write_predictions(y_hat_dv,'avp-dev.preds')\n",
    "y_hat_te = clf_base.predict_all(x_te,theta_avp,labels)\n",
    "evaluation.write_predictions(y_hat_te,'avp-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.66800000000000004"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluation.acc(y_hat_te,y_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Logistic regression\n",
    "\n",
    "Total: 2 points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 5.1** Write a function to compute the conditional probability,\n",
    "\\begin{equation}\n",
    "p(y \\mid x; \\theta) = \\frac{\\exp(\\theta^{\\top} f(x,y))}{\\sum_{y'}\\exp(\\theta^{\\top} f(x,y'))}\n",
    "\\end{equation}\n",
    "\n",
    "Implement this in ```compute_py``` in ```logreg.py```. You should use your ```predict``` function from ```clf_base.py```.\n",
    "\n",
    "(0.5 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib import logreg\n",
    "reload(logreg);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{u'askreddit': 0.19587982773688248,\n",
       " u'iama': 0.21648068905247014,\n",
       " u'science': 0.19587982773688248,\n",
       " u'todayilearned': 0.19587982773688248,\n",
       " u'worldnews': 0.19587982773688248}"
      ]
     },
     "execution_count": 274,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "logreg.compute_py({'i':1,'am':2},theta_hand,labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{u'askreddit': 0.11707223997893113,\n",
       " u'iama': 0.12938483493868785,\n",
       " u'science': 0.31823534255172503,\n",
       " u'todayilearned': 0.11707223997893113,\n",
       " u'worldnews': 0.31823534255172503}"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "logreg.compute_py({'i':1,'news':2,'science':1},theta_hand,labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 5.2** Complete the function ```estimate_logreg``` in ```logreg.py```. (1 point)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2\n"
     ]
    }
   ],
   "source": [
    "# train on the first ten instances\n",
    "theta_lr,theta_lr_hist = logreg.estimate_logreg(x_tr[:10],y_tr[:10],3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "# this takes approximately 2 minutes to execute on my laptop\n",
    "theta_lr,theta_lr_hist = logreg.estimate_logreg(x_tr,y_tr,20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.604\n"
     ]
    }
   ],
   "source": [
    "y_hat = clf_base.predict_all(x_dv,theta_lr,labels)\n",
    "evaluation.write_predictions(y_hat,'lr-dev.preds')\n",
    "print evaluation.acc(y_hat,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y_hat_te = clf_base.predict_all(x_te,theta_lr,labels)\n",
    "evaluation.write_predictions(y_hat_te,'lr-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.562\n"
     ]
    }
   ],
   "source": [
    "print evaluation.acc(y_hat_te,y_te)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEPCAYAAABRHfM8AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl0VPX9//HnO2FTAVlEwUQ2QUXRr4CAC2KAqkgL1OAC\nVEXrglWrnlorWheo369Wrda9VXFBUVxKUOuKCxFRISgg/JDgxhp2IRCQJcv798cdYhICTEImdyZ5\nPc6Zw9w7d3nPnMm8+ezm7oiIiOxNUtgBiIhIYlDCEBGRqChhiIhIVJQwREQkKkoYIiISFSUMERGJ\nSswThpn1N7NsM/vWzG7azTHnmdl8M5tnZuNL7C80s1lmNtvMXo91rCIisnsWy3EYZpYEfAv0A1YA\nM4Gh7p5d4pgOwCtAH3ffZGYHufu6yGub3L1xzAIUEZGoxbqE0QP4zt2XuHs+8DIwuMwxlwOPufsm\ngJ3JIsJiHJ+IiEQp1gkjBVhWYnt5ZF9JRwBHmtk0M/vczM4s8Vp9M8uK7C+baEREpBrVCTsAghg6\nAL2B1sBUM+scKXG0cfeVZtYO+NjM5rr7ojCDFRGprWKdMHIIksBOqZF9JS0Hprt7EbDYzL4FOgJf\nuftKAHdfZGaZQBegVMIwM02GJSJSCe5eoWr/WFdJzQQ6mFkbM6sHDAXeLHPM60AfADM7iCBZ/Ghm\nTSLn7Nx/MvBNeTdxdz2q6HHHHXeEHkNNeujz1OcZr4/KiGkJw90LzewaYDJBcnra3ReY2Rhgpru/\n5e7vm9kZZjYfKAD+7O4bzOwk4AkzK4yce7eX6F0lIiLVK+ZtGO7+HnBkmX13lNm+AbihzL4vgONi\nHZ+IiERHI72llLS0tLBDqFH0eVYtfZ7hiunAvepgZp7o70FEpLqZGR5njd4iIlJDKGGIiEhUlDBE\nRCQqShgiIhIVJQwREYmKEoaIiERFCUNERKKihCEikiBmz4aLL4axY8O5vxKGiEicKSgof3/9+nDS\nSdCnT/XGs5NGeouIhMgdFi2Czz+HL74I/q1XD2bMiO19KzPSWwlDRCQkGzfCkUdCUhKccgqcfHLw\n6NIlSBqxpIQhIhJn8vKCUkO/flCnnPnBly6Fww4Dq9BP976rTMKIhyVaRURqjLVrYdo0mDoVPv0U\nsrOhWzc47jho1WrX41u33nVfvFIJQ0SkCp17LmzeDL17w6mnQvfuQWN1vFGVlIhIDLnDwoVByaFz\n56DHUqJSlZSISBUrLAyqmDIyYNKkoK2hd2/o1CnsyKqfEoaIyB5kZMDdd8PZZ8O778LRR1d/A3W8\nUJWUiAiQnw916+66371mJgituCciUgEbNsALLwSlh9atYceOXY+picmispQwRKTWef55OPNMaNsW\nJk4MEsb8+bEfLJfo1IYhIrXOxo1wxRVB+8QBB4QdTeJQG4aI1Cj5+fDllzBlCnTtCv37hx1RfFK3\nWhGplRYvhldfDZLEZ59B+/aQlgYHHRR2ZDWLEoaIJLylS2HZMrj8chg/Hpo3DzuimklVUiIS99at\ngwkTYPlyuOeesKOpGdStVkRqDHfIzIRhw6BDB8jKCuZlkvCohCEicalPH1izBkaOhAsvhKZNw46o\nZtHkgyJSYyxfDikpGjgXK6qSEpGEsm4dzJ5d/mupqUoW8UYJQ0SqVdm2iTfeCDsiiZaqpESkWuTn\nw8MPw5NPBpP8jRwJF1ygtomwaOCeiMStOnWCRuxnnw0WHlJ1U+JRCUNEqkxREcyaFaxdnZISdjSy\nJ2r0FpFql5cXTOJ36aVBkrjgAliwIOyoJBZinjDMrL+ZZZvZt2Z2026OOc/M5pvZPDMbX2L/iMh5\nC83soljHKiIV88ILQZJ44gn4n/8J1rrOzoZf/SrsyCQWYlolZWZJwLdAP2AFMBMY6u7ZJY7pALwC\n9HH3TWZ2kLuvM7OmwJdAV8CAr4Cu7r6xzD1UJSUSY7tbdW7DhqABu2HD6o+pNtu0fRON6zfep2vE\nY5VUD+A7d1/i7vnAy8DgMsdcDjzm7psA3H1dZP+ZwGR33+juucBkQBMVi1STwkKYPBmGD4eePcs/\npmlTJYvqsnTjUh6a/hCnPXcahz98OFvzt1Z7DLHuJZUCLCuxvZwgiZR0BICZTSNIYGPc/f1yzs2J\n7BORGMrOhnHjguqmli3h4ovhwQfDjqp2WrhuIRkLMsjIzmDRhkUMOnIQN558I79q/ysa1GlQ7fHE\nQ7faOkAHoDfQGphqZp0rcoHRo0cXP09LSyMtLa0KwxOpXW64AY4+Gt57DzpX6C9R9pW7M2fVnOIk\nkbstl7OPOpt7fnUPvdv0pk5S5X+yMzMzyczM3Kf4Yt2GcSIw2t37R7ZHAe7u95Q45l/AdHcfF9n+\nELgJ6AikufuVkf3/Bqa4+ytl7qE2DBFJWEVexBfLvihOEkmWxJBOQ0jvlE6PlB4kWWxaDuJu8kEz\nSwYWEjR6rwSygGHuvqDEMWdG9l1sZgcRNG4fH3l5Z6N3UuR5t0h7Rsl7KGGIVMD8+UGVU/PmcFO5\n/RYl1vIL88lcnEnGggxeX/g6LfZvQXqndNI7pXPswcdi1TCqMe5Gert7oZldQ9BgnQQ87e4LzGwM\nMNPd33L3983sDDObDxQAf3b3DQBmdidBonCCto3c3dxKRPbgp5/g5ZfhuedgxQq46CL47W/Djqpm\n21awjRV5K8jZlENOXg7LNy0nZ1MOSzctJXNxJh2bdSS9UzpTL55Kx+Ydww43KhrpLVLD/fQTdOwI\n/fsHDdj9+kFycthRJS53J3dbLjl5Obskg+LneTls2r6JVg1bkdI4hZRGKaQ2TiWlUQopjVPo1boX\nqY1TQ30fcVclVR2UMET2bssWOOCAsKOIf4VFhazavGqXJFB2u05SneIf/+JEsDMpRBJEiwNaxKz9\noSooYYjUUmvXwksvQe/e0KVL2NFUPXdn9ZbV7CjcsU/X2Vaw7ZcksOmX0sDO7TVb1tB8/+a7lAhK\nPk9plEKj+o2q6J2FJ+7aMEQkdnbsgHfeCdolMjNh4MCguqkmyN2Wy5crvmTG8hnMyJlBVk4WBUUF\n7F93/326br3kesU/+imNUujQrAOntT2tOEG0bNiSusl1q+hd1DwqYYgkoE8+gXPPhaOOCtolzjkH\nGu/bTBGh2VG4g3mr5zEj55fksHzTcrq07ELPlJ70TO1Jj5QeHNb4sGrpPVRbqEpKpJbIzQ0asw8/\nPOxIKsbdWZS7qFTJ4evVX9O+afsgOaQEyeGYg4/Zp0FqsndKGCI1iDu8/XbQu6lOgv52rt+6nqyc\nLGYsn0HWiiyycrJoUKcBPVJ6FCeHbq261Yg2gUSjhCFSQyxaFCxhunp1MEVHq1ZhR7R32wu2M2fV\nnOKSw4ycGazevJoTDj2hOEH0TO3JoY0ODTtUQQlDJOEVFATrXt91F9x4I/zpT8H04fGmyIv4fv33\nQckhkhzmr53PEc2PoMehPeiZGlQvHXXQUSQnadBHPFIvKZEEtnYtDBgQTBf+xRfBYLt4sXbL2lIl\nh5k5M2lcv3FxyeH8zufTpWUXDqinwR41mUoYInGiqAjeeCOYsiNeOgPlbsvl8v9ezgc/fED3lO7F\npYceKT1o2bBl2OHJPlCVlIhUmaycLIb+Zyi/7vhr/nHGP6hfp37YIUkVUpWUSIIoKoKkOJ01wt15\naMZD3PXpXfzr1/9iyNFDwg5J4kScfmVFaiZ3mDgRjjsONm8OO5pdrd+6nrNfOZuX5r3E9MumK1lI\nKUoYItUkJwfS0+HWW+Hf/46/tbCnL59O1ye60q5JO6b9fhrtm7YPOySJM0oYIjFWVARPPAHHHw/H\nHguzZ0OvXmFH9YsiL+Ifn/+DQRMG8WD/B/ln/39SL7le2GFJHFIbhkiMLVwI48fDlCnxt0b2Tz//\nxIjXR7Du53VkXZ5F2yZtww5J4ph6SYlUA/f46Sq702dLP2PYxGGcd8x53NXvLpUqahn1khIJ2e4S\nQzwliyIv4r7P7uOB6Q8wduBYBh45MOyQJEEoYYhUgSVL4N57obAwaNCOV2u3rGXE6yPYuH0jMy+f\nSesDW4cdkiQQNXqL7IOFC+GSS6BrV2jUCMaMCTui3ft0yad0fbIrxx58LJkjMpUspMJUwhCpBPcg\nUbz9Nvzxj/D999C0adhRla/Ii7j707t5JOsRnhn8DAM6Dgg7JElQavQWqaQPP4SePYOSRTxakbeC\nrJwsHp/5OFsLtjJhyARSG6eGHZbECc0lJVJLbd6xma9WfFVqRtmt+VvpkdKD09ufzh97/lEr2Ekp\nShgiVcgd3norGD/xwANhR/OLwqJC5q+dX2otih82/MBxhxxXvIpdz5SetG/aXmtgy26pW61IFdi8\nGV59FR56KOgO+9e/hjeOwt1Zvml5qZLDrJWzSGmUUpwYRp4wkuMOOU7jKCTmVMIQKeGvf4XHH4dT\nT4Urr4Szzoptoti8YzPLNy0nZ1MOOXk55GzKCbbzgu0luUsAilew65HSg+6HdqfpfnHawi4JQ1VS\nIvvok0+Cle4OrYJlp/O25/Hd+u92SQIlt/ML80lpnEJq41RSGqUEjxLbqY1TObTRoapakiqnhCES\nhcLCYObY1jEYhrBmyxreyH6DjOwMPlv6Ge2btg8SQKNUUhrvmhCaNGiiZCChUMIQ2YMff4Rnnw0e\nffvC889XzXWXblzKpAWTyMjO4OtVX3NWx7NIPyqd/h3606h+nPa5lVpPCUOkjMJCeOUVePppmDsX\nfvc7uPTSYJrxfbFw3UIyFmSQkZ3B4tzFDDpiEOmd0unXvh8N6jSomuBFYkgJQ6QMd7jiCjj9dBg8\nGOpXcllqd2fOqjnFSSJ3Wy7pR6WT3imdU9ucqjEOknCUMESqUGFRIV8s/yJIEgsyqJNUhyGdhpDe\nKZ3uKd1JMk3FJolLCUNqpZUrgxXtmjWDa6+N/jx3Z+P2jaV7MZV4/uWKLzmk4SHFJYnOB3dWA7XU\nGEoYUmu4w4wZ8Mgj8M47MHRoMAng0UcHrxcWFbJ6y+pSYxxKJoWd28mWvEu31tTGQY+mY1ocw+HN\nDg/3jYrEiBKG1ApbtkCfPvDTT3D11cGssU2bwqrNq3g9+3UyFmQwdclUmjRoUvzjX5wIynRrVS8m\nqa3iMmGYWX/gQYK1N55293vKvD4CuA9YHtn1qLs/E3mtEPgaMGCJu/+2nOsrYdRC06bBSSfB0k2L\nmJQ9iYwFGcxfO58BHQeQflQ6Z3Y4k4b1GoYdpkjciruEYWZJwLdAP2AFMBMY6u7ZJY4ZAXRz911q\nn81sk7s33ss9lDBqKHfYvh0aNCi5z/lm7TfFvZVyNuUw+MjBpHdKp2+7vtSvU8luUCK1TDxOPtgD\n+M7dlwCY2cvAYCC7zHG7C1otjLXQtm0wYULQPjFgANx5p/Plii+Lk8TW/K2kd0rnwTMfpFfrXiQn\nJYcdskitEOuEkQIsK7G9nCCJlJVuZqcSlEb+5O47q6fqm1kWUADc4+5vxDRaCVVBQTDAbvRo+J8u\nBZx/0zRyGk+izYOT2K/ufgzpNIQX01+kW6tu6q0kEoJ4GG30JvCSu+eb2RXAOIIqLIA27r7SzNoB\nH5vZXHdfFFqkEjNbtxfQ5Yz5kJJF9//7nOk/vc2a3FTSW6Xz3gXv0emgTkoSIiGLdcLIAUpO8ZYa\n2VfM3TeU2BwL3FvitZWRfxeZWSbQBdglYYwePbr4eVpaGmlpafscuMSOu7Ns07JgfYflM8hakcWs\nlbM4aFAKvdv3pGdqTx7qcDvtmrYLO1SRGiMzM5PMzMx9ukasG72TgYUEJYaVQBYwzN0XlDimpbuv\nijw/G7jR3U82sybAz+6+w8wOAj4DBpdsMI+co0bvOLdx20a+XPFlqUWACosKi9d46JnSkxMOPUFr\nPIhUo5g1eptZBvA08K67F0V7cXcvNLNrgMn80q12gZmNAWa6+1vAtWY2CMgH1gMXR07vBDwR6Vqb\nBNxdNllI/MkvzGfemnnFJYcZy2ewdONSjm95PD1TepJ+xDB+VfAgV/+ujaqYRBJMVCUMM/sVcAlw\nIvAa8Ky7L4xxbFFRCSM87s7i3MXFpYYZOTOYs2oObZu0LV4+tGdKTzof3Jlkq8uLL8IttwTjJ8aP\nh3paUVQkNDEfh2FmBwLDgL8S9H56Chjv7vkVuWlVUsKoPhu2bmDmipmlSg/JScnFiaFnak+6terG\ngQ0OLHXeJ5/ADTdAnTpw//1wyikhvQERKRbThGFmzYELgAsJBuG9CPQCjnX3tIqFWnWUMGJjR+EO\nvl71danSw4q8FXRt1bU4QfRI6UFq49Q9Vi2NHw+33gp//zucf35s18cWkejFLGGY2STgSOAF4Lmd\nvZcir33p7idUNNiqooRRdZZuXMr9n99P1oos5q6ey+FNDy9ODD1Te3J0i6MrvO7Dzz9DUlLp0doi\nEr5YJow+7j6l0pHFkBJG1dhRuINTnjmFE1NO5Jyjz6Hbod00F5NIDVaZhBHtCjBHR7q57rxRUzO7\nqkLRSVy77ePbaNmwJQ+f9TCntT2tQsmioACeeQY++iiGAYpI6KJNGJe7e+7Ojchgu8tjE5JUtw9/\n/JDx88bzzKBnKtTV1R0mTYLjjoNx46BJk72fIyKJK9oK6WQrUfcTGZCnTpE1wNota7n49YsZ99tx\ntDigRdTnffIJjBoFW7cGPZ/691eDtkhNF20bxn1AG+CJyK6RwDJ3vyGGsUVFbRiV5+4MfnkwnQ7q\nxD2n37P3EyLy8+GMM+Cyy2DYsKBRW0QSSywbvZMIksTOSQE/AMa6e2GFo6xiShiV91jWYzz39XN8\n9vvPqJesAqNIbRJ3CyhVByWMypm3eh59n+/L57//nI7NO+72uMJCSNZyEyI1Tsx6SZlZRzP7j5l9\nY2Y/7nxULkwJ29b8rQybOIz7Tr9vt8li48ZgwN2JJwaN2yIi0dY+Pwv8i2Ahoz7A88D4WAUlsfXn\nyX/m2EOOZcT/jNjltW3bgkbsjh0hJwf+8x81ZotIINpeUvu5+0eRnlJLgNFm9hVwewxjkxh4I/sN\n3vn+HeaMnLNLF9oPPoBLL4Vu3WDKFDjmmJCCFJG4FG3C2B5p+P4uMl15DqBhwAkmZ1MOI98aScb5\nGbtMEAjB7LHPPw9af0pEyhNtL6nuwAKgCXAn0Bi4z92nxza8vVOjd3QKiwo5Y/wZpLVJ47bTbgs7\nHBEJWUwWUIoM0jvf3f8MbCZYF0MSzH2f30d+YT63nHpL2KGISILaa8KIrJrXqzqCkdjIysnin9P/\nyczLZ5KcFPSRzcuDRo1CDkxEEkq0vaRmm9mbZnahmaXvfMQ0MqkSedvzGD5xOI8NeIzWB7YGIDMT\njjwSli0LNzYRSSzRNno3AH4C+pbY50BGlUckVerqd66mT9s+nHP0OQCMHQt//Su89BIcdljIwYlI\nQokqYbi72i0S0ItzX2Tmipl8efmXFBbCTTfBm2/C1KlBCUNEpCKiShhm9ixBiaIUd/99lUckVeLH\nDT9y/fvXM/mCyRxQ7wAuvRQWLYLp06FZs7CjE5FEFG2V1FslnjcAziZY11viUH5hPsMnDueWXrfQ\npVUXIJiKvG1bqFs33NhEJHFVavLByCC+ae5+ctWHVOFYNA6jjFs/vpWvVn7F28PfJsk097iI7Com\n4zB2oyNwcCXPlRjKXJzJM7OfYfbI2UoWIlKlom3DyKN0G8Yq4KaYRCSVtn7rei6adBHXtX2GQxoe\nEnY4IlLDaD2MGqLIizh7wjks+KItLWY9wJQpwdxQIiLlieV6GGeb2YEltpuY2W8rGqDExvw18+n2\nWC+mfJFLt9y7+egjJQsRqXrRVnLf4e4bd264ey5wR2xCkmhtL9jOze+PpvtjaXw38UL+94gPeen5\n+jRoEHZkIlITRdvoXV5iqWyDuVSBz5d9zmVvXka7xh0Znjebu19NpUWLsKMSkZos2unNnwFygcci\nu64Gmrn7xbELLTq1rQ1j0/ZN3PLRLWQsyODhsx5mSKchuyyEJCKyNzFrwwD+COwAXgFeBrYRJA2p\nRm9m/5djHj+GbQXbmH/VfM45+hwlCxGpNuollQCWbVjNwMev5dtNs3hr5JP0bd8n7JBEJMHFspfU\nB2bWpMR2UzN7v6IBSsW4Oze88Czt7j2WvKXtmD5irpKFiIQm2obrgyI9owBw9w1mppHeMfTxnB84\n/4Ur2JSfy/293ufac7ug2icRCVO0bRhFZtZ654aZtaWc2Wtl3xUUFXDvZ/fy27d60qPpANbfM4Pr\nzlOyEJHwRVvC+Cswzcw+AQw4FbgiZlHVUrNWzuKyNy+j+f7NmXN1Fu2btg87JBGRYlGVMNz9PeAE\nYCEwAbgB2BrNuWbW38yyzexbM9tl/ikzG2Fma8xsVuTx+zKvfWtmC83soqjeUQL6Of9n/vLBX+g/\nvj/X9byOyRdMVrIQkbgT7eSDlwHXAanAHOBE4AtKL9la3nlJwKNAP4L1M2aa2Rvunl3m0Jfd/doy\n5zYFbge6EpRqvoqcu5Ea5IMfPmLEf67gtA49mPeHeZo0UETiVrRtGNcB3YEl7t4H6EIwkG9vegDf\nufsSd88nGMMxuJzjyquhPxOY7O4bIw3uk4H+UcYb99ZvXc8lb1zCkOd/T7MZDzP+txOULEQkrkWb\nMLa5+zYAM6sfKSFEsyp0CrCsxPbyyL6y0s1sjpm9amY7Xy97bs5uzk0o7s4r/+8Vjnn8GBZlN6Ll\nxP/H1LG/Jjk57MhERPYs2kbv5ZFxGK8DH5jZBmBJFcXwJvCSu+eb2RXA8wRVWDXOso3LuOqdq/hx\nw4/86dAM/nnDSUybpjW2RSQxRJUw3P3syNPRZjYFOBB4L4pTc4DWJbZTI/tKXntDic2xwD0lzk0r\nc+6U8m4yevTo4udpaWmkpaWVd1hoiryIf838F3dk3sG1Pa/llsMnMujX9Xj7bWivtm0RqQaZmZlk\nZmbu0zViOjWImSUT9KzqB6wEsoBh7r6gxDEt3X1V5PnZwI3ufnKk0ftLgkbvpMjzbiUHEEbOieup\nQeavmc/l/72cJEviqYFP0alFJxYsgMWL4ayzwo5ORGqr6lzTOyruXmhm1xA0WCcBT7v7AjMbA8x0\n97eAa81sEJAPrAcujpy7wczuJEgUDowpmyzi2faC7dw97W4ezXqUO/vcycgTRhavsd2pU/AQEUkk\nmnwwBnauVdGhWQce//XjpDZODTskEZFS4q6EUduUXKviof4PafpxEalRou1WK3vx34Wl16o495hz\ni5PF55+HHJyISBVQCWMfFRYV8oe3/8DHiz5m3G/H0bdd6cHvTz4J990Hs2dDw4YhBSkiUgWUMPZB\nfmE+F066kLU/r2XOlXNoWK90Rnj3Xbj9dvj0UyULEUl8ShiVtL1gO+f/53zyi/J5a9hb7Fd3v1Kv\nz5kDI0bA669Dx44hBSkiUoXUhlEJP+f/zOCXB5OclMyk8yftkiyWLYOBA+Hxx+Hkk0MKUkSkiilh\nVFDe9jwGvDiAg/Y/iFfOeYV6yfV2OaagAO68E845J4QARURiROMwKiB3Wy5nvXgWnVt05t+/+TfJ\nSZoxUEQSU2XGYaiEEaV1P6+j77i+9Di0B08OfFLJQkRqHSWMKKzavIq059I48/AzebD/gxqMJyK1\nkhLGXizbuIzez/ZmaOeh3NXvrnKTxVdfQYLX7ImI7JUSxh78uOFHej/XmytPuJJbe99abrJ45hkY\nPBhWrQohQBGRaqRxGLuRvS6b0184nVt63cIfuv+h3GOeegr+9jf4+GNo1aqaAxQRqWZKGOWYu3ou\n/cf35+5+dzPi+BHlHvPvf8Pdd8OUKdChQzUHKCISAiWMMr5c8SW/eek3PNT/Ic7vfH65x7zwAvz9\n70Gy0Ip5IlJbaBxGCZ8t/YyzXzmbsYPGMujIQbs9buVK2LYN2rWrktuKiFS7yozDUMKI+HjRxwz9\nz1DGp4/njMPPqILIRETilxZQqqR3vnuHi1+/mNfOfY3T2p4WdjgiInGp1pcwpi2dxpBXh/DG0Dc4\nMfXEco9xB43VE5GaRFODVFCRF3Hde9fxyFmP7DZZ/O//Bg3cIiK1Xa2ukpowbwJ1k+py7tHnlvv6\nmDHw8svBOAsRkdqu1iaMbQXbuOXjW3gx/cVdRnC7wx13wMSJkJkJhxwSTowiIvGk1iaMh2c8TLdW\n3ejVulep/e5w663w5pvBOIuDDw4pQBGROFMrE8ZPP//EfZ/fx2e//2yX17ZsgR9/DKqhWrQIITgR\nkThVK3tJXf/e9RQUFfDogEdjFJWISHzTOIwofL/+e8bPHc+CqxeEHYqISEKpdd1qb/7oZv500p9o\ncYDqm0REKqJWJYwvln3BjOUzuP7E64v3ZWVBQUGIQYmIJIhakzDcnT9/8Gfu7HMn+9fdH4Bvv4UB\nA2D58pCDExFJALUmYUzKnsSWHVu44LgLACgqgksvhdtvh7Ztw41NRCQR1IpG7x2FOxj14SgeG/AY\nyUnJADz2WDDm4pprQg5ORCRB1IqE8cSXT9C+aXtOP/x0ABYtCqb9+PxzSKo1ZSwRkX1T48dhbNy2\nkSMePYIPL/yQYw85FoCbb4ZmzeDGG6srShGR+KIFlMpx84c3s2bLGp4e/HTxPvegDSM5uToiFBGJ\nPxq4V8ayjct4ctaTzL1ybqn9ZkoWIiIVVaNr8G+dcitXnXAVKY1Twg5FRCThxTxhmFl/M8s2s2/N\n7KY9HDfEzIrMrGtku42Z/WxmsyKPxyty39krZzP5h8n85ZS/7OtbEBERYlwlZWZJwKNAP2AFMNPM\n3nD37DLHNQSuBaaXucT37t61ovd1d2784EZu7307jeo3YtUqyM+Hww6r5BsRkSrXtm1blixZEnYY\nNV6bNm1YvHhxlVwr1m0YPYDv3H0JgJm9DAwGssscdyfwd6BscaBSK2m/9/175OTlcFnXy3CHkSOh\na9dgUSQRiQ9Lliwh0TvdJIKyC8Tti1hXSaUAy0psL4/sK2ZmXYBUd3+3nPPbmtlXZjbFzHqV8/ou\nCosK+cuHf+GeX91D3eS6vPwy/PADjBpV6fcgIiKE3EvKgtT3ADCi5O7IvyuB1u6+IdKu8bqZHe3u\nm8teZ/Q0aXabAAAM20lEQVTo0cXPtxy6hWb7NWPgEQNZswauvx7++1+oXz9270NEJN5lZmaSmZm5\nT9eI6TgMMzsRGO3u/SPbowB393si242B74HNBImiJfATMMjdZ5W51hTghnL2F4/D2LJjC0c8egSv\nn/863VO6c/750KYN3HtvzN6iiFRSZBxA2GHUeLv7nONxHMZMoIOZtSEoMQwFhu180d03AcWrZkeS\nwp/cfbaZHQSsd/ciM2sPdAB+3NPN7v/ifnq36U33lO4sXAjffAPPPVf1b0pEpDaKaRuGuxcC1wCT\ngfnAy+6+wMzGmNlvyjuFX6qkegNzzWwW8Cow0t1zd3evVZtX8fCMh7mr710AHHkkzJoF++1XhW9I\nRCRKf/jDH/i///u/Kj82TDVmapAr37qShvUa8o8z/hF2SCIShXivkmrXrh1PP/00ffv2DTuUfZJI\nVVLV4pu135CxIIOF1ywMOxQRqQUKCwtJroXzC9WIqUFu+vAmRvUaRdP9moYdiojUABdddBFLly7l\nN7/5DY0bN+a+++4jKSmJZ555hjZt2tCvXz8AzjvvPFq1akXTpk1JS0vjm2++Kb7GJZdcwu233w7A\nJ598wmGHHcYDDzzAIYccQkpKCs+VaGCtyLHr169n4MCBHHjggfTs2ZPbbruNU089NfYfCjUkYcxf\nM5+ru1/N3Ll7P1ZEZG+ef/55Wrduzdtvv82mTZs477zzAJg6dSrZ2dm8//77AAwYMIAffviBNWvW\n0LVrV373u9/t9pqrVq0iLy+PFStWMHbsWK6++mo2btxY4WOvuuoqGjVqxJo1a3juuecYN25clQ7O\n25MakTDu6ncXn3xcn0GDYNu2sKMRkaoyenQwu3TZR4mhV3s8fnfHRatk3b+ZMWbMGPbbbz/qRwZ2\nXXzxxey///7UrVuX22+/na+//pq8vLxyr1WvXj1uu+02kpOTOeuss2jYsCELF5Zfjb67Y4uKisjI\nyOBvf/sb9evXp1OnTowYMaLca8RCjUgYA1qfzxVXwJNPQoMGYUcjIlVl9Ohg/Zqyjz0ljGiOq6zU\n1NTi50VFRYwaNYoOHTrQpEkT2rVrh5mxbt26cs9t3rw5SSWW+Nx///3ZvHmXcch7PHbt2rUUFhaW\niuOwapwkr0YkjFGjjH794Iwzwo5ERGqK8qp5Su576aWX+O9//8vHH39Mbm4uixcvxt1j2vOrRYsW\n1KlTh+XLlxfvW7Zs2R7OqFo1ImG8+Sbcf3/YUYhITdKyZUt+/DEYK1xeIsjLy6N+/fo0bdqULVu2\ncPPNN8e8LSEpKYn09HRGjx7N1q1byc7O5vnnn4/pPUvdv9ruFEP//jc0aRJ2FCJSk4waNYo777yT\nZs2aMXHixF2SwUUXXUTr1q1JSUmhc+fOnHzyyRW6fkWSS8ljH3nkEXJzc2nVqhUjRoxg+PDhxW0q\nsVZjBu6JSGKJ94F7iWLUqFGsXr2aZ599ttzXq3LgXo0oYYiI1BYLFy5k3rx5AGRlZfH000+Tnp5e\nLfeuESO9RURqi7y8PIYNG8bKlSs55JBDuPHGGxk4cGC13FtVUiISClVJVQ9VSYmISLVTwhARkago\nYYiISFSUMEREJCpKGCIiEhUlDBGRKJRcs6K2UsIQEZGoKGGIiEhUlDBERMoxe/ZsunXrxoEHHsjQ\noUPZVmJ1trfeeosuXbrQtGlTevXqVTxVx7333su5555b6jrXXXcd119/fbXGHitKGCIiZeTn53P2\n2WczYsQI1q9fz7nnnsvEiRMBmDNnDpdeeilPPfUU69evZ+TIkQwaNIj8/HyGDh3Ku+++y5YtW4Bg\nkaXXXnttj0u3JhJNDSIioYhmahAbs+/rS/gdFf99+PTTTxk2bFiphYpOOeUU+vXrx7p162jRogVj\nxowpfu2oo47iqaee4tRTT6V3795cccUVXHDBBXzwwQdcddVVfPfdd/v8PiqrKqcG0eSDIhK3KvNj\nXxVWrFhBSkpKqX1t2rQBYMmSJYwbN45HHnkECBZXys/PZ8WKFQAMGzaMCRMmcMEFFzBhwgSGDx9e\nvcHHkEoYIhKKeJ58cOrUqQwfPrxUCaNXr1707duXtWvX0rp1a26++eZyz123bh1t2rTh22+/pXPn\nzkyfPp0jjzyyukLfhSYfFBGJoZNOOok6derwyCOPUFBQQEZGBllZWQBcdtll/Otf/yre3rJlC++8\n805xu8VBBx3EaaedxiWXXEL79u1DTRZVTQlDRKSMunXrkpGRwbPPPkvz5s157bXXGDJkCADdunVj\n7NixXHPNNTRr1owjjjiCcePGlTp/+PDhfPTRRzWmsXsnVUmJSCjiuUqqJlGVlIiIVDslDBERiYoS\nhoiIREUJQ0REoqKEISIiUVHCEBGRqGhqEBEJRZs2bTDb97miZM92TmlSFWI+DsPM+gMPEpRmnnb3\ne3Zz3BDgNeAEd58V2Xcz8HugALjO3SeXc57GYYiIVFDcjcMwsyTgUeBM4BhgmJkdVc5xDYFrgekl\n9nUCzgM6AWcBj5v+OxJzmZmZYYdQo+jzrFr6PMMV6zaMHsB37r7E3fOBl4HB5Rx3J/B3YHuJfYOB\nl929wN0XA99FricxpD/IqqXPs2rp8wxXrBNGCrCsxPbyyL5iZtYFSHX3d/dybk7Zc0VEpPqE2ugd\nqWJ6ABgRZhwiIrJ3MW30NrMTgdHu3j+yPQrwnQ3fZtYY+B7YDBjQEvgJGAScQXDw3yPHvgfc4e4z\nytxDLd4iIpVQ0UbvWCeMZGAh0A9YCWQBw9x9wW6OnwL8yd1nm9nRwItAT4KqqA+AjuoSJSISjphW\nSbl7oZldA0zml261C8xsDDDT3d8qewpBSQN3/8bMXgW+AfKBq5QsRETCk/DrYYiISPVI6KlBzKy/\nmWWb2bdmdlPY8SQ6M1tsZl+b2Wwzywo7nkRjZk+b2Wozm1tiX1Mzm2xmC83sfTM7MMwYE8VuPss7\nzGy5mc2KPPqHGWMiMbNUM/vYzOab2Twzuzayv0Lfz4RNGNEOCpQKKQLS3L2Lu2vMS8U9S/B9LGkU\n8KG7Hwl8DNxc7VElpvI+S4AH3L1r5PFedQeVwAoI2oePAU4Cro78Xlbo+5mwCYPoBwVK9IzE/k6E\nyt2nARvK7B4M7FzweRzw22oNKkHt5rOESBunVIy7r3L3OZHnm4EFQCoV/H4m8o/DXgcFSoU58L6Z\nzTSzy8MOpoY42N1XQ/BHCxwccjyJ7mozm2NmY1W9Vzlm1hY4nmAqpkMq8v1M5IQhVe8Udz8BGEDw\nh9kr7IBqIPUyqbzHgcPd/XhgFcGgX6mAyLx9/yGYzHUzu34f9/j9TOSEkQO0LrGdGtknleTuKyP/\nrgUmobm7qsJqMzsEwMxaAmtCjidhufvaEl3rnwK6hxlPojGzOgTJ4gV3fyOyu0Lfz0ROGDOBDmbW\nxszqAUOBN0OOKWGZ2f6R/31gZgcQjLT/f+FGlZCM0vXsbwIXR56PAN4oe4LsVqnPMvKDtlM6+n5W\n1DPAN+7+UIl9Ffp+JvQ4jEi3uof4ZVDg30MOKWGZWTuCUoUTDOh8UZ9nxZjZS0Aa0BxYDdwBvE6w\nzsthwBLgPHfPDSvGRLGbz7IPQd17EbAYGLmz/l32zMxOAaYC8wj+xh24hWD2jVeJ8vuZ0AlDRESq\nTyJXSYmISDVSwhARkagoYYiISFSUMEREJCpKGCIiEhUlDBERiYoShkgJZjYt8m8bMxtWxde+ucz2\ntKq8vkisaRyGSDnMLA24wd0HVuCcZHcv3MPree7eqCriEwmDShgiJZhZXuTp3UCvyEI915lZkpnd\na2YzIrOlXh45/jQzm2pmbwDzI/smRWb8nWdml0X23Q3sF7neC2XuhZndFzn+azM7r8S1p5jZa2a2\nYOd5ImGJ6ZreIgloZ5F7FEEJYxBAJEHkunvPyNxln5nZ5MixXYBj3H1pZPsSd881swbATDOb6O43\nm9nV7t617L3MbAhwnLsfa2YHR875JHLM8cDRBLOzfmZmJ7v75zF67yJ7pBKGSHTOAC4ys9nADKAZ\n0DHyWlaJZAFwvZnNIVhvILXEcbtzCjABwN3XAJn8MhNrlruvjMzSOgdou+9vRaRyVMIQiY4Bf3T3\nD0rtNDsN2FJmuy/Q0923m9kUoEGJa0R7r522l3heiP5mJUQqYYiUtvPHOg8o2UD9PnBVZE0BzKyj\nme1fzvkHAhsiyeIo4MQSr+3YeX6Ze30KnB9pJ2kBnEowi6hIXNH/VkRK29mGMRcoilRBPefuD0WW\ntpxlZkaw0Ex56x+/B1xpZvOBhcAXJV57EphrZl+5+4U77+Xuk8zsROBrgqm7b3T3NWbWaTexiYRC\n3WpFRCQqqpISEZGoKGGIiEhUlDBERCQqShgiIhIVJQwREYmKEoaIiERFCUNERKKihCEiIlH5/0pB\n/WIqs8BpAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b3819dd90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_accs(theta_lr_hist);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The figure suggests that you can get higher accuracy by training for longer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 5.3** \n",
    "\n",
    "\n",
    "- Try to improve on the performance that you get with the default hyperparameters.\n",
    "- Specifically, try different values for regularization, learning rate, and number of iterations\n",
    "- Because training is somewhat slow, you will have to be careful in how you do this.\n",
    "- Write the predictions of your best models to ```lr-best-dev.preds``` and ```lr-best-test.preds```.\n",
    "- You should be able to get at least 66% accuracy on the dev set.\n",
    "- As you try different configurations **save the weights** for each configuration separately. This will help you with problem 6.2.\n",
    "\n",
    "(0.5 points)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_lr_best,theta_lr_hist_best = logreg.estimate_logreg(x_tr,y_tr,20) #add your hyperparameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEPCAYAAABRHfM8AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl4VOX5//H3HXaUHVkMiygIWuAri+ACGsQF9wpKARfA\nunwVxbYWBS0KautafypqvwqIWBWVQgVBRVwCWCthFRACqBAh7EIg7CG5f3+cSQwhwCRkMpnweV3X\nXMycOefMnVwhnzzPc57nmLsjIiJyNHHRLkBERGKDAkNERMKiwBARkbAoMEREJCwKDBERCYsCQ0RE\nwhLxwDCzbmaWbGYrzOzBw+zT08y+N7PFZvZ2ru2ZZjbfzBaY2YeRrlVERA7PIjkPw8zigBVAV2Ad\nMAfo5e7JufZpCrwPdHH3HWZW2923hN7b4e5VI1agiIiELdItjA7ASndPcfcM4D3g2jz73A684u47\nALLDIsQiXJ+IiIQp0oERD6zJ9XptaFtupwPNzexrM/vGzC7L9V4FM0sKbc8bNCIiUozKRrsAghqa\nAhcAjYCZZtYy1OJo7O7rzawJ8KWZLXL3VdEsVkTkeBXpwEglCIFsDULbclsLfOvuWcBqM1sBNAPm\nuft6AHdfZWaJQBvgoMAwMy2GJSJSCO5eoG7/SHdJzQGamlljMysP9AIm59nnQ6ALgJnVJgiLn8ys\neuiY7O3nAUvz+xB316OIHo8++mjUayhND30/9f0sqY/CiGgLw90zzewe4DOCcBrt7svMbDgwx92n\nuPs0M7vUzL4HDgB/dvdtZnYu8JqZZYaOfdJzXV0lIiLFK+JjGO7+KdA8z7ZH87y+H7g/z7b/Aq0j\nXZ+IiIRHM73lIAkJCdEuoVTR97No6fsZXRGduFcczMxj/WsQESluZoaXsEFvEREpJRQYIiISFgWG\niIiERYEhIiJhUWCIiEhYFBgiIhIWBYaIiIRFgSEiImFRYIiISFgUGCIiEhYFhoiIhEWBISIiYVFg\niIhIWBQYIiISFgWGiIiERYEhIiJhUWCIiEhYFBgiIhIWBYaIiIRFgSEiImFRYIiISFgUGCIiEhYF\nhoiIhEWBISIiYVFgiIhIWBQYIiISFgWGiIiERYEhIiJhUWCIiEhYFBgiIhIWBYaIiIRFgSEiImFR\nYIiISFgUGCIiEpaIB4aZdTOzZDNbYWYPHmafnmb2vZktNrO3c23vGzpuuZndEulaRUTk8MzdI3dy\nszhgBdAVWAfMAXq5e3KufZoC7wNd3H2HmdV29y1mVgOYC7QFDJgHtHX37Xk+wyP5NYiIlAR79sCN\nN8JPP0GfPvDAA8d2PjPD3a0gx5Q9to88qg7ASndPATCz94BrgeRc+9wOvOLuOwDcfUto+2XAZ9kB\nYWafAd0IwkVEJOZt2RIEwE8/wY8/Bv+uWgXTpkG5cgfvW7FiEBRNmkDTptGpN9KBEQ+syfV6LUGI\n5HY6gJl9TdBFNtzdp+VzbGpom4hIibZnD2zcCBs2BI9u3YJf+Hmdey5Uqwannho8OnaE3r3B8vm7\n3wyuvz7ytR9JpAMjHGWBpsAFQCNgppm1LMgJhg0blvM8ISGBhISEIixPRCSwaxesWAEtWkClSoe+\nf9FFMH9+EBj16v36OO+8/ANj5crI15wtMTGRxMTEYzpHpMcwzgGGuXu30OvBgLv707n2+QfwrbuP\nDb3+HHgQaAYkuPv/hrb/H/CVu7+f5zM0hiEiEbN+PUyZApMmwcyZQZfQxIlw2mmH7rtqFVSvHjzy\nayWUJIUZw4j0VVJzgKZm1tjMygO9gMl59vkQ6AJgZrUJguInYBpwiZlVCw2AXxLaJiJSLO6/H848\nE778Mhhw/vln+O67/MMCgjCpUaPkh0VhRbSFAcFltcCLBOE02t2fMrPhwBx3nxLa5+8EA9oHgCfc\nfXxoez/gYcBD29/K5/xqYYhIRKxfD7VqQfny0a6k6BWmhRHxwIg0BYaIFEZ6enA10uTJQRfSSy9F\nu6LiVRIvqxURKTF27oS33w7GI/7zn2Aw+pprgoccnQJDRI4bWVlBUNx6K7z/PlStGu2KYou6pESk\nVHCH5GSYNSt4vPoqVKkS7apKrpJ4lZSISESNGQPdu0PdunDFFfD113DhhaX3SqW0vWlMSp4Ulc9W\nl5SIxLQDB4IZ0C++CA0bRruayNi4cyOTlk9i4rKJfLPmGxJOSeDS0y6lUrl8Zg9GkLqkRKTESkmB\nqVODx/XXQ//+0a6o+KSkpfDv5H8zcdlEFm1cxOXNLqd7i+50a9qNKhWOva9Nl9WKSMxbuRJGjQpC\nYtMmuPxyuPJKuPTS4PLX0mzZ5mU5IZGyPYVrTr+G7md0p+upXalYNp+1RY6BLqsVkZi3bRtUqACj\nR8PZZ0NcKR5pdXfmr5/PxGUTmZg8kfR96VzX4jqeveRZOjfuTNm4kvUrWi0MESlW7rBwIcybB7fd\nFu1qil9mVibfrPkmJyTKlylP9xbd6X5Gd86OP5s4K56EVAtDREqkXbvg88+DRfw+/hgqV4arrw7m\nRZTmFkRumVmZvLP4HR5NfJSqFarSvUV3pvSeQss6LbEYuaRLLQwRiSh3aN06uOz1yiuDx+mnR7uq\n4uPufLTiIx764iGqVazGU12fonPjztEuS4PeIlIy7d9fOhfwO5qvf/6awZ8PJm1vGk92fZKrTr+q\nxLQm1CUlIsUuKwu++Qbeew/+53/g9tsP3ed4C4tFGxfx0BcPsWTTEh7r8hg3trqRMnFlol3WMVNg\niEiBZQ9cjxsXBEXVqsGtRS++ONqVRdeqbat4JPERPvvxMx7q9BATek6gQtkK0S6ryCgwRKTAFi6E\nHj2CkJg6FVq1inZF0bVx50b+OuuvvLP4He7tcC8r711J1Qqlb2VDjWGISIFl/5crId3xUbNj3w7+\n/s3feXnOy9zU6iYevuBh6pxQJ9plhUWLD4pIkUhJgeeeg44dg5nXeZkd32Gx78A+Xvj2BZqNaMaq\ntFXMvX0uL17+YsyERWGpS0pEgOB+1R98AOPHw08/wXXXwRNPwCmnRLuykiMzK5O3F73No4mP0rJO\nS6bfPJ3WdVtHu6xio8AQESC4odDKlUFIJCRAuXLRrij61qevZ3bqbJJSk5idOpu56+bSum5r/nnd\nP0vEXIripjEMkePM7t3BTGs52K79u5i3fh6z187OCYldGbvoEN+BjvEd6RDfgQ7xHahduXa0Sy0S\nmrgnIvlKSQm6msaPh4oVYcaMaFcUXZlZmSzdvPSg1sMPW3+gVZ1WOQHRsUFHTqtxWomZaFfUFBgi\nkuPAAfjzn4NJdatWBWMSN9wQe91NaXvTmLtuLgs3LGR/5v5jPldSahLz1s/j5Con/xoO8R1pXbd1\nqZozcTQKDJHjyL59sHw5LFkS3KK0Yj63S3jlFTjzTOjUKTZCYn/mfhZvXHzQX/5rtq+hbf22tK3f\nlsrljq0v7cTyJ9L+5Pa0P7k9NSvVLKKqY5MCQ6SUGzEiuGf1kiXBlUxNmkDLlvDyy1Anxq7odHdW\npa06aMzgu43fcWqNU+lwcgc6Ngj+8v9Nnd+UuPtClAYKDJEYt38/fP89NGoEtWod+v7IkVCpUjCz\nunnz/FsVJdXWPVtJSk3KaTkkpSZRvkz5nC6hDvEdaH9y+yK5/agcnQJDJMasWAEzZwY3E5o7NwiL\nJk3gtdeCbqRYte/APhZuWJgTDrNTZ7Nh5wban9w+Jxw6xnckvmp8tEs9bikwRGLM3/8O330H7dtD\nu3Zw1llwwgnRrqpg3J0ftv4QBMPa2SStS2LJpiU0q9nsoMtRzzzpzFKxYmtpocAQKSF274ZJk4LL\nV+fNgyuugOHDo11V0di8a/NB3UpJqUlUqVDloJZD2/ptOaF8jCXfcUaBIRJlKSnw+OMwYQKccw5c\nfnl0Wg67M3aTuiOVtTvWsmX3lmM+X2p6ak4L4pc9v3D2yWfnzFXoEN+BeifWK4KqpTjpBkoiUVa2\nbHD70e+/h5NPLvrzuzu/7PmFtTvWkrojldT01EOfp6eyJ2MP8VXjia8Sz0knnEScHds6oydVPolu\np3XjkQseoXnt5sd8PolNamGIFMLOncHyGnFF+HszIzOD9TvX5xsA2dvWpa+jcrnKOWHQoGoD4qvE\nH/y6ajy1KtUqtTOUpWioS0okgrKygiua3nwTPvwweN46zIVK0/elH7Y1kN11tHXPVuqcUIf4qrmC\nIFcIZAfDsU5eEwEFhkhEpKTAmDEwdixUqQL9+sGNN0Lduofuu23PNuasm5NztdCPW38kNT2VA1kH\n8m8NhF43qNqAuifU1VVEUmw0hiESAbNmwbZtMHFiMHid3dOzP3M/3234LmeeQVJqEuvT19Pu5HZ0\nOLkD/f6nHy1qtyC+ajzVKlRTF5HEPLUwREIyMg6/3pK78+O2Hw9axmLxpsU0q9nsoOWvNddAYkWJ\n7JIys27ACwS3gx3t7k/neb8v8CywNrTpZXd/I/ReJvAdYECKu/82n/MrMKTQtm+Hjz4K7jS3dGlw\nAyEz2LJ7SzDXINS1lJSaxAnlTshZ36hDfAfa1W+nuQYSs0pcYJhZHLAC6AqsA+YAvdw9Odc+fYF2\n7j4wn+N3uHvVo3yGAkMKbNy44JGYCJ277KXdVQuo1HQ2i7cGE9K27N6Ss4xFdkDUr1I/2mWLFJmS\nOIbRAVjp7ikAZvYecC2QnGe/wxWtTl8pUlmexYpfVvB+8mx2d0nitMtnk7htGRu8BR13d+TS0y5l\n6AVDNddAJB+RDox4YE2u12sJQiSv7mbWmaA18id3z+6eqmBmScAB4Gl3nxTRaqVU2b4dVm3ayM9Z\nv95bYU7qHGpWqknH1h258OQOdGxwI23qtaFSuUrRLlekxCsJV0lNBt519wwzuwMYS9CFBdDY3deb\nWRPgSzNb5O6rolapRFxKWgovzX6JrXu3Fup4z4K1qbD0h3Q2lJlDpWrpdD41WPzuDx3/wNnxZ1Pn\nhBi7cYRICRHpwEgFGuV63SC0LYe7b8v1chTwTK731of+XWVmiUAb4JDAGDZsWM7zhIQEEhISjrlw\nKV5bdm/hb7P+xtjvxnJ729u5oNEFBTp+7z6YOQO++CJYs+marpW4/aq/0bZxM13OKgIkJiaSmJh4\nTOeI9KB3GWA5QYthPZAE9Hb3Zbn2qefuG0LPrwMGuft5ZlYd2O3u+82sNvAf4NrcA+ahYzToHcN2\n7t/J//vv/+PF2S/Sq2Uv/nLBXwq1kF1aGgwcCHffDR07/jpXQkTyF7FBbzObCIwGPnH3rHBP7u6Z\nZnYP8Bm/Xla7zMyGA3PcfQow0MyuATKArUC/0OFnAK+FLq2NA57MGxYSu/Zn7uf1ea/z11l/pcsp\nXZh922xOq3laoc9XvTq89VYRFigihwirhWFmFwP9gXOA8cAYd18e4drCohZGbMnyLMYtHsfQr4Ir\nkZ7s+iRn1TsrrGO3boXRo4PZ1pdcEuFCRUq5iLUw3P1z4HMzqwb0Dj1fA4wE3nb3jAJXK8cVd+eT\nHz5hyBdDqFS2Em9c+wYJpySEdezixTBiBIwfD1dfHdxjQkSKX9iD3mZWC7gJuBlYALwDdAL6AgmR\nKE5Kh/+u+S+DvxjM5l2b+VvXv3Ft82vDGoheswZuvjmYfX3XXbB8OdTRBU4iURNul9S/gebAP4E3\ns69eCr03193bR67Eo9amLqkSaunmpTz0xUPMXz+f4QnDufl/bqZsXPgX5u3bB5Mnw29/e/g1nkSk\ncCK2NIiZdXH3rwpdWQQpMEqen7f/zKOJjzJ1xVQePP9BBnQYQMWyFaNdlojkUpjACHftgzNDl7lm\nf1ANM7u7QNXJceHpr5+mzWttiK8Sz8p7V3L/efcfMSy2bYNhw+Cf/yy+GkWkcMINjNvdPS37RWiy\n3e2RKUli1XPfPMeYhWNY9L+LeOKiJ6hWsdph9/3lFxg6FJo1g59/hnPPLcZCRaRQwg2MMpZrlDI0\nIa98ZEqSWDRy3kheTnqZ6TdPJ75q/GH327sXhgyB00+HjRshKQneeAOaNi3GYkWkUMIdgfwUeN/M\nXgu9vjO0TYT3l7zPo4mPMqPfDBpWa3jEfStUgMqVYf58aNy4mAoUkSIR7qB3HEFIZC8KOB0Y5e6Z\nEawtLBr0jq6PV35M/0n9mX7zdFrXbR3tckQkTCXuBkrFQYERPTNTZtLjgx5M7jWZcxsePAiRmgpL\nlsBll0WpOBE5oohdJWVmzczsX2a21Mx+yn4UrkwpDeatm8f1H1zPu93fPSgsUlNhwABo1Qpmz45i\ngSJS5MId9B4D/IPgRkZdgLeAtyNVlJRsyzYv48p3r+S1q17jktOCRZ3cg8Hrs84KlhdPToZHHoly\noSJSpMIdw5jn7u3MbLG7t8q9LeIVHr02dUkVo9Vpq+k8pjNPdHmCvmf1zdk+dChMmRKsGNuqVRQL\nFJGwRHKm9zcE60b9C/iS4CZIT7l788IUWpQUGMVnffp6Oo/pzMCOAxnYceBB723cCDVqQHldbC0S\nEyIZGGcDy4DqwONAVeBZd/+2MIUWJQVG8di6ZysXvnkhPc/sydALh0a7HBE5RhEJjNAkvafd/c/H\nUlykKDAib+f+nVz81sWc3/B8nrv0OTIyTC0JkRgXkaukQnMtOhW6Kolpew/s5bfv/ZaWdVoytONz\n3Hqrcd990a5KRKIh3JneC8xsMsHd9nZlb3T3iRGpSkqEA1kH6PWvXtSsVJMbKr1G69bGVVfBM89E\nuzIRiYZwA6Mi8AtwUa5tDigwSqksz+LWSbeye98+6iV9wO0flWHUKLj00mhXJiLREu4tWvtHuhAp\nOdyd+z65j1Vpq7hs0zR+2FWeRYugevWjHysipVdYgWFmYwhaFAdx91uLvCKJuke+eoT/rPkPX/X9\niirlKxMX7vROESnVwu2SmpLreUXgOmBd0Zcj0fb3b/7O+KXjmdl/5hHvZyEix59CLT4YWr32a3c/\nr+hLKnAtuqz2GGVlweipi5iY+iLL9n7BrP6zjrpMuYjEtsJcVhtuCyOvZkCdQh4rJUTyigP85e0P\nmbJpBJnVf6BHo7uYc/scTjrhpGiXJiIlULhjGOkcPIaxAXgwIhVJxC1dvYUrho5kTd1/UK9SI4Zf\nfS9/6tadcmXKRbs0ESnBwr1KqkqkC5HIW7B+ASOSRvDv5H9z9jnX8cE1k+jQsE20yxKRGBFuC+M6\n4Et33x56XR1IcPcPI1mcHJvly6Fq9Qxmbp7IiKQR/Lz9Z+5qfxcr711J7cq1o12eiMSYcBcfXOju\nZ+XZtsDdo/7nqQa9D5aWBu+/DyPf3UTyCa9TqfP/8Zv6Tbm3w71c2+JaysYVdthKREqTSA5653cl\nvn7zlCCrV8OQIfDRvDnUumIEv1zyEb9rdT33nfOx7rUtIkUi3F/6c83seeCV0OsBwLzIlCSF8e3a\nb/nmjD9R8+x13NNxAL9v+wI1K9WMdlkiUoqE2yV1AjAUuJjgaqnpwF/dfdcRDywGx3uXVPq+dP7y\n5V/4YOkHPHfJc/Rq2YsycWWiXZaIlHARu4FSSXY8B8bHKz/mrql30bVJV5679Dm1KEQkbBEbwzCz\n6cAN7p4Wel0DeM/dLyt4mXIsFiyAtyZsYmObPzA7dTajrxnNxadeHO2yROQ4EO6ycrWzwwLA3beh\nmd7Fau9eeOhh58KBb/FGhVbEV2nA4rsWKyxEpNiEO+idZWaN3P1nADM7hXxWr5XI+O9/4aZ7V7Ez\n4U4a99rC2O6f0LZ+22iXJSLHmXAD42HgazObARjQGbgjYlVJjg8nH+CWV16C3/6NoV0e5I/n/lFz\nKUQkKsLqknL3T4H2wHJgHHA/sCecY82sm5klm9kKMztk/Skz62tmm8xsfuhxa573VpjZcjO7Jayv\nqBRZuGEhj607h7N6TmX+3d8y6PxBCgsRiZpwL6u9DbgPaAAsBM4B/uvuFx3luDhgBdCV4P4Zc4Be\n7p6ca5++QDt3H5jn2BrAXKAtQatmHtA2e3mSXPuVuquk9mTs4bEZjzF6wWievvhp+p3VD7MCXcwg\nInJEhblKKtxB7/uAs4EUd+8CtAHSjnwIAB2Ale6e4u4ZwHvAtfnsl1/RlwGfufv20ID7Z0C3MOuN\nSWlp8NWqr2j9f635Ke0nFt21iP5t+issRKRECLd/Y6+77zUzzKyCuyebWfMwjosH1uR6vZYgRPLq\nbmadCVojf3T31HyOzd5W6mRkQL+7tjGj3APEnT6NV654haubXx3tskREDhJuC2NtaIXaD4HpZjYJ\nSCmiGiYDp4QWN/wceKuIzhsT9u+HrrfOYGLd1lzZrQJL7l6isBCREinc+2FcF3o6zMy+AqoBn4Zx\naCrQKNfrBqFtuc+9LdfLUcDTuY5NyHPsV/l9yLBhw3KeJyQkkJCQkN9uJc7uPZm0ve9vrG78KhNu\nGsuVLS6NdkkiUkolJiaSmJh4TOeI6NIgZlaG4MqqrsB6IAno7e7Lcu1Tz903hJ5fBwxy9/PyDHrH\nhZ63yz2BMHRMTA56r9+xkVbDbsTKHGDukHdpXPPkaJckIseRSA56F4q7ZwL3EAxYf0+wnMgyMxtu\nZleFdhtoZkvMbEFo336hY7cBjxMExWxgeN6wiFVfrvqS9qPacnGL8/j5ic8VFiISE7T4YDHKzMrk\nsRmPMXL+SN667i0t6yEiURPJGyjJMVqfvp4+E/sQZ3HMv3M+9U6sF+2SREQKJKJdUhKY/uN02r3e\nji6ndOGzmz5TWIhITFILI4IOZB1gWOIw3lgwhqaL3qHfDV0oo4gWkRilwIiQ1B2p9J7Qm7JWkQZT\n59P8tLo0aBDtqkRECk9/70bApz98SrvX23Fhg8vY8/qntD29Lq+9BnH6botIDFMLowhlZGYw9Kuh\nvLP4Hd64/AMe+/0FtG0LL7+ssBCR2KfAKCJrtq+h14ReVClfhfl3zGfGJyfRoQO8+CJo7UARKQ00\nD6MITF0xlVsn38ofz/kjD5z/AHGm5oSIlGyah1HMMjIzGPLFED74/gMm9JxAp0adol2SiEjEKDAK\nKSUthV4TelGrUi3m3zmf2pVrR7skEZGIUt9JIUxKnkSHUR3ocUYPJveeTNbO2ixeHO2qREQiSy2M\nAtifuZ8Hpz/IxOSJfPi7Dzm34bmkpcEll0CvXtCqVbQrFBGJHAVGmFZtW8Xv/vU76p1YjwV3LqBm\npZrs3g1XXQVdusDgwdGuUEQkstQlFYaJyybScVRHerfszaRek6hZqSYZGXD99XDqqfD887p0VkRK\nP7UwjmDfgX0Mmj6Ij1Z8xEe9P6Jjg44AuEP//lC2LIwerUl5InJ8UGAcxo9bf+R3//odDas1ZP4d\n86lRqUbOe2bQp0/QFVWuXBSLFBEpRpq4l4/x349nwMcD+MsFf+HeDvdi6m8SkVJGE/eO0d4De7l/\n2v18+uOnfHzjx7Q/uX20SxIRKTEUGCErf1lJz3/1pGnNpsy/Yz7VKlaLdkkiIiWKhmuB95a8x3lv\nnMdtbW7jg+s/OCQspk6F2bOjVJyISAlx3AfG24ve5qEvHmLaTdMY0GHAIeMVM2YEV0TpSigROd4d\n14PeuzN20/zl5nxw/Qec2/DcQ96fPx+6dYNx46Br12OtVESk5CjMoPdx/XfzC9++wDkNzsk3LJYv\nhyuvhNdeU1iIiMBx3MLYtGsTZ75yJt/e9i1NazY96L19++DMM+Hhh+HWW4uqUhGRkqMwLYzjNjDu\n+fgeysaV5YVuL+T7/g8/QNOm+b4lIhLzFBhhWr5lOZ3GdCJ5QDK1KteKUGUiIiWXxjDCNPiLwQw6\nb5DCQkSkAI67iXuzUmYxf/18xvUYF+1SRERiynHVwnB3Bk0fxF8v+isVy1YMbYOBA2Hu3CgXJyJS\nwh1XgTF+6XgysjLo06pPzrZnnglmcbdoEcXCRERiwHHTJbXvwD6GfDGEkVePJM6CnExKCm5+NGcO\nnHhilAsUESnhjpsWxqtzXuWM2mdwUZOLAEhPD+5p8eqr0KhRlIsTEYkBx8Vltdv2bKP5y81J7JfI\nmSedCQTrQ5UrB6+/XhxVioiULJqHcRiDPhvE9n3bef3qX9MhKQl+8xs44YRIVygiUvIoMPKxOm01\n7V5vx5K7llC/Sv1irExEpOTSxL18PPzlwwzsMFBhISJyjCIeGGbWzcySzWyFmT14hP16mFmWmbUN\nvW5sZrvNbH7o8WpBP3vuurkkrk7k/vPuP5YvQUREiPBltWYWB7wMdAXWAXPMbJK7J+fZ70RgIPBt\nnlP84O5tC/PZ7s6fP/szwy4cxonlT2T7dqimu66KlBinnHIKKSkp0S6j1GvcuDGrV68uknNFeh5G\nB2Clu6cAmNl7wLVAcp79HgeeAh7Is71A/Wu5TVkxhc27N9O/TX+2boU2bWDaNE3QEykpUlJSiPUx\n1FiQ9y6ixyLSXVLxwJpcr9eGtuUwszZAA3f/JJ/jTzGzeWb2lZl1CvdDD2Qd4IHPH+CZi5+hjJXl\nttugRw+FhYjIsYjqTG8Lou95oG/uzaF/1wON3H1baFzjQzM709135j3PsGHDcp4nJCSw/MTl1D+x\nPlc0u4LXX4dVq4LbrIqIHK8SExNJTEw8pnNE9LJaMzsHGObu3UKvBwPu7k+HXlcFfgB2EgRFPeAX\n4Bp3n5/nXF8B9+ez/aDLatP3pXP6y6cztc9UKm5ry4UXwqxZal2IlDShyzqjXUapd7jvc2Euq410\nC2MO0NTMGhO0GHoBvbPfdPcdQJ3s16FQ+JO7LzCz2sBWd88ys1OBpsBPR/vAZ795lotPvZi29dty\n1e3w5JMKCxGRohDRwHD3TDO7B/iMYLxktLsvM7PhwBx3n5L3EH7tkroAeMzM9gNZwJ3unnakz1uX\nvo5X5rzC/DuCRsi4cVpUUESi46677qJBgwY8/PDDRbpvNJWqmd63Tb6NWpVq8fQlT0e5KhE5mpLe\nJdWkSRNGjx7NRRddFO1SjkksdUkVm8UbF/PRio9Yfs/yaJciIqVcZmYmZcqUiXYZxa7ULA3ywOcP\n8FCnh6hesXq0SxGRGHfLLbfw888/c9VVV1G1alWeffZZ4uLieOONN2jcuDFdu3YFoGfPntSvX58a\nNWqQkJBA8QvIAAALOElEQVTA0qVLc87Rv39/HnnkEQBmzJhBw4YNef7556lbty7x8fG8+eabhdp3\n69atXH311VSrVo2OHTsydOhQOnfuHPlvCqUkMD7/6XNW/rKSlnvvYv/+aFcjIrHurbfeolGjRkyd\nOpUdO3bQs2dPAGbOnElycjLTpk0D4IorruDHH39k06ZNtG3blhtvvPGw59ywYQPp6emsW7eOUaNG\nMWDAALZv317gfe+++26qVKnCpk2bePPNNxk7dmyRTs47klIRGIOmD+L2Jk/Ru2d5NmyIdjUiUlSG\nDQOzQx+5pl4dcf/D7Reu3H3/Zsbw4cOpVKkSFSpUAKBfv35UrlyZcuXK8cgjj/Ddd9+Rnp6e77nK\nly/P0KFDKVOmDJdffjknnngiy5fn34V+uH2zsrKYOHEijz32GBUqVOCMM86gb9+++Z4jEkpFYJS3\nSoy6vwcvvaS754mUJsOGgfuhjyMFRjj7FVaDBg1ynmdlZTF48GCaNm1K9erVadKkCWbGli1b8j22\nVq1axMX9+iu3cuXK7Nx5yDzkI+67efNmMjMzD6qjYcOGx/plha1UBMZJC56j0/lGr17RrkRESov8\nunlyb3v33Xf56KOP+PLLL0lLS2P16tW4e0Sv/DrppJMoW7Ysa9euzdm2Zs2aIxxRtEpFYCz//Dxe\neinaVYhIaVKvXj1++imYK5xfEKSnp1OhQgVq1KjBrl27GDJkSMTHEuLi4ujevTvDhg1jz549JCcn\n89Zbb0X0Mw/6/GL7pAgaNw6qVIl2FSJSmgwePJjHH3+cmjVrMmHChEPC4JZbbqFRo0bEx8fTsmVL\nzjvvvAKdvyDhknvfESNGkJaWRv369enbty99+vTJGVOJtFI1cU9EYkdJn7gXKwYPHszGjRsZM2ZM\nvu8X5cS9UtHCEBE5XixfvpzFixcDkJSUxOjRo+nevXuxfHapmektInI8SE9Pp3fv3qxfv566desy\naNAgrr766mL5bHVJiUhUqEuqeKhLSkREip0CQ0REwqLAEBGRsCgwREQkLAoMEREJiwJDRCQMue9Z\ncbxSYIiISFgUGCIiEhYFhohIPhYsWEC7du2oVq0avXr1Yu/evTnvTZkyhTZt2lCjRg06deqUs1TH\nM888ww033HDQee677z7+8Ic/FGvtkaLAEBHJIyMjg+uuu46+ffuydetWbrjhBiZMmADAwoUL+f3v\nf8/IkSPZunUrd955J9dccw0ZGRn06tWLTz75hF27dgHBTZbGjx9/xFu3xhItDSIiURHO0iA2/Njv\nL+GPFvz3w6xZs+jdu/dBNyo6//zz6dq1K1u2bOGkk05i+PDhOe+1aNGCkSNH0rlzZy644ALuuOMO\nbrrpJqZPn87dd9/NypUrj/nrKKyiXBpEiw+KSIlVmF/2RWHdunXEx8cftK1x48YApKSkMHbsWEaM\nGAEEN1fKyMhg3bp1APTu3Ztx48Zx0003MW7cOPr06VO8xUeQWhgiEhUlefHBmTNn0qdPn4NaGJ06\ndeKiiy5i8+bNNGrUiCFDhuR77JYtW2jcuDErVqygZcuWfPvttzRv3ry4Sj+EFh8UEYmgc889l7Jl\nyzJixAgOHDjAxIkTSUpKAuC2227jH//4R87rXbt28fHHH+eMW9SuXZsLL7yQ/v37c+qpp0Y1LIqa\nAkNEJI9y5coxceJExowZQ61atRg/fjw9evQAoF27dowaNYp77rmHmjVrcvrppzN27NiDju/Tpw9f\nfPFFqRnszqYuKRGJipLcJVWaqEtKRESKnQJDRETCosAQEZGwKDBERCQsCgwREQmLAkNERMKipUFE\nJCoaN26M2bGvFSVHlr2kSVGI+DwMM+sGvEDQmhnt7k8fZr8ewHigvbvPD20bAtwKHADuc/fP8jlO\n8zBERAqoxM3DMLM44GXgMuA3QG8za5HPficCA4Fvc207A+gJnAFcDrxq+nMk4hITE6NdQqmi72fR\n0vczuiI9htEBWOnuKe6eAbwHXJvPfo8DTwH7cm27FnjP3Q+4+2pgZeh8EkH6D1m09P0sWvp+Rlek\nAyMeWJPr9drQthxm1gZo4O6fHOXY1LzHiohI8YnqoHeoi+l5oG806xARkaOL6KC3mZ0DDHP3bqHX\ngwHPHvg2s6rAD8BOwIB6wC/ANcClBDs/Fdr3U+BRd5+d5zM04i0iUggFHfSOdGCUAZYDXYH1QBLQ\n292XHWb/r4A/ufsCMzsTeAfoSNAVNR1opkuiRESiI6JdUu6eaWb3AJ/x62W1y8xsODDH3afkPYSg\npYG7LzWzD4ClQAZwt8JCRCR6Yv5+GCIiUjxiemkQM+tmZslmtsLMHox2PbHOzFab2XdmtsDMkqJd\nT6wxs9FmttHMFuXaVsPMPjOz5WY2zcyqRbPGWHGY7+WjZrbWzOaHHt2iWWMsMbMGZvalmX1vZovN\nbGBoe4F+PmM2MMKdFCgFkgUkuHsbd9ecl4IbQ/DzmNtg4HN3bw58CQwp9qpiU37fS4Dn3b1t6PFp\ncRcVww4QjA//BjgXGBD6fVmgn8+YDQzCnxQo4TNi+2ciqtz9a2Bbns3XAtk3fB4L/LZYi4pRh/le\nQmiMUwrG3Te4+8LQ853AMqABBfz5jOVfDkedFCgF5sA0M5tjZrdHu5hSoo67b4TgPy1QJ8r1xLoB\nZrbQzEape69wzOwU4CyCpZjqFuTnM5YDQ4re+e7eHriC4D9mp2gXVArpKpPCexU4zd3PAjYQTPqV\nAgit2/cvgsVcd3Loz+MRfz5jOTBSgUa5XjcIbZNCcvf1oX83A/9Ga3cVhY1mVhfAzOoBm6JcT8xy\n9825Lq0fCZwdzXpijZmVJQiLf7r7pNDmAv18xnJgzAGamlljMysP9AImR7mmmGVmlUN/fWBmJxDM\ntF8S3apiknFwP/tkoF/oeV9gUt4D5LAO+l6GfqFl645+PgvqDWCpu7+Ya1uBfj5jeh5G6LK6F/l1\nUuBTUS4pZplZE4JWhRNM6HxH38+CMbN3gQSgFrAReBT4kOA+Lw2BFKCnu6dFq8ZYcZjvZReCvvcs\nYDVwZ3b/uxyZmZ0PzAQWE/wfd+AhgtU3PiDMn8+YDgwRESk+sdwlJSIixUiBISIiYVFgiIhIWBQY\nIiISFgWGiIiERYEhIiJhUWCI5GJmX4f+bWxmvYv43EPyvP66KM8vEmmahyGSDzNLAO5396sLcEwZ\nd888wvvp7l6lKOoTiQa1MERyMbP00NMngU6hG/XcZ2ZxZvaMmc0OrZZ6e2j/C81spplNAr4Pbft3\naMXfxWZ2W2jbk0Cl0Pn+meezMLNnQ/t/Z2Y9c537KzMbb2bLso8TiZaI3tNbJAZlN7kHE7QwrgEI\nBUSau3cMrV32HzP7LLRvG+A37v5z6HV/d08zs4rAHDOb4O5DzGyAu7fN+1lm1gNo7e6tzKxO6JgZ\noX3OAs4kWJ31P2Z2nrt/E6GvXeSI1MIQCc+lwC1mtgCYDdQEmoXeS8oVFgB/MLOFBPcbaJBrv8M5\nHxgH4O6bgER+XYk1yd3Xh1ZpXQiccuxfikjhqIUhEh4D7nX36QdtNLsQ2JXn9UVAR3ffZ2ZfARVz\nnSPcz8q2L9fzTPR/VqJILQyRg2X/sk4Hcg9QTwPuDt1TADNrZmaV8zm+GrAtFBYtgHNyvbc/+/g8\nnzUL+F1onOQkoDPBKqIiJYr+WhE5WPYYxiIgK9QF9aa7vxi6teV8MzOCG83kd//jT4H/NbPvgeXA\nf3O99zqwyMzmufvN2Z/l7v82s3OA7wiW7h7k7pvM7IzD1CYSFbqsVkREwqIuKRERCYsCQ0REwqLA\nEBGRsCgwREQkLAoMEREJiwJDRETCosAQEZGwKDBERCQs/x9mLo2Iz8TabQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f5b38026410>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_accs(theta_lr_best);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_lr_best,theta_lr_hist_best = logreg.estimate_logreg(x_tr,y_tr,...)#add your hyperparameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "y_hat = clf_base.predict_all(x_dv,theta_lr_best,labels)\n",
    "evaluation.write_predictions(y_hat,'lr-best-dev.preds')\n",
    "y_hat_te = clf_base.predict_all(x_te,theta_lr_best,labels)\n",
    "evaluation.write_predictions(y_hat_te,'lr-best-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.686\n"
     ]
    }
   ],
   "source": [
    "# here are the scores for some weights that i got\n",
    "y_hat_dv = evaluation.read_predictions('lr-best-dev.preds')\n",
    "print evaluation.acc(y_hat_dv,y_dv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.664\n"
     ]
    }
   ],
   "source": [
    "y_hat_te = evaluation.read_predictions('lr-best-test.preds')\n",
    "print evaluation.acc(y_hat_te,y_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Feature analysis\n",
    "\n",
    "1 points for 4650; 0.5 point for 7650\n",
    "\n",
    "** Deliverable 6.1**\n",
    "\n",
    "Implement ```get_top_features_for_label``` in ```clf_base.py```. (0.5 points for 4650 / .25 points for 7650)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 259,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(clf_base);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "clf_base.get_top_features_for_label(theta_lr_best,'science',5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "clf_base.get_top_features_for_label(theta_lr_best,'worldnews',5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 6.2**\n",
    "\n",
    "- Now compare the top 5 features and weights for logistic regression under the largest regularizer and smallest regularizer that you tried in problem 5.3. \n",
    "- Paste the output into ```text_answers.md```, and explain the difference.\n",
    "- You cannot get full credit if your logistic regression classifier is not implemented correctly, so make sure you pass the units tests for part 5 before starting this.\n",
    "- 0.5 points for 4650 / 0.25 points for 7650. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# use this cell (and make more cells) to run your code to get the top features.\n",
    "# save the output in the notebook for when you submit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. Better preprocessing\n",
    "\n",
    "Total: 1 points for CS 4650; 0.5 points for CS 7650.\n",
    "\n",
    "Now try to make some changes to the preprocessing code to improve the performance of these classifiers.\n",
    "\n",
    "**Deliverable 7.1** \n",
    "\n",
    "- Write the function ```custom_preproc``` in ```preproc.py```\n",
    "- Then load the data using the code below\n",
    "- Choose one of the classifiers, train it on this new data, and print out the predictions on the test set and dev, using the code block below that.\n",
    "\n",
    "Full credit for doing something interesting, +1 points for beating my best test set score. (0.75 point for 4650 / 0.25 points for 7650)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 261,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(preproc);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "y_tr_bake,x_tr_bake = preproc.read_data('reddit-train.csv', #filename\n",
    "                                    'subreddit', #label field\n",
    "                                    preprocessor=preproc.custom_preproc) #your preprocessor\n",
    "y_dv_bake,x_dv_bake = preproc.read_data('reddit-dev.csv', #filename\n",
    "                                    'subreddit', #label field\n",
    "                                    preprocessor=preproc.custom_preproc) #your preprocessor\n",
    "y_te_bake,x_te_bake = preproc.read_data('reddit-test.csv', #filename\n",
    "                                    'subreddit', #label field\n",
    "                                    preprocessor=preproc.custom_preproc) #your preprocessor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# use this block to train your classifier on the new data.\n",
    "# you don't have to use Naive Bayes!\n",
    "theta_nb = naive_bayes.estimate_nb(x_tr_bake,y_tr_bake,smoothing=1e-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "y_hat_dv_bake = clf_base.predict_all(x_dv_bake,theta_nb,labels)\n",
    "evaluation.write_predictions(y_hat_dv_bake,'bakeoff-dev.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.78200000000000003"
      ]
     },
     "execution_count": 290,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's how well my preprocessed features do on the dev set\n",
    "evaluation.acc(y_hat_dv_bake,y_dv_bake)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y_hat_te_bake = clf_base.predict_all(x_te_bake,theta_nb,labels)\n",
    "evaluation.write_predictions(y_hat_te_bake,'bakeoff-test.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Here's how well my preprocessed features do on the test set\n",
    "evaluation.acc(y_hat_te_bake,y_te_bake)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 7.2 **\n",
    "\n",
    "Explain your novel preprocessing code in ```text-answers.md```\n",
    "\n",
    "(0.25 points for 4650, 0.25 points for 7650)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8. 7650 Research Question\n",
    "\n",
    "(1 point.) CS 4650 students may do this component if they want; if they do, then the assignment will be graded as if they are in 7650. This is optional for CS4650 students, but if you submit something for this part, that is how you will be scored -- we're not taking the max over the two possible scoring options. CS 7650 students must do this part.\n",
    "\n",
    "You will select a recent research paper that performs *document* classification, using text. Summarize the paper, answering the following questions:\n",
    "\n",
    "- What are the labels, and how were they obtained?\n",
    "- Why is it interesting/useful to predict these labels?  \n",
    "- What classifier(s) do they use, and the reasons behind their choice? Do they use linear classifiers like the ones in this problem set?\n",
    "- What features do they use? Explain any features outside the bag-of-words model, and why they used them.\n",
    "- What is the conclusion of the paper? Do they compare between classifiers, between feature sets, or on some other dimension? \n",
    "- Give a one-sentence summary of the message that they are trying to leave for the reader.\n",
    "\n",
    "Your selection of papers is determined by the last digit of your GTID.\n",
    "\n",
    "- Digits 0,1: choose from ACL 2016, AAAI 2016\n",
    "- Digits 2,3,4: choose from NAACL 2016, KDD 2016\n",
    "- Digits 5,6,7: choose from EMNLP 2016, ICWSM 2016\n",
    "- Digits 8,9: choose from ACL 2015, IJCAI 2016\n",
    "\n",
    "You must choose a paper in the main conference (not workshops). The paper must be at least four pages long. All papers from these conferences are available for free online."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}