ML_lab3_linear_reg_student.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![ML Logo](http://spark-mooc.github.io/web-assets/images/CS190.1x_Banner_300.png)\n",
    "# **Linear Regression Lab**\n",
    "#### This lab covers a common supervised learning pipeline, using a subset of the [Million Song Dataset](http://labrosa.ee.columbia.edu/millionsong/) from the [UCI Machine Learning Repository](https://archive.ics.uci.edu/ml/datasets/YearPredictionMSD). Our goal is to train a linear regression model to predict the release year of a song given a set of audio features.\n",
    "#### ** This lab will cover: **\n",
    "+  ####*Part 1:* Read and parse the initial dataset\n",
    " + #### *Visualization 1:* Features\n",
    " + #### *Visualization 2:* Shifting labels\n",
    "+  ####*Part 2:* Create and evaluate a baseline model\n",
    " + #### *Visualization 3:* Predicted vs. actual\n",
    "+  ####*Part 3:* Train (via gradient descent) and evaluate a linear regression model\n",
    " + #### *Visualization 4:* Training error\n",
    "+  ####*Part 4:* Train using MLlib and tune hyperparameters via grid search\n",
    " + #### *Visualization 5:* Best model's predictions\n",
    " + #### *Visualization 6:* Hyperparameter heat map\n",
    "+  ####*Part 5:* Add interactions between features\n",
    " \n",
    "#### Note that, for reference, you can look up the details of the relevant Spark methods in [Spark's Python API](https://spark.apache.org/docs/latest/api/python/pyspark.html#pyspark.RDD) and the relevant NumPy methods in the [NumPy Reference](http://docs.scipy.org/doc/numpy/reference/index.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "labVersion = 'cs190_week3_v_1_3'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ** Part 1: Read and parse the initial dataset **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (1a) Load and check the data **\n",
    "#### The raw data is currently stored in text file.  We will start by storing this raw data in as an RDD, with each element of the RDD representing a data point as a comma-delimited string. Each string starts with the label (a year) followed by numerical audio features. Use the [count method](https://spark.apache.org/docs/latest/api/python/pyspark.html#pyspark.RDD.count) to check how many data points we have.  Then use the [take method](https://spark.apache.org/docs/latest/api/python/pyspark.html#pyspark.RDD.take) to create and print out a list of the first 5 data points in their initial string format."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# load testing library\n",
    "from test_helper import Test\n",
    "import os.path\n",
    "baseDir = os.path.join('data')\n",
    "inputPath = os.path.join('cs190', 'millionsong.txt')\n",
    "fileName = os.path.join(baseDir, inputPath)\n",
    "\n",
    "numPartitions = 2\n",
    "rawData = sc.textFile(fileName, numPartitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6724\n",
      "[u'2001.0,0.884123733793,0.610454259079,0.600498416968,0.474669212493,0.247232680947,0.357306088914,0.344136412234,0.339641227335,0.600858840135,0.425704689024,0.60491501652,0.419193351817', u'2001.0,0.854411946129,0.604124786151,0.593634078776,0.495885413963,0.266307830936,0.261472105188,0.506387076327,0.464453565511,0.665798573683,0.542968988766,0.58044428577,0.445219373624', u'2001.0,0.908982970575,0.632063159227,0.557428975183,0.498263761394,0.276396052336,0.312809861625,0.448530069406,0.448674249968,0.649791323916,0.489868662682,0.591908113534,0.4500023818', u'2001.0,0.842525219898,0.561826888508,0.508715259692,0.443531142139,0.296733836002,0.250213568176,0.488540873206,0.360508747659,0.575435243185,0.361005878554,0.678378718617,0.409036786173', u'2001.0,0.909303285534,0.653607720915,0.585580794716,0.473250503005,0.251417011835,0.326976795524,0.40432273022,0.371154511756,0.629401917965,0.482243251755,0.566901413923,0.463373691946']\n"
     ]
    }
   ],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "numPoints = rawData.count()\n",
    "print numPoints\n",
    "samplePoints = rawData.take(5)\n",
    "print samplePoints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 test passed.\n",
      "1 test passed.\n"
     ]
    }
   ],
   "source": [
    "# TEST Load and check the data (1a)\n",
    "Test.assertEquals(numPoints, 6724, 'incorrect value for numPoints')\n",
    "Test.assertEquals(len(samplePoints), 5, 'incorrect length for samplePoints')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (1b) Using `LabeledPoint` **\n",
    "#### In MLlib, labeled training instances are stored using the [LabeledPoint](https://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LabeledPoint) object.  Write the parsePoint function that takes as input a raw data point, parses it using Python's [unicode.split](https://docs.python.org/2/library/string.html#string.split) method, and returns a `LabeledPoint`.  Use this function to parse samplePoints (from the previous question).  Then print out the features and label for the first training point, using the `LabeledPoint.features` and `LabeledPoint.label` attributes. Finally, calculate the number features for this dataset.\n",
    "#### Note that `split()` can be called directly on a `unicode` or `str` object.  For example, `u'split,me'.split(',')` returns `[u'split', u'me']`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pyspark.mllib.regression import LabeledPoint\n",
    "import numpy as np\n",
    "\n",
    "# Here is a sample raw data point:\n",
    "# '2001.0,0.884,0.610,0.600,0.474,0.247,0.357,0.344,0.33,0.600,0.425,0.60,0.419'\n",
    "# In this raw data point, 2001.0 is the label, and the remaining values are features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.884123733793,0.610454259079,0.600498416968,0.474669212493,0.247232680947,0.357306088914,0.344136412234,0.339641227335,0.600858840135,0.425704689024,0.60491501652,0.419193351817] 2001.0\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "def parsePoint(line):\n",
    "    \"\"\"Converts a comma separated unicode string into a `LabeledPoint`.\n",
    "\n",
    "    Args:\n",
    "        line (unicode): Comma separated unicode string where the first element is the label and the\n",
    "            remaining elements are features.\n",
    "\n",
    "    Returns:\n",
    "        LabeledPoint: The line is converted into a `LabeledPoint`, which consists of a label and\n",
    "            features.\n",
    "    \"\"\"\n",
    "    values = line.split(',')\n",
    "    return LabeledPoint(values[0], values[1:])\n",
    "\n",
    "\n",
    "parsedSamplePoints = parsePoint(samplePoints[0])\n",
    "firstPointFeatures = parsedSamplePoints.features\n",
    "firstPointLabel = parsedSamplePoints.label\n",
    "print firstPointFeatures, firstPointLabel\n",
    "\n",
    "\n",
    "d = len(firstPointFeatures)\n",
    "print d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 test passed.\n",
      "1 test passed.\n",
      "1 test passed.\n",
      "1 test passed.\n"
     ]
    }
   ],
   "source": [
    "# TEST Using LabeledPoint (1b)\n",
    "Test.assertTrue(isinstance(firstPointLabel, float), 'label must be a float')\n",
    "expectedX0 = [0.8841,0.6105,0.6005,0.4747,0.2472,0.3573,0.3441,0.3396,0.6009,0.4257,0.6049,0.4192]\n",
    "Test.assertTrue(np.allclose(expectedX0, firstPointFeatures, 1e-4, 1e-4),\n",
    "                'incorrect features for firstPointFeatures')\n",
    "Test.assertTrue(np.allclose(2001.0, firstPointLabel), 'incorrect label for firstPointLabel')\n",
    "Test.assertTrue(d == 12, 'incorrect number of features')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **Visualization 1: Features**\n",
    "#### First we will load and setup the visualization library.  Then we will look at the raw features for 50 data points by generating a heatmap that visualizes each feature on a grey-scale and shows the variation of each feature across the 50 sample data points.  The features are all between 0 and 1, with values closer to 1 represented via darker shades of grey."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAApsAAAJsCAYAAACyBWjFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzs3XmQ1PWd//FXH3NfPTfDMSAgyKA4ooAii4gIKELimawm\nbqIxlU22sru1tdmrav9Ibe3Wb7d2N5vaZFOJiRVNNNmsMR6ggqggIiAwHDLAyDEMMMAcXHPP9PH7\ng/oOISLM0J8vn+6Pz8c/OkPX8PrSPd9+fz/d/XkFEolEQgAAAIAPgrYDAAAAwF0MmwAAAPANwyYA\nAAB8w7AJAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8w7AJAAAA3zBsAgAAwDdh2wEAIFmbN2/W1q1b\nP/H9SCSiRx55xNjfs3PnThUVFam6utrYzwQA1zFsAnBCOBzWfffd94nvmbRz506NHTuWYRMAhoFh\nE4ATAoGAKioqfP87TIpGo8YHYgBINZzlADivqalJW7Zs0cmTJ5WRkaHx48fr1ltvHRz0otGoNmzY\noKNHj6qrq0s5OTkaPXq0Zs2apczMTEnS888/r87OTu3atUu7du2SJM2bN0+TJk3Sj3/8Y916662a\nNm3a4N+5fft2bdy4UV//+tclSc3NzXrttde0ePFi7d27V0eOHFFVVZUWL16svr4+ffjhh2psbFRf\nX5+Ki4s1c+ZMjR49+ir/SwGAeQybAJwRj8cv+DoYDOrAgQNavXq1Jk+erBkzZqirq0ubNm1SX1+f\n7rrrLknnhs1EIqEZM2YoJydHnZ2dqqur08qVKwdfml+4cKHeeOMNjRgxYnCoLCwsHHbG9957T9de\ne62mTp0qSYrFYlqxYoV6eno0Y8YM5eXl6eOPP9Ybb7yhBx54QCUlJcn8kwCAdQybAJwwMDCgp59+\n+oLv3Xnnnfrwww81YcIEzZ07d/D7OTk5evPNNzV9+nQVFxcrOztbf/RHfzT45/F4XAUFBXrllVd0\n5swZFRUVqaysTKFQSDk5OUm9XD9u3DjNnDlz8Ou9e/eqvb1dDz30kCKRiCRp9OjROn36tLZu3aoF\nCxZc8d8FAKmAYROAE8LhsJYtW3bB9+LxuDo7OzV+/PgLVj2rqqokSa2trSouLpYkNTQ0aOfOnTp7\n9qwGBgYGb+sNm6aMGTPmgq+PHDmikpISFRYWXpBx1KhR2r9/v7G/FwBsYdgE4IRAIKCysrILvnf8\n+HFJ0sqVKy96+66uLknSwYMH9e6772rKlCmaOXOmsrKy1N3drZUrVyoWixnNmZOTc8HXvb29amtr\n+8SqrHTubQAAkO4YNgE4KysrS5I0Z86ci770nZubK0k6cOCAysrKLngpvbm5ech/TygU+sT7Rfv6\n+i562z/8RHtWVpZKS0t1xx13DPnvA4B0wrAJwFmRSER5eXk6e/asampqPvV2sVjsE6uI+/bt+8Tt\ngsHgRVc68/LydOrUqQu+d/To0SFtlTR69GgdPnxYubm5g8MvALiEYROAswKBgG677Ta9/fbbGhgY\nUHV1tcLhsDo7O9XU1KSZM2eqqKhIo0eP1rp167R161ZVVFTo8OHDF13ZjEQiOnr0qI4cOaKsrCwV\nFBQoOztb48eP186dO1VeXq6ioiJ9/PHH6unpUSKRuGzGa6+9Vrt379arr76qadOmqaioSP39/Wpr\na1M8Hr/gw0QAkI4YNgGkvUutII4fP16ZmZmqq6sbXK3Mz8/XmDFjBt8/OWXKFJ09e1a7du3S9u3b\nNWbMGM2fP1+/+93vLvhZM2fO1Lp167Rq1SpFo1HdcccdmjRpkqZPn66enh5t2bJFwWBQU6ZMUWlp\nqTZt2nTZnKFQSEuWLNGWLVtUV1en7u5uZWdnq6ys7JKrsQCQLgKJoVx6AwAAAFeAjzoCAADANwyb\nAAAA8A3DJgAAAHzDsAkAAADfMGwCAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADANwybAAAA\n8A3DJgAAAHzDsAkAAADfMGwCAADANwybAAAA8E3YdoCradeuXdqxY4e6u7tVXFys2bNna8SIEbZj\nDduxY8e0fft2tbW1qbu7WwsXLtS4ceNsx7oidXV1amxs1OnTpxUOh1VZWamZM2cqEonYjnZF6uvr\nVV9fr46ODklSSUmJpk+frjFjxlhOZsa2bdu0adMmXX/99Zo9e7btOMOyefNmbd269YLv5ebm6ktf\n+pKlRMnr6urSxo0bdfjwYcViMRUVFemOO+5QWVmZ7WjD9vzzz6uzs/MT36+pqdGcOXMsJLpy8Xhc\nmzdv1v79+9Xd3a3c3FxNnjxZN910kwKBgO14V6S/v1+bN29WY2Ojenp6VFZWptmzZ6u8vNx2tGEb\nynPo5s2btWfPHvX19amiokJz5sxRcXGxncCXcLljOXjwoOrr69XW1qa+vj49+OCDKi0tveo5PzPD\n5v79+/XBBx9ozpw5GjFihOrr6/X666/r4YcfVn5+vu14wxKNRlVWVqbrrrtOK1eutB0nKcePH9fU\nqVNVXl6ueDyuDz/8UCtWrNAjjzyicDj9Hp55eXmaNWuWioqKlEgk1NDQoDfffFMPPPCASkpKbMdL\nSktLi3bv3q3S0tK0fcIsKSnRkiVLBr9O1+OQpL6+Pr388ssaNWqU7r33XuXk5Ojs2bPKzMy0He2K\nPPDAA0okEoNfnzx5UsuXL9eECRMsproydXV12rNnj+bNm6eSkhK1tLRozZo1yszM1PXXX2873hVZ\nu3atTp06pfnz5ys3N1cff/yxli9frocfflh5eXm24w3L5Z5Dt23bpo8++kjz5s1TYWGh6urqtHz5\ncn3hC19QRkaGhcSf7nLHEo1GVVVVpQkTJmjt2rUWEp6Tfs/mV2jHjh267rrrdN1110mSZs+erSNH\njqi+vl4zZ860nG54xowZ48xK2T333HPB1/PmzdOzzz6rtra2tFx1Hjt27AVfz5gxQ/X19WptbU3r\nYXNgYEDvvPOO5s6d+4nVwXQSCASUk5NjO4YR27ZtU0FBge64447B76XbhfPvy87OvuDrQ4cOqaio\nSFVVVZYSXbnW1laNGzdO1dXVks7dL/v27VNra6vlZFcmGo3q4MGDWrRo0eB5+eabb1ZjY6Pq6+s1\nY8YMywmH51LPoYlEQjt37tRNN900uEI4b948Pffcc9q3b5+mTJlyFZNe3uXmgWuvvVaSBl9ts+Uz\n8Z7NWCymtrY2jR49+oLvjx49WidOnLCUChfT19cnScrKyrKcJHnxeFz79u1TLBZLy8H5961bt07V\n1dUaNWqU7ShJOXPmjH7xi1/ohRde0OrVq3X27Fnbka7YoUOHVFZWplWrVum5557Tiy++qD179tiO\nZUQsFtPHH3+syZMn245yRaqrq3X06FGdOXNGktTe3q4TJ04MDp/pJh6PK5FIKBQKXfD9UCik48eP\nW0rlj46ODvX09FwwL4RCIVVVVTEvJOEzsbLZ29urRCLxiRWNnJwcdXd3W0qFP5RIJPTBBx+oqqoq\nJd8bM1QnT57U7373O8ViMYXDYS1YsEBFRUW2Y12xffv2qb29Xffff7/tKEmprKzUnXfeqaKiIvX0\n9Gjr1q16+eWX9fDDD39iVS0ddHR0qL6+XtOmTdP06dPV0tKi999/X8FgUJMmTbIdLymNjY3q7+9P\n2+OoqalRZ2enfv3rXysYDCqRSGjGjBlp+ZYAScrMzFRlZaW2bt2q4uJiZWdna//+/WptbU3rc9vF\neDPBxeaFi72nGEPzmRg2kR7ef/99nTp1SsuWLbMdJSmRSEQPPfSQ+vv7deDAAa1evVpLly5Nyw9t\ndHZ26oMPPtCSJUsuWNX4/ffWpYs/fKmpsrJSL7zwghoaGjRt2jRLqa5cIpFQeXn54EuYpaWlOnXq\nlHbv3p22Q5pn7969qq6uVm5uru0oV+Sjjz7S3r17ddddd6m4uFjt7e1av369cnNz0/a+ufPOO7Vm\nzRr94he/UCAQUHl5uSZMmKC2tjbb0a6adH6Pt22fiWEzOztbgUBAPT09F3y/p6cnbU9mrnn//ffV\n1NSkpUuXpt2bzf9QMBhUYWGhJKmsrEytra2qr6/X3LlzLScbvra2NvX09OjFF18c/F4ikdDx48dV\nX1+vJ598Mm1PwOFwWCUlJWn7Unpubu4nXgGIRCI6ePCgpURmdHR06OjRo1q4cKHtKFesrq5O06dP\nH1zJLCkpUUdHh7Zt25a2w2ZhYaGWLl2qaDSq/v5+5ebm6q233ho817nCmwn+cD7o6elx5v3eNnwm\nhs1QKKTy8nIdOXLkgi0B/vBrXH2JRELvv/++Dh06pKVLl6qgoMB2JOMSiURargRK0qhRo/Twww8P\nfp1IJLRmzRpFIhHV1tam7aApnXtf4OnTp9PyAyiSNGLECJ0+ffqC750+fTqtPyQknVvVzMnJSdv3\nN0rnfk/+8HcjEAik7Xng94XDYYXDYfX19enIkSO69dZbbUcyqqCgQLm5uTpy5MjgFkGxWEzHjh3T\nrFmzLKdLX5+JYVOSbrjhBr3zzjsqLy9XRUWFdu/era6uLtXU1NiONmwDAwODbzyXzq0EtLW1KTs7\nO+2eaN5//33t27dPixYtUjgcHny/TGZmZlpufbRp0yaNGTNG+fn5GhgY0L59+3Ts2DHddNNNtqNd\nkYyMjE+snoXDYWVlZaXd+2o3bNigsWPHKi8vT729vdq6dasGBgbSdqXphhtu0Msvv6y6ujqNHz9e\nra2t2rNnT1quoHu87cImTZqU1hcy48aNU11dnfLz81VcXKy2tjbt3LlzcDeUdHTkyBElEgkVFRXp\n7Nmz2rhxo4qLi9Py9+dyz6HXX3+96urqVFRUNLj1UUZGhiZOnGgx9cVd7lj6+vrU0dEx+Nx6+vRp\nJRIJ5ebmXtVXdgMJFy61hqi+vl7bt29Xd3e3SkpKdNttt6Xlp4Sbm5v12muvSbrwannSpEmaN2+e\nxWTD9+Mf//iiV/zz5s1Ly5PYmjVr1NzcrO7ubmVmZqqkpES1tbVp/ynu3/fqq6+qrKxMt912m+0o\nw7J69WodO3ZMvb29ysnJUUVFhWbMmJG2BQKS1NTUpE2bNunMmTMqLCzUDTfckPYDzeuvv65HHnkk\nrT94MjAwoC1btujgwYPq7u5WXl6eJk6cqOnTpysYTM9NYA4cOKBNmzapq6tLWVlZuuaaazRjxoy0\n3Nd1KM+hW7Zs0e7du1N+U/fLHcvevXu1Zs2aT/z5zTffrJtvvvmq5fxMDZsAAAC4utLzEgsAAABp\ngWETAAAAvknZT2C4siXRSy+9JOncB2Fc8MgjjygQCFywFU46e/DBB5Wfn69du3bZjpK0qVOnSpLK\ny8stJzGjv79fkpzZx6+wsFCBQEBdXV22oyTN257MlVIM7/nmf/7nfywnMePBBx+UZL+i0ARvf9yf\n/OQnlpOY4e3u4doG8Zf7pD4rmwAAAPANwyYAAAB8w7AJAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8\nw7AJAAAA3zBsAgAAwDcMmwAAAPBNIJFIJGyHuJi33nrLdgQjJk+eLEk6e/as5SRmlJaWSpLa29st\nJzGjtLRUoVDIiTaH/Px8SVI4nLLFYJ950WjUiVaXgoICSVJPT4/lJGbk5ORIko4cOWI5iRkjRoyQ\n5EaDUCQSkeTOc05JSYkkaWBgwHIScw4cOKC5c+de8jasbAIAAMA3KbsE8thjj9mOYMQvf/lLSe50\noz/00EOSzne+p7v7779fubm52rp1q+0oSZs+fbqk86vP6S4Wi0lyZ6XWW9XctGmT7ShJmzlzpiRp\n//79lpOY4b0C5Ur/9lNPPSVJ2rhxo+UkyZs/f74k6dVXX7WcxIylS5dKklpbWy0nubpY2QQAAIBv\nGDYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5J2brK119/3XYE\nI2pqaiRJZ86csZzEjIqKCgUCAZ0+fdp2FCMikYiCwSB1lSksHo/bjmBEIBBQPB5Xb2+v7ShJy87O\nliQnjkU6fzxHjx61nMSMiooKSVJfX5/lJMnLy8uT5M4m6F7phkt1lfv27dO8efMueRtWNgEAAOCb\nlF0Cuffee21HMGLFihWSpHfeecdyEjO+9KUvKSsrSytXrrQdxYiFCxcqMzNTW7ZssR0laTfffLMk\nqaSkxHISM7wVTVdWADIyMtTb2+tExeOECRMkuVNX6R3Pz372M8tJzHjiiSckSQcPHrScJHm1tbWS\n3KpIlqSWlhbLSa4uVjYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAA\nAL5h2AQAAIBvGDYBAADgm5TtRl+9erXtCEZMmjRJktTd3W05iRlel3hHR4ftKEYUFBQoEAg40fHs\n9TsHg25dQ7pyPIlEQtFoVF1dXbajJM3rq07Rp49hC4VCktxpdfFaxAKBgOUkyfPum0OHDllOYkZV\nVZXtCMY1NzcPNth9GjfO4gAAAEhJKduN/vjjj9uOYMSzzz4rSdq1a5flJGYsWrRIGRkZ2rhxo+0o\nRsyaNUuZmZk6cOCA7ShJGz9+vCQpKyvLchIzvBWNjIwMy0nMGBgYUFdXl7Zv3247StJuvPFGSe70\n1hcVFUmSli9fbjmJGUuWLJEkhcMp+xQ/ZN5988Mf/tByEjO++c1vSnLnVYGhYmUTAAAAvmHYBAAA\ngG8YNgEAAOAbhk0AAAD4hmETAAAAvmHYBAAAgG8YNgEAAOAbhk0AAAD4JmXrKl9//XXbEYyoqamR\nJJ06dcpyEjMqKysVDAbV3t5uO4oRpaWlCgaDTtSJ5ubmSnJnE3Tv1BSLxSwnMSMYDCqRSKi/v992\nlKRlZmZKkqLRqOUkZnibnx89etRyEjMqKiokyYkaXq8a1ZXnnOLiYklSX1+f5STm7N27V3ffffcl\nb8PKJgAAAHyTsl1W9957r+0IRqxYsUKSOyu1TzzxhDIzM/XKK6/YjmLEsmXLlJeXp/r6ettRkuat\nopeVlVlOYoZXhejC6owkZWdna2BgQMeOHbMdJWlVVVWSpDNnzlhOYoa32vTLX/7SchIzHnvsMUnS\noUOHLCdJ3g033CDJnefQe+65R5J0+PBhy0muLlY2AQAA4BuGTQAAAPiGYRMAAAC+YdgEAACAbxg2\nAQAA4BuGTQAAAPiGYRMAAAC+YdgEAACAb1K2rvKNN96wHcEIb6NtF+oQpXObH8fjcbW0tNiOYkRF\nRYVCoZBOnz5tO0rSIpGIJCkrK8tyEjPi8fgF/013gUBAAwMDTlTXepugu1Il6tVvtra2Wk5iRklJ\niaTzla/pzKvfPXHihOUkZpSWlkpy53dHkpqbm3XLLbdc8jasbAIAAMA3KVtXed9999mOYMRrr70m\nSdq9e7flJGbcc8896uvr0zPPPGM7ihFf/epXlZOTo7ffftt2lKTNnz9fkjR27FjLSczwair7+vos\nJzEjIyNDp06dcuJVm8WLF0uSzp49azmJGaNHj5YkLV++3HISM5YsWSJJikajlpMkr7y8XJKcqkiW\n3Hm1c6hY2QQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAA\nAL6hrtJnXl2lC3WI0rl6x2Aw6MzxRCIRBQIBdXV12Y6StLy8PEnnq/fSnVdT6dKm7pLU399vOUny\nvMeYC5uGS1I4fK7fZP/+/ZaTmOFtUu9CNapX7+jCOVqSCgoKJLlzPJK0ZcsWPfTQQ5e8DSubAAAA\n8A11lT7z6ipXr15tOYkZX/7yl5Wdne1EvaN0ruIxMzNT27Ztsx0labW1tZKkoqIiy0nM6OnpkSS1\ntLRYTmJGRUWFEomEjh07ZjtK0qqqqiS5U1cZiUQkSf/6r/9qOYkZ3/nOdyRJr7/+uuUkyfNWzLZs\n2WI5iRm33367JKmurs5ykquLlU0AAAD4hmETAAAAvmHYBAAAgG8YNgEAAOAbhk0AAAD4hmETAAAA\nvmHYBAAAgG8YNgEAAOAb6ip9Rl1laqOuMnVRV5m6qKtMbdRVpq7Pal1lyjYIeSfmdBcIBCS5dTzx\neFwDAwO2oxgRj8cVCAScGGhycnIkSSl6/XjFQqGQ7QhGBAIBxWKxwWakdOYNZy4MztL5x5h3wZbu\ngsFzL1q6cDzefePKc453fs7NzbWcxBxvUe1SUnbYfPzxx21HMOLZZ5+VJG3evNlyEjOWLVumeDyu\n3/zmN7ajGPHwww8rHA7rrbfesh0laQsWLJB0flUj3XlPLh0dHZaTmFFQUKCOjg59+OGHtqMkbcaM\nGZKkQ4cOWU5ixsSJEyVJv/3tby0nMeOBBx6QJO3bt89ykuTdeOONktx5tXPx4sWSzr9y81nBezYB\nAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADg\nm5TtRn/zzTdtRzBiypQpktzqRg8EAs4cTyQSUSgUUm9vr+0oScvOzpZ0vqrOFa4cTyKRUDQaVXd3\nt+0oSfOq9lyo3pTOV70ePnzYchIzqqqqJLnVje5Kk1hhYaEkOVGR7GloaNBdd911ydu4cRYHAABA\nSkrZbvQHH3zQdgQjXnzxRUnSqlWrLCcx4/HHH1dWVpYzK8+LFi1SXl6eDhw4YDtK0saPHy/p/KqT\nKzIzM21HMKK/v1/d3d2qr6+3HSVpNTU1kqQ9e/ZYTmKG9wrUf//3f1tOYsaf/dmfSXLjFcLPfe5z\nkqQNGzZYTmLG3LlzJUmHDh2ynOTqYmUTAAAAvmHYBAAAgG8YNgEAAOAbhk0AAAD4hmETAAAAvmHY\nBAAAgG8YNgEAAOAbhk0AAAD4JmXrKt9//33bEYwYN26cJKm1tdVuEEMqKyuVlZWleDxuO4oRwWBQ\n8Xhc/f39tqMkzdv83JV6R09XV5ftCEZ4lYgu1NRlZWVJOlfB6YJQKCRJampqspzEjMrKSklyooY3\nPz9fkjvngby8PEnuVFhL0rvvvqunnnrqkrdx61kJAAAAKSVl6yr//u//3nYEI/75n/9ZkvT8889b\nTmLGU089pdGjRzuxEiidWw3s7+/XkSNHbEdJ2ujRoyVJGRkZlpOY4a02NTQ0WE5ixqRJkxQMBp2o\nqRs7dqwkKRqNWk5ihlfx+tOf/tRyEjOefPJJSdLHH39sOUnybrnlFknS9u3bLScxo7a2VtK51cDP\nElY2AQAA4BuGTQAAAPiGYRMAAAC+YdgEAACAbxg2AQAA4BuGTQAAAPiGYRMAAAC+YdgEAACAb1K2\nrnLnzp22IxhRXl4uyZ2qrYKCAoXDYefqKl2odcvOzpZ0fjN0V5w4ccJ2BCOKi4sVDAbV0dFhO0rS\nCgoKJEmxWMxyEjO8IgRXHmulpaWS3Kiu9c5nLhyLdL7i1ZXfHUnq7+/XyJEjL3kbN+49AAAApKSU\nrav81a9+ZTuCEV/84hclSdu2bbOcxIzZs2erqKhIPT09tqMYkZOTo97eXh08eNB2lKRdc801kqS8\nvDzLScxasWKF7QhG3HvvvcrMzNSHH35oO0rSZsyYIUnOnAe8lcCXXnrJchIz7r//fklunAu8KtHM\nzEzLSczwKl5dqXweKlY2AQAA4BuGTQAAAPiGYRMAAAC+YdgEAACAbxg2AQAA4BuGTQAAAPiGYRMA\nAAC+YdgEAACAb1K2rnL37t22IxhRUlIiSeru7racxIz8/HwFg8HBjWnTXTgcViAQsB3DqHA4Zbsa\nhsWrc0vRU9QVicViTmyEnpOTI8mdTd294zl16pTlJGZEIhFJbmwc7tXwuvZYc+G+8Rw+fFizZs26\n5G1Y2QQAAIBvUnYJ5JVXXrEdwYhly5ZJkurr6y0nMWP69OnKzc11ZgWguLhYGRkZisfjtqMkLRg8\nd+1YWFhoOYkZZ8+eleTOCkAwGFRPT4/27t1rO0rSJk+eLElOHIt0/nhWr15tOYkZd911lySpubnZ\ncpLkTZw4UZLU0NBgOYkZkyZNkuTGfTMcrGwCAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADA\nNwybAAAA8A3DJgAAAHzDsAkAAADfUFfpM+oqUxt1lamLusrURV1laqOuMnV9VusqU/ZZqaKiwnYE\nI7xBpri42HISMxKJhOLxuFMDQCKRcOIXPzMzU5LU19dnOYkZoVBIkpy7GHChrcozMDBgO4IR3kDj\nyn3jnZ9dOK9lZWVJcuNYJPeOR5KOHTt22duk7LDpykksIyNDkjurTdFoVAMDA2pra7MdxYiysjIl\nEgm1tLTYjpI07wLNlZNYbm6uJHd+dySpq6tL27Ztsx0jabW1tZKkjRs3Wk5ihrcqs2LFCstJzLj3\n3nslSXV1dZaTJM+7b9avX285iRmzZ8+WJO3cudNykquL92wCAADANwybAAAA8A3DJgAAAHzDsAkA\nAADfMGwCAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADAN3Sj+8zrRu/q6rKcxIyCggKFQqHB\n3up0FwqFlEgknDger94xGHTrGjJFT1FXJBaLOXEuyMvLk+RWu5MknThxwnYEI7x6ZBeqXr3z2qFD\nhywnMaOqqkqSnGit8zzzzDP63ve+d8nbuPWsBAAAgJSSspelr7zyiu0IRixbtkySnOhDls711BYU\nFKijo8N2FCMKCgqUSCScOJ6CggJJ51cC0p1LK5qerq4ubd++3XaMpN14442Szq+gpbt4PC5JeuON\nNywnMWPx4sWSpIyMDMtJkued137wgx9YTmLGt771LUnSs88+aznJ1cXKJgAAAHzDsAkAAADfMGwC\nAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADANwybAAAA8E3K1lXu3LnTdgQjysvLJUlnz561\nnMSMSCTiXEVdIpFQf3+/7RhJy8zMlOROhaC30fbAwIDlJGZ41ag9PT22oyQtJydHkpyoeZXO/840\nNzdbTmKG97zT2dlpOUnyCgsLJUknT560nMQMrwjBlfOaJO3fv1933HHHJW/DyiYAAAB8k7JLIL/6\n1a9sRzA+znKkAAAgAElEQVTii1/8oiTpvffes5zEjAULFqisrMx2DKP6+/udWNEYOXKkpPMrAemu\nu7tbknT69GnLScyIRCLq6+tTQ0OD7ShJmzRpkiQ3Vs4kqaSkRJL0/PPPW05ixqOPPipJ+vDDDy0n\nSd7cuXMlSa+//rrlJGbcc889kqQTJ05YTnJ1sbIJAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8w7AJ\nAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8k7J1lfv377cdwYiCggJJ7lRTZWVlKRAIOHM8GRkZkuRU\nXWUgELCcxKwUPUUNWyAQUDwep64yBXl1la5stF1aWirJjU33vefQ1tZWy0nM8O6btrY2y0nM+dWv\nfqV/+qd/uuRtWNkEAACAb1K2rnL9+vW2Ixgxe/ZsSe5clY0ZM0ahUEjt7e22oxhRWlqqRCLhxIpG\nZWWlpPMrnOnOW6F1aRW9p6fHqbrKrq4uy0nMKC4uliS98sorlpOYsWzZMknStm3bLCdJ3qxZsyRJ\nv/nNbywnMePhhx+W5E4l91CxsgkAAADfMGwCAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADA\nNwybAAAA8A3DJgAAAHxDXaXPqKtMbdRVpr4UPUUNG3WVqYu6ytRFXWXqG0pdZco2CIVCIdsRjPCe\n+L2hJt0FAgEFg0Hl5ubajmJELBZTPB5XMOjOIn88HrcdwQjvPunr67OcxIzMzExnfne885orbVXe\n0Nzb22s5iRneOcCF5x3XHmveea28vNxyEnMee+yxy94mZYfNHTt22I5gxLRp0yS5sXImSZFIRBkZ\nGcrPz7cdxYjOzk719/fr9OnTtqMkLRKJSHLnseatnjU3N1tOYsbIkSOVlZXlxGqgtxiQl5dnOYkZ\nXu3mD3/4Q8tJzPjmN78pSWppabGcJHk1NTWSpHfeecdyEjPuvPNOSVI0GrWc5OpyZzkHAAAAKYdh\nEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgm5Stq2xsbLQdwQhv\n0+MU/WcetlAopGAw6EzDk9cg5MIGu17lniuPNa9pw5VWF69ByIX7x2t18R5z6c7baP/gwYOWk5hR\nVVUlyY2aZK/cwYXiDUkqKiqS5M55WpJOnjypKVOmXPI2KXumOHnypO0IRmRlZUk631CR7goLCxWL\nxZzpqfVad1zqEM7OzracxAxvAHDlwiYQCCgajaqjo8N2lKR5jzVX2qq8WkfvuNKd9zvjXRSkM++i\ns6enx3ISM7zHmAtNYp6hXAik7LD5ox/9yHYEI77xjW9Iknbu3Gk5iRm333674vG4Vq9ebTuKEXfd\ndZdCoZDWr19vO0rSZs+eLUkqKyuznMQM7wLg1KlTlpOYUVxcrM7OTr3//vu2oyTt9ttvl+TORXRF\nRYUkae3atZaTmDF37lxJblwMlJaWSpJ++ctfWk5ihtcj7srvzlDxnk0AAAD4hmETAAAAvmHYBAAA\ngG8YNgEAAOAbhk0AAAD4hmETAAAAvmHYBAAAgG8YNgEAAOAbhk0AAAD4JmW70Xfv3m07ghElJSWS\npPb2dstJzPDaHFzpqY1EIgoEAjp79qztKEkrLCyUdK6D2wXeqenMmTOWk5iRl5cnyY3aPa+vOhqN\nWk5ihvc709bWZjmJGV4NrwuPNe/3xpWKZO85tK+vz3ISc+rr67V48eJL3oaVTQAAAPgmZbvRX3vt\nNdsRjLjvvvskSS+//LLlJGZ87nOfUygU0sqVK21HMWLhwoUKhUJOdCJ7fchVVVWWk5gxMDAgSdq5\nc6flJGbccMMNCgaDqq+vtx0laTU1NZLc6a33utFXrVplOYkZd999tyRpz549lpMk78Ybb5Tk1nOo\nJDU1NVlOcnWxsgkAAADfMGwCAADANwybAAAA8A3DJgAAAHzDsAkAAADfMGwCAADANwybAAAA8A3D\nJgAAAHyTsnWVO3bssB3BCG+zYFcq9yKRiEKhkHp7e21HMSI7O1uBQMCJ2r1w+FxHQyAQsJzErHg8\nbjuCEcFgUIlEYnCz+nSWkZEhSU4ci3T+eI4dO2Y5iRllZWWSpP7+fstJkudVo548edJyEjO8KtHO\nzk7LSczZsGGDHnvssUvehpVNAAAA+CZl6yqfe+452xGM+PKXvyxJTtQhSudq0PLy8rRv3z7bUYyY\nOHGiMjIynKjdKy4ulnRuBc0FoVBIktTT02M5iRk5OTmKRqNqa2uzHSVp3spZe3u75SRmlJaWSpJ+\n/etfW05ixhe+8AVJbqzUTp48WZL01ltvWU5ixoIFCyRJmzdvtpzk6nLjWQkAAAApiWETAAAAvmHY\nBAAAgG8YNgEAAOAbhk0AAAD4hmETAAAAvmHYBAAAgG8YNgEAAOCblK2r3LNnj+0IRngbbafoP/Ow\nZWRkKJFIOFGDJkmZmZkKBoOKxWK2oyTN2wTdlceaV7vpSjVqZmamJDc2qfcqBI8ePWo5iRlerXBr\na6vlJGZ4x7N//37LSZI3btw4SXLiHC2d/905cuSI5STm/OQnP9EPf/jDS96GlU0AAAD4JmXrKpcv\nX247ghFLliyR5M5VWWlpqeLxuDMrGqNGjVJGRoY6OjpsR0laQUGBJHdWNr2V2ubmZstJzBg5cqRi\nsZgTVa8TJ06UJD3zzDOWk5jx1a9+VZL0/PPPW05ixmOPPSZJ+ru/+zvLSZL3L//yL5LkxDlakmpq\naiSdWw38LGFlEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL654k+j9/T0qKOj46Kfsq6q\nqkoqFAAAANww7GGzu7tbb7/99qduRxIIBPTUU08lHQwAAADpb9jD5rp169Te3q5Zs2appKRkcC88\nAAAA4A8Nu67y5z//uWbNmqXrrrvOr0ySqKtMVdRVpi7qKlMbdZWpi7rK1EVdZeobSl3lsFc2A4GA\n8vPzrzjUUHV3d/v+d1wNRUVFkqQzZ85YTmJGcXGxQqGQMwONdG44i8fjtmMkLRg893k/b0hDanLp\n/nHpPCC5czzecbhwYeOdm72LtXTnnae9/7ogOzv7srcZ9rB5zTXXqKmpSaNHj76iUEP1ox/9yNef\nf7V84xvfkCStWbPGchIz7rnnHhUUFOjw4cO2oxgxZswYhcNhnTp1ynaUpHmr6K6cxLyVWldWAEaP\nHq14PO5UXeVPf/pTy0nMePLJJyWde+XOBV/5ylckSV/+8pftBjHgueeek3R+tTbdecfhymNtqIY9\nbE6YMEFr165VIpHQ2LFjLzrRlpWVGQkHAACA9DbsYfO1116TJO3atUu7du36xJ/zaXQAAAB4hj1s\n3nHHHX7kAAAAgIOGPWxOnjzZjxwAAABw0BU3CEnS6dOn1dfXp+zs7MFPXQMAAACeKxo29+/frw0b\nNqirq2vwe/n5+br11ls1fvx4Y+EAAACQ3oY9bDY1Nentt99WcXGxrr/+euXm5qqrq0v79u3T6tWr\nFQ6HVV1d7UdWAAAApJlhD5t1dXUaNWqU7rnnngs2J77xxhv1+uuvq66ujmETAAAAkq6grvJnP/uZ\n5s+fP1gh9fsaGxv19ttv64knnkg62NatW5P+GamgqqpKknsNQn19fbajGJGVlaVAIKBoNGo7StLC\n4XPXji411Eju1VW6cDze/squbLhfWVkpSWppabGcxAxv4/CLbU+YbrwPJWdkZFhOYoZ3HK787kjn\nNqj/j//4j0ve5orqKj+t2i8ejxt7onOlNswzlDqndBAMBhUMBqkOS0He754rFwLeY8yV4dk7Dhd+\nd7xjcaXAwxsAXHusRSIRy0mS5zWJubAgIJ1fFCgtLbWcxJzPf/7zl73NsIfN8vJybd++XdXV1YP/\naNK5B8KOHTuMVUp9//vfN/JzbPv2t78tSc7UO9bW1iovL08dHR22oxhRUFAgSU4cj3csx44ds5zE\nDO9VgebmZstJzBg5cqRCoZBTj7WDBw9aTmLGNddcI8mdCsE/+ZM/kST953/+p+UkyfvLv/xLSVJn\nZ6flJGZ4Va8HDhywnOTqGvawecstt+i1117TCy+8oPHjxw9+QKixsVG9vb267777/MgJAACANDTs\nYXPEiBG69957tWnTJtXX1yuRSCgQCKiiokJ33XWXRowY4UdOAAAApKEr2mdz5MiR+vznP6+BgQH1\n9fUpKyvLmTfvAgAAwJykGoQyMjIYMgEAAPCphjRsNjQ0qLq6WtnZ2WpoaLjs7SdNmpR0MAAAAKS/\nIQ2b7777rj7/+c8rOztb77777mVvz7AJAAAAaYjD5h//8R8rNzd38P8BAACAoRjSsOntqfaH/w8A\nAABcyrBrU1544QW1t7df9M9OnjypF154IelQAAAAcMOwP43e0dGhWCx20T+LRqPG2jG++93vGvk5\ntnlvPxg9erTlJGaEw2HFYjFn6kQTiYQz9ZteRd3YsWMtJzHDOx5Xat3C4bACgYBycnJsR0maV+/q\nyitdXiXil770JctJzCgvL5ck/emf/qnlJMnz9u7u7u62nMQM77nGheccz3e/+13NnTv3krcxWgjd\n0dHBVkgAAAAYNOStj/bu3Tv49bp16z4xlUejUbW3tw/2GSdr165dRn6ObVOnTpUk9fb2Wk5iRiQS\nUWdnpzZu3Gg7ihGzZs1SVlaWEx3PXr9zOJzU9rkpw7tw3bZtm+UkZtTW1iozM1NHjhyxHSVp3is1\nTz/9tOUkZnzta1+TJP34xz+2nMSMr3/965Kkv/7rv7acJHn/9m//JknauXOn5SRm3HXXXZLcefV2\nqIb0rDQwMHDBsNTf3/+Jl9JDoZAmTJigW265xWxCAAAApK0hDZtTp04dXKF7/vnntWDBApWVlfka\nDAAAAOlv2K+3Pfroo37kAAAAgIOSenNXT0/PRT+Znp+fn8yPBQAAgCOuaNjcunWrPvroI/X19Q1u\ngRMIBJRIJBQIBPTUU08ZDQkAAID0NOytj/bs2aNt27bp+uuvVyKR0E033aSbbrpJeXl5Kioquuxe\nSwAAAPjsGPawWV9fr9raWtXW1ko6t93KjBkz9MgjjygjI0M9PT3GQwIAACA9DXvYPHPmjCorKwfb\nPbz3bIbDYU2bNk179uwxmxAAAABpa9jv2QwGg4PvzczMzFRXV9fgn2VnZ1/wdTJKSkqM/BzbvA22\no9Go5SRmJBIJRSIR3XnnnbajGOGVE0ycONFykuR5x+JVCbpi1qxZtiMYkZmZqXg8rsrKSttRkuZt\nuP+3f/u3lpOYkZ2dLcmNekdJqqiokCT99re/tZwked55zautTHeFhYWSpP/6r/+ynMSctWvXXvY2\nw35WKiwsVGdnp6Rz/au7d+9WLBZTPB7Xnj17nOnKBQAAQPKGvbJZXV2t48eP67rrrlNtba1WrFih\nn//85woEAhoYGNAdd9xhJJgrVU7/+I//KElatWqV5SRmPPDAAyopKdGJEydsRzHCW2U6fvy45STJ\n8678c3JyLCcxw9vpoqWlxXISMyoqKtTf3+9EFa9X8tHY2Gg3iCETJkyQJD377LOWk5jx+OOPSzr/\nO5TOvFXaoayepQPvQ9SuHM9QDXvYvPnmmwf/f9SoUfrc5z6n/fv3S5LGjh2rkSNHmksHAACAtJbU\npu7SuasO78oDAAAA+H3Dfs/mypUr1dTU5MTyPAAAAPw17JXNlpYWNTY2Kjc3V9dee60mT56sSCTi\nRzYAAACkuWEPm48++qiOHDmihoYGffTRR9q+fbsqKys1adIkTZgwYXCbAgAAAOCK9tmsrq5WdXW1\n+vr6tG/fPjU0NOi9997TBx98oGuuucaZPRgBAACQnKR2f87KytLUqVN1//33a9myZcrKytK+fftM\nZQMAAECaS+rT6IlEQkePHtXevXvV2NioWCzmRDsGAAAAzAgkruBj5WfOnFFDQ4MaGhrU1dWlvLw8\nXXvttZo0aZKxDwtt2LDByM+xbcyYMZKk06dPW05iRmlpqTIyMtTf3287ihHee4xdOB5X6yp7e3tt\nRzDCq6vs7u62HSVpubm5kqS+vj7LSczw6iqbm5stJzHD247QhV1jvPPaqVOnLCcxw6urPHPmjOUk\n5qxdu1ZPPvnkJW8z7JXNV155RcePH1coFNLYsWM1adIkjRkzRoFA4IqDXjRYOOktQFOC9+9i+t/H\nFu84XBpoEomEEydl7xhcuW/i8fgF/013LjzG/lAoFLIdwQjvvOZ1vqc773hcuIj2ZgFXzmvefZOV\nlWU5iTnV1dWXvc2wJ7qBgQHNnj1bEydOHLwa9IMrJfV//ud/Lkl68803LScx4/7771dpaakzV5nF\nxcWKxWI6fPiw7ShJ81bR8/PzLScxw1s1O3TokOUkZowdO1bRaFT19fW2oyStpqZGknTy5EnLSczw\nql5fffVVy0nMWLp0qSSpqanJcpLkTZkyRZL04YcfWk5ixowZMyRpsHnxs2JYlwrRaFRjxoxRZWWl\nr4MmAAAA3DCsYTMcDmvnzp2KRqN+5QEAAIBDhv0miEgkoo6ODj+yAAAAwDHDHjanT5+urVu36uzZ\ns37kAQAAgEOG/QGhvXv3KhqN6n//939VUlIyuAXG71u8eLGRcAAAAEhvwx42T548qVAopNzcXPX2\n9n5iDzxXtvgBAABA8oY9bD766KN+5AAAAICD3NglFQAAACnpiuoqo9GoGhoa1NzcrL6+Ps2ZM0dF\nRUVqbGxUSUnJYB1TMjZv3pz0z0gFI0eOlORWXWU4HHZm+6twOKxEIuFE04ZX6+ZKC4rXHORCvaN0\nrjEkkUg4cTzee/VdOQ94vzstLS2Wk5hRUlIiyY060ZycHElyZhecgoICSVJPT4/lJObs3btXd999\n9yVvM+yX0Xt7e/Xqq6/q1KlTysnJUU9PjwYGBiRJjY2NOnLkiObMmXNlif/g73GB94Tp/RulO9cq\nBKVz7zN2oR7VtWpUjzcIpLtgMKhYLObU/eNKBadrVa8el87Trt03riwKSFJ5efllbzPsZ9gNGzao\nv79/sLbw6aefHvyzkSNHatu2bcP9kRf1V3/1V0Z+jm3//u//Lkl68cUXLScx4ytf+YoqKip04sQJ\n21GMqKysVCgU0pkzZ2xHSVpRUZGk86sa6c5byXDhvpGkvLw89fT0aO/evbajJG3y5MmSpOPHj1tO\nYsbo0aMluVMrvGjRIknSnj17LCdJ3o033ihJxmYL22prayW582rnUA37UqGpqUk333zzRSfZvLw8\ndXV1GQkGAACA9DfsYXNgYGDwPQd/KB6PO7VsDwAAgOQMe9jMz8//1JdQW1tbFYlEkg4FAAAANwx7\n2Lz22mu1fft2NTY2XvD9lpYW7dy5U9dee62pbAAAAEhzw/6A0I033qgTJ05o5cqVysrKkiStWLFC\nvb29GjNmjK6//nrjIQEAAJCehj1shkIhLV68WPv371dTU5N6enqUnZ2tsWPHasKECU5t6wEAAIDk\nXNHmgoFAQBMnTtTEiRNN5wEAAIBDhj1sRqNRxePxCzZa3r9/v9ra2jRq1KjB/coAAACAYddVrlq1\nShkZGZo3b54k6aOPPtL69evP/bBAQIsWLVJ1dXXSwdatW5f0z0gF48aNkyS1t7fbDWJIRUWFMjMz\nnah3lM6308RiMctJkhcKhSS500zh3SeuVCKGQiHFYjEnauq8CkFXmtG884Ar52lvVxgXHmt5eXmS\n5Mwe3t7xuHJek6QTJ04Mblb/aYa9stna2qqZM2cOfv3RRx9p4sSJmjNnjtasWaMdO3YYGTZdqqiT\n3DoeV+odpXMXSIlEwon9Yb1h04XB+fe5Vono0pOMa1yrSXbpMxSunNe884ArF2rS0JrEhj0x9PT0\nDE7mZ8+e1dmzZzV//nxlZmZq8uTJevfdd4cd9GL+9V//1cjPse073/mOJGnt2rWWk5ixZMkSlZWV\nqbu723YUI3JzcxWLxdTS0mI7StIqKioknb9yTnfeUOZKXWVRUZE6Ozu1adMm21GS5i04nDx50nIS\nM0aOHClJeuaZZywnMeOrX/2qJKm5udlykuTV1NRI0uArqOlu9uzZkqSPP/7YcpKra9j7bIbD4cGX\nUI8fP66MjIzB6spwOOzUtA4AAIDkDHtls6SkRLt27VJBQYHq6+tVVVU1uFTf2dmp3Nxc4yEBAACQ\nnoa9sjl9+nQdO3ZM//d//6f29vYL3hTa1NSk0tJSowEBAACQvoa9sjlq1Cg98sgjam1tVVlZmQoL\nCwf/bOTIkSorKzMaEAAAAOnrij5SXFBQoIKCgk9833sjLwAAACBd4bAZj8d14MABNTc3q7e3V9nZ\n2Ro5cqTGjx8/uNUPAAAAMOxhs7e3VytWrFBbW5uCwaCysrLU29urPXv2aPv27VqyZImys7P9yAoA\nAIA0M+xhc/369Tpz5ozmz58/uJLprXS+9957Wr9+vebPn+9HVgAAAKSZYQ+bTU1NuuWWWzRx4sTB\n7wWDQU2cOFE9PT3avHmz0YAAAABIX8MeNhOJhIqLiy/6Z5/2/SvxD//wD8Z+lk0jRoyQJC1dutRy\nEjMikYjC4fAFuxCku0Ag4MSWXV6FqGvFCl4Pd7oLBoMqKCgYbBBJZ9594koNr3ccTz31lOUkZnjn\nM5PPybZ4j7Xbb7/dchIzvA9Xjx071nISc1599VUtXrz4krcZ9qd5Ro0apaNHj170z44ePTpY+wUA\nAAAMaWWzt7d38P+nT5+uVatWKZFIaOLEicrNzVV3d7c+/vhjNTY26u677zYS7Ec/+pGRn2PbN77x\nDUnSe++9ZzmJGYsWLVJFRYVCoZDtKEbEYjH19fXp8OHDtqMkbcyYMZLcWQn0NDY22o5gxLhx4xSP\nx7V7927bUZI2ZcoUSdKhQ4csJzHjmmuukST95je/sZzEjIcffliSnDiveVsqbtq0yXISM2bOnCnp\n3GrgZ8mQhs1nn332E9/bsWOHduzY8Ynvv/TSS868FAEAAIDkDGnYnD59+pB/oNeTDgAAAAxp2Lzl\nllsu+DqRSAy+tJ6dnc2ACQAAgIsa1qfRT5w4obq6Oh07dkzRaPTcDwiHNXLkSNXW1qqystKXkAAA\nAEhPQx42d+3apfXr10uSysrKBj++39HRoaamJjU1NWn27NmaOnWqP0kBAACQdoY0bJ44cULr16/X\nmDFjNGfOHOXn51/w552dnVq3bp3Wr1+v8vJyVVRU+BIWAAAA6WVI+2zu2LFDFRUVWrhw4ScGTUnK\nz8/XwoULVVFRoe3btxsPCQAAgPQ0pGHz+PHjqqmpUTD46TcPBoOqqanR8ePHjYUDAABAegskEonE\n5W709NNP67777husXvw0x44d0/Lly/W1r30t6WC7du1K+mekAq82rKOjw3ISM4qKihQOhzWEh01a\nCAQCSiQSgx94S2deXaX333QXj8clXVgqkc4yMzMVi8WcOBd479l34fdGOl9X2draajmJGSUlJZLO\n/w6lM+++ceU8kJWVJcmtWuETJ06otrb2krcZ0spmVlbWkE6QXV1dg/+QAAAAwJCWQEaMGKH6+npN\nnDjxU/fUTCQS2rVrl6qqqowEc602bMOGDZaTmDF37lyVlJQ4c1WWkZGhaDSqU6dO2Y6StOLiYklS\nYWGh5SRmdHd3Szp31eyCyspKdXd3D+7qkc5mz54tSWpra7OcxAyv6vWVV16xnMSMZcuWSZL6+vos\nJ0met6ViU1OT5SRmVFdXS3JnFX2ohrSyOW3aNLW0tGjlypXq6ur6xJ93dXVp5cqVamlp0bRp04yH\nBAAAQHoa0spmZWWlbrvtNn3wwQd64YUXVF5efsE+my0tLZKk2267jW2PAAAAMGjInyS4/vrrVVZW\npm3btqm5uXnwpa1wOKwxY8aotrb2sh8gAgAAwGfLsD62OmLECC1evFjxePyCbvRLbYkEAACAz64r\n2iMlGAwqNzfXdBYAAAA4hiVJAAAA+IZhEwAAAL5h2AQAAIBvhlRXaQN1lamJusrURV1laqOuMnVR\nV5m6qKtMfUOpq0zZZyUXGl2kc8OZJMViMctJzEgkEhfsRpDusrOzP7UVK125MgB490tGRoblJGYE\nAgEFAgGFQiHbUZLm3TcuDDMuc+nc5spw5g3PrizYSENrqkrZYfNv/uZvbEcw4v/9v/8nSdq4caPl\nJGYsWbJE+fn5OnjwoO0oRlxzzTXKyMhQe3u77ShJ81bRXRkAvJOyC5V70rkVja6uLm3bts12lKR5\nqxhHjhyxnMSMcePGSXKvrtKFC8/y8nJJ0o4dOywnMcNrWXSlhneoeM8mAAAAfMOwCQAAAN8wbAIA\nAMA3DJsAAADwDcMmAAAAfMOwCQAAAN8wbAIAAMA3DJsAAADwTcrWVa5bt852BCO8zYI7OzvtBjGk\nuLhYoVDIuQYhFzY/dqWm0uNaS00wGFQsFlNXV5ftKEnLy8uT5M6G+9nZ2ZLcq6tM0af3YfEaxFyo\neZXO/+640ogkSYcPH9asWbMueZuUfXbKycmxHcEIr5ouGHRjETkQCCgYDA72u6a7YDCoRCLhxEnZ\n41JFneTOQOP9zrj0WHPlQsC7T1w5T3tceqy5cjHtnZ9dum+GsliTsvfe97//fdsRjPj2t78tyZ26\nygULFqi4uNiZldr8/HzFYjEnVjS8Wjev5tEVTU1NtiMYUV1drf7+fm3evNl2lKTdcsstkqSGhgbL\nScyYMmWKJGnVqlWWk5hx9913S5ITr0BVVFRIklMVyZJ06NAhy0muLrcu4wAAAJBSGDYBAADgG4ZN\nAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5J2brKLVu22I5gxMiRIyW5U7UV\niUQUDocVi8VsRzEiFAopkUg4UR3m1bq51iDU09NjO4IRWVlZSiQSThQi5OfnS3LnvvEa606ePGk5\niRmRSESSGw1PXkmFK481rxrVlWY0SWpsbNTtt99+ydukbIOQV/PoCpeOJxAIDA426S6RSCgejzsx\nPOSFpkgAABgqSURBVLtS5+bxhmbXhucUvb6/Ii4MM7/PteNx4bzm/b50dXVZTmKGi4sCQ3nuSdln\np5/97Ge2IxjxxBNPSJJ27dplOYkZt956q0pLS52pROzv71dfX58TlYjV1dWS5MyFgHeBdvToUctJ\nzBg1apR6e3u1adMm21GSNnPmTEnSjh07LCcxo7a2VpK0fPlyy0nMWLJkiSQ5UcM7fvx4SdKbb75p\nOYkZixYtkiSdPn3acpKri/dsAgAAwDcMmwAAAPANwyYAAAB8w7AJAAAA3zBsAgAAwDcMmwAAAPAN\nwyYAAAB8w7AJAAAA3zBsAgAAwDcp242+detW2xGMqKqqkuROW0BJSYkyMjKcqXULBoPOdaO7Uo3q\nnZqi0ajlJGaEQiHFYjF1d3fbjpK03NxcSe70VXvd6G1tbZaTmFFSUiJJ6ujosJwkeYWFhZKkU6dO\nWU5ihtdbf/bsWctJzHnnnXf09a9//ZK3YWUTAAAAvknZbvQf/OAHtiMY8a1vfUuStHr1astJzLjv\nvvtUXl7u1IpGNBpVe3u77ShJKy0tlSRlZWVZTmKGt6LpwkqgdG41sLu7W/X19bajJK2mpkaStGfP\nHstJzJgyZYok6dVXX7WcxIylS5dKkjZt2mQ5SfJuv/12SdLKlSstJzFj4cKFkqQ1a9ZYTnJ1sbIJ\nAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8w7AJAAAA3zBsAgAAwDcMmwAAAPANwyYAAAB8Q12lz6ir\nTG3UVaYu6ipTF3WVqY26ytT1Wa2rTNkGoc7OTtsRjIjFYpKk/v5+y0nMiMfjSiQSg8eV7gKBgAKB\ngBMDWiAQuOC/6c4bNl26sJHcuX8kKRxO2aeQYfHuExfOA9L543Hh/vGOxRs60513nxQUFFhOYo7X\n8nQpKftI/Iu/+AvbEYz43ve+J0l66aWXLCcx4ytf+YpGjBihkydP2o5iRElJiYLBoBMXN/n5+Rf8\nN915q2auvCoQiUTU19envXv32o6StMmTJ0uSWlpaLCcxY+TIkZKkt956y3ISMxYsWCBJTlSj1tbW\nSnLnPFBZWSlJzjyHDhXv2QQAAIBvGDYBAADgG4ZNAAAA+IZhEwAAAL5h2AQAAIBvGDYBAADgG4ZN\nAAAA+IZhEwAAAL5J2brKtWvX2o5gxPjx4yVJ7e3tlpOYUVFRoczMTGcqBMPhsAKBgBONSF77iSst\nKF5zkCvtW+FwWPF43ImKR6/e0YWaV0nKzMyU5M5G214logvVqHl5eZLcqa31Hmuu/O5I5+abqVOn\nXvI2Kdsg5MoTple15T3A0p1XueeSRCLhRCWid9+k6PXjFXPhvvEEAgEnfodcqkOUzh/P/2/vTn6k\nKts3jl+nhm56squ7oYvxFSWgwWhCJNGdRIizRpyiEmMCO2JiYhziX2DUFRsTF7JU4xAcImgcAk5R\ng0NEMYISBpkbugEbmm666rfoPPSbN78gWM/jfer2+1nX4jpWnXOuc9pweShn0uQUoqdrgYeVN0nq\n7u6W5Ou6dj7fTW6vFE8//bR1hCieeeYZSdLnn39unCSOO+64Q729vRocHLSOEkVPT48kH2+e+/r6\nJEmtra3GSeIIbzK8TCL29/drfHxcO3bssI7SsPAXm9OnTxsniSOUs7Vr1xoniWPlypWSpO3btxsn\nadzixYslSRs3brQNEsmSJUsk+XmLfr6a/xEbAAAAuUXZBAAAQDKUTQAAACRD2QQAAEAylE0AAAAk\nQ9kEAABAMpRNAAAAJEPZBAAAQDK5nav84osvrCNEMXfuXEnS8ePHbYNE0tvbq1Kp5GY6LCygeDie\ncCxe1rfCpWlkZMQ4SRwtLS2q1+sujmfKlCmS/KyghHNmz549xkniqFarknycO52dnZKkoaEh4yRx\nhAUhD/ecYM+ePbrmmmvO+ZncLgh5KWfhB+VhD1mauLnU63U3u67FYlFZlrmadfOmXC5bR4gi/M48\nzFUG4+Pj1hGiCGXT029N8rEmFo7FGy/njtTkc5W33HKLdYQo1q9fL0l6/fXXjZPE8cgjj6i/v1+/\n//67dZQo5s2bp1KppIGBAesoDZs6daokqb293ThJHGEK0cuDWltbm0ZHR128PZszZ44k6fDhw8ZJ\n4ujv75ckrVu3zjhJHMuXL5ckDQ8PGydp3OzZsyVJmzZtMk4Sx3XXXSdJ2r17t3GSf5afR2wAAADk\nDmUTAAAAyVA2AQAAkAxlEwAAAMlQNgEAAJAMZRMAAADJUDYBAACQDGUTAAAAyeR2rnLDhg3WEaJY\nuHChJOnIkSPGSeKYMWOGyuWyixk0aWJ2L8syF4tIYf3E21yll6WNQqGgWq2m0dFR6ygNa2lpkSQX\n5400eTwHDhwwThJHX1+fJB9zouG7GRwcNE4SR5irDKMVHmzbtk1Lly4952dyuyDk5YYZprY8TdRl\nWeZu1s3T9+NNTp+H/zZvx+OJl2nEcBweymZQKuW2rlyQ8N14+a1J5zfzmttv75577rGOEMUbb7wh\nSXr33XeNk8SxatUqzZgxw82b2r6+PmVZpqGhIesoDatUKpIm3tZ6EN6aeZjck6SOjg6Njo5q586d\n1lEaNnfuXEl+3gTOnDlTkvTOO+8YJ4njjjvukORjTnTevHmSpO+//944SRyLFi2SJBeztReC1zkA\nAABIhrIJAACAZCibAAAASIayCQAAgGQomwAAAEiGsgkAAIBkKJsAAABIhrIJAACAZCibAAAASCa3\n2+jvv/++dYQowjb60aNHjZPEUa1WVS6XderUKesoUbS1tSnLMld71V6mXsOlycuGcLlcVr1ed3E8\nra2tkuTivJEmz52DBw8aJ4kjbKN7+H7a2tok+dlGD0tvXjqBJK1fv16PPfbYOT/Dm00AAAAkk9tt\n9LDt2uzC1u769euNk8SxcuVK9fX1adu2bdZRoliwYIFKpZKLNxrValXS5JNzswtvAAcGBoyTxDF1\n6lSNj4+72ESeM2eOJGn//v3GSeII2+ivv/66cZI47r33Xkk+9rfDXwc/+eQT4yRxXH/99ZL8dILz\nxZtNAAAAJEPZBAAAQDKUTQAAACRD2QQAAEAylE0AAAAkQ9kEAABAMpRNAAAAJEPZBAAAQDLMVSbG\nXGW+MVeZX8xV5hdzlfnGXGV+/VvnKnO7INTb22sdIYpSaeI/cThhml2hUFCWZWcvzs0uyzJJE8fl\nhZdjGR8fl+TneDzy8t14uw6E4/EkPOA0u/DdhAcCD+66666//Exuy+Zzzz1nHSGKJ598UpL09ddf\nGyeJ44YbblClUtGRI0eso0QRTngPT809PT2SpO7ubuMkcZw8eVKS3PzWLrroIo2NjbmYEAxzlUND\nQ8ZJ4gjXgffee884SRy33nqrJGnXrl3GSRoX/jq4detW4yRxhOPJ6R+Vk/HxGAcAAIBcomwCAAAg\nGcomAAAAkqFsAgAAIBnKJgAAAJKhbAIAACAZyiYAAACSoWwCAAAgmdzOVX7zzTfWEaKYPXu2JOnE\niRPGSeKoVCoqlUo6c+aMdZQowsKTh+MJx1Iul42TxBEWhMbGxoyTxFEsFt3NVXo4b6TJc+bQoUPG\nSeIIC3wefmthfS+MPDS79vZ26wjRDQ8Pa+7cuef8TG4XhMKNs9mFaSovU1thrtLTrNv4+LiGh4et\nozSsq6tLkr9limPHjllHiKK7u1v1et3Fg2e4Pnu5rgXFYtE6QhThvtPR0WGcpHHhWLw82ITrs6fr\n9MjIyF9+JreN7oUXXrCOEMXq1aslSX/88YdxkjiuuuoqdXR0uLhhShMF7cSJEy7mRK+55hpJk2/T\nm92pU6ckSZs2bTJOEsd1112n8fFxbdiwwTpKw26++WZJ0vTp042TxBFu/B9//LFxkjiWLl0qaWIi\ntdmFt84ertHS5HXay19szpeP11MAAADIJcomAAAAkqFsAgAAIBnKJgAAAJKhbAIAACAZyiYAAACS\noWwCAAAgGcomAAAAksntXOV3331nHSGKGTNmSPIxGyZNLFIUi8WzU4LNLhyLh3+kPiwItbS0GCeJ\no1arSZIGBgaMk8QRFoQGBwetozSsp6dHkp/fWnD48GHrCFFUKhVJPhaRwoKQh/NG8rn0Njg4qMsv\nv/ycn8ntglBYD2l24YY5OjpqnCSO9vZ21et1N9NhhUJBhULBxaxbmBANvzkvPKygSBM3/lqt5mIb\nOfzWvFwHQinz8hAdioyHlZqwIORpIlnyVTbPR27L5tNPP20dIYpnnnlGkvTjjz8aJ4lj6dKl6urq\n0sGDB62jRFGtVlUoFHT06FHrKA3r7e2VJLW1tRkniSPc+L280ejp6dHp06f166+/Wkdp2GWXXSbJ\nz4NNeNh89913jZPEcfvtt0vy8f309fVJkr799lvjJHFcffXVkvz8tfN8+XhUAAAAQC5RNgEAAJAM\nZRMAAADJUDYBAACQDGUTAAAAyVA2AQAAkAxlEwAAAMlQNgEAAJBMbucqv/jiC+sIUcydO1eSNDw8\nbBskkkqlomKx6GYRKczteVhCKZUmNhq8LG0EXn5rpVJJtVrNxTqal+GAICwIeRmrCAMPOb29X5Cw\nIHT8+HHjJHF0dnZK8vEP7gdNPVfp4SSRJo9jZGTEOEkctVpNpVLpbLFpdlmWqV6vn50Q88BL2QwX\nY08X5UKh4GJPPPzGvKyghPPf21ylh3MnHIuX31qYq/WyjCZJ69evb96y+cQTT1hHiOL555+X5GcG\nbcWKFZoxY4aLtzPSxBuaer3u4qk5bIh72HmXJm8uXt42VatVZVmmQ4cOWUdpWH9/vyRp7969xkni\nmDVrliTptddeM04Sx3333SdJLq7T4bvZsGGDcZI4br75ZkkTBe3fxMcrEAAAAOQSZRMAAADJUDYB\nAACQDGUTAAAAyVA2AQAAkAxlEwAAAMlQNgEAAJAMZRMAAADJUDYBAACQTG630b2sBSxcuFCSdOzY\nMeMkcfT396tUKrlYppAmFoSyLNPY2Jh1lIaFDWEvU6Jhas/Dbr00sb/tbRvdw3kj6eyE6IEDB4yT\nxNHX1yfJx7kzZcoUSdLRo0eNk8RRqVQkSaOjo8ZJ4vntt9+0ZMmSc36GN5sAAABIJrevQG699Vbr\nCFG89957kqSNGzfaBolkxYoV6unp0bZt26yjRLFgwQKVy2UdPnzYOkrDpk2bJknq7Ow0ThLHyMiI\nJB/7ztLE28CRkRFt377dOkrD5s+fL0kaGBgwThLH9OnTJUlvvvmmcZI47r77bkk+3gZecsklkqSP\nPvrIOEkcy5YtkyTt27fPOMk/izebAAAASIayCQAAgGQomwAAAEiGsgkAAIBkKJsAAABIhrIJAACA\nZCibAAAASIayCQAAgGSYq0yMucp8Y64yv5irzC/mKvONucr8+rfOVeb2rhROlmYXCkA4YZpdoVBQ\nlmVnj6vZZVmmer3u4qLspWT+Ly+FJssy1Wo1FzeZ1tZWSX5umF7PnePHj1tHaJi3e2iWZZImH3A8\nmDlz5l9+Jrdn2LPPPmsdIYqnnnpKkrR582bjJHEsW7ZMF110kYt5R2li4vHMmTPasWOHdZSGXXrp\npZKkrq4u4yRxhLnKvXv3GieJY9asWTp16pS++uor6ygNu/baayVJv/76q3GSOK644gpJ/uYq33rr\nLeMkjVu+fLkkaffu3cZJ4gh/7QzXt38L/p9NAAAAJEPZBAAAQDKUTQAAACRD2QQAAEAylE0AAAAk\nQ9kEAABAMpRNAAAAJEPZBAAAQDK5nav85ptvrCNEMXv2bEnSn3/+aZwkjkqlomKx6GbVpVwuq16v\nu/gHdsPChpd1pzBX6WHeUZpYDKnVajpx4oR1lIaF4QAv3017e7sk6dChQ8ZJ4ggLfB4mHsOxnD59\n2jhJHGHqNafV628ZGhrSggULzvmZ3C4IeSln4+Pjkvxso3d2dqpYLJ6d3EL+eLqISX7Kc6FQUL1e\nV6HQ/H9QCud/mK1sdh6+k/9PKDbNLHw3Hl4ISJMvBU6ePGmcJJ6tW7c2b9lcuXKldYQo1q5dK0l6\n8cUXjZPE8fjjj+s///mPjhw5Yh0lir6+Po2Njbmaq+zt7TVOEkfY3fZyUW5vb9eff/6p77//3jpK\nwxYtWiTJz3cT3p6tW7fOOEkcYeJx69atxkkat3jxYknSxx9/bJwkjqVLl0ry8d1cCJ+PcwAAAMgF\nyiYAAACSoWwCAAAgGcomAAAAkqFsAgAAIBnKJgAAAJKhbAIAACAZyiYAAACSye1c5SeffGIdIYr5\n8+dLkg4cOGCcJI5Zs2aptbVVZ86csY4SRalUcjdXWSrldqvhgoRLk5ffWrFY1Pj4uIt1tM7OTkmT\nC2nNLqxUeblOh3+k3sOcaPitDQ4OGieJo1KpSPIziCBJP/zwg+68885zfia3d6VisWgdIYow69bS\n0mKcJI5wPDl9RvlbsixzUdDCd+NlSjT8xrz81rwcx3/zdky1Ws06QlRergXS5H59swvzm56+m/O5\nf+b2Drt69WrrCFG88MILkqS3337bOEkcDz/8sKrVqqu5Skk6dOiQcZLG9ff3S5I6OjqMk8Rx+vRp\nSdKxY8eMk8TR3d2t4eFhbd682TpKw8KEoJfvplqtSpJefvll4yRxPPjgg5KknTt32gaJ4Morr5Qk\n7dq1yzhJHPPmzZMkbdmyxTjJP4v/ZxMAAADJUDYBAACQDGUTAAAAyVA2AQAAkAxlEwAAAMlQNgEA\nAJAMZRMAAADJUDYBAACQTG7nKjdt2mQdIYrwD7h6+UfQ+/v71dLSorGxMesoUYSZOg/HE47FwxqS\nNLnm4uG7kSZW0Wq1mqu5Si9TomHhbd++fcZJ4pg2bZokuZjhDSMVYeSh2YVZ4eHhYeMk8WzZskW3\n3XbbOT+T27uSpyknSWpra7OOEEWxWFS9XneziVwqlZRl2dkJMeSPl2tB+J2Fm00zC+dLa2urcZK4\nvFzXwjskL+eO5GPnXZp8sPHyoCad3259bsvmo48+ah0hijVr1kiSfvrpJ+MkcSxbtkwdHR3as2eP\ndZQo5syZo3K57GJ2r7u7W5LU1dVlnCSOcHPx8CZQmngbeObMGRdvz2bOnClp8m16swvl+aWXXjJO\nEseqVaskSfv37zdO0riFCxdKkjZu3GgbJJIlS5ZIkr766ivbIP8wXucAAAAgGcomAAAAkqFsAgAA\nIBnKJgAAAJKhbAIAACAZyiYAAACSoWwCAAAgGcomAAAAkqFsAgAAIJncbqN/+umn1hGiuPTSSyVJ\nJ0+eNE4SR6VSUaFQcLNT29raqizLXMzUFYtFSf620b3MuoWp19HRUesoDQuTe57mECVp9+7d1hGi\nqFarkuTit9be3i5JGhoaMk4SR1h6O3HihHGSeL788ks99NBD5/xMbu9KXspMuGHmtNNfMC/H8b88\nlc3wm/PCS9ksFAqq1+suzqFwDB7KjDRZntva2oyTxOFpuz4ci4drtDR57oTrtQeVSuUvP5PbsvnA\nAw9YR4jilVdekST98ssvxkniuPHGG9XZ2aldu3ZZR4ni4osvVqFQcLVXHd4ENLtQmg8ePGicJI5q\ntap6va49e/ZYR2nYnDlzJEmHDx82ThJHf3+/JOmDDz4wThLHjTfeKMnHw8C0adMkSe+//75xkjhu\nuukmSdL27duNk/yz+H82AQAAkAxlEwAAAMlQNgEAAJAMZRMAAADJUDYBAACQDGUTAAAAyVA2AQAA\nkAxlEwAAAMnkdq7yww8/tI4QxWWXXSZJOnXqlHGSOCqViorFopuFpzBX6eEfPw4rKGFxw4uRkRHr\nCFG0tLS4m6scGxszThJHOJ6BgQHjJHGERZec3t4vSLlcluRnQKCnp0eSn04gSVu2bNHtt99+zs/k\ndkHIw8yW5G9qS5rYQ/YytZVlmbsJQQ/H8t9CEWh2WZapVqu5KGihAJRKub2FXJCw8e7hu5H8XQMk\nP/fQ8N2E35wH53MdyO2V4tFHH7WOEMWaNWskSZ999plxkjiWL1+u3t5eN28Apk6dqlqtpr1791pH\nadisWbMkSVOmTDFOEpeXAlAul3Xy5En9/PPP1lEadsUVV0jyUwC6urokSa+++qpxkjjuv/9+ST5K\nZ5irfPPNN42TxHH33XdLknbv3m2c5J/l6+9tAAAAyBXKJgAAAJKhbAIAACAZyiYAAACSoWwCAAAg\nGcomAAAAkqFsAgAAIBnKJgAAAJKhbAIAACCZ3G6jAwAAoPnxZhMAAADJUDYBAACQDGUTAAAAyVA2\nAQAAkAxlEwAAAMlQNgEAAJAMZRMAAADJUDYBAACQDGUTAAAAyfwfJSwVFOixMg4AAAAASUVORK5C\nYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0xb0ee9d8c>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    "\n",
    "sampleMorePoints = rawData.take(50)\n",
    "# You can uncomment the line below to see randomly selected features.  These will be randomly\n",
    "# selected each time you run the cell.  Note that you should run this cell with the line commented\n",
    "# out when answering the lab quiz questions.\n",
    "# sampleMorePoints = rawData.takeSample(False, 50)\n",
    "\n",
    "parsedSampleMorePoints = map(parsePoint, sampleMorePoints)\n",
    "dataValues = map(lambda lp: lp.features.toArray(), parsedSampleMorePoints)\n",
    "\n",
    "def preparePlot(xticks, yticks, figsize=(10.5, 6), hideLabels=False, gridColor='#999999',\n",
    "                gridWidth=1.0):\n",
    "    \"\"\"Template for generating the plot layout.\"\"\"\n",
    "    plt.close()\n",
    "    fig, ax = plt.subplots(figsize=figsize, facecolor='white', edgecolor='white')\n",
    "    ax.axes.tick_params(labelcolor='#999999', labelsize='10')\n",
    "    for axis, ticks in [(ax.get_xaxis(), xticks), (ax.get_yaxis(), yticks)]:\n",
    "        axis.set_ticks_position('none')\n",
    "        axis.set_ticks(ticks)\n",
    "        axis.label.set_color('#999999')\n",
    "        if hideLabels: axis.set_ticklabels([])\n",
    "    plt.grid(color=gridColor, linewidth=gridWidth, linestyle='-')\n",
    "    map(lambda position: ax.spines[position].set_visible(False), ['bottom', 'top', 'left', 'right'])\n",
    "    return fig, ax\n",
    "\n",
    "# generate layout and plot\n",
    "fig, ax = preparePlot(np.arange(.5, 11, 1), np.arange(.5, 49, 1), figsize=(8,7), hideLabels=True,\n",
    "                      gridColor='#eeeeee', gridWidth=1.1)\n",
    "image = plt.imshow(dataValues,interpolation='nearest', aspect='auto', cmap=cm.Greys)\n",
    "for x, y, s in zip(np.arange(-.125, 12, 1), np.repeat(-.75, 12), [str(x) for x in range(12)]):\n",
    "    plt.text(x, y, s, color='#999999', size='10')\n",
    "plt.text(4.7, -3, 'Feature', color='#999999', size='11'), ax.set_ylabel('Observation')\n",
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(1c) Find the range **\n",
    "#### Now let's examine the labels to find the range of song years.  To do this, first parse each element of the `rawData` RDD, and then find the smallest and largest labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "parsedDataInit = rawData.map(<FILL IN>)\n",
    "onlyLabels = parsedDataInit.map(<FILL IN>)\n",
    "minYear = <FILL IN>\n",
    "maxYear = <FILL IN>\n",
    "print maxYear, minYear"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Find the range (1c)\n",
    "Test.assertEquals(len(parsedDataInit.take(1)[0].features), 12,\n",
    "                  'unexpected number of features in sample point')\n",
    "sumFeatTwo = parsedDataInit.map(lambda lp: lp.features[2]).sum()\n",
    "Test.assertTrue(np.allclose(sumFeatTwo, 3158.96224351), 'parsedDataInit has unexpected values')\n",
    "yearRange = maxYear - minYear\n",
    "Test.assertTrue(yearRange == 89, 'incorrect range for minYear to maxYear')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(1d) Shift labels **\n",
    "#### As we just saw, the labels are years in the 1900s and 2000s.  In learning problems, it is often natural to shift labels such that they start from zero.  Starting with `parsedDataInit`, create a new RDD consisting of `LabeledPoint` objects in which the labels are shifted such that smallest label equals zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "parsedData = parsedDataInit.<FILL IN>\n",
    "\n",
    "# Should be a LabeledPoint\n",
    "print type(parsedData.take(1)[0])\n",
    "# View the first point\n",
    "print '\\n{0}'.format(parsedData.take(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Shift labels (1d)\n",
    "oldSampleFeatures = parsedDataInit.take(1)[0].features\n",
    "newSampleFeatures = parsedData.take(1)[0].features\n",
    "Test.assertTrue(np.allclose(oldSampleFeatures, newSampleFeatures),\n",
    "                'new features do not match old features')\n",
    "sumFeatTwo = parsedData.map(lambda lp: lp.features[2]).sum()\n",
    "Test.assertTrue(np.allclose(sumFeatTwo, 3158.96224351), 'parsedData has unexpected values')\n",
    "minYearNew = parsedData.map(lambda lp: lp.label).min()\n",
    "maxYearNew = parsedData.map(lambda lp: lp.label).max()\n",
    "Test.assertTrue(minYearNew == 0, 'incorrect min year in shifted data')\n",
    "Test.assertTrue(maxYearNew == 89, 'incorrect max year in shifted data')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** Visualization 2: Shifting labels **\n",
    "#### We will look at the labels before and after shifting them.  Both scatter plots below visualize tuples storing i) a label value and ii) the number of training points with this label.  The first scatter plot uses the initial labels, while the second one uses the shifted labels.  Note that the two plots look the same except for the labels on the x-axis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# get data for plot\n",
    "oldData = (parsedDataInit\n",
    "           .map(lambda lp: (lp.label, 1))\n",
    "           .reduceByKey(lambda x, y: x + y)\n",
    "           .collect())\n",
    "x, y = zip(*oldData)\n",
    "\n",
    "# generate layout and plot data\n",
    "fig, ax = preparePlot(np.arange(1920, 2050, 20), np.arange(0, 150, 20))\n",
    "plt.scatter(x, y, s=14**2, c='#d6ebf2', edgecolors='#8cbfd0', alpha=0.75)\n",
    "ax.set_xlabel('Year'), ax.set_ylabel('Count')\n",
    "pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# get data for plot\n",
    "newData = (parsedData\n",
    "           .map(lambda lp: (lp.label, 1))\n",
    "           .reduceByKey(lambda x, y: x + y)\n",
    "           .collect())\n",
    "x, y = zip(*newData)\n",
    "\n",
    "# generate layout and plot data\n",
    "fig, ax = preparePlot(np.arange(0, 120, 20), np.arange(0, 120, 20))\n",
    "plt.scatter(x, y, s=14**2, c='#d6ebf2', edgecolors='#8cbfd0', alpha=0.75)\n",
    "ax.set_xlabel('Year (shifted)'), ax.set_ylabel('Count')\n",
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (1e) Training, validation, and test sets **\n",
    "#### We're almost done parsing our dataset, and our final task involves split it into training, validation and test sets. Use the [randomSplit method](https://spark.apache.org/docs/latest/api/python/pyspark.html#pyspark.RDD.randomSplit) with the specified weights and seed to create RDDs storing each of these datasets. Next, cache each of these RDDs, as we will be accessing them multiple times in the remainder of this lab. Finally, compute the size of each dataset and verify that the sum of their sizes equals the value computed in Part (1a)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "weights = [.8, .1, .1]\n",
    "seed = 42\n",
    "parsedTrainData, parsedValData, parsedTestData = parsedData.<FILL IN>\n",
    "parsedTrainData.<FILL IN>\n",
    "parsedValData.<FILL IN>\n",
    "parsedTestData.<FILL IN>\n",
    "nTrain = parsedTrainData.<FILL IN>\n",
    "nVal = parsedValData.<FILL IN>\n",
    "nTest = parsedTestData.<FILL IN>\n",
    "\n",
    "print nTrain, nVal, nTest, nTrain + nVal + nTest\n",
    "print parsedData.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Training, validation, and test sets (1e)\n",
    "Test.assertEquals(parsedTrainData.getNumPartitions(), numPartitions,\n",
    "                  'parsedTrainData has wrong number of partitions')\n",
    "Test.assertEquals(parsedValData.getNumPartitions(), numPartitions,\n",
    "                  'parsedValData has wrong number of partitions')\n",
    "Test.assertEquals(parsedTestData.getNumPartitions(), numPartitions,\n",
    "                  'parsedTestData has wrong number of partitions')\n",
    "Test.assertEquals(len(parsedTrainData.take(1)[0].features), 12,\n",
    "                  'parsedTrainData has wrong number of features')\n",
    "sumFeatTwo = (parsedTrainData\n",
    "              .map(lambda lp: lp.features[2])\n",
    "              .sum())\n",
    "sumFeatThree = (parsedValData\n",
    "                .map(lambda lp: lp.features[3])\n",
    "                .reduce(lambda x, y: x + y))\n",
    "sumFeatFour = (parsedTestData\n",
    "               .map(lambda lp: lp.features[4])\n",
    "               .reduce(lambda x, y: x + y))\n",
    "Test.assertTrue(np.allclose([sumFeatTwo, sumFeatThree, sumFeatFour],\n",
    "                            2526.87757656, 297.340394298, 184.235876654),\n",
    "                'parsed Train, Val, Test data has unexpected values')\n",
    "Test.assertTrue(nTrain + nVal + nTest == 6724, 'unexpected Train, Val, Test data set size')\n",
    "Test.assertEquals(nTrain, 5371, 'unexpected value for nTrain')\n",
    "Test.assertEquals(nVal, 682, 'unexpected value for nVal')\n",
    "Test.assertEquals(nTest, 671, 'unexpected value for nTest')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ** Part 2: Create and evaluate a baseline model **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(2a) Average label **\n",
    "#### A very simple yet natural baseline model is one where we always make the same prediction independent of the given data point, using the average label in the training set as the constant prediction value.  Compute this value, which is the average (shifted) song year for the training set.  Use an appropriate method in the [RDD API](https://spark.apache.org/docs/latest/api/python/pyspark.html#pyspark.RDD)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "averageTrainYear = (parsedTrainData\n",
    "                    <FILL IN>)\n",
    "print averageTrainYear"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Average label (2a)\n",
    "Test.assertTrue(np.allclose(averageTrainYear, 53.9316700801),\n",
    "                'incorrect value for averageTrainYear')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(2b) Root mean squared error **\n",
    "#### We naturally would like to see how well this naive baseline performs.  We will use root mean squared error ([RMSE](http://en.wikipedia.org/wiki/Root-mean-square_deviation)) for evaluation purposes.  Implement a function to compute RMSE given an RDD of (label, prediction) tuples, and test out this function on an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "def squaredError(label, prediction):\n",
    "    \"\"\"Calculates the the squared error for a single prediction.\n",
    "\n",
    "    Args:\n",
    "        label (float): The correct value for this observation.\n",
    "        prediction (float): The predicted value for this observation.\n",
    "\n",
    "    Returns:\n",
    "        float: The difference between the `label` and `prediction` squared.\n",
    "    \"\"\"\n",
    "    <FILL IN>\n",
    "\n",
    "def calcRMSE(labelsAndPreds):\n",
    "    \"\"\"Calculates the root mean squared error for an `RDD` of (label, prediction) tuples.\n",
    "\n",
    "    Args:\n",
    "        labelsAndPred (RDD of (float, float)): An `RDD` consisting of (label, prediction) tuples.\n",
    "\n",
    "    Returns:\n",
    "        float: The square root of the mean of the squared errors.\n",
    "    \"\"\"\n",
    "    <FILL IN>\n",
    "\n",
    "labelsAndPreds = sc.parallelize([(3., 1.), (1., 2.), (2., 2.)])\n",
    "# RMSE = sqrt[((3-1)^2 + (1-2)^2 + (2-2)^2) / 3] = 1.291\n",
    "exampleRMSE = calcRMSE(labelsAndPreds)\n",
    "print exampleRMSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Root mean squared error (2b)\n",
    "Test.assertTrue(np.allclose(squaredError(3, 1), 4.), 'incorrect definition of squaredError')\n",
    "Test.assertTrue(np.allclose(exampleRMSE, 1.29099444874), 'incorrect value for exampleRMSE')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(2c) Training, validation and test RMSE **\n",
    "#### Now let's calculate the training, validation and test RMSE of our baseline model. To do this, first create RDDs of (label, prediction) tuples for each dataset, and then call calcRMSE. Note that each RMSE can be interpreted as the average prediction error for the given dataset (in terms of number of years)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "labelsAndPredsTrain = parsedTrainData.<FILL IN>\n",
    "rmseTrainBase = <FILL IN>\n",
    "\n",
    "labelsAndPredsVal = parsedValData.<FILL IN>\n",
    "rmseValBase = <FILL IN>\n",
    "\n",
    "labelsAndPredsTest = parsedTestData.<FILL IN>\n",
    "rmseTestBase = <FILL IN>\n",
    "\n",
    "print 'Baseline Train RMSE = {0:.3f}'.format(rmseTrainBase)\n",
    "print 'Baseline Validation RMSE = {0:.3f}'.format(rmseValBase)\n",
    "print 'Baseline Test RMSE = {0:.3f}'.format(rmseTestBase)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Training, validation and test RMSE (2c)\n",
    "Test.assertTrue(np.allclose([rmseTrainBase, rmseValBase, rmseTestBase],\n",
    "                            [21.305869, 21.586452, 22.136957]), 'incorrect RMSE value')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** Visualization 3: Predicted vs. actual **\n",
    "#### We will visualize predictions on the validation dataset. The scatter plots below visualize tuples storing i) the predicted value and ii) true label.  The first scatter plot represents the ideal situation where the predicted value exactly equals the true label, while the second plot uses the baseline predictor (i.e., `averageTrainYear`) for all predicted values.  Further note that the points in the scatter plots are color-coded, ranging from light yellow when the true and predicted values are equal to bright red when they drastically differ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from matplotlib.colors import ListedColormap, Normalize\n",
    "from matplotlib.cm import get_cmap\n",
    "cmap = get_cmap('YlOrRd')\n",
    "norm = Normalize()\n",
    "\n",
    "actual = np.asarray(parsedValData\n",
    "                    .map(lambda lp: lp.label)\n",
    "                    .collect())\n",
    "error = np.asarray(parsedValData\n",
    "                   .map(lambda lp: (lp.label, lp.label))\n",
    "                   .map(lambda (l, p): squaredError(l, p))\n",
    "                   .collect())\n",
    "clrs = cmap(np.asarray(norm(error)))[:,0:3]\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, 100, 20), np.arange(0, 100, 20))\n",
    "plt.scatter(actual, actual, s=14**2, c=clrs, edgecolors='#888888', alpha=0.75, linewidths=0.5)\n",
    "ax.set_xlabel('Predicted'), ax.set_ylabel('Actual')\n",
    "pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "predictions = np.asarray(parsedValData\n",
    "                         .map(lambda lp: averageTrainYear)\n",
    "                         .collect())\n",
    "error = np.asarray(parsedValData\n",
    "                   .map(lambda lp: (lp.label, averageTrainYear))\n",
    "                   .map(lambda (l, p): squaredError(l, p))\n",
    "                   .collect())\n",
    "norm = Normalize()\n",
    "clrs = cmap(np.asarray(norm(error)))[:,0:3]\n",
    "\n",
    "fig, ax = preparePlot(np.arange(53.0, 55.0, 0.5), np.arange(0, 100, 20))\n",
    "ax.set_xlim(53, 55)\n",
    "plt.scatter(predictions, actual, s=14**2, c=clrs, edgecolors='#888888', alpha=0.75, linewidths=0.3)\n",
    "ax.set_xlabel('Predicted'), ax.set_ylabel('Actual')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ** Part 3: Train (via gradient descent) and evaluate a linear regression model **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (3a) Gradient summand **\n",
    "#### Now let's see if we can do better via linear regression, training a model via gradient descent (we'll omit the intercept for now). Recall that the gradient descent update for linear regression is: $$ \\scriptsize \\mathbf{w}_{i+1} = \\mathbf{w}_i - \\alpha_i \\sum_j (\\mathbf{w}_i^\\top\\mathbf{x}_j  - y_j) \\mathbf{x}_j \\,.$$ where $ \\scriptsize i $ is the iteration number of the gradient descent algorithm, and $ \\scriptsize j $ identifies the observation.\n",
    "#### First, implement a function that computes the summand for this update, i.e., the summand equals $ \\scriptsize (\\mathbf{w}^\\top \\mathbf{x} - y) \\mathbf{x} \\, ,$ and test out this function on two examples.  Use the `DenseVector` [dot](http://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.linalg.DenseVector.dot) method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pyspark.mllib.linalg import DenseVector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "def gradientSummand(weights, lp):\n",
    "    \"\"\"Calculates the gradient summand for a given weight and `LabeledPoint`.\n",
    "\n",
    "    Note:\n",
    "        `DenseVector` behaves similarly to a `numpy.ndarray` and they can be used interchangably\n",
    "        within this function.  For example, they both implement the `dot` method.\n",
    "\n",
    "    Args:\n",
    "        weights (DenseVector): An array of model weights (betas).\n",
    "        lp (LabeledPoint): The `LabeledPoint` for a single observation.\n",
    "\n",
    "    Returns:\n",
    "        DenseVector: An array of values the same length as `weights`.  The gradient summand.\n",
    "    \"\"\"\n",
    "    <FILL IN>\n",
    "\n",
    "exampleW = DenseVector([1, 1, 1])\n",
    "exampleLP = LabeledPoint(2.0, [3, 1, 4])\n",
    "# gradientSummand = (dot([1 1 1], [3 1 4]) - 2) * [3 1 4] = (8 - 2) * [3 1 4] = [18 6 24]\n",
    "summandOne = gradientSummand(exampleW, exampleLP)\n",
    "print summandOne\n",
    "\n",
    "exampleW = DenseVector([.24, 1.2, -1.4])\n",
    "exampleLP = LabeledPoint(3.0, [-1.4, 4.2, 2.1])\n",
    "summandTwo = gradientSummand(exampleW, exampleLP)\n",
    "print summandTwo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Gradient summand (3a)\n",
    "Test.assertTrue(np.allclose(summandOne, [18., 6., 24.]), 'incorrect value for summandOne')\n",
    "Test.assertTrue(np.allclose(summandTwo, [1.7304,-5.1912,-2.5956]), 'incorrect value for summandTwo')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (3b) Use weights to make predictions **\n",
    "#### Next, implement a `getLabeledPredictions` function that takes in weights and an observation's `LabeledPoint` and returns a (label, prediction) tuple.  Note that we can predict by computing the dot product between weights and an observation's features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "def getLabeledPrediction(weights, observation):\n",
    "    \"\"\"Calculates predictions and returns a (label, prediction) tuple.\n",
    "\n",
    "    Note:\n",
    "        The labels should remain unchanged as we'll use this information to calculate prediction\n",
    "        error later.\n",
    "\n",
    "    Args:\n",
    "        weights (np.ndarray): An array with one weight for each features in `trainData`.\n",
    "        observation (LabeledPoint): A `LabeledPoint` that contain the correct label and the\n",
    "            features for the data point.\n",
    "\n",
    "    Returns:\n",
    "        tuple: A (label, prediction) tuple.\n",
    "    \"\"\"\n",
    "    return <FILL IN>\n",
    "\n",
    "weights = np.array([1.0, 1.5])\n",
    "predictionExample = sc.parallelize([LabeledPoint(2, np.array([1.0, .5])),\n",
    "                                    LabeledPoint(1.5, np.array([.5, .5]))])\n",
    "labelsAndPredsExample = predictionExample.map(lambda lp: getLabeledPrediction(weights, lp))\n",
    "print labelsAndPredsExample.collect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Use weights to make predictions (3b)\n",
    "Test.assertEquals(labelsAndPredsExample.collect(), [(2.0, 1.75), (1.5, 1.25)],\n",
    "                  'incorrect definition for getLabeledPredictions')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (3c) Gradient descent **\n",
    "#### Next, implement a gradient descent function for linear regression and test out this function on an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "def linregGradientDescent(trainData, numIters):\n",
    "    \"\"\"Calculates the weights and error for a linear regression model trained with gradient descent.\n",
    "\n",
    "    Note:\n",
    "        `DenseVector` behaves similarly to a `numpy.ndarray` and they can be used interchangably\n",
    "        within this function.  For example, they both implement the `dot` method.\n",
    "\n",
    "    Args:\n",
    "        trainData (RDD of LabeledPoint): The labeled data for use in training the model.\n",
    "        numIters (int): The number of iterations of gradient descent to perform.\n",
    "\n",
    "    Returns:\n",
    "        (np.ndarray, np.ndarray): A tuple of (weights, training errors).  Weights will be the\n",
    "            final weights (one weight per feature) for the model, and training errors will contain\n",
    "            an error (RMSE) for each iteration of the algorithm.\n",
    "    \"\"\"\n",
    "    # The length of the training data\n",
    "    n = trainData.count()\n",
    "    # The number of features in the training data\n",
    "    d = len(trainData.take(1)[0].features)\n",
    "    w = np.zeros(d)\n",
    "    alpha = 1.0\n",
    "    # We will compute and store the training error after each iteration\n",
    "    errorTrain = np.zeros(numIters)\n",
    "    for i in range(numIters):\n",
    "        # Use getLabeledPrediction from (3b) with trainData to obtain an RDD of (label, prediction)\n",
    "        # tuples.  Note that the weights all equal 0 for the first iteration, so the predictions will\n",
    "        # have large errors to start.\n",
    "        labelsAndPredsTrain = trainData.<FILL IN>\n",
    "        errorTrain[i] = calcRMSE(labelsAndPredsTrain)\n",
    "\n",
    "        # Calculate the `gradient`.  Make use of the `gradientSummand` function you wrote in (3a).\n",
    "        # Note that `gradient` sould be a `DenseVector` of length `d`.\n",
    "        gradient = <FILL IN>\n",
    "\n",
    "        # Update the weights\n",
    "        alpha_i = alpha / (n * np.sqrt(i+1))\n",
    "        w -= <FILL IN>\n",
    "    return w, errorTrain\n",
    "\n",
    "# create a toy dataset with n = 10, d = 3, and then run 5 iterations of gradient descent\n",
    "# note: the resulting model will not be useful; the goal here is to verify that\n",
    "# linregGradientDescent is working properly\n",
    "exampleN = 10\n",
    "exampleD = 3\n",
    "exampleData = (sc\n",
    "               .parallelize(parsedTrainData.take(exampleN))\n",
    "               .map(lambda lp: LabeledPoint(lp.label, lp.features[0:exampleD])))\n",
    "print exampleData.take(2)\n",
    "exampleNumIters = 5\n",
    "exampleWeights, exampleErrorTrain = linregGradientDescent(exampleData, exampleNumIters)\n",
    "print exampleWeights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Gradient descent (3c)\n",
    "expectedOutput = [48.88110449,  36.01144093, 30.25350092]\n",
    "Test.assertTrue(np.allclose(exampleWeights, expectedOutput), 'value of exampleWeights is incorrect')\n",
    "expectedError = [79.72013547, 30.27835699,  9.27842641,  9.20967856,  9.19446483]\n",
    "Test.assertTrue(np.allclose(exampleErrorTrain, expectedError),\n",
    "                'value of exampleErrorTrain is incorrect')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (3d) Train the model **\n",
    "#### Now let's train a linear regression model on all of our training data and evaluate its accuracy on the validation set.  Note that the test set will not be used here.  If we evaluated the model on the test set, we would bias our final results.\n",
    "#### We've already done much of the required work: we computed the number of features in Part (1b); we created the training and validation datasets and computed their sizes in Part (1e); and, we wrote a function to compute RMSE in Part (2b)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "numIters = 50\n",
    "weightsLR0, errorTrainLR0 = linregGradientDescent(<FILL IN>)\n",
    "\n",
    "labelsAndPreds = parsedValData.<FILL IN>\n",
    "rmseValLR0 = calcRMSE(labelsAndPreds)\n",
    "\n",
    "print 'Validation RMSE:\\n\\tBaseline = {0:.3f}\\n\\tLR0 = {1:.3f}'.format(rmseValBase,\n",
    "                                                                       rmseValLR0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Train the model (3d)\n",
    "expectedOutput = [22.64535883, 20.064699, -0.05341901, 8.2931319, 5.79155768, -4.51008084,\n",
    "                  15.23075467, 3.8465554, 9.91992022, 5.97465933, 11.36849033, 3.86452361]\n",
    "Test.assertTrue(np.allclose(weightsLR0, expectedOutput), 'incorrect value for weightsLR0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** Visualization 4: Training error **\n",
    "#### We will look at the log of the training error as a function of iteration. The first scatter plot visualizes the logarithm of the training error for all 50 iterations.  The second plot shows the training error itself, focusing on the final 44 iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "norm = Normalize()\n",
    "clrs = cmap(np.asarray(norm(np.log(errorTrainLR0))))[:,0:3]\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, 60, 10), np.arange(2, 6, 1))\n",
    "ax.set_ylim(2, 6)\n",
    "plt.scatter(range(0, numIters), np.log(errorTrainLR0), s=14**2, c=clrs, edgecolors='#888888', alpha=0.75)\n",
    "ax.set_xlabel('Iteration'), ax.set_ylabel(r'$\\log_e(errorTrainLR0)$')\n",
    "pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "norm = Normalize()\n",
    "clrs = cmap(np.asarray(norm(errorTrainLR0[6:])))[:,0:3]\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, 60, 10), np.arange(17, 22, 1))\n",
    "ax.set_ylim(17.8, 21.2)\n",
    "plt.scatter(range(0, numIters-6), errorTrainLR0[6:], s=14**2, c=clrs, edgecolors='#888888', alpha=0.75)\n",
    "ax.set_xticklabels(map(str, range(6, 66, 10)))\n",
    "ax.set_xlabel('Iteration'), ax.set_ylabel(r'Training Error')\n",
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ** Part 4: Train using MLlib and perform grid search **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(4a) `LinearRegressionWithSGD` **\n",
    "#### We're already doing better than the baseline model, but let's see if we can do better by adding an intercept, using regularization, and (based on the previous visualization) training for more iterations.  MLlib's [LinearRegressionWithSGD](https://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LinearRegressionWithSGD) essentially implements the same algorithm that we implemented in Part (3b), albeit more efficiently and with various additional functionality, such as stochastic gradient approximation, including an intercept in the model and also allowing L1 or L2 regularization.  First use LinearRegressionWithSGD to train a model with L2 regularization and with an intercept.  This method returns a [LinearRegressionModel](https://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LinearRegressionModel).  Next, use the model's [weights](http://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LinearRegressionModel.weights) and [intercept](http://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LinearRegressionModel.intercept) attributes to print out the model's parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pyspark.mllib.regression import LinearRegressionWithSGD\n",
    "# Values to use when training the linear regression model\n",
    "numIters = 500  # iterations\n",
    "alpha = 1.0  # step\n",
    "miniBatchFrac = 1.0  # miniBatchFraction\n",
    "reg = 1e-1  # regParam\n",
    "regType = 'l2'  # regType\n",
    "useIntercept = True  # intercept"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "firstModel = LinearRegressionWithSGD.<FILL IN>\n",
    "\n",
    "# weightsLR1 stores the model weights; interceptLR1 stores the model intercept\n",
    "weightsLR1 = <FILL IN>\n",
    "interceptLR1 = <FILL IN>\n",
    "print weightsLR1, interceptLR1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST LinearRegressionWithSGD (4a)\n",
    "expectedIntercept = 13.3335907631\n",
    "expectedWeights = [16.682292427, 14.7439059559, -0.0935105608897, 6.22080088829, 4.01454261926, -3.30214858535,\n",
    "                   11.0403027232, 2.67190962854, 7.18925791279, 4.46093254586, 8.14950409475, 2.75135810882]\n",
    "Test.assertTrue(np.allclose(interceptLR1, expectedIntercept), 'incorrect value for interceptLR1')\n",
    "Test.assertTrue(np.allclose(weightsLR1, expectedWeights), 'incorrect value for weightsLR1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **(4b) Predict**\n",
    "#### Now use the [LinearRegressionModel.predict()](http://spark.apache.org/docs/latest/api/python/pyspark.mllib.html#pyspark.mllib.regression.LinearRegressionModel.predict) method to make a prediction on a sample point.  Pass the `features` from a `LabeledPoint` into the `predict()` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "samplePoint = parsedTrainData.take(1)[0]\n",
    "samplePrediction = <FILL IN>\n",
    "print samplePrediction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Predict (4b)\n",
    "Test.assertTrue(np.allclose(samplePrediction, 56.8013380112),\n",
    "                'incorrect value for samplePrediction')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (4c) Evaluate RMSE **\n",
    "#### Next evaluate the accuracy of this model on the validation set.  Use the `predict()` method to create a `labelsAndPreds` RDD, and then use the `calcRMSE()` function from Part (2b)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "labelsAndPreds = <FILL IN>\n",
    "rmseValLR1 = <FILL IN>\n",
    "\n",
    "print ('Validation RMSE:\\n\\tBaseline = {0:.3f}\\n\\tLR0 = {1:.3f}' +\n",
    "       '\\n\\tLR1 = {2:.3f}').format(rmseValBase, rmseValLR0, rmseValLR1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Evaluate RMSE (4c)\n",
    "Test.assertTrue(np.allclose(rmseValLR1, 19.691247), 'incorrect value for rmseValLR1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (4d) Grid search **\n",
    "#### We're already outperforming the baseline on the validation set by almost 2 years on average, but let's see if we can do better. Perform grid search to find a good regularization parameter.  Try `regParam` values `1e-10`, `1e-5`, and `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "bestRMSE = rmseValLR1\n",
    "bestRegParam = reg\n",
    "bestModel = firstModel\n",
    "\n",
    "numIters = 500\n",
    "alpha = 1.0\n",
    "miniBatchFrac = 1.0\n",
    "for reg in <FILL IN>:\n",
    "    model = LinearRegressionWithSGD.train(parsedTrainData, numIters, alpha,\n",
    "                                          miniBatchFrac, regParam=reg,\n",
    "                                          regType='l2', intercept=True)\n",
    "    labelsAndPreds = parsedValData.map(lambda lp: (lp.label, model.predict(lp.features)))\n",
    "    rmseValGrid = calcRMSE(labelsAndPreds)\n",
    "    print rmseValGrid\n",
    "\n",
    "    if rmseValGrid < bestRMSE:\n",
    "        bestRMSE = rmseValGrid\n",
    "        bestRegParam = reg\n",
    "        bestModel = model\n",
    "rmseValLRGrid = bestRMSE\n",
    "\n",
    "print ('Validation RMSE:\\n\\tBaseline = {0:.3f}\\n\\tLR0 = {1:.3f}\\n\\tLR1 = {2:.3f}\\n' +\n",
    "       '\\tLRGrid = {3:.3f}').format(rmseValBase, rmseValLR0, rmseValLR1, rmseValLRGrid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Grid search (4d)\n",
    "Test.assertTrue(np.allclose(17.017170, rmseValLRGrid), 'incorrect value for rmseValLRGrid')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** Visualization 5: Best model's predictions**\n",
    "#### Next, we create a visualization similar to 'Visualization 3: Predicted vs. actual' from Part 2 using the predictions from the best model from Part (4d) on the validation dataset.  Specifically, we create a color-coded scatter plot visualizing tuples storing i) the predicted value from this model and ii) true label."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "predictions = np.asarray(parsedValData\n",
    "                         .map(lambda lp: bestModel.predict(lp.features))\n",
    "                         .collect())\n",
    "actual = np.asarray(parsedValData\n",
    "                    .map(lambda lp: lp.label)\n",
    "                    .collect())\n",
    "error = np.asarray(parsedValData\n",
    "                   .map(lambda lp: (lp.label, bestModel.predict(lp.features)))\n",
    "                   .map(lambda (l, p): squaredError(l, p))\n",
    "                   .collect())\n",
    "\n",
    "norm = Normalize()\n",
    "clrs = cmap(np.asarray(norm(error)))[:,0:3]\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, 120, 20), np.arange(0, 120, 20))\n",
    "ax.set_xlim(15, 82), ax.set_ylim(-5, 105)\n",
    "plt.scatter(predictions, actual, s=14**2, c=clrs, edgecolors='#888888', alpha=0.75, linewidths=.5)\n",
    "ax.set_xlabel('Predicted'), ax.set_ylabel(r'Actual')\n",
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (4e) Vary alpha and the number of iterations **\n",
    "#### In the previous grid search, we set `alpha = 1` for all experiments.  Now let's see what happens when we vary `alpha`.  Specifically, try `1e-5` and `10` as values for `alpha` and also try training models for 500 iterations (as before) but also for 5 iterations. Evaluate all models on the validation set.  Note that if we set `alpha` too small the gradient descent will require a huge number of steps to converge to the solution, and if we use too large of an `alpha` it can cause numerical problems, like you'll see below for `alpha = 10`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "reg = bestRegParam\n",
    "modelRMSEs = []\n",
    "\n",
    "for alpha in <FILL IN>:\n",
    "    for numIters in <FILL IN>:\n",
    "        model = LinearRegressionWithSGD.train(parsedTrainData, numIters, alpha,\n",
    "                                              miniBatchFrac, regParam=reg,\n",
    "                                              regType='l2', intercept=True)\n",
    "        labelsAndPreds = parsedValData.map(lambda lp: (lp.label, model.predict(lp.features)))\n",
    "        rmseVal = calcRMSE(labelsAndPreds)\n",
    "        print 'alpha = {0:.0e}, numIters = {1}, RMSE = {2:.3f}'.format(alpha, numIters, rmseVal)\n",
    "        modelRMSEs.append(rmseVal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Vary alpha and the number of iterations (4e)\n",
    "expectedResults = sorted([56.969705, 56.892949, 355124752.221221])\n",
    "Test.assertTrue(np.allclose(sorted(modelRMSEs)[:3], expectedResults), 'incorrect value for modelRMSEs')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **Visualization 6: Hyperparameter heat map **\n",
    "#### Next, we perform a visualization of hyperparameter search using a larger set of hyperparameters (with precomputed results).  Specifically, we create a heat map where the brighter colors correspond to lower RMSE values.  The first plot has a large area with brighter colors.  In order to differentiate within the bright region, we generate a second plot corresponding to the hyperparameters found within that region."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from matplotlib.colors import LinearSegmentedColormap\n",
    "\n",
    "# Saved parameters and results, to save the time required to run 36 models\n",
    "numItersParams = [10, 50, 100, 250, 500, 1000]\n",
    "regParams = [1e-8, 1e-6, 1e-4, 1e-2, 1e-1, 1]\n",
    "rmseVal = np.array([[  20.36769649,   20.36770128,   20.36818057,   20.41795354,  21.09778437,  301.54258421],\n",
    "                    [  19.04948826,   19.0495    ,   19.05067418,   19.16517726,  19.97967727,   23.80077467],\n",
    "                    [  18.40149024,   18.40150998,   18.40348326,   18.59457491,  19.82155716,   23.80077467],\n",
    "                    [  17.5609346 ,   17.56096749,   17.56425511,   17.88442127,  19.71577117,   23.80077467],\n",
    "                    [  17.0171705 ,   17.01721288,   17.02145207,   17.44510574,  19.69124734,   23.80077467],\n",
    "                    [  16.58074813,   16.58079874,   16.58586512,   17.11466904,  19.6860931 ,   23.80077467]])\n",
    "\n",
    "numRows, numCols = len(numItersParams), len(regParams)\n",
    "rmseVal = np.array(rmseVal)\n",
    "rmseVal.shape = (numRows, numCols)\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, numCols, 1), np.arange(0, numRows, 1), figsize=(8, 7), hideLabels=True,\n",
    "                      gridWidth=0.)\n",
    "ax.set_xticklabels(regParams), ax.set_yticklabels(numItersParams)\n",
    "ax.set_xlabel('Regularization Parameter'), ax.set_ylabel('Number of Iterations')\n",
    "\n",
    "colors = LinearSegmentedColormap.from_list('blue', ['#0022ff', '#000055'], gamma=.2)\n",
    "image = plt.imshow(rmseVal,interpolation='nearest', aspect='auto',\n",
    "                    cmap = colors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Zoom into the bottom left\n",
    "numItersParamsZoom, regParamsZoom = numItersParams[-3:], regParams[:4]\n",
    "rmseValZoom = rmseVal[-3:, :4]\n",
    "\n",
    "numRows, numCols = len(numItersParamsZoom), len(regParamsZoom)\n",
    "\n",
    "fig, ax = preparePlot(np.arange(0, numCols, 1), np.arange(0, numRows, 1), figsize=(8, 7), hideLabels=True,\n",
    "                      gridWidth=0.)\n",
    "ax.set_xticklabels(regParamsZoom), ax.set_yticklabels(numItersParamsZoom)\n",
    "ax.set_xlabel('Regularization Parameter'), ax.set_ylabel('Number of Iterations')\n",
    "\n",
    "colors = LinearSegmentedColormap.from_list('blue', ['#0022ff', '#000055'], gamma=.2)\n",
    "image = plt.imshow(rmseValZoom,interpolation='nearest', aspect='auto',\n",
    "                    cmap = colors)\n",
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ** Part 5: Add interactions between features **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (5a) Add 2-way interactions **\n",
    "#### So far, we've used the features as they were provided.  Now, we will add features that capture the two-way interactions between our existing features.  Write a function `twoWayInteractions` that takes in a `LabeledPoint` and generates a new `LabeledPoint` that contains the old features and the two-way interactions between them.  Note that a dataset with three features would have nine ( $ \\scriptsize 3^2 $ ) two-way interactions.\n",
    "#### You might want to use [itertools.product](https://docs.python.org/2/library/itertools.html#itertools.product) to generate tuples for each of the possible 2-way interactions.  Remember that you can combine two `DenseVector` or `ndarray` objects using [np.hstack](http://docs.scipy.org/doc/numpy/reference/generated/numpy.hstack.html#numpy.hstack)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "import itertools\n",
    "\n",
    "def twoWayInteractions(lp):\n",
    "    \"\"\"Creates a new `LabeledPoint` that includes two-way interactions.\n",
    "\n",
    "    Note:\n",
    "        For features [x, y] the two-way interactions would be [x^2, x*y, y*x, y^2] and these\n",
    "        would be appended to the original [x, y] feature list.\n",
    "\n",
    "    Args:\n",
    "        lp (LabeledPoint): The label and features for this observation.\n",
    "\n",
    "    Returns:\n",
    "        LabeledPoint: The new `LabeledPoint` should have the same label as `lp`.  Its features\n",
    "            should include the features from `lp` followed by the two-way interaction features.\n",
    "    \"\"\"\n",
    "    <FILL IN>\n",
    "\n",
    "print twoWayInteractions(LabeledPoint(0.0, [2, 3]))\n",
    "\n",
    "# Transform the existing train, validation, and test sets to include two-way interactions.\n",
    "trainDataInteract = <FILL IN>\n",
    "valDataInteract = <FILL IN>\n",
    "testDataInteract = <FILL IN>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Add two-way interactions (5a)\n",
    "twoWayExample = twoWayInteractions(LabeledPoint(0.0, [2, 3]))\n",
    "Test.assertTrue(np.allclose(sorted(twoWayExample.features),\n",
    "                            sorted([2.0, 3.0, 4.0, 6.0, 6.0, 9.0])),\n",
    "                'incorrect features generatedBy twoWayInteractions')\n",
    "twoWayPoint = twoWayInteractions(LabeledPoint(1.0, [1, 2, 3]))\n",
    "Test.assertTrue(np.allclose(sorted(twoWayPoint.features),\n",
    "                            sorted([1.0,2.0,3.0,1.0,2.0,3.0,2.0,4.0,6.0,3.0,6.0,9.0])),\n",
    "                'incorrect features generated by twoWayInteractions')\n",
    "Test.assertEquals(twoWayPoint.label, 1.0, 'incorrect label generated by twoWayInteractions')\n",
    "Test.assertTrue(np.allclose(sum(trainDataInteract.take(1)[0].features), 40.821870576035529),\n",
    "                'incorrect features in trainDataInteract')\n",
    "Test.assertTrue(np.allclose(sum(valDataInteract.take(1)[0].features), 45.457719932695696),\n",
    "                'incorrect features in valDataInteract')\n",
    "Test.assertTrue(np.allclose(sum(testDataInteract.take(1)[0].features), 35.109111632783168),\n",
    "                'incorrect features in testDataInteract')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (5b) Build interaction model **\n",
    "#### Now, let's build the new model.  We've done this several times now.  To implement this for the new features, we need to change a few variable names.  Remember that we should build our model from the training data and evaluate it on the validation data.\n",
    "####  Note that you should re-run your hyperparameter search after changing features, as using the best hyperparameters from your prior model will not necessary lead to the best model.  For this exercise, we have already preset the hyperparameters to reasonable values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "numIters = 500\n",
    "alpha = 1.0\n",
    "miniBatchFrac = 1.0\n",
    "reg = 1e-10\n",
    "\n",
    "modelInteract = LinearRegressionWithSGD.train(<FILL IN>, numIters, alpha,\n",
    "                                              miniBatchFrac, regParam=reg,\n",
    "                                              regType='l2', intercept=True)\n",
    "labelsAndPredsInteract = <FILL IN>.map(lambda lp: (lp.label, <FILL IN>.predict(lp.features)))\n",
    "rmseValInteract = calcRMSE(labelsAndPredsInteract)\n",
    "\n",
    "print ('Validation RMSE:\\n\\tBaseline = {0:.3f}\\n\\tLR0 = {1:.3f}\\n\\tLR1 = {2:.3f}\\n\\tLRGrid = ' +\n",
    "       '{3:.3f}\\n\\tLRInteract = {4:.3f}').format(rmseValBase, rmseValLR0, rmseValLR1,\n",
    "                                                 rmseValLRGrid, rmseValInteract)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Build interaction model (5b)\n",
    "Test.assertTrue(np.allclose(rmseValInteract, 15.6894664683), 'incorrect value for rmseValInteract')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ** (5c) Evaluate interaction model on test data **\n",
    "#### Our final step is to evaluate the new model on the test dataset.  Note that we haven't used the test set to evaluate any of our models.  Because of this, our evaluation provides us with an unbiased estimate for how our model will perform on new data.  If we had changed our model based on viewing its performance on the test set, our estimate of RMSE would likely be overly optimistic.\n",
    "#### We'll also print the RMSE for both the baseline model and our new model.  With this information, we can see how much better our model performs than the baseline model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Replace <FILL IN> with appropriate code\n",
    "labelsAndPredsTest = <FILL IN>\n",
    "rmseTestInteract = <FILL IN>\n",
    "\n",
    "print ('Test RMSE:\\n\\tBaseline = {0:.3f}\\n\\tLRInteract = {1:.3f}'\n",
    "       .format(rmseTestBase, rmseTestInteract))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TEST Evaluate interaction model on test data (5c)\n",
    "Test.assertTrue(np.allclose(rmseTestInteract, 16.3272040537),\n",
    "                'incorrect value for rmseTestInteract')"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}