P556_Assignment1_S19_Vijaya_Krishna.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "woZuGLfokoCx"
   },
   "source": [
    "# CSCI-P556\n",
    "# Assignment 1\n",
    "# Due date: Friday, February 15, 11:59PM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "5d1GxwAzsRfB"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sklearn as sk\n",
    "import time\n",
    "\n",
    "diab = pd.read_csv(\"diabetes.txt\", delim_whitespace = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mCxVSEY_ku5i"
   },
   "source": [
    "## Question 1 (10 points)\n",
    "\n",
    "Implement linear regression using ordinary least squares (closed-form solution)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DQevk_umkdh3"
   },
   "outputs": [],
   "source": [
    "def linear_regression_ols(X, y):\n",
    "  # Make sure that you return the weights in a np.array, \n",
    "  # other data types will cause our grading script to crash\n",
    "    X_transpose = X.T\n",
    "    temp = np.dot(X_transpose, X)\n",
    "    temp = np.linalg.inv(temp)\n",
    "    temp = np.dot(temp, X_transpose)\n",
    "    ols = np.dot(temp, y)\n",
    "    return ols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "R_CofGkGmgR6"
   },
   "source": [
    "## Question 2 (40 points)\n",
    "\n",
    "Implement linear regression using gradient descent. A boolean parameter named *regularization* has been included in the function definition. If regularization=True, then the linear regression will be computed using L2 regularization.\n",
    "\n",
    "![L2 regularization](https://cdn-images-1.medium.com/max/1200/1*jgWOhDiGjVp-NCSPa5abmg.png)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lCS581-dm3PV"
   },
   "outputs": [],
   "source": [
    "def linear_regression_gd(X, y, theta, \\\n",
    "                         learning_rate, \\\n",
    "                         num_iters, \\\n",
    "                         regularization=False):\n",
    "  # Make sure that you return the weights in a np.array, \n",
    "  # other data types will cause our grading script to crash\n",
    "    lamda = 3\n",
    "    iterations = 0\n",
    "    while iterations<num_iters:\n",
    "        h_theta = np.dot(X, theta) \n",
    "        if regularization == True:\n",
    "            loss = np.square(h_theta - y)\n",
    "            gradient = np.dot((h_theta - y).T,X)/(X.shape[0])\n",
    "            reg_factor = 1 - ((learning_rate * lamda)/X.shape[0])\n",
    "            theta = (theta * reg_factor) - (learning_rate * gradient.T)\n",
    "        elif regularization == False:\n",
    "            loss = np.square(h_theta - y)\n",
    "            gradient = np.dot((h_theta - y).T,X)/(X.shape[0])\n",
    "            theta = theta - (learning_rate * gradient.T)\n",
    "        iterations = iterations + 1\n",
    "    return theta\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "VV6PVnE0n4eb"
   },
   "source": [
    "## Question 3 (20 points)\n",
    "\n",
    "- Apply your linear regression OLS, gradient descent without regularization, and gradient descent with regularization functions to [Sci-Kit Learn's diabetes dataset](https://www.programcreek.com/python/example/85913/sklearn.datasets.load_diabetes). Additionally, apply [Sci-Kit Learn's Linear Regression model](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LinearRegression.html)\n",
    "- Calculate the amount of time it took for each of the functions to execute with the code that we have included."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "mFVwHrYfpKbI"
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_diabetes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "zlwnxRsarM0M"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linear Regression using OLS:  [[-3.34567139e+02]\n",
      " [-3.63612242e-02]\n",
      " [-2.28596481e+01]\n",
      " [ 5.60296209e+00]\n",
      " [ 1.11680799e+00]\n",
      " [-1.08999633e+00]\n",
      " [ 7.46450456e-01]\n",
      " [ 3.72004715e-01]\n",
      " [ 6.53383194e+00]\n",
      " [ 6.84831250e+01]\n",
      " [ 2.80116989e-01]]\n",
      "Total execution time for OLS: 0.015625\n",
      "Linear Regression using Gradient Descent without regularization:  [[-6.24569101e+00]\n",
      " [ 1.71076672e-02]\n",
      " [-2.37808723e+01]\n",
      " [ 5.49302209e+00]\n",
      " [ 1.02567573e+00]\n",
      " [ 1.33546739e+00]\n",
      " [-1.36701744e+00]\n",
      " [-3.02589875e+00]\n",
      " [-4.71242711e+00]\n",
      " [ 2.52093522e+00]\n",
      " [ 1.56491118e-01]]\n",
      "Total execution time for gradient descent without regularization: 71.3125\n",
      "Linear Regression using Gradient Descent with regularization:  [[-6.00137266e+00]\n",
      " [ 1.50867474e-02]\n",
      " [-2.31815840e+01]\n",
      " [ 5.49706904e+00]\n",
      " [ 1.02049071e+00]\n",
      " [ 1.34227351e+00]\n",
      " [-1.37505862e+00]\n",
      " [-3.02479745e+00]\n",
      " [-4.67409381e+00]\n",
      " [ 2.35663528e+00]\n",
      " [ 1.51620552e-01]]\n",
      "Total execution time for gradient descent with regularization: 79.15625\n",
      "Linear Regression using sklearn:  [[ 0.00000000e+00 -3.63612242e-02 -2.28596481e+01  5.60296209e+00\n",
      "   1.11680799e+00 -1.08999633e+00  7.46450456e-01  3.72004715e-01\n",
      "   6.53383194e+00  6.84831250e+01  2.80116989e-01]]\n",
      "Total execution time for Sci-Kit Learn's Linear Regression: 0.21875\n"
     ]
    }
   ],
   "source": [
    "# load variables in this area\n",
    "y = (diab['Y'])\n",
    "y = np.array(y)\n",
    "y = np.reshape(y, (442,1))\n",
    "diab = np.matrix(diab)\n",
    "X = np.delete(diab, 10,axis = 1) #delete target variable and load  to a new variable X\n",
    "X = np.insert(X, 0, np.array([1]).T, axis = 1) #insert bias term\n",
    "original_x = X\n",
    "theta = np.array([0.0] * 11)\n",
    "theta = np.reshape(theta, (11,1))\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do OLS here\n",
    "print(\"Linear Regression using OLS: \",linear_regression_ols(X,y))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for OLS: \" + str(end_time-start_time))\n",
    "\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do GD without regularization here\n",
    "print(\"Linear Regression using Gradient Descent without regularization: \",linear_regression_gd(X, y,theta, learning_rate = 0.000026, num_iters = 500000, regularization = False))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for gradient descent without regularization: \" + str(end_time-start_time))\n",
    "\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do GD with regularization here\n",
    "print(\"Linear Regression using Gradient Descent with regularization: \",linear_regression_gd(X, y,theta, learning_rate = 0.000026, num_iters = 500000, regularization = True))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for gradient descent with regularization: \" + str(end_time-start_time))\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do SK's linear regression here\n",
    "from sklearn import linear_model\n",
    "l_regr = linear_model.LinearRegression()\n",
    "l_regr.fit(X,y)\n",
    "print(\"Linear Regression using sklearn: \",l_regr.coef_)\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for Sci-Kit Learn's Linear Regression: \" + str(end_time-start_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "J7p2lIOzc5T-"
   },
   "source": [
    "## Question 4 (20 points)\n",
    "\n",
    "Normalize the appropriate variables in the dataset and re-do Question 3 using this dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ON8HYSCjc2Hv"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\vjkri\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:6: RuntimeWarning: invalid value encountered in true_divide\n",
      "  \n"
     ]
    }
   ],
   "source": [
    "# Normalize variables here\n",
    "mu = np.zeros(X.shape[1])\n",
    "sigma = np.zeros(X.shape[1])\n",
    "mu = np.mean(X, axis = 0)\n",
    "sigma = np.std(X, axis = 0)\n",
    "X = (X - mu)/sigma\n",
    "X = np.delete(X, 0, axis = 1)\n",
    "X = np.insert(X, 0, np.array([1]).T, axis = 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "QfN0z1ZjdcHk"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linear Regression using OLS:  [[152.13348416]\n",
      " [ -0.47612079]\n",
      " [-11.40686692]\n",
      " [ 24.72654886]\n",
      " [ 15.42940413]\n",
      " [-37.67995261]\n",
      " [ 22.67616277]\n",
      " [  4.80613814]\n",
      " [  8.42203936]\n",
      " [ 35.73444577]\n",
      " [  3.21667372]]\n",
      "Total execution time for OLS: 0.0\n",
      "Linear Regression using Gradient Descent without regularization:  [[152.13348416]\n",
      " [ -0.47612079]\n",
      " [-11.40686692]\n",
      " [ 24.72654886]\n",
      " [ 15.42940413]\n",
      " [-37.67995261]\n",
      " [ 22.67616277]\n",
      " [  4.80613814]\n",
      " [  8.42203936]\n",
      " [ 35.73444577]\n",
      " [  3.21667372]]\n",
      "Total execution time for gradient descent without regularization: 15.90625\n",
      "Linear Regression using Gradient Descent with regularization:  [[151.10786517]\n",
      " [ -0.37238047]\n",
      " [-11.22224526]\n",
      " [ 24.78272579]\n",
      " [ 15.29197839]\n",
      " [-21.61503683]\n",
      " [  9.93607156]\n",
      " [ -2.23138687]\n",
      " [  6.5650626 ]\n",
      " [ 29.56618188]\n",
      " [  3.34055771]]\n",
      "Total execution time for gradient descent with regularization: 15.90625\n",
      "Linear Regression using sklearn:  [[  0.          -0.47612079 -11.40686692  24.72654886  15.42940413\n",
      "  -37.67995261  22.67616277   4.80613814   8.42203936  35.73444577\n",
      "    3.21667372]]\n",
      "Total execution time for Sci-Kit Learn's Linear Regression: 0.0\n"
     ]
    }
   ],
   "source": [
    "# Make sure to use the normalized variables here, not the original ones.\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do OLS here\n",
    "print(\"Linear Regression using OLS: \",linear_regression_ols(X,y))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for OLS: \" + str(end_time-start_time))\n",
    "\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do GD without regularization here\n",
    "print(\"Linear Regression using Gradient Descent without regularization: \",linear_regression_gd(X, y,theta, learning_rate = 0.1, num_iters = 100000, regularization = False))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for gradient descent without regularization: \" + str(end_time-start_time))\n",
    "\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do GD with regularization here\n",
    "print(\"Linear Regression using Gradient Descent with regularization: \",linear_regression_gd(X, y,theta, learning_rate = 0.1, num_iters = 100000, regularization = True))\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for gradient descent with regularization: \" + str(end_time-start_time))\n",
    "\n",
    "\n",
    "start_time = time.process_time()\n",
    "# Do SK's linear regression here\n",
    "l_regr = linear_model.LinearRegression()\n",
    "l_regr.fit(X,y)\n",
    "print(\"Linear Regression using sklearn: \",l_regr.coef_)\n",
    "end_time = time.process_time()\n",
    "print(\"Total execution time for Sci-Kit Learn's Linear Regression: \" + str(end_time-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "I8gPX8LruFKw"
   },
   "source": [
    "## Question 5 (10 points, 2 points per quesiton)\n",
    "\n",
    "1. Did you notice any difference between the normalize and non-normalized versions in questions 3 and 4? Explain your answer.\n",
    "2. Which is the linear regressions is faster? Why is it faster?\n",
    "3. Why don't we train all the machine learning models using that technique?\n",
    "4. Describe in your own words at least two regularization methods\n",
    "5. What would happen if you use a regularization parameter value that is too low or too high?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JJevEyH8KPWZ"
   },
   "source": [
    "Write your answers here:\n",
    "\n",
    "1. I normalized the dataset using mean normalization in which case all the features will be in the same range. As the features are in the same range the contour circles around the local minima gets shrunk and the descent happened soon compared to the non-normalized version. Another difference I found was that in this specific dataset the ranges of the features varied widely because of which we had no control of the magnitude of the gradient step size and ended up with an exploded gradient for the unnormalized version. To fix the shoot up of the weights, we had to take a very low learning rate and run for a higher number of iterations. If the data is normalized then the magnitude of step size is fixed and the convergence occurs with considerably high learning rate and less number of iterations. \n",
    "\n",
    "2. Sklearn's implementation is faster than all three implementations. But when sklearn is not considered then OLS(Normal equation is faster than Gradient descent(both without and with regularization). OLS is faster than gradient descent because in OLS we just take matrix transposes and donot do any iterations like in gradient descent.\n",
    "\n",
    "3. In the diabetes dataset we just have ten features so OLS was faster than other techniques but as the feature count gets significantly high then the OLS method gets very slow as a matrix inverse function is involved, in this case gradient descent will be a better option. Or if np.dot(X,X.T) becomes non-invertible like a singular matrix or degenerate matrix then also OLS method cannot be used as an inverse function is involved.\n",
    "\n",
    "4. The two famous regularization methods are L1 and L2 regularization (aka Lasso and Ridge regression respectively). Regularization is the process of penalizing the higher order parameters so that the model doesnot overfit the data. By penalizing we reduce the influence of higher order polynomials in the prediction equation. In Lasso Regression, we penalize by taking absolute values of the weights and in ridge regression we penalize the weights by take square of the weights. \n",
    "\n",
    "5. If lambda value is too high then it may smooth out the function too much and cause underfitting and if lambda value is too small or close to zero then regularization will have no effect and overfitting might remain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "name": "P556-Assignment1-S19.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}