lasso-regression-coordinate-descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LASSO (coordinate descent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fire up graphlab create"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import graphlab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load in house sales data\n",
    "\n",
    "Dataset is from house sales in King County, the region where the city of Seattle, WA is located."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[INFO] graphlab.cython.cy_server: GraphLab Create v2.1 started. Logging: C:\\Users\\Nan\\AppData\\Local\\Temp\\graphlab_server_1529606132.log.0\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This non-commercial license of GraphLab Create for academic use is assigned to nanlee_89@yahoo.com and will expire on December 07, 2018.\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": [
    "### Function to convert Sframe into Numpy "
   ]
  },
  {
   "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  # add a constant column to an SFrame\n",
    "    \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 # combine two lists\n",
    "    \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",
    "    \n",
    "    #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",
    "    \n",
    "    # convert the SArray into a numpy array by first converting it to a list\n",
    "    output_array = output_sarray.to_numpy()\n",
    "    \n",
    "    return(feature_matrix, output_array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function to predict output given the feature matrix and the weights"
   ]
  },
  {
   "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": [
    "### Function to normalize the feature matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def normalize_features(feature_matrix):\n",
    "    # function normalizes columns of a given feature matrix \n",
    "    # The function returns a pair (normalized_features, norms), where the second item contains the norms of original features\n",
    "    \n",
    "    norms = np.linalg.norm(feature_matrix, axis=0)\n",
    "    features = feature_matrix/norms\n",
    "    return features, norms"
   ]
  },
  {
   "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. 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": [
    "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": [
    "### First, consider a simple model with 2 features:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "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": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# normalize features:\n",
    "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": 9,
   "metadata": {
    "collapsed": false
   },
   "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": 10,
   "metadata": {
    "collapsed": false
   },
   "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": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[       0 87939470 80966698]\n"
     ]
    }
   ],
   "source": [
    "ro = np.array([0,0,0])\n",
    "ro[1] = np.sum(simple_feature_matrix[:,1] * (output - prediction + weights[1]*simple_feature_matrix[:,1]))\n",
    "ro[2] = np.sum(simple_feature_matrix[:,2] * (output - prediction + weights[2]*simple_feature_matrix[:,2]))\n",
    "\n",
    "print ro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** The range of values of `l1_penalty` ***would not*** set `w[1]` zero, but ***would*** set `w[2]` to zero**\n",
    "\n",
    "Simply calculate the value for lambda that will set w2 to zero\n",
    "\n",
    "i.e. a lambda value that is greater than 2*ro[2]\n",
    "\n",
    "but that is less than the value that will set w1 to zero\n",
    "\n",
    "i.e. a lambda value that is less then 2*ro[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ranges would NOT set w[1] to zero : (-175878940, 175878940)\n",
      "ranges would NOT set w[2] to zero: (-161933396, 161933396)\n",
      "ranges of l1_penalty set w2 zero but NOT set w1 zero: (-175878940, -161933396) (161933396, 175878940)\n"
     ]
    }
   ],
   "source": [
    "print \"ranges would NOT set w[1] to zero :\", (-ro[1]*2, ro[1]*2)\n",
    "print \"ranges would NOT set w[2] to zero:\", (-ro[2]*2, ro[2]*2)\n",
    "\n",
    "print \"ranges of l1_penalty set w2 zero but NOT set w1 zero:\", (-ro[1]*2, -ro[2]*2), (ro[2]*2, ro[1]*2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**The range of values of `l1_penalty` would set **both** `w[1]` and `w[2]` to zero, if we were to take a step in that coordinate\n",
    "**\n",
    "\n",
    "For W[1] to be zero, we need ro[1] in [-lambda/2, lambda/2]\n",
    "\n",
    "We have -lambda/2 <= ro[1] <= lambda/2\n",
    "\n",
    "This translates to lambda <= -2ro[1] and lambda >= 2ro[1]\n",
    "\n",
    "For both conditions to be satisfied, lambda >= 2ro[1] = 1.75e8\n",
    "\n",
    "we are looking for a value that will set both w1 and w0 to zero,\n",
    "\n",
    "i.e. a lambda value that is greater than both 2ro[1] and 2ro[2] (in this case just 2*ro[1] as this is the greater)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we can say that `ro[i]` quantifies the significance of the i-th feature: the larger `ro[i]` is, the more likely it is for the i-th feature to be retained."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Single Coordinate Descent Step"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement coordinate descent that minimizes the cost function over a single feature i by using the formula above. Here the intercept (weight 0) is not regularized. The function accepts feature matrix, output, current weights, l1 penalty, and index of feature to optimize over, and returns new weight for feature i."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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 = np.sum(feature_matrix[:,i] * (output - prediction + weights[i]*feature_matrix[:,i]))\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": "markdown",
   "metadata": {
    "collapsed": true
   },
   "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",
    "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.\n",
    "\n",
    "For each iteration:\n",
    "1. As we 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def lasso_cyclical_coordinate_descent(feature_matrix, output, initial_weights, l1_penalty, tolerance):\n",
    "    \n",
    "    weights = initial_weights\n",
    "    max_coordinate_changes = 0.0\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",
    "        coordinate_changes_i = old_weights_i - weights[i]\n",
    "        if coordinate_changes_i > max_coordinate_changes:\n",
    "            max_coordinate_changes = coordinate_changes_i\n",
    "            # print max_coordinate_changes\n",
    "\n",
    "    \n",
    "    if max_coordinate_changes <= tolerance:\n",
    "        return weights\n",
    "    \n",
    "    else:\n",
    "        lasso_cyclical_coordinate_descent(feature_matrix, output, weights, l1_penalty, tolerance)\n",
    "           \n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Using the following parameters, learn the weights on the sales dataset. **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "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": 16,
   "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 implementation of LASSO coordinate descent:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "weights = lasso_cyclical_coordinate_descent(normalized_simple_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 21624996.11991366,  63157248.84047247,         0.        ])"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lasso_cyclical_coordinate_descent(normalized_simple_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 21624996.11991366  63157248.84047247         0.        ]\n"
     ]
    }
   ],
   "source": [
    "print weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**the RSS of the learned model on the normalized dataset **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS of the learned model on the normalized dataset:1.63049e+15\n"
     ]
    }
   ],
   "source": [
    "predictions = predict_output(normalized_simple_feature_matrix, weights)\n",
    "print \"RSS of the learned model on the normalized dataset:{:.5e}\".format( ((output - predictions)**2).sum())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluating LASSO fit with more features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Split the sales dataset into training and test sets.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_data,test_data = sales.random_split(.8,seed=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Let us consider the following set of features.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "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.  __"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(all_feature_matrix, output) = get_numpy_data(train_data, all_features, my_output)\n",
    "(normalized_all_feature_matrix, all_norms) = normalize_features(all_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`.  __"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e7\n",
    "tolerance = 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "weights1e7 = lasso_cyclical_coordinate_descent(normalized_all_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 24429599.89016737         0.                 0.          48389175.02950662\n",
      "         0.                 0.           3317511.16366192\n",
      "   7329961.94051543         0.                 0.                 0.\n",
      "         0.                 0.                 0.        ]\n"
     ]
    }
   ],
   "source": [
    "print weights1e7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** Features had non-zero weight in this case ***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "feature_list = ['constant'] + all_features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "constant 24429599.8902\n",
      "sqft_living 48389175.0295\n",
      "waterfront 3317511.16366\n",
      "view 7329961.94052\n"
     ]
    }
   ],
   "source": [
    "for k,v in zip(feature_list, weights1e7):\n",
    "    if v != 0.0:\n",
    "        print k, v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "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": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e8\n",
    "tolerance = 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "weights1e8 = lasso_cyclical_coordinate_descent(normalized_all_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Features had non-zero weight in this case***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "constant 71114625.7528\n"
     ]
    }
   ],
   "source": [
    "for k,v in zip(feature_list, weights1e8):\n",
    "    if v != 0.0:\n",
    "        print k, v"
   ]
  },
  {
   "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`.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "initial_weights = np.zeros(14)\n",
    "l1_penalty = 1e4\n",
    "tolerance = 5e5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "weights1e4 = lasso_cyclical_coordinate_descent(normalized_all_feature_matrix, output,\n",
    "                                            initial_weights, l1_penalty, tolerance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** Features had non-zero weight in this case***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 76259298.99182403, -22370834.16840227,  18573078.36061361,\n",
       "        81736690.36290801,  -2145049.58385188, -10188516.60493549,\n",
       "         6492635.81786232,   7189407.99249122,   1319350.29358088,\n",
       "        12362479.75987415,  -5610729.08012918,  -3371915.78488671,\n",
       "       -75364444.70568328,   2730228.52966835])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights1e4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "constant 76259298.9918\n",
      "bedrooms -22370834.1684\n",
      "bathrooms 18573078.3606\n",
      "sqft_living 81736690.3629\n",
      "sqft_lot -2145049.58385\n",
      "floors -10188516.6049\n",
      "waterfront 6492635.81786\n",
      "view 7189407.99249\n",
      "condition 1319350.29358\n",
      "grade 12362479.7599\n",
      "sqft_above -5610729.08013\n",
      "sqft_basement -3371915.78489\n",
      "yr_built -75364444.7057\n",
      "yr_renovated 2730228.52967\n"
     ]
    }
   ],
   "source": [
    "for k,v in zip(feature_list, weights1e4):\n",
    "    if v != 0.0:\n",
    "        print k, v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rescaling learned weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a normalized version of each of the weights learned above. (`weights1e4`, `weights1e7`, `weights1e8`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "my_output = 'price'\n",
    "(feature_matrix, output) = get_numpy_data(train_data, all_features, my_output)\n",
    "normalized_feature_matrix, norms = normalize_features(feature_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "161.317458506\n"
     ]
    }
   ],
   "source": [
    "normalized_weights1e7 = weights1e7 / norms\n",
    "normalized_weights1e8 = weights1e8 / norms\n",
    "normalized_weights1e4 = weights1e4 / norms\n",
    "print normalized_weights1e7[3]"
   ]
  },
  {
   "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": 49,
   "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": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS for model with weights1e4 is 2.31426e+14\n"
     ]
    }
   ],
   "source": [
    "prediction = predict_output(test_feature_matrix, normalized_weights1e4)\n",
    "rss = ((test_output - prediction)**2).sum()\n",
    "print 'RSS for model with weights1e4 is {:.5e}'.format(rss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS for model with weights1e7 is 2.75962e+14\n"
     ]
    }
   ],
   "source": [
    "prediction = predict_output(test_feature_matrix, normalized_weights1e7)\n",
    "rss = ((test_output - prediction)**2).sum()\n",
    "print 'RSS for model with weights1e7 is {:.5e}'.format(rss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RSS for model with weights1e8 is 5.37166e+14\n"
     ]
    }
   ],
   "source": [
    "prediction = predict_output(test_feature_matrix, normalized_weights1e8)\n",
    "rss = ((test_output - prediction)**2).sum()\n",
    "print 'RSS for model with weights1e8 is {:.5e}'.format(rss)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** By comparing the rss on test data of learned models, model with `l1_penalty = 1e4` performed best on the test data**"
   ]
  },
  {
   "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}