23. Debug Gradient Descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Debug Gradient\n",
    "\n",
    "Gradient Descent is not a Machine Learning algorithm, is ased on search optimization.\n",
    "\n",
    "$ \\frac{dJ}{d\\theta} = \\frac{J(\\theta + \\epsilon) -J(\\theta - \\epsilon) }{2\\epsilon}$\n",
    "\n",
    "If $\\theta$ is a Vector:\n",
    "\n",
    "$\\theta = (\\theta_0, ···, \\theta_n)$\n",
    "\n",
    "$\\frac{\\partial J}{\\partial \\theta} = (\\frac{\\partial J}{\\partial \\theta_0}, ···, \\frac{\\partial J}{\\partial  \\theta_n})$\n",
    "\n",
    "$\\theta^+ = (\\theta_0, ···, \\theta_n)$\n",
    "\n",
    "$\\theta^- = (\\theta_0, ···, \\theta_n)$\n",
    "\n",
    "$\\frac{\\partial J}{\\partial \\theta_i} = \\frac{J(\\theta_i^+) -J(\\theta_i^-) }{2\\epsilon}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(666)\n",
    "X = np.random.random(size = (1000,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "true_theta = np.arange(1, 12, dtype = float)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "y = X_b.dot(true_theta) + np.random.normal(size = 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1000, 10)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1000,)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.,  2.,  3.,  4.,  5.,  6.,  7.,  8.,  9., 10., 11.])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta)) ** 2) / len(X_b)\n",
    "    except:\n",
    "        return float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_math(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2 / len(X_b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_debug(theta, X_b, y, epsilon = 0.01):\n",
    "    res = np.empty(len(theta))\n",
    "    for i in range(len(theta)):\n",
    "        theta_1 = theta.copy()\n",
    "        theta_1[i] += epsilon\n",
    "        theta_2 = theta.copy()\n",
    "        theta_2[i] -= epsilon\n",
    "        res[i] = (J(theta_1, X_b, y) - J(theta_2, X_b, y))/(2 * epsilon)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradient_descent(dJ, X_b, y, initial_theta, eta, n_iters = 1e4, epsilon = 1e-8):\n",
    "\n",
    "    theta = initial_theta\n",
    "    i_iter = 0\n",
    "\n",
    "    while i_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "\n",
    "        i_iter += 1\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.57 s, sys: 16 ms, total: 3.58 s\n",
      "Wall time: 3.6 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([ 1.1251597 ,  2.05312521,  2.91522497,  4.11895968,  5.05002117,\n",
       "        5.90494046,  6.97383745,  8.00088367,  8.86213468,  9.98608331,\n",
       "       10.90529198])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X.shape[1] + 1)\n",
    "eta = 0.01\n",
    "\n",
    "%time theta = gradient_descent(dJ_debug, X_b, y, initial_theta, eta)\n",
    "theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.09 s, sys: 20.6 ms, total: 2.11 s\n",
      "Wall time: 536 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([ 1.1251597 ,  2.05312521,  2.91522497,  4.11895968,  5.05002117,\n",
       "        5.90494046,  6.97383745,  8.00088367,  8.86213468,  9.98608331,\n",
       "       10.90529198])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time theta = gradient_descent(dJ_math, X_b, y, initial_theta, eta)\n",
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mini-Batch Gradient Descent\n",
    "\n",
    "Combine the strengths of Batch Gradient Descent and Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size = m)\n",
    "X = x.reshape(-1, 1)\n",
    "y = 4. * x + 3. + np.random.normal(0, 3, size = m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.4 s, sys: 24.6 ms, total: 1.43 s\n",
      "Wall time: 977 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "LinearRegression()"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from playML.LinearRegression import LinearRegression\n",
    "\n",
    "lin_reg = LinearRegression()\n",
    "%time lin_reg.fit_mbgd(X, y, k = 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([4.00050775])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lin_reg.coef_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.003468139922483"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lin_reg.intercept_"
   ]
  }
 ],
 "metadata": {
  "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}