2.5.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LASSO (coordinate descent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start Graphlab Create"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import graphlab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This non-commercial license of GraphLab Create for academic use is assigned to soubhik.dd2015@cs.iiests.ac.in and will expire on August 22, 2017.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[INFO] graphlab.cython.cy_server: GraphLab Create v2.1 started. Logging: C:\\Users\\soubhik\\AppData\\Local\\Temp\\graphlab_server_1487150815.log.0\n"
     ]
    }
   ],
   "source": [
    "sales = graphlab.SFrame('kc_house_data.gl/')\n",
    "# In the dataset, 'floors' was defined with type string, \n",
    "# so we'll convert them to int, before using it below\n",
    "sales['floors'] = sales['floors'].astype(int) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Import useful functions from previous notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_numpy_data(data_sframe, features, output):\n",
    "    data_sframe['constant'] = 1 # this is how you add a constant column to an SFrame\n",
    "    # add the column 'constant' to the front of the features list so that we can extract it along with the others:\n",
    "    features = ['constant'] + features # this is how you combine two lists\n",
    "    # select the columns of data_SFrame given by the features list into the SFrame features_sframe (now including constant):\n",
    "    features_sframe = data_sframe[features]\n",
    "    # the following line will convert the features_SFrame into a numpy matrix:\n",
    "    feature_matrix = features_sframe.to_numpy()\n",
    "    # assign the column of data_sframe associated with the output to the SArray output_sarray\n",
    "    output_sarray = data_sframe[output]\n",
    "    # the following will convert the SArray into a numpy array by first converting it to a list\n",
    "    output_array = output_sarray.to_numpy()\n",
    "    return(feature_matrix, output_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict_output(feature_matrix, weights):\n",
    "    # assume feature_matrix is a numpy matrix containing the features as columns and weights is a corresponding numpy array\n",
    "    # create the predictions vector by using np.dot()\n",
    "    predictions = np.dot(feature_matrix, weights)\n",
    "    return(predictions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Normalize features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Normalize features\n",
    "In the house dataset, features vary wildly in their relative magnitude: `sqft_living` is very large overall compared to `bedrooms`, for instance. As a result, weight for `sqft_living` would be much smaller than weight for `bedrooms`. This is problematic because \"small\" weights are dropped first as `l1_penalty` goes up. \n",
    "\n",
    "To give equal considerations for all features, we need to **normalize features** as discussed in the lectures: we divide each feature by its 2-norm so that the transformed feature has norm 1.\n",
    "\n",
    "Let's see how we can do this normalization easily with Numpy: let us first consider a small matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  3.   5.   8.]\n",
      " [  4.  12.  15.]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[3.,5.,8.],[4.,12.,15.]])\n",
    "print X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Numpy provides a shorthand for computing 2-norms of each column:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  5.  13.  17.]\n"
     ]
    }
   ],
   "source": [
    "norms = np.linalg.norm(X, axis=0) # gives [norm(X[:,0]), norm(X[:,1]), norm(X[:,2])]\n",
    "print norms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To normalize, apply element-wise division:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.6         0.38461538  0.47058824]\n",
      " [ 0.8         0.92307692  0.88235294]]\n"
     ]
    }
   ],
   "source": [
    "print X / norms # gives [X[:,0]/norm(X[:,0]), X[:,1]/norm(X[:,1]), X[:,2]/norm(X[:,2])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the shorthand we just covered, write a short function called `normalize_features(feature_matrix)`, which normalizes columns of a given feature matrix. The function should return a pair `(normalized_features, norms)`, where the second item contains the norms of original features. As discussed in the lectures, we will use these norms to normalize the test data in the same way as we normalized the training data. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def normalize_features(feature_matrix):\n",
    "    norms = np.linalg.norm(feature_matrix, axis=0)\n",
    "    normalized_features = feature_matrix/norms\n",
    "    return (normalized_features, norms)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test the function, run the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.6  0.6  0.6]\n",
      " [ 0.8  0.8  0.8]]\n",
      "[  5.  10.  15.]\n"
     ]
    }
   ],
   "source": [
    "features, norms = normalize_features(np.array([[3.,6.,9.],[4.,8.,12.]]))\n",
    "print features\n",
    "# should print\n",
    "# [[ 0.6  0.6  0.6]\n",
    "#  [ 0.8  0.8  0.8]]\n",
    "print norms\n",
    "# should print\n",
    "# [5.  10.  15.]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementing Coordinate Descent with normalized features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We seek to obtain a sparse set of weights by minimizing the LASSO cost function\n",
    "```\n",
    "SUM[ (prediction - output)^2 ] + lambda*( |w[1]| + ... + |w[k]|).\n",
    "```\n",
    "(By convention, we do not include `w[0]` in the L1 penalty term. We never want to push the intercept to zero.)\n",
    "\n",
    "The absolute value sign makes the cost function non-differentiable, so simple gradient descent is not viable (you would need to implement a method called subgradient descent). Instead, we will use **coordinate descent**: at each iteration, we will fix all weights but weight `i` and find the value of weight `i` that minimizes the objective. That is, we look for\n",
    "```\n",
    "argmin_{w[i]} [ SUM[ (prediction - output)^2 ] + lambda*( |w[1]| + ... + |w[k]|) ]\n",
    "```\n",
    "where all weights other than `w[i]` are held to be constant. We will optimize one `w[i]` at a time, circling through the weights multiple times.  \n",
    "  1. Pick a coordinate `i`\n",
    "  2. Compute `w[i]` that minimizes the cost function `SUM[ (prediction - output)^2 ] + lambda*( |w[1]| + ... + |w[k]|)`\n",
    "  3. Repeat Steps 1 and 2 for all coordinates, multiple times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this notebook, we use **cyclical coordinate descent with normalized features**, where we cycle through coordinates 0 to (d-1) in order, and assume the features were normalized as discussed above. The formula for optimizing each coordinate is as follows:\n",
    "```\n",
    "       ┌ (ro[i] + lambda/2)     if ro[i] < -lambda/2\n",
    "w[i] = ├ 0                      if -lambda/2 <= ro[i] <= lambda/2\n",
    "       └ (ro[i] - lambda/2)     if ro[i] > lambda/2\n",
    "```\n",
    "where\n",
    "```\n",
    "ro[i] = SUM[ [feature_i]*(output - prediction + w[i]*[feature_i]) ].\n",
    "```\n",
    "\n",
    "Note that we do not regularize the weight of the constant feature (intercept) `w[0]`, so, for this weight, the update is simply:\n",
    "```\n",
    "w[0] = ro[i]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Effect of L1 penalty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us consider a simple model with 2 features:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "simple_features = ['sqft_living', 'bedrooms']\n",
    "my_output = 'price'\n",
    "(simple_feature_matrix, output) = get_numpy_data(sales, simple_features, my_output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "simple_feature_matrix, norms = normalize_features(simple_feature_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We assign some random set of initial weights and inspect the values of ro[i]:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "weights = np.array([1., 4., 1.])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use predict_output() to make predictions on this data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prediction = predict_output(simple_feature_matrix, weights)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute the values of `ro[i]` for each feature in this simple model, using the formula given above, using the formula:\n",
    "```\n",
    "ro[i] = SUM[ [feature_i]*(output - prediction + w[i]*[feature_i]) ]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[79400300.034929156, 87939470.772991076, 80966698.675965652]\n"
     ]
    }
   ],
   "source": [
    "ro=[]\n",
    "for i in range(len(weights)):\n",
    "    ro.append((simple_feature_matrix[:,i] * (output - prediction + weights[i]*simple_feature_matrix[:,i])).sum())\n",
    "print ro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Single Coordinate Descent Step"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the formula above, implement coordinate descent that minimizes the cost function over a single feature i. Note that the intercept (weight 0) is not regularized. The function should accept feature matrix, output, current weights, l1 penalty, and index of feature to optimize over. The function should return new weight for feature i."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def lasso_coordinate_descent_step(i, feature_matrix, output, weights, l1_penalty):\n",
    "    # compute prediction\n",
    "    prediction = predict_output(feature_matrix, weights)\n",
    "    # compute ro[i] = SUM[ [feature_i]*(output - prediction + weight[i]*[feature_i]) ]\n",
    "    ro_i = (feature_matrix[:,i] * (output - prediction + weights[i]*feature_matrix[:,i])).sum()\n",
    "\n",
    "    if i == 0: # intercept -- do not regularize\n",
    "        new_weight_i = ro_i \n",
    "    elif ro_i < -l1_penalty/2.:\n",
    "        new_weight_i = ro_i + l1_penalty/2\n",
    "    elif ro_i > l1_penalty/2.:\n",
    "        new_weight_i = ro_i - l1_penalty/2\n",
    "    else:\n",
    "        new_weight_i = 0.\n",
    "    \n",
    "    return new_weight_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.425558846691\n"
     ]
    }
   ],
   "source": [
    "# should print 0.425558846691\n",
    "import math\n",
    "print lasso_coordinate_descent_step(1, np.array([[3./math.sqrt(13),1./math.sqrt(10)],[2./math.sqrt(13),3./math.sqrt(10)]]), \n",
    "                                   np.array([1., 1.]), np.array([1., 4.]), 0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cyclical coordinate descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a function that optimizes the cost function over a single coordinate, let us implement cyclical coordinate descent where we optimize coordinates 0, 1, ..., (d-1) in order and repeat.\n",
    "\n",
    "When do we know to stop? Each time we scan all the coordinates (features) once, we measure the change in weight for each coordinate. If no coordinate changes by more than a specified threshold, we stop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each iteration:\n",
    "1. As you loop over features in order and perform coordinate descent, measure how much each coordinate changes.\n",
    "2. After the loop, if the maximum change across all coordinates is falls below the tolerance, stop. Otherwise, go back to step 1.\n",
    "\n",
    "Return weights\n",
    "\n",
    "**IMPORTANT: when computing a new weight for coordinate i, make sure to incorporate the new weights for coordinates 0, 1, ..., i-1. One good way is to update your weights variable in-place. See following pseudocode for illustration.**\n",
    "```\n",
    "for i in range(len(weights)):\n",
    "    old_weights_i = weights[i] # remember old value of weight[i], as it will be overwritten\n",
    "    # the following line uses new values for weight[0], weight[1], ..., weight[i-1]\n",
    "    #     and old values for weight[i], ..., weight[d-1]\n",
    "    weights[i] = lasso_coordinate_descent_step(i, feature_matrix, output, weights, l1_penalty)\n",
    "    \n",
    "    # use old_weights_i to compute change in coordinate\n",
    "    ...\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def lasso_cyclical_coordinate_descent(feature_matrix, output, initial_weights, l1_penalty, tolerance):\n",
    "    converged = False\n",
    "    weights = np.array(initial_weights.copy())\n",
    "    while not converged:\n",
    "        change = list()\n",
    "        for i in range(len(weights)):\n",
    "            old_weights_i= weights[i]\n",
    "            weights[i] = lasso_coordinate_descent_step(i, feature_matrix, output, weights, l1_penalty)\n",
    "            change_in_weight = abs(old_weights_i - weights[i])\n",
    "            change.append(change_in_weight)\n",
    "        if max(change) < tolerance:\n",
    "            break\n",
    "    return weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the following parameters, learn the weights on the sales dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "simple_features = ['sqft_living', 'bedrooms']\n",
    "my_output = 'price'\n",
    "initial_weights = np.zeros(3)\n",
    "l1_penalty = 1e7\n",
    "tolerance = 1.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First create a normalized version of the feature matrix, normalized_simple_feature_matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(simple_feature_matrix, output) = get_numpy_data(sales, simple_features, my_output)\n",
    "(normalized_simple_feature_matrix, simple_norms) = normalize_features(simple_feature_matrix) # normalize features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, run the implementation of LASSO coordinate descent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS 1.63049248148e+15\n",
      "bedrooms\n"
     ]
    }
   ],
   "source": [
    "def check(weight, l1_penalty):\n",
    "    return 0 if -l1_penalty/2 < weight < l1_penalty/2 else weight\n",
    "\n",
    "weights = lasso_cyclical_coordinate_descent(normalized_simple_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)\n",
    "predictions = predict_output(normalized_simple_feature_matrix, weights)\n",
    "residuals = predictions - output\n",
    "RSS = (residuals**2).sum()\n",
    "print \"RSS\", RSS\n",
    "\n",
    "for i in range(len(weights)):\n",
    "    if i == 0:\n",
    "        pass\n",
    "    n = check(weights[i], l1_penalty)\n",
    "    if n == 0:\n",
    "        print simple_features[i - 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluating LASSO fit with more features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us split the sales dataset into training and test sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_data,test_data = sales.random_split(.8,seed=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "all_features = ['bedrooms',\n",
    "                'bathrooms',\n",
    "                'sqft_living',\n",
    "                'sqft_lot',\n",
    "                'floors',\n",
    "                'waterfront', \n",
    "                'view', \n",
    "                'condition', \n",
    "                'grade',\n",
    "                'sqft_above',\n",
    "                'sqft_basement',\n",
    "                'yr_built', \n",
    "                'yr_renovated']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, create a normalized feature matrix from the TRAINING data with these features. (Make you store the norms for the normalization, since we'll use them later)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(feature_matrix, output) = get_numpy_data(train_data, all_features, my_output)\n",
    "(normalized_feature_matrix, norms) = normalize_features(feature_matrix) # normalize features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, learn the weights with l1_penalty=1e7, on the training data. Initialize weights to all zeros, and set the tolerance=1. Call resulting weights weights1e7, you will need them later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show_nnz_features(w, f):    \n",
    "    for i in range(len(w)):\n",
    "        if i == 0:\n",
    "            continue\n",
    "        weight = w[i]\n",
    "        if weight != 0.:\n",
    "            print f[i - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 24429600.60933314         0.                 0.          48389174.35227978\n",
      "         0.                 0.           3317511.16271982   7329961.9848964\n",
      "         0.                 0.                 0.                 0.\n",
      "         0.                 0.        ]\n",
      "sqft_living\n",
      "waterfront\n",
      "view\n"
     ]
    }
   ],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e7\n",
    "tolerance = 1.0\n",
    "weights1e7 = lasso_cyclical_coordinate_descent(normalized_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)\n",
    "print weights1e7\n",
    "show_nnz_features(weights1e7, all_features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, learn the weights with l1_penalty=1e8, on the training data. Initialize weights to all zeros, and set the tolerance=1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 71114625.75280938         0.                 0.                 0.\n",
      "         0.                 0.                 0.                 0.\n",
      "         0.                 0.                 0.                 0.\n",
      "         0.                 0.        ]\n"
     ]
    }
   ],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e8\n",
    "tolerance = 1.0\n",
    "weights1e8 = lasso_cyclical_coordinate_descent(normalized_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)\n",
    "print weights1e8\n",
    "show_nnz_features(weights1e8, all_features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, learn the weights with l1_penalty=1e4, on the training data. Initialize weights to all zeros, and set the tolerance=5e5. This case will take a bit longer to converge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 77779073.91265225 -22884012.25023361  15348487.08089996\n",
      "  92166869.69883074  -2139328.0824278   -8818455.54409492\n",
      "   6494209.73310655   7065162.05053198   4119079.21006765\n",
      "  18436483.52618776 -14566678.54514342  -5528348.75179426\n",
      " -83591746.20730537   2784276.46012858]\n",
      "bedrooms\n",
      "bathrooms\n",
      "sqft_living\n",
      "sqft_lot\n",
      "floors\n",
      "waterfront\n",
      "view\n",
      "condition\n",
      "grade\n",
      "sqft_above\n",
      "sqft_basement\n",
      "yr_built\n",
      "yr_renovated\n"
     ]
    }
   ],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e4\n",
    "tolerance = 5e5\n",
    "weights1e4 = lasso_cyclical_coordinate_descent(normalized_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)\n",
    "print weights1e4\n",
    "show_nnz_features(weights1e4, all_features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rescaling learned weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that we normalized our feature matrix, before learning the weights.  To use these weights on a test set, we must normalize the test data in the same way.\n",
    "\n",
    "Alternatively, we can rescale the learned weights to include the normalization, so we never have to worry about normalizing the test data: \n",
    "\n",
    "In this case, we must scale the resulting weights so that we can make predictions with *original* features:\n",
    " 1. Store the norms of the original features to a vector called `norms`:\n",
    "```\n",
    "features, norms = normalize_features(features)\n",
    "```\n",
    " 2. Run Lasso on the normalized features and obtain a `weights` vector\n",
    " 3. Compute the weights for the original features by performing element-wise division, i.e.\n",
    "```\n",
    "weights_normalized = weights / norms\n",
    "```\n",
    "Now, we can apply `weights_normalized` to the test data, without normalizing it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a normalized version of each of the weights learned above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "normalized_weights1e4 = weights1e4/norms\n",
    "normalized_weights1e7 = weights1e7/norms\n",
    "normalized_weights1e8 = weights1e8/norms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluating each of the learned models on the test data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now evaluate the three models on the test data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "(test_feature_matrix, test_output) = get_numpy_data(test_data, all_features, 'price')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute the RSS of each of the three normalized weights on the (unnormalized) `test_feature_matrix`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS 2.2778100476e+14\n"
     ]
    }
   ],
   "source": [
    "predictions = predict_output(test_feature_matrix, normalized_weights1e4)\n",
    "residuals = predictions - test_output\n",
    "RSS = (residuals**2).sum()\n",
    "print \"RSS\", RSS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS 2.75962079909e+14\n"
     ]
    }
   ],
   "source": [
    "predictions = predict_output(test_feature_matrix, normalized_weights1e7)\n",
    "residuals = predictions - test_output\n",
    "RSS = (residuals**2).sum()\n",
    "print \"RSS\", RSS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS 5.37166150034e+14\n"
     ]
    }
   ],
   "source": [
    "predictions = predict_output(test_feature_matrix, normalized_weights1e8)\n",
    "residuals = predictions - test_output\n",
    "RSS = (residuals**2).sum()\n",
    "print \"RSS\", RSS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}