handson-ml/extra_gradient_descent_comparison.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Comparison of Batch, Mini-Batch and Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook displays an animation comparing Batch, Mini-Batch and Stochastic Gradient Descent (introduced in Chapter 4). Thanks to [Daniel Ingram](https://github.com/daniel-s-ingram) who contributed this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "  <td>\n",
    "    <a href=\"https://colab.research.google.com/github/ageron/handson-ml3/blob/main/extra_gradient_descent_comparison.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>\n",
    "  </td>\n",
    "  <td>\n",
    "    <a target=\"_blank\" href=\"https://kaggle.com/kernels/welcome?src=https://github.com/ageron/handson-ml3/blob/main/extra_gradient_descent_comparison.ipynb\"><img src=\"https://kaggle.com/static/images/open-in-kaggle.svg\" /></a>\n",
    "  </td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.animation import FuncAnimation\n",
    "\n",
    "matplotlib.rc('animation', html='jshtml')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "m = 100\n",
    "X = 2 * np.random.rand(m, 1)\n",
    "X_b = np.c_[np.ones((m, 1)), X]\n",
    "y = 4 + 3 * X + np.random.rand(m, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def batch_gradient_descent():\n",
    "    n_iterations = 1000\n",
    "    learning_rate = 0.05\n",
    "    thetas = np.random.randn(2, 1)\n",
    "    thetas_path = [thetas]\n",
    "    for i in range(n_iterations):\n",
    "        gradients = 2 * X_b.T @ (X_b @ thetas - y) / m\n",
    "        thetas = thetas - learning_rate * gradients\n",
    "        thetas_path.append(thetas)\n",
    "\n",
    "    return thetas_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stochastic_gradient_descent():\n",
    "    n_epochs = 50\n",
    "    t0, t1 = 5, 50\n",
    "    thetas = np.random.randn(2, 1)\n",
    "    thetas_path = [thetas]\n",
    "    for epoch in range(n_epochs):\n",
    "        for i in range(m):\n",
    "            random_index = np.random.randint(m)\n",
    "            xi = X_b[random_index:random_index+1]\n",
    "            yi = y[random_index:random_index+1]\n",
    "            gradients = 2 * xi.T @ (xi @ thetas - yi)\n",
    "            eta = learning_schedule(epoch * m + i, t0, t1)\n",
    "            thetas = thetas - eta * gradients\n",
    "            thetas_path.append(thetas)\n",
    "\n",
    "    return thetas_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mini_batch_gradient_descent():\n",
    "    n_iterations = 50\n",
    "    minibatch_size = 20\n",
    "    t0, t1 = 200, 1000\n",
    "    thetas = np.random.randn(2, 1)\n",
    "    thetas_path = [thetas]\n",
    "    t = 0\n",
    "    for epoch in range(n_iterations):\n",
    "        shuffled_indices = np.random.permutation(m)\n",
    "        X_b_shuffled = X_b[shuffled_indices]\n",
    "        y_shuffled = y[shuffled_indices]\n",
    "        for i in range(0, m, minibatch_size):\n",
    "            t += 1\n",
    "            xi = X_b_shuffled[i : i + minibatch_size]\n",
    "            yi = y_shuffled[i : i + minibatch_size]\n",
    "            gradients = 2 * xi.T @ (xi @ thetas - yi) / minibatch_size\n",
    "            eta = learning_schedule(t, t0, t1)\n",
    "            thetas = thetas - eta * gradients\n",
    "            thetas_path.append(thetas)\n",
    "\n",
    "    return thetas_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_mse(theta):\n",
    "    return ((X_b @ theta - y) ** 2).sum() / m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learning_schedule(t, t0, t1):\n",
    "    return t0 / (t + t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "theta0, theta1 = np.meshgrid(np.arange(0, 5, 0.1), np.arange(0, 5, 0.1))\n",
    "r, c = theta0.shape\n",
    "cost_map = np.array([[0 for _ in range(c)] for _ in range(r)])\n",
    "for i in range(r):\n",
    "    for j in range(c):\n",
    "        theta = np.array([theta0[i,j], theta1[i,j]])\n",
    "        cost_map[i,j] = compute_mse(theta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "exact_solution = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y\n",
    "bgd_thetas = np.array(batch_gradient_descent())\n",
    "sgd_thetas = np.array(stochastic_gradient_descent())\n",
    "mbgd_thetas = np.array(mini_batch_gradient_descent())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "bgd_len = len(bgd_thetas)\n",
    "sgd_len = len(sgd_thetas)\n",
    "mbgd_len = len(mbgd_thetas)\n",
    "n_iter = min(bgd_len, sgd_len, mbgd_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAmAAAAFECAYAAACAvoJtAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAB3v0lEQVR4nO3deXxU1dnA8d8zk0z2QAg7Yd/3sAgEtwgIiCgqbrUFXFpc21Jrq9i61xetrVK1VWldwNYd9xVEoyJBZN+RHcJOWLJvM+f9YyYhyySZSWYyk8nz/XyGzNx77r3nZsKdZ8459zlijEEppZRSSjUcS6AroJRSSinV1GgAppRSSinVwDQAU0oppZRqYBqAKaWUUko1MA3AlFJKKaUamAZgSimllFINTAMwpVSTIyJ7RGSDiKwVkZVu1ouIPC0iO0RkvYgMDUQ9lVKhKyzQFVBKqQC5wBhzvJp1FwE9XY+RwHOun0op5RPaAqaUUlVNARYYp+VAcxFpF+hKKaVCR1C1gLVs2dJ06dIl0NVQSjWgVatWHTfGtGrgwxpgkYgY4AVjzLxK6zsA+8u9znAtO1S+kIjMBGYCxMTEDOvTp4//aqxUiKjL//kJF8SYzBN274+1vvALY8xErzdsAEEVgHXp0oWVK6sMx1BKhTAR2RuAw55tjDkoIq2BxSKy1RjzbflqudmmyrxtrsBtHsDw4cONXr+Uql1d/s8fP2Hnhy+SvD5WeLudLb3eqIEEVQCmlFINwRhz0PXzqIi8B4wAygdgGUDHcq+TgIMNV0OlVEUGu3EEuhI+pWPAlFJNiojEiEhc6XNgPLCxUrEPgemuuyFHAaeNMYdQSgWEARwYrx/BTFvAlFJNTRvgPREB5zXwNWPM5yJyC4Ax5nngU2ASsAPIA26obafbNx9k4uD76lYjcdfjWXfGm/15+jXc0316WM7jOnpYP2PxsKAXvxpj9fE5W3xczsP6GS+aWjw9Np7+boBvPvqD5xWogYPQagEL+gCsuLiYjIwMCgoKAl2VgIqMjCQpKYnw8PBAV0WpRs0YswsY7Gb58+WeG+D2+h4rJs7GVb88izZJ8UhNH9K+jb+aJh8HsTUxxnDoUDZv/m8duTlFDXZcFVqCPgDLyMggLi6OLl261HwBC2HGGDIzM8nIyKBr166Bro5SykNX/fIs+g3qRoQtumGvX345lI93GqjLuTctYNUUNsbQIjGXa34OL73wo48qpmpiMNhNcHcpeivox4AVFBSQmJjYZIMvABEhMTGxybcCKtXYtEmKb/jgS/mdiBBhi6Fdu7hAV6VJ0TFgAaAXL/0dKNUYiYj+3w1R+t42LAPYgzyg8lajCMCUUkop1bQFe4uWt4K+CzIYWK1WkpOT6d+/P4MHD+bJJ5/E4aj5bow9e/bw2muvNVANlVLKvd79k3jsrw+XvX7x5ed55p9/b9A6TLv+SjZsXFd1+YwrmTDpXKZcfiFTLr+Q38z6lc+P/e57b3Lk6OGy13/6813s2PGTz4+j/MsAdmO8fgQzbQHzQFRUFGvXrgXg6NGjXHfddZw+fZqHHnqo2m1KA7DrrruugWqplAoFdvsRTmbfRkL8c1gtreu9P5stgkVffsbMX91Bi4QWXm9fUlJCWJj/Pir+9tdnGTigyk2pPvPe+2/Ts2cf2rRuC8Cjf/mb346l/Cu0klCEaAtYeno6c+bMIT093ef7bt26NfPmzePZZ5/FGMOePXs499xzGTp0KEOHDmXZsmUA3HPPPXz33XckJyfz1FNPVVtOKaXKy86bS1HxCrJzn/LJ/sKsVq656ufMX/DvKusOHMxgxo3XcMnl45hx4zUcPHgAgHvu/R1zHn+Iaddfxd+e/D/uufd3PPDwPUy7/krGTkhhxY/pzP7znVx0yfncc++ssv098PA9XHH1RVx86QU8/WzdA539Gfu45meXMPXqScx9+q8MGdYTgB9WLOPmW6eXlXv4L3/i3ffeBODZfz3F1KsnMfnSMdz3wB8xxvD5Fx+zceM67vrjHUy5/EIKCvKZNv1Ma9zHn7zPJZeOZfIlY3jib4+W7XfIsJ48Nfcxplw2jmuumczx48fqfC7KNwwGex0ewSzkArD09HTGjh3Lfffdx9ixY/0ShHXr1g2Hw8HRo0dp3bo1ixcvZvXq1bz55pv85je/AeCxxx7j3HPPZe3atfzud7+rtpxSSgEcPNadg8eSyCt4FTDkFbzKwWNJHDzWvd77/vnPZvDRx++RnZ1VYfkjf/kzl116JR+99yWXTL6cv8y5v2zdnr27eOXFN7jnj85lWVmnWfDy28y++0Fuuf16rp/+Kz754Gt+2r6VLVucEwn87jd38+5bn/Hhe1/y48rlbN22uda6lQZHUy6/kMefeASAR+fcz8+unc7Ctz6lVUvPWgF/cd31LHzrUz7+8CsKCvL5Om0xEydMZsCAwfztr8/ywXuLiYyMKit/5Ohh/vb3R5n/ylu8/94iNmxcy5dffg5AXl4egwcP5YP3v2T48JG8/fb/PKqD8iMD9jo8glnIdUGmpaVRVFSE3W6nqKiItLQ0UlJSfH4c4+pbLi4u5o477mDt2rVYrVZ++sn92AJPyymlGiljoJaxoTVp02IZWbmPkF/4OVAARBIVcRHxsXXIrl/pgyc2Jo4pl05lwX9fIjIi0rnewJp1q3hm7r/BwJTJU3ni74+WbTtx/GSsFmvZ6wvOH4cAvXv0pmViS3r37ANAj+69OHBgP3379Oezzz/irXf+R4m9hGPHjrJz50/06d2XsgOWr5hx/vO3x5+p2AVpDGtW/8gzT80DY5hyyVT+VlovU37birv9YcUy/vPicxQU5HPq9Cl69ujNmAvGV/v72bB+HSPOSqFFQiIAl0y+gh9XLmfc2ImEh9u44PwLEWMY0H8g3y/7DqlmPJGUGBAPP+k9zB4vDg8z3HtaztPs9oCxeljO0bDRjXMqotBS7wBMRF4CJgNHjTEDKq27C3gCaGWMOV7fY3kiNTUVm81GUVERNpuN1NRUnx9j165dWK1WWrduzUMPPUSbNm1Yt24dDoeDyMhIt9s89dRTHpVTSjVNVmsbRGKBQiACKEQk1ifjwABmTPslV1x1EVdcdnW1ZcqnVYiKiqqwzmazOctYLNhsEWXLLRYLJfYS9mfs46VXnuedNz+hWbPm3HPv7ygsLKxzfd2leLBaw3CU++AvLHLuv7CwgIceuZeFb31Ku3YdeObZv9d+7BoGaIeHhZUd32KxYreX1OEMlG8J9hCbMsIXXZCvABMrLxSRjsCFwD4fHMNjKSkpLFmyhEceeYQlS5b4vPXr2LFj3HLLLdxxxx2ICKdPn6Zdu3ZYLBZeffVV7HY7AHFxcWRnZ5dtV105pZQq5XAcJzpyGq0SPiI6choOh+/GHjVvlsDECZN55903ypYNSR7OJ599AMBHn7zHsCFn1Xn/uTk5REVFExcXz/Hjx/h26dd13teQIWeV1evDj98tW96hfQd27vyJoqJCsrOzSF++FKAs2EpIaEFubi5fLPqkbJuYmBhyc3OqHGPQ4CH8+ONyTpw8gd1u55NP3ues4b7vLVG+YQCH8f4RzOrdAmaM+VZEurhZ9RTwR+CD+h7DWykpKT4NvPLz80lOTqa4uJiwsDCmTZvGnXfeCcBtt93G1KlTefvtt7nggguIiYkBYNCgQYSFhTF48GCuv/76assppVSpFs3+U/a8edz/+Xz/N864mf+9/krZ6z/Pfph77/s9L778PC1aJDLnL0/Wed99+vSjX98BXDxlDB2TOjF0yHCPtrvr7l87u0VxBlCvvPgGf5r9EHf98Q4WvPoSEy6cVFa2XbsOTJxwCZdcPo4unbvSr6+z0yU+vhlXXXkdl0wZR4cOSRW6NC+/7GoeeOgeIiMiefP1D8uWt27Vhjt/N5sZ11+FMYbzzhvDuLET6nz+yv9CrQVMjA/yZLgCsI9LuyBF5FJgrDHmtyKyBxheXRekiMwEZgJ06tRp2N69eyus37JlC3379q13HUOB/i5UKBKRVcYYzz6tg1izqHYmpceNFZbdM3cy7dt2ClCNAsTnn5HCkOE9WbNyewMft3Y
      "text/plain": [
       "<Figure size 720x360 with 3 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = plt.figure(figsize=(10, 5))\n",
    "data_ax = fig.add_subplot(121)\n",
    "cost_ax = fig.add_subplot(122)\n",
    "\n",
    "data_ax.plot(X, y, 'k.')\n",
    "\n",
    "cost_ax.plot(exact_solution[0,0], exact_solution[1,0], 'y*')\n",
    "cost_ax.pcolor(theta0, theta1, cost_map, shading='auto')\n",
    "\n",
    "i = -1\n",
    "[bgd_data_plot] = data_ax.plot(X, X_b @ bgd_thetas[i,:], 'r-')\n",
    "[bgd_cost_plot] = cost_ax.plot(bgd_thetas[:i,0], bgd_thetas[:i,1], 'r--')\n",
    "\n",
    "[sgd_data_plot] = data_ax.plot(X, X_b @ sgd_thetas[i,:], 'g-')\n",
    "[sgd_cost_plot] = cost_ax.plot(sgd_thetas[:i,0], sgd_thetas[:i,1], 'g--')\n",
    "\n",
    "[mbgd_data_plot] = data_ax.plot(X, X_b @ mbgd_thetas[i,:], 'b-')\n",
    "[mbgd_cost_plot] = cost_ax.plot(mbgd_thetas[:i,0], mbgd_thetas[:i,1], 'b--')\n",
    "\n",
    "data_ax.set_xlim([0, 2])\n",
    "data_ax.set_ylim([0, 15])\n",
    "cost_ax.set_xlim([3, 5])\n",
    "cost_ax.set_ylim([2, 5])\n",
    "\n",
    "data_ax.set_xlabel(r'$x_1$')\n",
    "data_ax.set_ylabel(r'$y$', rotation=0)\n",
    "cost_ax.set_xlabel(r'$\\theta_0$')\n",
    "cost_ax.set_ylabel(r'$\\theta_1$')\n",
    "\n",
    "data_ax.legend(('Data', 'BGD', 'SGD', 'MBGD'), loc=\"upper left\")\n",
    "cost_ax.legend(('Normal Equation', 'BGD', 'SGD', 'MBGD'), loc=\"upper left\")\n",
    "\n",
    "cost_ax.plot(exact_solution[0,0], exact_solution[1,0], 'y*')\n",
    "cost_img = cost_ax.pcolor(theta0, theta1, cost_map, shading='auto')\n",
    "fig.colorbar(cost_img)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def animate(i):\n",
    "    bgd_data_plot.set_data(X, X_b @ bgd_thetas[i,:])\n",
    "    bgd_cost_plot.set_data(bgd_thetas[:i,0], bgd_thetas[:i,1])\n",
    "\n",
    "    sgd_data_plot.set_data(X, X_b @ sgd_thetas[i,:])\n",
    "    sgd_cost_plot.set_data(sgd_thetas[:i,0], sgd_thetas[:i,1])\n",
    "\n",
    "    mbgd_data_plot.set_data(X, X_b @ mbgd_thetas[i,:])\n",
    "    mbgd_cost_plot.set_data(mbgd_thetas[:i,0], mbgd_thetas[:i,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "FuncAnimation(fig, animate, frames=n_iter // 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}